Permutations P90339


Statement
 

pdf   zip

thehtml

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 ≤ cn, 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.

Score

  • (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 ≤ 109.

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 ≤ 109.

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