E - Oversleeping Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

A と街 B の間を往復する電車があります。 電車は時刻 0 に街 A を出発した後、

  • X 秒かけて街 B に移動
  • BY 秒停車
  • X 秒かけて街 A に移動
  • AY 秒停車

を繰り返します。
より厳密には、これらは半開区間として扱います。すなわち、n = 0, 1, 2, \dots について、

  • (2X + 2Y)n ≤ t < (2X + 2Y)n + X を満たす時刻 t には電車は街 B に移動している
  • (2X + 2Y)n + X ≤ t < (2X + 2Y)n + X + Y を満たす時刻 t には電車は街 B で停車している
  • (2X + 2Y)n + X + Y ≤ t < (2X + 2Y)n + 2X + Y を満たす時刻 t には電車は街 A に移動している
  • (2X + 2Y)n + 2X + Y ≤ t < (2X + 2Y)(n + 1) を満たす時刻 t には電車は街 A で停車している

が満たされます。

高橋くんは電車に乗って時刻 0 に街 A を出発し、街 B で電車を降りようと思っています。 高橋くんは時刻 0 に街 A を出発した後、

  • P 秒間眠っている
  • Q 秒間起きている

を繰り返します。
これらも半開区間として扱います。すなわち、n = 0, 1, 2, \dots について、

  • (P + Q)n ≤ t < (P + Q)n + P を満たす時刻 t には高橋くんは眠っている
  • (P + Q)n + P ≤ t < (P + Q)(n + 1) を満たす時刻 t には高橋くんは起きている

が満たされます。

B に電車が停車しており、かつ、高橋くんが起きていれば高橋くんは街 B で電車を降りることができます。
高橋くんが街 B で電車を降りることができるか判定し、できる場合は、最短でいつになるか求めてください。
なお、この値はこの問題の制約下で整数になることが証明できます。

T 個のケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 入力は全て整数
  • 1 ≤ T ≤ 10
  • 1 ≤ X ≤ 10^9
  • 1 ≤ Y ≤ 500
  • 1 ≤ P ≤ 10^9
  • 1 ≤ Q ≤ 500

入力

入力は以下の形式で標準入力から与えられる。

T
\rm case_1
\rm case_2
\hspace{9pt}\vdots
\rm case_T

各ケースは以下の形式で与えられる。

X Y P Q

出力

T 行出力せよ。
i 行目には、\rm case_i についてこの問題を解き、街 B で電車を降りられる時刻が存在する場合、そのような時刻のうち最小のものを整数で出力せよ。 街 B で電車を降りられる時刻が存在しない場合、infinity と出力せよ。


入力例 1

3
5 2 7 6
1 1 3 1
999999999 1 1000000000 1

出力例 1

20
infinity
1000000000999999999

[a, b) で区間 a ≤ t < b を表すことにします。

1 個目のケースでは、電車が街 B で停車している時刻は [5, 7), [19, 21), [33, 35), \dots 、 高橋くんが起きている時刻は [7, 13), [20, 26), [33, 39), \dots なので、時刻 20 に初めて街 B で電車を降りることが出来ます。

Score : 500 points

Problem Statement

A train goes back and forth between Town A and Town B. It departs Town A at time 0 and then repeats the following:

  • goes to Town B, taking X seconds;
  • stops at Town B for Y seconds;
  • goes to Town A, taking X seconds;
  • stops at Town A for Y seconds.

More formally, these intervals of time are half-open, that is, for each n = 0, 1, 2, \dots:

  • at time t such that (2X + 2Y)n ≤ t < (2X + 2Y)n + X, the train is going to Town B;
  • at time t such that (2X + 2Y)n + X ≤ t < (2X + 2Y)n + X + Y, the train is stopping at Town B;
  • at time t such that (2X + 2Y)n + X + Y ≤ t < (2X + 2Y)n + 2X + Y, the train is going to Town A;
  • at time t such that (2X + 2Y)n + 2X + Y ≤ t < (2X + 2Y)(n + 1), the train is stopping at Town A.

Takahashi is thinking of taking this train to depart Town A at time 0 and getting off at Town B. After the departure, he will repeat the following:

  • be asleep for P seconds;
  • be awake for Q seconds.

Again, these intervals of time are half-open, that is, for each n = 0, 1, 2, \dots:

  • at time t such that (P + Q)n ≤ t < (P + Q)n + P, Takahashi is asleep;
  • at time t such that (P + Q)n + P ≤ t < (P + Q)(n + 1), Takahashi is awake.

He can get off the train at Town B if it is stopping at Town B and he is awake.
Determine whether he can get off at Town B. If he can, find the earliest possible time to do so.
Under the constraints of this problem, it can be proved that the earliest time is an integer.

You are given T cases. Solve each of them.

Constraints

  • All values in input are integers.
  • 1 ≤ T ≤ 10
  • 1 ≤ X ≤ 10^9
  • 1 ≤ Y ≤ 500
  • 1 ≤ P ≤ 10^9
  • 1 ≤ Q ≤ 500

Input

Input is given from Standard Input in the following format:

T
\rm case_1
\rm case_2
\hspace{9pt}\vdots
\rm case_T

Each case is in the following format:

X Y P Q

Output

Print T lines.
The i-th line should contain the answer to \rm case_i.
If there exists a time such that Takahashi can get off the train at Town B, the line should contain the earliest such time; otherwise, the line should contain infinity.


Sample Input 1

3
5 2 7 6
1 1 3 1
999999999 1 1000000000 1

Sample Output 1

20
infinity
1000000000999999999

Let [a, b) denote the interval a ≤ t < b.

In the first case, the train stops at Town B during [5, 7), [19, 21), [33, 35), \dots, and Takahashi is awake during [7, 13), [20, 26), [33, 39), \dots, so he can get off at time 20 at the earliest.