A permutation of the set { 1, 2, … , *n*}
is a way to sort those numbers.
For instance, [123], [132], [213], [231], [312], and [321]
are the 6 possible permutations for *n* = 3.

An alternative way to describe a permutation is giving its cycles. For instance, the permutation [6351274] can be written (1 6 7 4) (2 3 5). This is, to the position 1 goes the 6, to the position 6 goes the 7, to the position 7 goes the 4, to the position 4 goes the 1 (first cycle), to the position 2 goes the 3, to the position 3 goes the 5, and to the position 5 goes the 2 (second cycle). Notice that there are various ways to describe a permutation using cycles. For instance, the last permutation can be written also as (3 5 2) (6 7 4 1).

As can be seen on the right, the same permutation can be applied repeatedly. Thus, applying twice [6351274] [7526341] = (7 1) (6 4) (5 3 2) is obtained.

After three times we have [4237516] = (4 7 6 1) (2) (3) (5), and after 4 times [1364267] = (1) (4) (6) (7) (3 5 2). It is easy to see than after 12 times [1234567] = (1) (2) (3) (4) (5) (6) (7) would be obtained.

Your task is to write a program that, for each given permutation, prints the result to apply it a certain number of times.

**Input**

The input consists of a sequence of cases.
Each case starts with a line with *n*, *c*, and *m*
(respectively, the number of elements of the permutation,
its number of cycles, and the number of tests).
*c* lines follow, one per cycle.
Each cycle follows exactly the format of the instances.
Then, *m* lines come, each one with *k*
(the number of times that the permutation must be applied).
You can assume 1 ≤ *n* ≤ 10000,
1 ≤ *c* ≤ *n*,
*m* ≥ 1,
and *k* ≥ 1.

**Output**

For each case of the input,
your program must print the permutation obtained
after applying *k* times the given permutation.
It must print a line in white in the end of the answers for each case.
Follow the format of the instances.

**(25 points)****(20 points)**Some test cases will exclusively contain cases like the ones in the instance of input 2, in which all the*k*≤ 100.**(55 points)**Other test cases will contain cases of every kind, in which*k*≤ 10^{9}.

**Scoring**

**TestA:****25 Points**Some test cases will exclusively contain cases like the ones in the instances of input 1, in which all the

*k*are 1.

**TestB:****20 Points**Some test cases will exclusively contain cases like the ones in the instance of input 2, in which all the

*k*≤ 100.

**TestC:****55 Points**Other test cases will contain cases of every kind, in which

*k*≤ 10^{9}.

Public test cases

**Input**

7 2 3 (1 6 7 4) (2 3 5) 1 1 1 4 4 1 (1) (4) (2) (3) 1

**Output**

6 3 5 1 2 7 4 6 3 5 1 2 7 4 6 3 5 1 2 7 4 1 2 3 4

**Input**

7 2 8 (1 6 7 4) (2 3 5) 1 2 3 4 12 16 20 24 4 1 3 (2 3 4 1) 1 2 100

**Output**

6 3 5 1 2 7 4 7 5 2 6 3 4 1 4 2 3 7 5 1 6 1 3 5 4 2 6 7 1 2 3 4 5 6 7 1 3 5 4 2 6 7 1 5 2 4 3 6 7 1 2 3 4 5 6 7 2 3 4 1 3 4 1 2 1 2 3 4

**Input**

7 2 1 (3 5 2) (6 7 4 1) 1000000000

**Output**

1 3 5 4 2 6 7

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++