Permutaciones P90339

Statement

Una permutación del conjunto $\{ 1, 2, \dots , n\}$ es una manera de ordenar esos números. Por ejemplo, [123], [132], [213], [231], [312], y [321] son las 6 posibles permutaciones para $n = 3$ .

Un modo alternativo de describir una permutación es dando sus ciclos. Por ejemplo, la permutación [6351274] se puede escribir (1 6 7 4) (2 3 5). Ésto es, a la posición 1 va el 6, a la posición 6 va el 7, a la posición 7 va el 4, a la posición 4 va el 1 (primer ciclo), a la posición 2 va el 3, a la posición 3 va el 5, y a la posición 5 va el 2 (segundo ciclo). Nótese que hay varias maneras de describir una permutación mediante ciclos. Por ejemplo, la última permutación también se puede escribir como (3 5 2) (6 7 4 1).

Como se puede ver a, una misma permutación se puede aplicar repetidamente. Así, aplicando 2 veces [6351274] se obtiene [7526341] $=$ (7 1) (6 4) (5 3 2).

Después de 3 veces se tiene [4237516] $=$ (4 7 6 1) (2) (3) (5), y después de 4 veces [1364267] $=$ (1) (4) (6) (7) (3 5 2). Es fácil ver que después de 12 veces se obtendría [1234567] $=$ (1) (2) (3) (4) (5) (6) (7).

Hacer un programa que, para cada permutación dada, escriba el resultado de aplicarla un cierto número de veces.

Entrada

La entrada consiste en una secuencia de casos. Cada caso empieza con una línea con $n$ , $c$ , y $m$ (respectivamente, el número de elementos de la permutación, su número de ciclos, y el número de pruebas). Siguen $c$ líneas, una por ciclo. Cada ciclo sigue exactamente el formato de los ejemplos. A continuación vienen $m$ líneas, cada una con $k$ (el número de veces que se tiene que aplicar la permutación). Podeis asumir $1 \le n \le 10000$ , $1 \le c \le n$ , $m \ge 1$ , y $k \ge 1$ .

Salida

Para cada caso de la entrada, hay que escribir la permutación que se obtiene después de aplicar $k$ veces la permutación dada. Escribir una línea en blanco al final de las respuestas para cada caso. Seguir el formato de los ejemplos.

Puntuación

TestA:

Algunos juegos de pruebas contendrán exclusivamente casos como los del ejemplo de entrada 1, en los que todas las $k$ son 1.

TestB:

Algunos juegos de pruebas contendrán exclusivamente casos como los del ejemplo de entrada 2, en los que $k \le 100$ .

TestC:

Otros juegos de pruebas contendrán casos de todo tipo, en los que $k \le 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

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

Output

1 3 5 4 2 6 7

Information

Author: Omer Giménez
Language: Spanish
Other languages: English
Official solutions: C++
User solutions: C++