题目描述

Muxii有一个 $[1,n]$ 的数轴，$m$ 种颜色的线段。
Muxii规定，对于第 $i$ 种颜色，仅有 $[l_i,r_i]$ 部分的数轴允许覆盖线段，且每条线段的长度不能超过 $k_i$ $(k_i≤10)$。线段可以有任意多条。
现在Muxii将会询问你 $q$ 次，每次询问给出两个数字 $a$、$b$，请你回答若要覆盖 $[a,b]$ 部分的数轴最少需要几条线段。
数据保证数轴上不存在不能被任何线段覆盖的位置。

输入格式

本题部分数据点强制在线。
第一行四个数 $o$、$n$、$m$、$q$，其中当 $o=1$ 时，该数据点强制在线，即每次给出的 $a$、$b$ 异或上次询问的答案的结果为真正的 $a$、$b$，当第一次询问时，可认为上一次询问的答案为 $0$；当 $o=0$ 时，该数据点不强制在线。
接下来 $m$ 行，每行三个数 $l_i$、$r_i$、$k_i$；
再接下来 $q$ 行，每行两个数 $a$、$b$。以上未解释的变量意义皆已在题目描述中给出。

输出格式

共 $q$ 行，每行一个数表示答案。

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

3

提示

【样例 $1$ 说明】

最少需要 $3$ 条线段。下面给出一种可行的解决方案：
第 $1$ 条线段为 $[1,4]$ ，颜色为 $1$；
第 $2$ 条线段为 $[4,6]$ ，颜色为 $2$；
第 $3$ 条线段为 $[6,7]$ ，颜色为 $2$。

【数据范围与约定】

• Subtask 1（5 points）：$n,m,q≤1000$，不强制在线。
• Subtask 2（20 points）：$n≤2×10^5$。不强制在线。
• Subtask 3（20 points）：$n≤10^7$。不强制在线。
• Subtask 4（10 points）：$m≤1000$。不强制在线。
• Subtask 5（25 points）：无特殊限制，不强制在线。
• Subtask 6（20 points）：无特殊限制，强制在线。

对于 $100\%$ 的数据，保证 $1≤n≤10^9$，$1≤m≤2×10^5$，$1≤q≤10^6$，$1≤l_i<r_i≤n$，$1≤k_i≤\min(10,r_i-l_i)$，$1≤a<b≤n$。以上变量皆为整数。