The problem background is irrelevant to the problem statement and can be skipped.

1. Foreword:

The Brodal queue was proposed by Brodal in 1996. It is the first data structure that satisfies the worst-case time complexity for every operation while reaching the lower bound for comparison-based heaps.

The Brodal queue presented here is a min-heap.

Some characteristics of this data structure: 1. It maintains two trees. 2. The Brodal queue is a violation heap, meaning it allows some nodes to violate the heap property. 3. The implementation is truly complex, and the constant factors are quite large.

2. Notation:

The Brodal queue maintains two trees $T1$ and $T2$, with roots $t1$ and $t2$.

Definitions: $p(x)$: The parent node of $x$, assuming $x \neq t1$ and $x \neq t2$. $rank(x)$: A weight related to $\log( \text{subtree size} )$. $n(x,i)$: The number of children of $x$ that have a $rank$ of $i$. $w(x,i)$: The number of elements in $W(x)$ with $rank$ equal to $i$. $V$ and $W$ lists: Maintain all nodes that violate the heap property.

3. Overview:

Every node that has served as the root of $T1$ maintains $V$ and $W$. We denote $V(x)$ as the set $V$ of node $x$, and $W(x)$ as the set $W$ of node $x$.

$V$ maintains nodes with $rank \ge rank(t1)$, while $W$ maintains nodes with $rank < rank(t1)$. This holds true at the time of insertion, meaning it is not necessarily maintained after structural modification operations.

$V$ is append-only, while $W$ requires maintenance for balance; thus, we only need to ensure that for nodes in $W$ of $t1$, their $rank < rank(t1)$.

The following properties hold:

$rank$ properties: S1. The $rank$ of a leaf node is $0$. S2. $rank(x) < rank( p(x) )$. S3. If $rank(x) > 0$, then $n(x,rank(x)-1) \ge 2$. S4. $n(x,i)$ can only be an element of $\{0, 2, 3, 4, 5, 6, 7\}$. S5. When $T2 \neq \text{null}$, $rank(t1) \leq rank(t2)$.

Explanation: S1. Boundary definition. S2. $rank$ forms a max-heap. S3. A node has at least two children with $rank-1$, so the subtree size of $x$ is at least exponential with respect to $rank(x)$, meaning $rank$ is at most $O( \log n )$. S4. $n(x,i)$ has an $O(1)$ upper bound (excluding 1), and there are $O( \log n )$ possible $rank$ values, so the degree of each node is $O(\log n)$. S5. Either $T1$ is smaller than $T2$, or $T2$ is empty.

$V$ and $W$ list properties: O1. $t1$ is the minimum element among all elements. O2. If $y \in V(x)$ or $y \in W(x)$, then $x \leq y$, meaning this element violated the heap property when it was inserted into the list. O3. If $y < p(y)$, then there exists an $x$ such that $x \neq y$ and $y \in V(x)$ or $y \in W(x)$, meaning all nodes violating the heap property are in some node's $V$ or $W$ list. O4. For all $x$, $w(x,i) \leq 6$. O5. Let $V(x) = (y_{|V(x)|}, \dots, y_2, y_1)$, then $rank(y_i) \ge \lfloor (i-1)/\alpha \rfloor$, where $\alpha$ is a constant.

Explanation: O1. We need to find the minimum in $O(1)$, so $t1$ is defined as the minimum. O2. When $x$ is inserted, it is inserted into $V(t1)$ or $W(t1)$. O3. Nodes violating the heap property must be in another node's $V$ or $W$ set. O4. $w(x,i)$ has a constant upper bound, so the sizes of $V$ and $W$ lists are $O( \log n )$. O5. The $rank$ values in the $V$ list have a stepped lower bound.

Additional properties for $t1$ and $t2$: R1. For $i = 0 \sim rank(tj) - 1$, $n(tj,i) \ne 0$. R2. $|V(t1)| \leq \alpha \times rank(t1)$, where $\alpha$ is the same constant as before. R3. If $y \in W(t1)$, then $rank(y) < rank(t1)$.

Explanation: R1. For $t1$ and $t2$, there are at least 2 children for each $rank$. R2. The size of $V(t1)$ is bounded by $\alpha \times rank(t1)$. R3. Nodes in $W(t1)$ are smaller than $t1$.

R2 + O5 implies that if $rank(t1)$ increases by 1, we can add $\alpha$ large nodes that violate the heap property to $V(t1)$ without violating O5.

Every time DECREASEKEY is called, we directly add a new node that violates the heap property to $V(t1)$ or $W(t1)$.

To avoid having too many nodes violating the heap property, we incrementally perform two different transformations, primarily to maintain R2 and O4.

Type 1: Move children of $t2$ into $T1$ to become children of $t1$, causing $rank(t1)$ to increase. Type 2: Reduce the size of $W(t1)$ by replacing 2 nodes of $rank$ $k$ that violate the heap property with $\leq 1$ node of $rank$ $k+1$ that violates the heap property.

Note: We use many variable-length arrays here; we assume variable-length arrays are strictly $O(1)$, which is trivial and will not be detailed.

Here, we provide an implementation of a data structure the author calls a "guide".

4. Guide Data Structure:

Purpose: Maintain R1 and O4 properties, i.e., maintain upper bounds for $n(t1,i), n(t2,i), w(t1,i)$, which is essentially maintaining an $O(1)$ carry.

Abstracting what this guide data structure maintains: Maintenance: An int array of length $k$, $x_k, x_{k-1}, \dots, x_1$ (written from right to left). Requirement: $\max(x_i) \leq T$, where $T$ is a preset threshold constant.

We can only perform the REDUCE(i) operation on this array, where $x_i$ decreases by at least 2, and $x_{i+1}$ increases by at most 1 (in practice, $x_i$ can only decrease by 2 or 3, and $x_{i+1}$ can only increase by 0 or 1).

Each time an $+1$ or $-1$ operation occurs on $x_i$ at an arbitrary position $i$, we are allowed to perform $O(1)$ REDUCE operations to ensure the array still satisfies the properties.

The guide tells us what REDUCE operations to perform to keep the array valid.

Define $x'$ as $[T-2, T]$. We do not consider adjustments until $x_i$ enters the range $x'$. Let $T=2$, and we maintain this guide for $T=2$.

Divide the original sequence into blocks, considering continuous segments like $2, 1^*, 0$. Elements not in a segment can only be isolated $0$ or $1$. Create a new node for each block, and each element in the segment points to this node. Each node records the starting position of the block. Nodes not in a block point directly to null. Multiple points share a null, and multiple nulls exist.

Two important properties: 1. Given a position $x$, we can find the leftmost element in the block containing $x$ in $O(1)$ worst-case time. 2. We can destroy a given block in $O(1)$ worst-case time by changing the point storing the value to null.

The transformations are implemented as follows (based on personal understanding, so they may differ from the original paper):

Note that we can dismantle a block in $O(1)$.

Predecessor not in a block:

case1:
0 0
0 1
trivial

case2:
0 1
0 2
1 1
trivial

case3:
0 [2 1* 0]
0 [3 1* 0]
1 [1 1* 0]
Dismantle this block
1 1 1* 0

case4:
1 0
1 1
trivial

case5:
1 1
1 2
[2 0]
trivial

case6:
1 [2 1* 0]
1 [3 1* 0]
2 [1 1* 0]
[2 1 1* 0]

Predecessor is the end of a block:

case7:
[2 1* 0] 0
[2 1* 0] 1
trivial

case8:
[2 1* 0] 1
[2 1* 0] 2
[2 1* 1] 0
[2 1* 1 0]

case9:
[2 1* 0] [2 1* 0]
[2 1* 0] [3 1* 0]
[2 1* 1] [1 1* 0]
Dismantle the latter block
[2 1* 1] 1 1* 0
Dismantle the former block
2 1* 1 1 1* 0
Recurse into the case of 1 plus 1 outside a block (case 2, 5, 8)

Predecessor is in a block:

case10:
[2 1* 0]
[2 1* 1]
Dismantle block
2 1* 1
Recurse into the case of 1 plus 1 outside a block (case 2, 5, 8)

case11:
[2 1* 1 1* 0]
[2 1* 2 1* 0]
Dismantle part of the block by pointing to the second 2
2 1* [2 1* 0]
Recurse into the case of 1 plus 1 outside a block (case 2, 5, 8)

Note that $2$ moves monotonically to the right, except that each operation might allow it to move one step to the left, so moving a block endpoint to the right or moving it $O(1)$ positions to the left is feasible.

Using a memory pool, the space required does not exceed $O(k)$.

5. Link and Delink

These are two basic operations used to adjust the Brodal queue.

Link: Suppose we have 3 nodes $x_1, x_2, x_3$ that are not roots and have the same $rank$. After $O(1)$ comparisons, assume $x_1$ is the smallest. We can make $x_2$ and $x_3$ the leftmost children of $x_1$ (since it's a linked list, we can only insert at the head), and increment $x_1$'s $rank$ by 1. Then $x_2$ and $x_3$ are no longer nodes violating the heap property, and $x_1$ still satisfies all S1-S5 and O1-O5 properties.

Delink: For a node $x$, if $n(x, rank(x)-1)$ is 2 or 3, disconnect the edge between $x$ and its child of $rank(x)-1$, "cutting it out". Then $rank(x)$ becomes $\max(rank) + 1$ of the remaining children. Special instructions are needed for what to do after cutting it out. If $n(x, rank(x)-1) \ge 4$, cut out 2 children of $rank(x)-1$. Delinking a tree of $rank$ $k$ from a root always results in 2 or 3 trees of $rank$ $k-1$ rooted at the root, and an additional tree of $rank \leq k$ rooted at the root (the $rank$ of this tree's root can be any value in $[0, k]$).

Consider how to maintain the children of $t1$ to satisfy R1 (for each $rank$ in $[0, rank(t1)-1]$, $t1$ has $[2, 7]$ children). For the number of children of each $rank$ in $[0, rank(t1)-3]$, use two guides: one handles children in $[2, 4]$ to ensure the count $\ge 2$, and one handles children in $[5, 7]$ to ensure the count $\leq 7$. Children of $rank(t1)-1$ and $rank(t1)-2$ require special handling.

Maintain the children of $t1$ using two guides, guide1 and guide2. guide1 maintains children with $rank$ in $[T-2, T]$, and guide2 maintains children with $rank$ in $[2, 4]$. Here, we set $T=9$, a constant. We use the element $a_k$ in the guide to refer to the number of nodes of $rank$ $k$ in this guide. The link operation reduces an element $a_k$ in guide1 by 3 and increases $a_{k+1}$ by 1. Note that we are maintaining an upper bound, so reducing by 3 is similar to reducing by 2. The delink operation reduces an element $a_k$ in guide2 by 1 and increases $a_{k-1}$ by 2 or 3, and also produces an extra element of $rank$ in $[0, k]$. Since we are maintaining a lower bound, we only need to consider $+2$.

Note: $T=9$ is used here instead of the $T=7$ from the original paper, as $T=9$ is easier to implement.

$t1$ adding a child: If the number of children of the same $rank$ becomes 9, use the guide handling the upper bound to perform $O(1)$ REDUCE operations, corresponding to using link to merge 3 children of $rank$ $k$ into 1 child of $rank$ $k+1$. Note that after reducing by 3, the count becomes $6 > 4$, which does not affect the guide handling the lower bound. If this causes too many children of $rank(t1)-2$ or $rank(t1)-1$, use link to adjust, which might require increasing $rank(t1)$.

$t1$ deleting a child: Similar to adding, but REDUCE corresponds to delink.

6. Abstract Data Structure

For an abstract data structure—a priority queue—we can implement it using a Brodal queue:

MakeQueue: T1=T2=null
FindMin(Q): return t1
Insert(Q,e): Meld(Q,{T1=e,T2=null})
Meld(Q1,Q2):
Assume Q1.t1 < Q2.t1.
If Q1.T1 has the largest rank, insert the other 3 trees as children of Q1.t1, set Q1.T2 to null.
Otherwise, let the tree with the largest rank among Q1.T2 and Q2.T2 be the new Q1.T2, and insert the other 2 trees as children of Q1.t2.
DecreaseKey(Q,e,e'):
Check if the heap property is violated after modifying the value.
If violated, add to pv, then balance pv size.
DeleteMin(Q):
Cut all children of t2 (O(log n)) and add as children of t1; add t2 as a child of t1.
Delete t1 to get its children (O(log n)).
Traverse children of t1, V(t1), and W(t1) to find the new minimum t1'.
If t1' is not a child of t1, swap with a child of equal rank.
Merge V(t1), V(t1'), W(t1), W(t1') into W(t1').
Delete(Q,e): DecreaseKey(Q,e,-inf), DeleteMin(Q)

Given a sequence $a$ of length $n$, where each position has a color, perform $m$ operations: 1. 1 l r x: Change all numbers in the range $[l, r]$ to $x$. 2. 2 l r: Query the number of pairs $(i, j)$ such that $l \leq i < j \leq r$ and $a_i = a_j$.

This problem is online. Each $l, r, x$ must be XORed with the previous answer (modulo $2^{32}$). Use unsigned int to store the previous answer. If there was no previous query, the answer is 0. The output answer is not taken modulo $2^{32}$.

Input

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence $a$. The following $m$ lines each contain an operation 1 l r x or 2 l r.

Output

For each 2 operation, output one integer per line.

Examples

Input 1

10 12
6 9 9 4 7 8 10 4 9 2
2 1 4
1 0 5 0
2 3 6
2 10 9
1 7 9 2
2 7 9
1 2 7 1
1 2 11 4
2 6 10
1 3 12 0
1 14 14 15
2 7 12

Output 1

1
3
0
3
6
16

Subtasks

Note: This problem uses bundled testing. You only receive points for a subtask if you pass all test cases within that subtask.

• 1% of data: Example 1.
• 9% of data: No modification operations.
• 19% of data: $n, m \leq 500$.
• 19% of data: Each modification range length $\leq 5$.
• 19% of data: Data is random.
• 100% of data: $1 \leq n, m \leq 2 \times 10^5$, $1 \leq a_i, x \leq n$, $1 \leq l \leq r \leq n$.