Catapult-Carousel

Catapult-Carousel은 John이 발명한 새로운 실험적 놀이기구다. 같은 간격으로 $N$개의 좌석이 놓인 회전하는 바퀴다. 좌석은 시계 방향으로 $1 \ldots N$번까지 번호가 매겨져 있다. 각 좌석에는 탑승자를 공중으로 제어된 방식으로 띄워서 미리 정해진 좌석에 착지시키는 장치가 달려 있다.

$(X, Y)$-점프는 이 놀이기구의 운영 방식이다. 이 방식에서는 모든 탑승자가 동시에 발사된다. 좌석 1에서 발사된 탑승자는 좌석 $X$에 착지하고, 이어서 발사되는 탑승자(좌석 $2 \ldots N$)는 직전 착지 위치에서 시계 방향으로 $Y$칸 떨어진 좌석에 착지한다. John은 허용되는 어떤 점프 방식에서도 두 탑승자가 같은 좌석에 착지하지 않도록 놀이기구를 설계했다.

한 번의 라이드는 여러 번의 점프로 이루어진다. 점프의 횟수와 매개변수는 모든 라이드에서 같다. 탑승자는 점프 사이에 좌석을 바꾸지 않으며, 여러 라이드를 연달아 타더라도 마찬가지다. John은 시작 좌석과 라이드 횟수를 지정하는 다회 탑승권을 판매한다. 그는 탑승자가 모든 라이드를 마친 뒤 예상한 좌석에 있는지 확인하고 싶어 한다.

탑승자의 좌석 번호 $U$를 입력받아 $K$번 라이드를 마친 뒤의 좌석을 구하는 프로그램을 작성하라. $K$가 음수이면 $|K|$번 라이드 전에 있던 좌석을 구한다.

첫 줄에는 좌석 수 $N$($2 \le N < 2^{63}$)과 한 라이드의 점프 수 $S$($1 \le S \le 10^6$)가 주어진다.

이어지는 $S$개의 줄에는 각 점프의 매개변수 $X_i$와 $Y_i$가 주어진다($0 < X_i \le N$, $0 < Y_i < N$, $1 \le i \le S$).

마지막 줄에는 탑승자의 좌석 번호 $U$($1 \le U \le N$)와 라이드 횟수 $K$($-2^{63} \le K < 2^{63}$)가 주어진다.

한 줄에 정수 하나를 출력한다. 이는 $K$번 라이드를 마친 뒤 탑승자가 있는 좌석 번호다. $K$가 음수이면 $|K|$번 라이드 전에 탑승자가 있던 좌석 번호를 출력한다.