이진 탐색 트리

이진 탐색 트리(BST)는 기본적인 자료구조이다. BST는 루트가 있는 이진 트리이며, 각 노드에 값을 저장한다. 노드 $x$가 값 $a$를 가지면, $x$의 왼쪽 서브트리에 있는 모든 값은 $a$보다 작고, 오른쪽 서브트리에 있는 모든 값은 $a$보다 크다. 구현을 통일하기 위해, 루트가 $x$인 BST에서 값 $a$를 찾는 구현을 다음과 같이 제공한다. 여기서 $l[x]$는 $x$의 왼쪽 자식, $r[x]$는 $x$의 오른쪽 자식, $w[x]$는 $x$의 값이다. 왼쪽 자식(오른쪽 자식)이 없으면 $l[x]$ ($r[x]$)는 $0$이다. $A(root, a)$는 find(root, a)가 방문하는 모든 노드의 배열이다. find(root, a)의 비용은 $A(root, a)$에 속한 모든 $v$에 대해 $w[v]$를 더한 값이다. 비어 있는 BST가 $n$개 있고, $m$개의 연산을 빠르게 처리해야 한다. 연산은 두 종류이다. 1 l r w 형식의 연산 1은 각 $i \in [l, r]$에 대해 $i$번째 BST에 정수 $w$를 삽입한다. 이 BST들에는 $w$가 이미 없다고 보장된다. 삽입은 find와 같은 경로를 따라 루트에서 시작하되, 마지막 find(0, w) 호출 대신 그 위치에 값이 $w$인 새 노드를 만들고 끝낸다. 2 x a 형식의 연산 2는 $x$번째 BST에서 $a$를 찾는 비용을 계산한다.

첫 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 2 \cdot 10^{5}$)이 주어진다. $n$은 BST의 개수, $m$은 연산의 개수이다. 이후 $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$는 서로 다르다고 보장된다.

두 번째 종류의 연산마다 비용을 정수 하나로 한 줄에 출력한다.