$N$ people, labelled from $1$ to $N$, are playing a ball passing game, standing in a circle in clockwise order.
However, they think that simply passing the ball to the next player would be too simple, so they agree to modify the game rules:

• The game lasts for $Q$ rounds.
• In the $i$-th round ($1 \leq i \leq Q$),
• The player numbered $a_i$ holds the ball initially.
• The ball will be passed $k_i$ times.
• Let's say the player labelled $j$ hold the ball currently. If it is the $t$-th time he/she holds the ball in this specific round, he/she will pass it to the $t$-th next player clockwise (not including him/herself).
  For example, $N=4$ and player numbered $3$ is holding the ball, if it is the $2$-nd time he/she holds the ball in this round, he will pass it to the player numbered $1$.

Denote $e_i$ to be the label of player who holds the ball in the end of the $i$-th round. Write a program to find $e_i$ for $1 \leq i \leq Q$.

Input

The first line contains 2 integers: $N, Q$.
The next $Q$ lines contains 2 integers, where the $i$-th line is $a_i, k_i$.

Output

Output $Q$ lines. The $i$-th line contains 1 integer: $e_i$.

Constraints

For all subtasks:

• $2 \leq N \leq 2 × 10^5$, $1 \leq Q,k_i \leq 2 × 10^5$
• $1 \leq a_i \leq N$

---

Subtask 1 (40%): $N, T, k_i \leq 3000$
Subtask 2 (60%): No additional constraints