小 C 在 YTP 國發現了一個環形的軌道，軌道上共有 $N$ 個節點，依順時針方向編號為 $0, 1, \ldots, N-1$（從節點 $N-1$ 順時針走一格會回到節點 $0$）。
小 C 把一顆球放在某個節點之後，球會持續沿著順時針方向移動，移動的規則如下：
小 C 有 $Q$ 次詢問，每次詢問給定 $S, T, A, B$，代表他把一顆球放在節點 $S$，並依照上述規則（第奇數次走 $A$ 格、第偶數次走 $B$ 格）移動。請你幫他求出球最早會在第幾次移動之後抵達節點 $T$，如果不論移動多少次都無法抵達節點 $T$，請輸出 $-1$。
注意每次詢問都是獨立的，亦即每次詢問的 $A, B$ 可能不同，並且都是以節點 $S$ 重新開始。此外，初始時位於節點 $T$ 不算作抵達終點。
第一行輸入兩個正整數 $N, Q$，分別代表環上的節點數量與詢問次數。
接下來 $Q$ 行，每行輸入四個整數 $S, T, A, B$，代表一次詢問：把一顆球放在節點 $S$，第奇數次移動順時針走 $A$ 格、第偶數次移動順時針走 $B$ 格。
對於每次詢問，輸出一行一個正整數，代表球從節點 $S$ 出發最早在第幾次移動後抵達節點 $T$。
如果不可能抵達，輸出 $-1$。
6 4 0 2 2 1 0 3 2 1 0 4 2 1 0 0 2 1
1 2 -1 4
1000000000000000000 3 0 999999999999999999 1 0 5 5 0 0 123456789012345678 987654321098765432 111111111111111111 222222222222222222
1999999999999999997 1 814814807481481476
2026 YTP 國中組初賽 p6
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~23 | 無額外限制 | 25 |