Find the Joker 2

Interview

Time limit1sMemory limit1024 MB

Summary

Given shuffles that rotate the deck by one card or point back to an earlier deck state, find the joker's final position starting from position 1.

Level: Medium4 of 10
Topics: Tree, Prefix sum, Math
Solved: No attempts yet

Problem

Suhyeon, a student at Chung-Ang University, learned card-cheating techniques. This time, after watching a magic video on YouTube, Suhyeon wants to copy the trick. Suhyeon places the joker on top of a card deck and shuffles the cards to send the joker to a desired position.

The deck has $N$ cards in total: $N-1$ blank cards and 1 joker card. Call the top card card 1 and the bottom card card $N$ . In the initial deck, the joker is at position 1.

Suhyeon shuffles the cards $M$ times. There are 3 shuffle methods.

1 $x_i$ : Move card $N$ on top of card 1. Repeat this $x_i$ times.
2 $y_i$ : Move card 1 under card $N$ . Repeat this $y_i$ times.
3 $z_i$ $z_{i}$ : Change the deck state to the deck state after $z_i$ $z_{i}$ shuffles from the initial state. If $z_i = 0$ $z_{i} = 0$ , change to the initial deck.
- This does not turn back the deck's history. It only changes the deck state.

Input

The first line contains $N$ and $M$ , separated by a space.

The next $M$ lines describe the shuffles. Line $i$ describes the $i$ -th shuffle.

Output

Print the position of the joker from the top of the deck after all shuffles are finished.

Constraints

$1 \le N, M \le 100\,000$
$1 \le x_i, y_i \le 10^{18}$
$0 \le z_i < i$
$1 \le i \le M$
All input values are integers.

Examples4

Example 1
Input
```
3 3
3 0
1 1
2 2
```
Expected output
```
3
```
Example 2
Input
```
4 5
1 1
1 1
3 0
1 1
3 3
```
Expected output
```
1
```
Example 3
Input
```
5 5
1 4
2 3
3 1
2 4
1 3
```
Expected output
```
4
```
Example 4
Input
```
9 2
1 100000000000
2 100000000001
```
Expected output
```
9
```