Binary Search Tree

A binary search tree (BST) is a basic data structure. It is a rooted binary tree that stores a value in each node. If node $x$ contains value $a$, all values in the left subtree of $x$ are less than $a$, and all values in the right subtree of $x$ are greater than $a$. To keep the details uniform, here is an implementation of finding a value $a$ in a BST rooted at node $x$: Here, $l[x]$ is the left child of $x$, $r[x]$ is the right child of $x$, and $w[x]$ is the value of $x$. If $x$ has no left child (or right child), $l[x]$ ($r[x]$) is $0$. Let $A(root, a)$ be the array of all nodes visited by find(root, a). The cost of find(root, a) is the sum of $w[v]$ over all $v \in A(root, a)$. There are $n$ empty BSTs and $m$ operations, and you must process them quickly. There are two kinds of operations. Operation 1 is written as 1 l r w: for each $i \in [l, r]$, insert the integer $w$ into the $i$-th BST. It is guaranteed that $w$ is not already present in these BSTs. Insertion starts at the root and follows the same path as find, but instead of the final find(0, w) call, it creates a new node with value $w$ at that position and returns. Operation 2 is written as 2 x a: calculate the cost of finding $a$ in the $x$-th BST.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^{5}$), the number of BSTs and the number of operations. Then $m$ lines follow, each describing one operation in the form 1 l r w ($1 \le l \le r \le n$; $1 \le w \le 10^{9}$) or 2 x a ($1 \le x \le n$; $1 \le a \le 10^{9}$). It is guaranteed that all inserted numbers $w$ are different from each other.

For each operation of the second kind, output one line containing the cost as a single integer.