Dungeon Raid

Vitaro, a hero of the Lemon Kingdom, wants to raise his level by raiding dungeons.

There are $N$ dungeons. The difficulty of dungeon $i$ is represented by two integers $A_i,B_i$. If Vitaro attempts dungeon $i$ while his current level is $X$, the result is as follows.

• If $X \le A_i$, the raid fails and his level does not change.
• If $B_i \le X$, the raid succeeds and his level increases by .

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 $L$. For the initial dungeon configuration and after each update query, find the maximum level that Vitaro can reach when starting from level $L$.

For every answer, Vitaro starts again from level $L$, 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 $i,a,b$. After the query, the difficulty of dungeon $i$ becomes $A_i=a$ and $B_i=b$. The updated values remain in effect for subsequent queries.

The input is given from Standard Input in the following format:

$N\ Q\ L$ $A_1\ B_1$ $$

Print $Q+1$ lines.

On the first line, print the maximum reachable level before applying any update query.

For each $q$ from $1$ to $Q$, on line $q+1$, print the maximum reachable level after applying the first update queries.

• $1 \le N \le 500\,000$.
• $0 \le Q \le 200\,000$.
• $1\le L\le {}^{}$.