题目描述

系统中维护着 n 棵最初为空的二叉搜索树。每个节点保存一个值。对任意节点 x，若其值为 w[x]，则左子树中的所有值都小于 w[x]，右子树中的所有值都大于 w[x]。

在一棵二叉搜索树中查找数值 a 的过程如下：

• 从根节点开始；
• 若当前节点为空，查找结束；
• 若当前节点值等于 a，查找结束；
• 若 a 小于当前节点值，则进入左儿子；
• 若 a 大于当前节点值，则进入右儿子。

记 A(root, a) 为一次查找过程中访问到的所有非空节点。查找代价定义为这些节点权值之和：

sum_{v in A(root, a)} w[v]

现在有 m 个操作，需要快速处理。

操作分为两种：

1. 1 l r w：对所有 i in [l, r]，将整数 w 插入第 i 棵二叉搜索树。保证 w 此前不在这些树中。插入过程与查找相同，只是在本应进入空节点时新建一个值为 w 的节点。
2. 2 x a：询问在第 x 棵二叉搜索树中查找值 a 的代价。

保证所有第一类操作中出现的插入值 w 两两不同。

输入格式

第一行包含两个整数 n, m，分别表示二叉搜索树数量和操作数量。

接下来 m 行，每行描述一个操作，格式为以下两种之一：

1 l r w
2 x a

输出格式

对于每个第二类操作，输出一行一个整数，表示对应查找代价。

数据范围

• 1 <= n, m <= 200000
• 第一类操作：1 <= l <= r <= n，1 <= w <= 10^9
• 第二类操作：1 <= x <= n，1 <= a <= 10^9
• 所有插入操作中的 w 互不相同

样例

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

2
2
2
5
4
4