Downhill skiingAlice and Bob are keen dowhill skiers. Today they arrived at white northern slopes of Chevayootay range in Canadian Rockies. The ski resort stretches over many square miles and the tracks there are owned by several companies. A track is either a ski tow or ski slope. At the beginning and at the end of each track there is a hut. The huts serve as reference points of start and end of each track. More tracks may share a hut at their beginning or a hut at their end. A hut which is at the beginning of some track may be simultaneously at the end of some other track but never at the end of the same track. The skier can travel only in one direction on any particular track.
Due to complicated economic circumstances the huts and the tracks are divided between the companies in the following manner. Each track and each hut belongs to some company and always to one of them. All tracks which start at a particular hut belong to the same company as the hut. There might be companies which own only a single hut with no tracks at all. A trail is a sequence of tracks in which the end hut of any track is the also the beginning hut of the next track in the sequence. For each company C holds that for any pair of huts h1, h2 (h1 ≠ h2) belonging to C there is trail from h1 to h2 which contains only tracks belonging to C. Whenever a skier leaves a hut of a company, say company C1, and arrives to a hut of another company, say C2, than for him there is no trail which would bring him back to huts or tracks of C1.
Thanks to the organisation described above the companies can be divided into three categories: Root, leaf and transient. No hut of a root company can be reached from a hut of any other company by trail. There is no trail from any hut of a leaf company to any hut of any other company. The company which is nor root nor leaf is a transient one. There might be companies which are simultaneously root and leaf companies. Interestingly enough, no matter how the actual connection scheme looks like, it cannnot happen that there would be no leaf or no root company.
A skier has to pay for each track he travels. Alice and Bob are quite fortunate today, though. Their trip is funded by the faculty they study at, because they together have won this year's university competition for the most effective topological sort COBOL code. All they have to do is to obtain a credit chip in the first hut before they start their skiing day and the advanced wireless tracking technology installed in the tows and along the slopes takes care of the rest.
Additionally, there is a deal between the university and all companies in the area. The deal is identical with all companies and applies to all university members including Alice and Bob. The deal is like follows. When a skier on his trip uses a track connecting huts of two different companies he is charged the price of that track without change. When a skier uses any number of tracks (one or more) that connect the huts of the same company, say company C, he is charged only once and the price is equal to the price of the most expensive track of all tracks which connect two huts of C.
It is supposed that the skier travels only along the tracks during his trip and does not use other means of transport like car roads, helicopters etc.
Alice and Bob decided that each of them will start their trip in a hut owned by a root company and finish it in a hut owned by a leaf company. But aside from that their attitudes toward the trip differ significantly. Alice being quite modest person wants to travel on the slopes in such way that her trip will be cheapest possible. Bob, on the contrary, wants to stretch the school budget as much as he can and so he opts for a most expensive trip. Each skier will thus choose individually the root and leaf companies/huts of their trip. If there is a company which is both root and leaf then the cost of Alice's trip will be 0 and she will spend pleasant afternoon in a bar of appropriate hut instead of skiing.
InputInput consists of one text line containing six integers N, p1, p2, p3, p4, K. The numbers are separated by spaces. N is the number of huts in the whole ski area, the huts are numbered 0, 1, ... N − 1. The existence and cost of the track from hut i to hut j are given by the following rules:
1. If |i − j| > K then track from i to j does not exist.
2. If |i − j| ≤ K then first compute the track identifier ID(i, j) = i×(2K+1) + (j − i + K − 1).
Next compute the preliminary price PP(i, j) = (p1 × ID(i,j)) mod p2.
If p3 ≤ PP(i,j) ≤ p4 then the track exists and its price is PP(i,j).
If PP(i,j) < p3 or p4 < PP(i,j) then the track does not exist.
You may assume the following relations
2 ≤ K ≤ N ≤ 50000; 1 ≤ p1, p2, p3, p4 ≤ 10000.
OutputOutput consists of one text line containing two integers A, B separated by space. A is the price of Alice's trip and B is the price of Bob's trip.
9 5 19 1 10 2Output:
2 37We present connection schemes for reader's convenience. Each line contains hut number followed by the list of tracks starting in that hut. Each track in the list is specified by its end hut and the track cost in square brackets.
0 1 1 0[ 6] 3[ 2] 2 0[ 7] 3[ 3] 4[ 8] 3 4[ 9] 4 3[ 5] 6[ 1] 5 3[ 6] 6[ 2] 7[ 7] 6 7[ 8] 7 6[ 4] 8 6[ 5] 7
6 3 7 1 2 2Output:
2 4Connection scheme:
0 2[ 2] 1 0[ 1] 2 1[ 2] 3[ 1] 3 4[ 2] 4 2[ 1] 5 3[ 2]
6 3 8 3 5 2Output:
8 13Connection scheme:
0 1 2[ 5] 2 0[ 3] 3[ 4] 3 2[ 5] 4[ 3] 4 3[ 4] 5 4[ 3]
9 4 9 6 7 3Output:
13 26Connection scheme:
0 2[ 7] 1 2 1[ 6] 3 2[ 7] 4[ 6] 4 5[ 7] 7[ 6] 5 8[ 7] 6 4[ 6] 7 5[ 7] 8
12 31 100 30 60 3Output:
204 283Connection scheme:
0 3 1 0 3 2 0 4 3 1 4 4 1 5 2 8 6 5 9 7 6 9 8 6 10 9 7 10 10 7 11 8
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout a stderr is available to him/her.