Fxx and factory

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 65536/131072 K (Java/Others)

Description

Young theoretical computer scientist Fxx goes to a factory.

In the factory,there are $n$ receiving barrel in a row from left to right.The plan has m operations,and each operation has to be one of the following three ways

$(1,x,y)\:$:put $y$ products into $x\:$th barrel(counted from left to right).

$(2,x)\:$:Take out all the products in the $x$th barrel(counted from left to right).

$(3,x,y)\:$ Swap the $x$th barrel and $y$th barrel(counted from left to right)

Then the factory will continue to repeat the $m$ operations in turn,and give $Q$ queries,each query will give an integer $k$, asking after $mk$ operations(repeat the $m$ operations $k$ times),the maximum number of products in the $n$ barrel。

Input

In the first line, there is an integer $T(T\leq 5)$ indicating the number of test cases.

For each case, the first line contains three integers $n,m,Q(n\leq1000,m\leq10^5,Q\leq3\times10^5)$

In the next $m$ lines,each line contains an operation.

In the next $Q$ lines,each line contains an integer $k(k\leq10^9)$ indicating an query.

We guarantee that each answer is no more than $10^{18}$.

We guarantee that the number of operation $2$ is no more than 100, under this condition, all other operations are randomly.

<b>This problem does not support hack.</b>

Output

Print a response for each query in a separate line.

Sample Input

1 3 6 4 1 2 7 1 1 8 3 1 3 1 1 4 2 2 1 2 2 1 3 5 12

Sample Output

8 20 32 72

Hint

wange2014

Source

BestCoder Round #89

提交代码