6815：Funny String

You are given a string $S$ with length $n$. And it is guaranteed that $S_i$ $\in$ $[1,m]$ for $i$ from $1$ to $n$.

Denote $suf(S,i)$ as the suffix of $S$ with length $n-i+1$. In other words,$suf(S,i)=S_iS_{i+1}...S_n$.

Each time you will be asked one of the following questions:

1.Given a character $c$ and an integer $i$. Then you will obtain a new string $T$ by inserting the character $c$ to the front of $S$ (namely $T=cS_1S_2...S_n$ ). What is the rank of $suf(T,i)$ among all the $suf(T,k)$ ($k\in[1,n+1]$) in lexicographical order.

2.Given a character $c$ and an integer $i$. Then you will obtain a new string $T$ by inserting the character $c$ to the back of $S$ (namely $T=S_1S_2...S_nc$ ). What is the rank of $suf(T,i)$ among all the $suf(T,k)$ ($k\in[1,n+1]$) in lexicographical order.

Notice, we just want to find the answer of each question and won't really add the character $c$ to the string $S$. In other words, each question is independent.

The first line contains a single integer $T(1 \leq T \leq 30)$ , the number of test cases.

For each test case, the first line gives three integers $n$, $m$ and $q$ ($1 \leq n,m,q \leq 10^6$). $n$ is the length of string $S$, each character $S_i$ $\in$ $[1,m]$ and $q$ is the number of questions.

The next line gives the string $S$ that consists of $n$ positive integers which are in $[1,m]$.

Each of the following $q$ lines consists of three integers $t,c,i(1 \leq t \leq 2,1 \leq c \leq m,1 \leq i \leq n+1)$, representing the type of this question is $1$ if $t=1$ and $2$ if $t=2$.

Note that $c$ and $i$ is encrypted. Assuming $last$ is the previous query answer, the actual values of $c$ and $i$ are $c \oplus last$ and $i \oplus last$ ($\oplus$ denotes the exclusive or operation). For the first query , $last = 0$.

It is guaranteed that both $\sum$ $n$ and $\sum$ $q$ don't exceed $3 \times 10^6$.

For each test case, you should print $q$ lines, each containing an integer, indicating the query answer.