Ce problème porte sur les arbres binaires de recherche (BST), une structure de données fondamentale. Cette structure est un arbre binaire enraciné qui stocke des valeurs dans ses nœuds. Si un nœud $x$ contient une valeur $a$, toutes les valeurs dans le sous-arbre gauche de $x$ sont inférieures à $a$, et toutes les valeurs dans le sous-arbre droit de $x$ sont supérieures à $a$.

Afin d'unifier les détails, nous fournissons une implémentation de la recherche d'une valeur $a$ dans un BST enraciné au nœud $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);
}

Ici, $l[x]$ est l'enfant gauche de $x$, $r[x]$ est l'enfant droit de $x$, et $w[x]$ est la valeur de $x$. Plus précisément, si $x$ n'a pas d'enfant gauche (ou droit), $l[x]$ (ou $r[x]$) vaut 0.

Nous définissons $A(root, a)$ comme le tableau de tous les nœuds visités par find(root, a). Nous définissons également le coût de find(root, a) comme : $$\sum_{v \in A(root, a)} w[v].$$

Il y a maintenant $n$ BST vides et $m$ opérations. Votre tâche est de traiter ces opérations rapidement. Il existe deux types d'opérations différents :

• « 1 $l$ $r$ $w$ ». Pour chaque $i \in [l, r]$, insérez un entier $w$ dans le $i$-ème BST. Il est garanti que $w$ n'est pas présent dans ces BST. L'insertion commence à la racine, suit le même chemin que find, mais au lieu d'effectuer le dernier appel find(0, w), elle crée un nouveau nœud avec la valeur $w$ à cet emplacement et s'arrête.
• « 2 $x$ $a$ ». Calculez le coût de la recherche de $a$ dans le $x$-ème BST.

Entrée

La première ligne contient deux entiers, $n$ et $m$ ($1 \le n, m \le 2 \cdot 10^5$), indiquant le nombre de BST et le nombre d'opérations.

Ensuite, $m$ lignes suivent. Chaque ligne contient la description d'une opération et est formatée soit comme « 1 $l$ $r$ $w$ » ($1 \le l \le r \le n$; $1 \le w \le 10^9$), soit comme « 2 $x$ $a$ » ($1 \le x \le n$; $1 \le a \le 10^9$).

Il est garanti que tous les nombres insérés ($w$ dans les opérations du premier type) sont distincts les uns des autres.

Sortie

Pour chaque opération du second type, affichez une seule ligne contenant un seul entier : le coût.

Exemples

Entrée 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

Sortie 1

2
2
2
5
4
4

Implémentation de la recherche d'une valeur a dans un BST enraciné au nœud x