Description
A gigantic amount of space stations has been built in the deep space. Space ships that can travel in the space at the speed closed to the speed of light are also available. Although space ships can travel extremely fast, they cannot go directly from any station to any other station. The stations it can go depends on the numbers labeled on the buttons in the control room. Furthermore, it must refuel after each stop. The time to refuel take one unit of time which is much longer than the time to travel between any pair of stations.
Each space station has a unique number. Assume that there are n stations and they are numbered from 0 to n - 1. The operation of the space ship is very simple. There are only two buttons in a space ship, and each button is marked by a positive integer. Suppose that you are at station s. Pushing the button marked a can take you to station (s + a) mod n, and pushing the other button marked b can take you to station (s+b) mod n. These two numbers marked on the buttons are set at the factory, and they cannot be changed.
Astronauts at station s received a critical mission. To carry out the mission they must go to station t as fast as they can. Since the number of stations is huge, the captain cannot figure out how to get to station t fast. The captain, who is not an expert in programming, has tried a simple program which does a simple search for solutions. The program takes a long time to compute the answer. Please write an efficient program to solve the problem for the captain. In designing the program remember that the captain is left-handed. That is, the captain can push the button labeled a much faster than the button labeled b.
Input
Each line of the input contains 5 integers n, a, b, s and t, which means hat there are n space stations, the two numbers marked on the space ship are a and b respectively, the space ship is at station s and wants to go to station t. The last line is followed by a 0, which means that there are no more test data. Assume that n < 231 and a, b < n.
Output
For each input line, print out two integers x and y, where x and y are the number of times the two buttons must be pushed for the space ship to go from station s to station t with minimum delay. If there are more than one solutions, print the one with the larger x value. If there are no solutions, print 'no solution'.
If there are more than one solutions, first print the one with minimum x + y, then the one with maximum x.
Sample Input
15 2 3 0 1
43 3 11 1 3
2147483647 1 2 0 2147483645
0
Sample Output
2 4
4 3
1 1073741822
http://poj.org/problem?id=2700
