Fxx and factory

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。

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>

Print a response for each query in a separate line.

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

8
20
32
72

BestCoder Round #89