题目描述

I 先生有一个 $C$ 天的电缆建设计划。第 $(i+1)\ (0\le i\le C-1)$​ 天的计划用三个整数 $T_i,X_i,Y_i$ 表示，分别表示：

• 如果 $T_i=0$，他们会架设一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间没有电缆。
• 如果 $T_i=1$​，他们会拆除一段连接城镇 $X_i$​ 与城镇 $Y_i$​ 的电缆。保证在第 $(i+1)$​ 天开始的时候城镇 $X_i$​ 与城镇 $Y_i$​ 之间有电缆。

JOI 国经常发生山体滑坡。如果在城镇 $x$ 与 $x+1\ (0\le x\le N-2)$​ 之间发生山体滑坡，则只有连接两端编号均不超过 $x$ 与编号均不少于 $x+1$ 城镇的电缆可用。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。

I 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 $Q$ 个问题：第 $(j+1)$ 个问题用两个整数 $W_j,P_j$ 表示，表示他想知道在 $(W_j+1)$ 天结束时，如果在城镇 $P_j$ 和 $P_j+1$ 之间发生山体滑坡，至少应该建立多少基站。

你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。

输入格式

LOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。

第一行三个整数 $N,C,Q$。

接下来 $C$ 行，每行三个整数 $T_i,X_i,Y_i$。

接下来 $Q$ 行，每行两个整数 $W_j,P_j$。

输出格式

输出 $Q$ 行，第 $j+1$ 行输出 $D_j$ 表示对第 $(j+1)$​ 个问题的回答。

5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3

3
2

提示

【样例】

考虑有 $5$ 个城镇的情况。接下来用 $(x,y)$ 代表连接城镇 $x$ 和城镇 $y$ 的电缆。

• 假设当有四根电缆 $(0,1),(1,3),(2,4),(4,0)$ 时，在城镇 $1$ 和 $2$ 之间发生了滑坡。电缆 $(1,3)$ 和 $(4,0)$ 不可用了，因此可用的电缆是 $(0,1)$ 和 $(2,4)$。你需要在城镇 $0,2,3$ 建立基站。最少要建立基站数为 $3$。
• 假设当有六根电缆 $(0, 1), (0, 3), (1, 2), (2, 4), (4, 0)$​​ 和 $(4,3)$​​ 时，在城镇 $3$​​ 和 $4$​​ 之间发生了滑坡。电缆 $(2,4),(4,0)$​​ 和 $(4,3)$​​ 不可用了，因此可用的电缆是 $(0,1),(0,3)$​​ 和 $(1,2)$​​。你需要在城镇 $0$​​ 和 $4$ 建立基站。最少要建立基站数为 $2$​​。

【数据范围】

本题有四个子任务。子任务分值及附加限制如下表所示：