이 문제는 기본적인 자료 구조인 이진 탐색 트리(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입니다.

BST에서 값 a를 찾는 구현

$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]$에 대해, $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$)이 주어지며, 이는 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