Catapult-Carousel

Catapult-Carousel is a new experimental fairground attraction that John invented. It is a rotating wheel with $N$ seats spaced at equal distances. The seats are numbered $1 \ldots N$ in clockwise order. Each seat has a mechanism that launches the rider into the air in a controlled manner, so that the rider lands on a predetermined seat.

An $(X, Y)$-jump is an operating mode of the carousel. In this mode, all riders are launched simultaneously. The rider launched from seat $1$ lands on seat $X$, and each subsequent rider (from seats $2 \ldots N$) lands $Y$ positions clockwise from the previous landing position. John designed the carousel so that no two riders land on the same seat in any allowed jump mode.

One ride consists of several jumps. The number and parameters of the jumps are the same in every ride. Riders do not change seats between jumps, even when they take several rides in a row. John sells multiple-ride tickets that specify the initial seat and the number of rides. He wants to check that a rider is in the expected seat after completing all the rides.

Write a program that takes the seat number $U$ of a rider and computes their seat after $K$ rides. If $K$ is negative, the program computes the seat they were on $|K|$ rides ago.

The first line contains $N$, the number of seats ($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 contains the parameters $X_i$ and $Y_i$ of one jump ($0 < X_i \le N$, $0 < Y_i < N$, $1 \le i \le S$).

The last line contains $U$, the seat number of the rider ($1 \le U \le N$), and $K$, the number of rides ($-2^{63} \le K < 2^{63}$).

The only line contains one integer: the seat the rider is on after $K$ rides. If $K$ is negative, print the seat the rider was on $|K|$ rides ago.