Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 3563
Alice's Sequence II

Time Limit: 5 Seconds      Memory Limit: 65536 KB

Alice loves play with the math, though she always doesn't know how to solve her own problems.

Alice writes down a sequence(called a) of N integers on the blackboard, indexing from 1 to N, then she wants to do some operations on this sequence. She defines four types of operations.

1. remove i: ai=0
2. double i: ai=2* ai
3. add i j: ai= ai + aj
4. swap i j: swap the number of ai , aj
5. invert i j: invert the sequence from index i to index j (i ≤ j), for example, a = 1,2,3,4,5,6, after operation "invert 1 6", a will turn into sequence of 6,5,4,3,2,1
6. transform c i d j: ai = c*ai + d*aj and aj = 0

Alice will give out a operation sequence S with M operations, naming from 1 to M, you need to make P steps on this operation set S. You must make the operation S one by one, and if you reach the Mth operation, you should make the operation on the 1st operation in your next step. For example, if the size of S is 5, and we need to make 8 steps, we make operation S1, S2, ..., S5, S1, S2 and S3. Alice wonders what would happen after all of P steps.

For the "double", "add" and "transform" operations would lead the value of sequence become too large to express, so, you just need to output the sequence by mod 10000007 to each element.

Input

There are multiple cases. In each case, it contains an integer N (1≤ N ≤25) in the first line. The following line contains N integers representing the initial value of sequence of a. All of the initial value of sequence of a is a non-negative number and less than 100.

Then it comes an integer M (1 ≤ M ≤ 10) in one line, th following M lines contain M operations on each line. The operation is claimed above. The format is "name_of_operation parameters", name_of_operation can be "remove", "double", "add", "swap", "invert", "transform". And the parameters is a list of parameter which has different length according to the description above. Specially, the integer c and the integer d are non-negative and less than 100.

Finally, the input contains an integer P (1≤ P ≤ 109) in one line, which means the total steps you need to make.

Ouptut

For each case, you should output the result of sequence a after P steps.

Sample Input

```10
1 2 3 4 5 6 7 8 9 10
6
transform 1 2 3 4
remove 1
swap 2 3
```0 6 5 0 14 12 7 8 18 10