문제

박정희 교수님의 자료구조 수업에서 서현이는 AVL 트리를 배웠다. AVL 트리는 균형 이진 탐색 트리의 하나로 $O(\log{N})$ 시간 내에 원소를 추가, 제거, 조회할 수 있는 자료구조다. 균형 이진 탐색 트리는 AVL 트리 말고도, 스플레이 트리나 트립(Treap), 레드-블랙 트리, Weight-Balanced 트리 등등 다양하다.

이때, 균형 이진 탐색 트리의 키(key) 대신에 해당 노드의 왼쪽 노드 서브 트리 크기로 키를 암시적으로 생성하면 $O(\log{N})$ 시간 내에 원소 추가, 제거, 조회 등이 가능한 동적 배열로 다룰 수 있다. 알고리즘 문제 해결에서는 이쪽을 더 많이 쓴다.

길이가 $0$인 배열이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• 1 i x: 배열의 $i$번째 원소 앞에 값이 $x$인 원소를 하나 추가한다. 만약 $i=\text{현재 배열의 길이}+1$라면 배열의 맨 뒤에 추가하는 것이다.
• 2 j: 배열의 $j$번째 원소를 배열에서 제거한다.
• 3 l r: 현재 배열의 $l$번째 원소부터 $r$번째 원소까지 뒤집는다. 즉, 원래 배열이 $A_1, \cdots, A_{l-1}, A_l, A_{l+1}, \cdots, A_{r-1}, A_r, A_{r+1} \cdots, A_N$이었다면 $A_1, \cdots, A_{l-1}, A_r, A_{r-1}, \cdots, A_{l+1}, A_l, A_{r+1}, \cdots, A_N$이 되는 것이다.
• 4 i x: $A_i = x$를 적용한다.
• 5 l r: $A_l + A_{l+1} + \cdots + A_r$을 출력한다.

배열의 인덱스는 $1$부터 시작한다.

입력

첫째 줄에 $Q$가 주어진다. ($1\le Q\le 300\,000$)

둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 쿼리가 주어진다.

배열의 길이가 $0$인 상태에서는 1번 쿼리만 주어짐이 보장된다.

$1\le i\le \text{현재 배열의 길이} + 1$

$1\le j\le \text{현재 배열의 길이}$

$1\le l\le r\le \text{현재 배열의 길이}$

$-10^9\le x\le 10^9$

출력

5번 쿼리의 답을 한 줄에 하나씩 출력한다.

예제 입력 1

9
1 1 2
1 1 1
1 3 3
5 1 3
4 3 5
3 1 3
5 1 2
2 2
5 1 2

예제 출력 1

6
7
6