Bài toán này đề cập đến Cây tìm kiếm nhị phân (BST), một cấu trúc dữ liệu cơ bản. Cấu trúc này là một cây nhị phân có gốc, lưu trữ các giá trị tại các nút của nó. Nếu nút $x$ chứa giá trị $a$, thì tất cả các giá trị trong cây con bên trái của $x$ đều nhỏ hơn $a$, và tất cả các giá trị trong cây con bên phải của $x$ đều lớn hơn $a$.

Để thống nhất các chi tiết, chúng tôi cung cấp một cách cài đặt để tìm kiếm một giá trị $a$ trong một BST có gốc tại nút $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);
}

Ở đây, $l[x]$ là con trái của $x$, $r[x]$ là con phải của $x$, và $w[x]$ là giá trị của $x$. Cụ thể, nếu $x$ không có con trái (con phải), $l[x]$ ($r[x]$) sẽ bằng 0.

Chúng ta định nghĩa $A(root, a)$ là mảng tất cả các nút được ghé thăm bởi find(root, a). Chúng ta cũng định nghĩa chi phí của find(root, a) là:

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

Hiện có $n$ cây BST rỗng và $m$ thao tác. Nhiệm vụ của bạn là xử lý các thao tác này một cách nhanh chóng. Có hai loại thao tác khác nhau:

• “1 $l$ $r$ $w$”. Với mỗi $i \in [l, r]$, chèn một số nguyên $w$ vào cây BST thứ $i$. Đảm bảo rằng $w$ chưa tồn tại trong các cây BST này. Việc chèn bắt đầu tại gốc, thực hiện tương tự như find, nhưng thay vì thực hiện lệnh gọi find(0, w) cuối cùng, nó tạo ra một nút mới với giá trị $w$ tại đó và kết thúc.
• “2 $x$ $a$”. Tính chi phí tìm kiếm $a$ trong cây BST thứ $x$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 2 \cdot 10^5$), biểu thị số lượng cây BST và số lượng thao tác.

Sau đó là $m$ dòng tiếp theo. Mỗi dòng chứa mô tả của một thao tác và được định dạng là “1 $l$ $r$ $w$” ($1 \le l \le r \le n$; $1 \le w \le 10^9$) hoặc “2 $x$ $a$” ($1 \le x \le n$; $1 \le a \le 10^9$).

Đảm bảo rằng tất cả các số được chèn vào ($w$ trong các thao tác loại một) đều khác nhau.

Dữ liệu ra

Với mỗi thao tác loại hai, in ra một dòng duy nhất chứa một số nguyên: chi phí tìm kiếm.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2
2
2
5
4
4