402659: GYM100834 H Polycarp and Chains

Polycarp has got a set of N slots, there is one adornment in each slot. Each adornment has got a peculiar number — integer within the interval [1... N]. Polycarp has also got a set of M base and K compound operations. Base operations are called chains. Each chain with the number i is set by the number bl_i and numbers b_i, 1, ..., b_i, bli. All b_i, j numbers are integers, they are different for each chain and belong to the interval [1... N]. It means the following: the adornment from the position b_i, j goes to position b_{i, j + 1} for 1 ≤ j < bl_i. The adornment from the position b_i, bli goes to position b_i, 1. Compound operation with number i is described as follows: numbers cl_i and cl_i of a couple of numbers co_i, j and cc_i, j are selected. Each couple means to use the chain co_i, j cc_i, j times.

Polycarp carries out experiments with this set. Before starting each experiment the i-th adornment is placed into slot i. The experiment i is described by el_i and el_i couple of numbers eo_i, j and ec_i, j. Each couple means to use the compound operation eo_i, j ec_i, j times. Polycarp is eager to know what there will be in each slot after the recurrent experiment is carried out.

The first line contains integer N, 1 ≤ N ≤ 100 — the number of slots and adornments.

The second line contains integer M, 1 ≤ M ≤ 100 — the number of chains. The descriptions of the chains are in the next M lines. The chain is described by bl_i, 1 ≤ bl_i ≤ N and different integers b_i, j within the interval [1... N].

The next line contains integer K, 1 ≤ K ≤ 100 — the number of compound operations. Their descriptions are in the next lines. Each compound operation is defined by the number 1 ≤ cl_i ≤ 100 — the number of used chains. Next cl_i lines include couples of integers co_i, j and cc_i, j, 1 ≤ co_i, jM, 1 ≤ cc_i, j ≤ 10⁹. The couples of integers and their quantity are in the separate lines.

The integer L, 1 ≤ L ≤ 100 is in the next line — the number of experiments. The next lines include their descriptions. Each experiment is defined by the integer 1 ≤ el_i ≤ 100 — the number of used compound operations. In the next el_i lines there are integers eo_i, j and ec_i, j, 1 ≤ eo_i, jK, 1 ≤ ec_i, j ≤ 10⁹. The couples of numbers and their quantity are in separate lines.

Output N numbers in a separate line for each experiment — which number of adornment is situated in the slot i for all integers i within the interval [1... N].

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

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