The King of the Saracens is quite impressed with the Saboteurs. He tests their mettle further with the following task:-
There exists a linked list that consists of K nodes. The nodes of the path are numbered from 1 to K. Two pointers start moving at time t = 0 (seconds) with speeds A and B (nodes/second). The slower pointer starts at node 1 and the faster pointer starts at node D + 1. The task is to print the minimum integer L denoting the number of nodes in a loop that needs to be attached to node K such that the two pointers never meet. If no such L exists print “Impossible” (without quotes). Note that node K is not part of the loop.
Note that the two pointers are considered to have met each other if and only if they are at the same node at the same integer time t. Also, note that L must be at least 2.
Solve the problem and earn the trust of the King of the Saracens!
The first and only line contains 4 integers A, B, K and D as described in the problem statement
Print a single integer L (>= 2) or “Impossible” (without quotes) denoting the answer.
1≤A,B≤1012
0≤D<K≤1018
The constructed linked list has 4 nodes with nodes 1 and 2 in the straight path, nodes 3 and 4 in a loop with node 3 attached to node 2. Let the pointer of speed 1 be denoted by P1 and let the pointer of speed 3 be denoted by P2.
At time t = 0, P1 is at node 1 and P2 is at node 2.
At time t = 1, P1 is at node 2 and P2 is at node 3.
At time t = 2, P1 is at node 3 and P2 is at node 4.
At time t = 3, P1 is at node 4 and P2 is at node 3.
…
They never meet! Hence, the answer.