题目描述

A $\emph{binary search tree}$ is a rooted binary tree whose nodes store keys so that each node's key is greater than all the keys in the node's left subtree and less than those in its right subtree.

A binary search tree can be used to maintain sorted sets and allows to perform different types of queries on the set. A query that we are considering in this problem is finding the number of values in the range $[L, R]$ within the set.

Let $S$ be the set of all keys in the binary search tree. You are given two values $L$ and $R$. The query is to find the number of such $x \in S$ so that $L \le x \le R$. The following recursive function computes this value when called with the parameters $\verb|lookup(root, L, R)|$, where $\verb|root|$ is the root of the binary search tree.

function lookup(v, L, R):
  if v == null:
    return 0
  if L <= v.min and v.max <= R:
    return v.count
  if v.max < L or R < v.min:
    return 0
  res = 0
  if L <= v.key and v.key <= R:
    res += 1
  res += lookup(v.left, L, R)
  res += lookup(v.right, L, R)
  return res

Values $\verb|v.left|, \verb|v.right|, \verb|v.min|, \verb|v.max|, \verb|v.key|$, and $\verb|v.count|$ are the fields of the nodes of the binary search tree.

• $\verb|v.left|$ and $\verb|v.right|$ are the left and the right children of node $v$, respectively.
• $\verb|v.min|$ and $\verb|v.max|$ are the minimum and the maximum keys in the subtree rooted at node $v$.
• $\verb|v.key|$ is the key of node $v$.
• $\verb|v.count|$ is the number of nodes in the subtree rooted at node $v$.

You are given a binary search tree with integer keys. You are also given queries, each query consisting of two integers $L$ and $R$. Find the number of calls of the $\verb|lookup|$ function that are made when $\verb|lookup(root, L, R)|$ is called, including the initial $\verb|lookup(root, L, R)|$ call itself.

输入格式

The first line contains an integer $n$ ($1 \le n \le 200\,000$) --- the number of nodes in the binary search tree.

The next $n$ lines describe the nodes of the tree. The $i$-th of these lines contains three integers $l_i$, $r_i$, and $k_i$ denoting the left child, the right child and the key of the $i$-th node. If the node does not have the left or/and the right child, the corresponding value is 0 ($l_i = 0$ or $i < l_i \le n$; $r_i = 0$ or $i < r_i \le n$; $-10^9 \le k_i \le 10^9$). The root of the tree is at node 1 and it is guaranteed to be a well-formed binary search tree.

Note that the values $\verb|v.min|, \verb|v.max|$ and $\verb|v.count|$ are not given in the input explicitly, since they can be deduced from $l_i$, $r_i$ and $k_i$.

The next line contains an integer $q$ ($1 \le q \le 200\,000$) --- the number of the queries.

Each of the next $q$ lines contains two integers $L$ and $R$ ($-10^9 \le L \le R \le 10^9$) --- the parameters given to the $\verb|lookup|$ function.

输出格式

Output $q$ lines, the $i$-th line containing a single integer --- the number of calls of the $\verb|lookup|$ function that are made for the $i$-th query.

7
2 3 4
4 0 2
5 6 8
0 0 1
0 7 5
0 0 9
0 0 6
5
2 7
0 10
2 8
4 4
3 3

7
1
7
3
3