Catapult-Carousel

문제

Catapult-carousel is a new experimental fairground attraction that John invented: a rotating wheel where $NN$ seats are spaced at equal distances. The seats are numbered $1\dots N1\; \backslash 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)(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 $11$ will land on seat $XX$ and each subsequent rider (from seats $2\dots N2\; \backslash ldots\; N$) will land on a seat $YY$ 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 $UU$ of a rider and computes their seat after $KK$ rides (or the seat they were at $\mathrm{\mid }K\mathrm{\mid }|K|$ rides ago, in case $KK$ is negative).

입력

The first line contains $NN$, the number of seats on the carousel (), and $SS$, the number of jumps in a ride ($1\le S\le {10}^{6}1\; \backslash le\; S\; \backslash le\; 10^6$).

Each of the following $SS$ lines sepcifies the parameters $X_{i}X\_i$ and $Y_{i}Y\_i$ of one jump (, , where $1\le i\le S1\; \backslash le\; i\; \backslash le\; S$).

The last line contains $UU$, the number of the seat in question ($1\le U\le N1\; \backslash le\; U\; \backslash le\; N$), and $KK$, the number of rides ().

출력

The only line should contain one integer: the number of the seat the rider will be on after $KK$ rides (or was on $\mathrm{\mid }K\mathrm{\mid }|K|$ rides ago, if $KK$ is negative).

11 2
3 2
5 7
4 2

1

911 4
3 2
5 7
133 22
11 12
1 -1

825