Cable Construction and Landslide Base Station Problem

Mr. I has a cable construction plan for $C$ days. On the $(i+1)$^th day (where $0\le i\le C-1$), the plan is given by three integers $T_i$, $X_i$, and $Y_i$. They mean the following:

• If $T_i=0$, a cable connecting town $X_i$ and town $Y_i$ is installed. It is guaranteed that at the beginning of day $(i+1)$ there is no cable between $X_i$ and $Y_i$.
• If $T_i=1$, the cable connecting town $X_i$ and town $Y_i$ is removed. It is guaranteed that at the beginning of day $(i+1)$ there is indeed a cable between $X_i$ and $Y_i$.

JOI Kingdom often experiences landslides between town $x$ and town $x+1$ ($0\le x\le N-2$). When a landslide occurs between town $x$ and town $x+1$, only the cables connecting towns with both endpoints not exceeding $x$ or both endpoints not less than $x+1$ remain available.

After a landslide, base stations are built in some of the towns. The base station placement must satisfy that every town can reach some base station via the available cables.

Mr. I has $Q$ questions. The $(j+1)$^th question is given by two integers $W_j$ and $P_j$, meaning that after the end of day $(W_j+1)$, if a landslide occurs between town $P_j$ and town $P_j+1$, what is the minimum number of base stations that must be built?

Your task is to answer all of Mr. I's questions.

inputFormat

The input begins with a line containing three integers $N$, $C$, and $Q$, representing the number of towns, the number of days (cable events), and the number of queries respectively.

The next $C$ lines each contain three integers $T_i$ $X_i$ $Y_i$ representing the event on day $(i+1)$.

The following $Q$ lines each contain two integers $W_j$ $P_j$ representing the query.

Note: Towns are numbered from 0 to $N-1$. For a query, consider only the cable events that have occurred up to day $(W_j+1)$.

outputFormat

For each query, output a single integer on a new line, which is the minimum number of base stations required so that every town is connected to some base station after a landslide between town $P_j$ and town $P_j+1$.

sample

6 5 4
0 0 1
0 2 3
0 1 2
1 1 2
0 4 5
0 0
2 2
4 1
4 3

6
4
3
3