本題關於二元搜尋樹（BST），這是一種基礎資料結構。該結構是一棵根節點樹，其節點儲存數值。若節點 $x$ 包含數值 $a$，則 $x$ 左子樹中的所有數值皆小於 $a$，而右子樹中的所有數值皆大於 $a$。

為了統一細節，我們提供在以節點 $x$ 為根的 BST 中尋找數值 $a$ 的實作方式：

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(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 相同，但在最後一次 find(0, w) 呼叫處，改為建立一個數值為 $w$ 的新節點並返回。
• 「$2\ x\ a$」：計算在第 $x$ 棵 BST 中尋找 $a$ 的代價。

輸入格式

第一行包含兩個整數 $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

BST 尋找數值 a 的實作方式