Vitaro, a hero of the Lemon Kingdom, wants to raise his level by raiding dungeons.
There are dungeons. The difficulty of dungeon is represented by two integers . If Vitaro attempts dungeon while his current level is , the result is as follows.
A dungeon that has been attempted cannot be attempted again. Vitaro may choose both the order of the attempts and how many dungeons to attempt.
Vitaro's initial level is . For the initial dungeon configuration and after each update query, find the maximum level that Vitaro can reach when starting from level .
For every answer, Vitaro starts again from level , and no dungeon has been attempted yet. Attempts made while computing one answer do not affect any other answer.
Each update query is given by three integers . After the query, the difficulty of dungeon becomes and . The updated values remain in effect for subsequent queries.
The input is given from Standard Input in the following format:
Print lines.
On the first line, print the maximum reachable level before applying any update query.
For each from to , on line , print the maximum reachable level after applying the first update queries.
Query changes the difficulty of dungeon to and .
| 3 | 4 | For every initial value and every value assigned by an update, . |
| 4 | 12 | For every initial value and every value assigned by an update, . |
| 5 | 32 | . |
| 6 | 22 | . |
| 7 | 14 | No additional constraints. |