二叉搜索树（binary search tree）是一种有根二叉树，其节点存储键值（key），使得每个节点的键值都大于其左子树中所有节点的键值，且小于其右子树中所有节点的键值。

二叉搜索树可用于维护有序集合，并允许对该集合执行不同类型的查询。在本题中，我们考虑的查询是寻找集合中处于区间 $[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) 调用本身。

输入格式

第一行包含一个整数 $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 函数的参数。

输出格式

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

样例

输入样例 1

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

输出样例 1

7
1
7
3
3