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.
This problem does not support hack.
Output
Print a response for each query in a separate line.
