Game

After discovering $n$ planets, numbered from $0$ to $n-1$, the Pharaohs have started to build a transportation system between them by one-way teleporters. Each teleporter has a starting planet and an ending planet. When a tourist uses a teleporter in the starting planet, the tourist is teleported to the ending planet. Note that the starting and ending planet of a teleporter may be the same. A teleporter with its starting planet $u$ and ending planet $v$ is denoted by $(u,v)$.

To encourage widespread use of the teleportation system, the Pharaohs have created a game that can be played by tourists while travelling with the transportation system. A tourist can start the game from any planet. The planets $0, 1, \ldots, k-1$ ($k \leq n$) are called special planets. Every time a tourist enters a special planet, the tourist gets an stamp.

Currently, for each $i$ ($0 \leq i \leq k-2$), there is a teleporter $(i, i+1)$. These $k-1$ teleporters are called starting teleporters.

New teleporters are added one by one. As new teleporters are added, it may become possible for a tourist to get infinite number of stamps. To be precise, this happens when there is a sequence of planets $w\[0], w\[1], \ldots, w\[t]$ satisfying the following conditions:

• $1 \leq t$
• $0 \leq w\[0] \leq k-1$
• $w\[t] = w\[0]$
• For each $i$ ($0 \leq i \leq t-1$), there is a teleporter $(w\[i], w\[i+1])$.

Note that a tourist can use starting teleporters and any teleporters that have been added so far.

Your task is to help the Pharaohs verify, after the addition of each teleporter, whether a tourist can get infinite number of stamps or not.

• $1 \leq n \leq 300\\,000$
• $1 \leq m \leq 500\\,000$
• $1 \leq k \leq n$

For each call to the add_teleporter procedure:

• $0 \leq u \leq n-1$ and $0 \leq v \leq n-1$
• There is no teleporter from the planet $u$ to the planet $v$ before adding the teleporter $(u,v)$.