Problem Description

Muxii has a number line $[1,n]$ and line segments in $m$ different colors.
Muxii specifies that for the $i$-th color, only the interval $[l_i,r_i]$ on the number line is allowed to be covered by segments of this color, and the length of each segment must not exceed $k_i$ $(k_i\le 10)$. There can be any number of segments.
Now Muxii will ask you $q$ queries. Each query gives two numbers $a$ and $b$. Please answer: to cover the interval $[a,b]$ on the number line, what is the minimum number of segments needed.
It is guaranteed that there is no position on the number line that cannot be covered by any segment.

Input Format

Some testdata in this problem enforces online queries.
The first line contains four integers $o$, $n$, $m$, $q$. When $o=1$, this testdata enforces online queries, i.e., the real $a$ and $b$ are obtained by XOR-ing the given $a$ and $b$ with the answer to the previous query. For the first query, you may assume the previous answer is $0$. When $o=0$, this testdata does not enforce online queries.
The next $m$ lines each contain three integers $l_i$, $r_i$, $k_i$.
The next $q$ lines each contain two integers $a$, $b$. The meanings of all variables not explained here have already been given in the description.

Output Format

Output $q$ lines, each containing one integer representing the answer.

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

3

Hint

[Sample $1$ Explanation]

At least $3$ segments are needed. One feasible solution is:
The $1$st segment is $[1,4]$, color $1$;
The $2$nd segment is $[4,6]$, color $2$;
The $3$rd segment is $[6,7]$, color $2$.

[Constraints and Notes]

• Subtask 1 (5 points): $n,m,q\le 1000$, no online requirement.
• Subtask 2 (20 points): $n\le 2\times 10^5$. No online requirement.
• Subtask 3 (20 points): $n\le 10^7$. No online requirement.
• Subtask 4 (10 points): $m\le 1000$. No online requirement.
• Subtask 5 (25 points): no special limits, no online requirement.
• Subtask 6 (20 points): no special limits, online required.

For $100\%$ of the data, it is guaranteed that $1\le n\le 10^9$, $1\le m\le 2\times 10^5$, $1\le q\le 10^6$, $1\le l_i<r_i\le n$, $1\le k_i\le \min(10,r_i-l_i)$, $1\le a<b\le n$. All variables above are integers.

Translated by ChatGPT 5