本题关于二叉搜索树（BST），这是一种基础数据结构。该结构是一棵有根二叉树，其节点存储数值。如果节点 $x$ 包含数值 $a$，则 $x$ 左子树中的所有值都小于 $a$，右子树中的所有值都大于 $a$。

为了统一细节，我们提供在以节点 $root$ 为根的 BST 中查找数值 $a$ 的实现：

void find(x, a) {
    if (x == 0 || w[x] == a) return;
    if (w[x] > a) find(l[x], a);
    else find(r[x], a);
}

这里 $l[x]$ 是 $x$ 的左孩子，$r[x]$ 是 $x$ 的右孩子，$w[x]$ 是 $x$ 的值。特别地，如果 $x$ 没有左孩子（或右孩子），则 $l[x]$（或 $r[x]$）为 $0$。

我们定义 $A(root, a)$ 为 find(root, a) 访问的所有节点的数组。我们还定义 find(root, a) 的代价为： $$\sum_{v \in A(root, a)} w[v]$$

现在有 $n$ 棵空 BST 和 $m$ 次操作。你的任务是快速处理这些操作。有两种不同类型的操作：

• “$1\ l\ r\ w$”。对于每个 $i \in [l, r]$，将整数 $w$ 插入到第 $i$ 棵 BST 中。保证 $w$ 在这些 BST 中不存在。插入从根开始，过程与 find 相同，但在最后一次 find(0, w) 调用处，创建一个值为 $w$ 的新节点并返回。
• “$2\ x\ a$”。计算在第 $x$ 棵 BST 中查找 $a$ 的代价。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 \cdot 10^5$)，表示 BST 的数量和操作的数量。

接下来 $m$ 行。每行包含一个操作的描述，格式为 “$1\ l\ r\ w$” ($1 \le l \le r \le n; 1 \le w \le 10^9$) 或 “$2\ x\ a$” ($1 \le x \le n; 1 \le a \le 10^9$)。

保证所有插入的数字（第一类操作中的 $w$）互不相同。

输出格式

对于每个第二类操作，输出一行，包含一个整数：代价。

样例

输入格式 1

3 9
1 1 2 2
1 1 3 1
1 2 3 3
2 1 2
2 1 4
2 2 2
2 2 4
2 3 2
2 3 4

输出格式 1

2
2
2
5
4
4