Description

Once there were $n$ fleas standing in a line doing morning exercises. Each flea has its own jumping power $a_i$. The Flea King was very pleased to see their prosperity. He then decided to have some rational fun by querying the range $k$-th smallest. Each time, he asked his servant Volter the following: among the fleas from the $x$-th to the $y$-th from left to right, what is the $k$-th smallest value of $a_i$?

This did not stump Volter. He used a persistent segment tree with prefix sums in his head to deal with the king’s queries.

Then Volter noticed that some fleas’ jumping power would change over time, some increasing and some decreasing.

This still did not stump Volter. He used a Binary Indexed Tree wrapped around segment trees in his head to handle the king’s queries. (orz “Chairman Tree”)

However, Volter then found that some late fleas would be inserted at some position in the line. He became very upset because... he could not do it.

Please help Volter.

Quick version of the statement: online queries for the range $k$-th smallest with insertions and modifications.

Input Format

The first line contains a positive integer $n$, the initial number of fleas in a line.

The second line contains $n$ non-negative integers separated by spaces, representing each flea’s jumping power from left to right.

The third line contains a positive integer $q$, the number of operations.

Then follow $q$ lines, each being one of three operations on the current sequence (suppose there are currently $m$ fleas):

1. Q x y k: Query the $k$-th smallest jumping power among the fleas from the $x$-th to the $y$-th from left to right. ($1 \le x \le y \le m, 1 \le k \le y - x + 1$)
2. M x val: Set the jumping power of the $x$-th flea from left to right to $\textit{val}$. ($1 \le x \le m$)
3. I x val: Insert a flea with jumping power $\textit{val}$ in front of the $x$-th flea from left to right. After insertion, the $x$-th flea from left to right is the newly inserted one. ($1 \le x \le m + 1$)

To enforce online operations, let $\textit{lastans}$ be the result output by the program in the most recent query; if there has been no query yet, then $\textit{lastans} = 0$.

Then the actual inputs are:

• Q _x _y _k: represents Q _x^lastans _y^lastans _k^lastans
• M _x _val: represents M _x^lastans _val^lastans
• I _x _val: represents I _x^lastans _val^lastans

In short, every integer in the operations must be XORed with the previous query’s result to decode.

(Wish the classmates using Pascal switch to C++ soon, so no Pascal version of the statement is provided.)

Output Format

For each query, output the answer, one per line.

10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

28
2
31
0
14
15
14
27
15
14

Hint

Constraints:

• $n \le 35000$.
• Number of insertions $\le 35000$, number of modifications $\le 70000$, number of queries $\le 70000$, and $0 \le$ every value at any time $\le 70000$.

The testdata has no gradient.

Translated by ChatGPT 5