Description

二叉搜索树（binary search tree）是一种带根的二叉树，其节点存储的键值满足：每个节点的键值大于其左子树中所有节点的键值，并小于其右子树中所有节点的键值。

二叉搜索树可用于维护有序集合，并支持对集合执行多种查询操作。本题中我们考虑的查询是：在集合中查找位于区间 $[L, R]$ 内的值的数量。

设 $S$ 为二叉搜索树中所有键值的集合。给定两个值 $L$ 和 $R$，查询的目标是找出满足 $L \le x \le R$ 的 $x \in S$ 的数量。以下递归函数在调用 lookup(root, L, R) 时会计算该值，其中 root 是二叉搜索树的根节点。

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

变量 v.left、v.right、v.min、v.max、v.key 和 v.count 是二叉搜索树节点的字段：

• v.left 和 v.right 分别是节点 $v$ 的左子节点和右子节点。
• v.min 和 v.max 分别是以节点 $v$ 为根的子树中的最小键值和最大键值。
• v.key 是节点 $v$ 的键值。
• v.count 是以节点 $v$ 为根的子树中的节点数量。

给定一棵键值为整数的二叉搜索树，以及若干查询，每个查询包含两个整数 $L$ 和 $R$。请计算在调用 lookup(root, L, R) 时，lookup 函数被调用的总次数（包括初始调用 lookup(root, L, R) 本身）。

Input Format

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）——二叉搜索树的节点数量。

接下来的 $n$ 行描述树的节点。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $k_i$，分别表示第 $i$ 个节点的左子节点、右子节点和键值。如果节点没有左子节点或右子节点，则对应值为 $0$（$l_i = 0$ 或 $i < l_i \le n$；$r_i = 0$ 或 $i < r_i \le n$；$-10^9 \le k_i \le 10^9$）。树的根节点为节点 $1$，保证这是一棵合法的二叉搜索树。

注意，v.min、v.max 和 v.count 并未在输入中显式给出，因为它们可以通过 $l_i$、$r_i$ 和 $k_i$ 推导得出。

接下来一行包含一个整数 $q$（$1 \le q \le 200\,000$）——查询的数量。

接下来的 $q$ 行每行包含两个整数 $L$ 和 $R$（$-10^9 \le L \le R \le 10^9$）——作为 lookup 函数的参数。

Output Format

输出 $q$ 行，第 $i$ 行包含一个整数——第 $i$ 个查询中 lookup 函数被调用的总次数。

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

Hint

翻译由 DeepSeek V3 完成