{"problem":{"name":"Oversleeping","description":{"content":"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$ seco","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc193_e"},"statements":[{"statement_type":"Markdown","content":"A train goes back and forth between Town $A$ and Town $B$. It departs Town $A$ at time $0$ and then repeats the following:\n\n*   goes to Town $B$, taking $X$ seconds;\n*   stops at Town $B$ for $Y$ seconds;\n*   goes to Town $A$, taking $X$ seconds;\n*   stops at Town $A$ for $Y$ seconds.\n\nMore formally, these intervals of time are half-open, that is, for each $n = 0, 1, 2, \\dots$:\n\n*   at time $t$ such that $(2X + 2Y)n ≤ t < (2X + 2Y)n + X$, the train is going to Town $B$;\n*   at time $t$ such that $(2X + 2Y)n + X ≤ t < (2X + 2Y)n + X + Y$, the train is stopping at Town $B$;\n*   at time $t$ such that $(2X + 2Y)n + X + Y ≤ t < (2X + 2Y)n + 2X + Y$, the train is going to Town $A$;\n*   at time $t$ such that $(2X + 2Y)n + 2X + Y ≤ t < (2X + 2Y)(n + 1)$, the train is stopping at Town $A$.\n\nTakahashi 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:\n\n*   be asleep for $P$ seconds;\n*   be awake for $Q$ seconds.\n\nAgain, these intervals of time are half-open, that is, for each $n = 0, 1, 2, \\dots$:\n\n*   at time $t$ such that $(P + Q)n ≤ t < (P + Q)n + P$, Takahashi is asleep;\n*   at time $t$ such that $(P + Q)n + P ≤ t < (P + Q)(n + 1)$, Takahashi is awake.\n\nHe can get off the train at Town $B$ if it is stopping at Town $B$ and he is awake.  \nDetermine whether he can get off at Town $B$. If he can, find the earliest possible time to do so.  \nUnder the constraints of this problem, it can be proved that the earliest time is an integer.\nYou are given $T$ cases. Solve each of them.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 ≤ T ≤ 10$\n*   $1 ≤ X ≤ 10^9$\n*   $1 ≤ Y ≤ 500$\n*   $1 ≤ P ≤ 10^9$\n*   $1 ≤ Q ≤ 500$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$\\rm case_1$\n$\\rm case_2$\n$\\hspace{9pt}\\vdots$\n$\\rm case_T$\n\nEach case is in the following format:\n\n$X$ $Y$ $P$ $Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc193_e","tags":[],"sample_group":[["3\n5 2 7 6\n1 1 3 1\n999999999 1 1000000000 1","20\ninfinity\n1000000000999999999\n\nLet $[a, b)$ denote the interval $a ≤ t < b$.\nIn 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."]],"created_at":"2026-03-03 11:01:14"}}