| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Catapult-carousel is a new experimental fairground attraction that John invented: a rotating wheel where $N$ seats are spaced at equal distances. The seats are numbered 1ドル \ldots N$ in clockwise order. Each seat is equipped with a mechanism that can launch the rider up the air in a controlled manner---so that they land on a predetermined seat.
An $(X, Y)$-jump is the mode of operation of the carousel where all riders will be launched simultaneously in such a way that the rider launched from seat 1ドル$ will land on seat $X$ and each subsequent rider (from seats 2ドル \ldots N$) will land on a seat $Y$ positions clockwise from the previous landing position. John has designed the carousel in a way that no two riders will ever land on the same seat (for any allowed jump mode).
One ride on the carousel comprises of several jumps. The number and parameters of jumps are the same in all rides. The riders do not change seats between jumps, even when a rider takes several rides in a sequence. John is selling multiple-ride tickets that specify the initial seat and the number of rides. Now he wants to check that the rider is in the expected seat after completing all the rides.
Write a program that gets the seat number $U$ of a rider and computes their seat after $K$ rides (or the seat they were at $|K|$ rides ago, in case $K$ is negative).
The first line contains $N,ドル the number of seats on the carousel (2ドル \le N < 2^{63}$), and $S,ドル the number of jumps in a ride (1ドル \le S \le 10^6$).
Each of the following $S$ lines sepcifies the parameters $X_i$ and $Y_i$ of one jump (0ドル < X_i \le N,ドル 0ドル < Y_i < N,ドル where 1ドル \le i \le S$).
The last line contains $U,ドル the number of the seat in question (1ドル \le U \le N$), and $K,ドル the number of rides ($-2^{63} \le K < 2^{63}$).
The only line should contain one integer: the number of the seat the rider will be on after $K$ rides (or was on $|K|$ rides ago, if $K$ is negative).
11 2 3 2 5 7 4 2
1
Let's number the riders according to their initial seats: $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$.
After the first jump of the first ride (where $X = 3,ドル $Y = 2$), they land as follows: $[11, 6, 1, 7, 2, 8, 3, 9, 4, 10, 5]$.
After the second jump of the first ride ($X = 5,ドル $Y = 7$): $[6, 10, 3, 7, 11, 4, 8, 1, 5, 9, 2]$.
After the first jump of the second ride ($X = 3,ドル $Y = 2$): $[2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 11]$.
After the second jump of the second ride ($X = 5,ドル $Y = 7$): $[4, 9, 3, 8, 2, 7, 1, 6, 11, 5, 10]$.
The answer is 1ドル,ドル as the rider who started from seat 4ドル$ ends up on seat 1ドル$ after 2ドル$ rides.
911 4 3 2 5 7 133 22 11 12 1 -1
825