Niniejszy problem dotyczy drzew poszukiwań binarnych (BST), podstawowej struktury danych. Struktura ta jest ukorzenionym drzewem binarnym, które przechowuje wartości w swoich węzłach. Jeśli węzeł $x$ zawiera wartość $a$, wszystkie wartości w lewym poddrzewie $x$ są mniejsze od $a$, a wszystkie wartości w prawym poddrzewie $x$ są większe od $a$.

W celu ujednolicenia szczegółów, przedstawiamy implementację wyszukiwania wartości $a$ w drzewie BST ukorzenionym w węźle $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);
}

Tutaj $l[x]$ to lewe dziecko $x$, $r[x]$ to prawe dziecko $x$, a $w[x]$ to wartość węzła $x$. W szczególności, jeśli $x$ nie posiada lewego dziecka (prawego dziecka), $l[x]$ ($r[x]$) wynosi 0.

Definiujemy $A(root, a)$ jako tablicę wszystkich węzłów odwiedzonych przez find(root, a). Definiujemy również koszt find(root, a) jako:

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

Dostępnych jest $n$ pustych drzew BST oraz $m$ operacji. Twoim zadaniem jest szybkie przetworzenie tych operacji. Istnieją dwa rodzaje operacji:

• „1 $l$ $r$ $w$”. Dla każdego $i \in [l, r]$, wstaw liczbę całkowitą $w$ do $i$-tego drzewa BST. Gwarantuje się, że $w$ nie występuje jeszcze w tych drzewach BST. Wstawianie rozpoczyna się od korzenia i przebiega tak samo jak wyszukiwanie, ale zamiast wykonywać ostatnie wywołanie find(0, w), tworzy w tym miejscu nowy węzeł o wartości $w$ i kończy działanie.
• „2 $x$ $a$”. Oblicz koszt wyszukania $a$ w $x$-tym drzewie BST.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 2 \cdot 10^5$), oznaczające liczbę drzew BST oraz liczbę operacji.

Następnie następuje $m$ linii. Każda linia zawiera opis operacji i jest sformatowana jako „1 $l$ $r$ $w$” ($1 \le l \le r \le n$; $1 \le w \le 10^9$) lub „2 $x$ $a$” ($1 \le x \le n$; $1 \le a \le 10^9$).

Gwarantuje się, że wszystkie wstawiane liczby ($w$ w operacjach pierwszego rodzaju) są od siebie różne.

Wyjście

Dla każdej operacji drugiego rodzaju wypisz w pojedynczej linii jedną liczbę całkowitą: koszt.

Przykład

Wejście 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

Wyjście 1

2
2
2
5
4
4

Implementacja wyszukiwania wartości a w drzewie BST