J. Characters Shift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$A$$$ consisting of $$$N$$$ positive integers where $$$1 \le A_i \le M$$$.

We define the shift operation as the following:

  • Let an integer $$$X$$$ be good if $$$X$$$ appears in $$$A$$$ at least once, and the number of occurrences of $$$X$$$ in the array is even (divisible by $$$2$$$).
  • Let $$$S$$$ be the set of indices $$$i$$$ where $$$A_i$$$ is good.
  • For each index $$$i$$$ in the set, you must change $$$A_i$$$ into $$$(A_i \bmod M) + 1$$$, where $$$\bmod$$$ is the modulo operation (remainder when divided by $$$M$$$).

You have to process $$$Q$$$ queries of two types:

  • $$$1$$$: perform the shift operation.
  • $$$2$$$ $$$i$$$: print the value of $$$A_i$$$.

Note that you have to answer $$$T$$$ testcases.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$) — representing the number of testcases.

The first line of each testcase contains three integers $$$N, M$$$ and $$$Q$$$ ($$$1 \le N, M, Q \le 10^5$$$) — representing the size of the array, the value of $$$M$$$, and the number of queries.

The second line of each testcase contains $$$n$$$ space separated integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le M$$$) — representing the elements of the array.

Each line of the next $$$Q$$$ lines has one of the following forms:

  • $$$1$$$: representing a shift query.
  • $$$2$$$ $$$i$$$: representing an ask query ($$$1 \le i \le N$$$).

It's guaranteed that the sum of $$$N$$$, the sum of $$$M$$$, and the sum of $$$Q$$$ over all testcases doesn't exceed $$$10^5$$$.

Output

For each query of the second type, print one line containing a single integer — the value of $$$A_i$$$.

Example
Input
1
3 4 4
4 4 3
1
2 2
1
2 1
Output
1
2