Эта задача посвящена бинарным деревьям поиска (BST) — базовой структуре данных. Эта структура представляет собой корневое бинарное дерево, в узлах которого хранятся значения. Если узел $x$ содержит значение $a$, то все значения в левом поддереве $x$ меньше $a$, а все значения в правом поддереве $x$ больше $a$.

Для уточнения деталей мы приводим реализацию поиска значения $a$ в BST с корнем в узле $x$:

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 в BST

Определим $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(0, w) создает новый узел со значением $w$ в этом месте и завершается.
• «2 $x$ $a$». Вычислите стоимость поиска $a$ в $x$-м BST.

Входные данные

Первая строка содержит два целых числа $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