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

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

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 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>

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>

提交代码