You are given a string S with length n. And it is guaranteed that Si ∈ [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)=SiSi+1...Sn.
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=cS1S2...Sn ). What is the rank of suf(T,i) among all the suf(T,k) (k∈[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=S1S2...Snc ). What is the rank of suf(T,i) among all the suf(T,k) (k∈[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≤T≤30) , the number of test cases.
For each test case, the first line gives three integers n, m and q (1≤n,m,q≤106). n is the length of string S, each character Si∈[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≤t≤2,1≤c≤m,1≤i≤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⊕last and i⊕last (⊕ denotes the exclusive or operation). For the first query , last=0.
It is guaranteed that both ∑n and ∑q don't exceed 3×106.
输出格式
For each test case, you should print q lines, each containing an integer, indicating the query answer.