この問題は、基本的なデータ構造である二分探索木（BST）に関するものです。この構造は、各ノードに値を格納する根付き二分木です。ノード $x$ が値 $a$ を保持している場合、$x$ の左部分木に含まれるすべての値は $a$ 未満であり、$x$ の右部分木に含まれるすべての値は $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$ 個の操作があります。あなたのタスクは、これらの操作を高速に処理することです。操作には以下の2種類があります。

• 「$1 \ l \ r \ w$」：各 $i \in [l, r]$ について、$i$ 番目の BST に整数 $w$ を挿入します。これらの BST に $w$ は存在しないことが保証されています。挿入は根から始まり、find と同様に進みますが、最後の find(0, w) を呼び出す代わりに、そこに値 $w$ を持つ新しいノードを作成して終了します。
• 「$2 \ x \ a$」：$x$ 番目の BST における $a$ の探索コストを計算します。

入力

最初の行には、$n$ と $m$ ($1 \le n, m \le 2 \cdot 10^5$) の2つの整数が含まれており、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$) の形式です。

挿入されるすべての数値（1番目の種類の操作における $w$）は互いに異なることが保証されています。

出力

2番目の種類の各操作に対して、コストを単一の整数として1行に出力してください。

入出力例

入力 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