Este problema trata sobre Árboles de Búsqueda Binaria (BST, por sus siglas en inglés), una estructura de datos básica. La estructura es un árbol binario con raíz que almacena valores en sus nodos. Si el nodo $x$ contiene el valor $a$, todos los valores en el subárbol izquierdo de $x$ son menores que $a$, y todos los valores en el subárbol derecho de $x$ son mayores que $a$.

Para unificar los detalles, proporcionamos una implementación para encontrar un valor $a$ en un BST con raíz en el nodo $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);
}

Aquí, $l[x]$ es el hijo izquierdo de $x$, $r[x]$ es el hijo derecho de $x$, y $w[x]$ es el valor de $x$. Específicamente, si $x$ no tiene un hijo izquierdo (hijo derecho), $l[x]$ ($r[x]$) es 0.

Definimos $A(root, a)$ como el arreglo de todos los nodos visitados por find(root, a). También definimos el costo de find(root, a) como:

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

Ahora hay $n$ BSTs vacíos y $m$ operaciones. Tu tarea es procesar estas operaciones rápidamente. Existen dos tipos diferentes de operaciones:

• “1 $l$ $r$ $w$”. Para cada $i \in [l, r]$, inserta un entero $w$ en el $i$-ésimo BST. Se garantiza que $w$ no está presente en estos BSTs. La inserción comienza en la raíz, sigue el mismo proceso que find, pero en lugar de realizar la última llamada find(0, w), crea un nuevo nodo con valor $w$ allí y retorna.
• “2 $x$ $a$”. Calcula el costo de encontrar $a$ en el $x$-ésimo BST.

Entrada

La primera línea contiene dos enteros, $n$ y $m$ ($1 \le n, m \le 2 \cdot 10^5$), que indican el número de BSTs y el número de operaciones.

Luego siguen $m$ líneas. Cada línea contiene la descripción de una operación y tiene el formato “1 $l$ $r$ $w$” ($1 \le l \le r \le n$; $1 \le w \le 10^9$) o “2 $x$ $a$” ($1 \le x \le n$; $1 \le a \le 10^9$).

Se garantiza que todos los números insertados ($w$ en las operaciones del primer tipo) son diferentes entre sí.

Salida

Para cada operación del segundo tipo, imprime una sola línea con un único entero: el costo.

Ejemplos

Entrada 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

Salida 1

2
2
2
5
4
4

Implementación para encontrar un valor a en un BST