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 bli and numbers bi, 1, ..., bi, bli. All bi, 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 bi, j goes to position bi, j + 1 for 1 ≤ j < bli. The adornment from the position bi, bli goes to position bi, 1. Compound operation with number i is described as follows: numbers cli and cli of a couple of numbers coi, j and cci, j are selected. Each couple means to use the chain coi, j cci, 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 eli and eli couple of numbers eoi, j and eci, j. Each couple means to use the compound operation eoi, j eci, 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 bli, 1 ≤ bli ≤ N and different integers bi, 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 ≤ cli ≤ 100 — the number of used chains. Next cli lines include couples of integers coi, j and cci, j, 1 ≤ coi, jM, 1 ≤ cci, j ≤ 109. 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 ≤ eli ≤ 100 — the number of used compound operations. In the next eli lines there are integers eoi, j and eci, j, 1 ≤ eoi, jK, 1 ≤ eci, j ≤ 109. 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].
## Input
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 bli, 1 ≤ bli ≤ N and different integers bi, 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 ≤ cli ≤ 100 — the number of used chains. Next cli lines include couples of integers coi, j and cci, j, 1 ≤ coi, jM, 1 ≤ cci, j ≤ 109. 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 ≤ eli ≤ 100 — the number of used compound operations. In the next eli lines there are integers eoi, j and eci, j, 1 ≤ eoi, jK, 1 ≤ eci, j ≤ 109. The couples of numbers and their quantity are in separate lines.
## Output
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].
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of slots and adornments.
Let $ M \in \mathbb{Z}^+ $ be the number of base operations (chains).
For each $ i \in \{1, \dots, M\} $, let $ b_i \in \mathbb{Z}^+ $ denote the length of chain $ i $, and let $ \mathbf{c}_i = (c_{i,1}, c_{i,2}, \dots, c_{i,b_i}) $ be a cyclic permutation of distinct integers in $ \{1, \dots, N\} $, representing the chain: $ c_{i,j} \to c_{i,j+1} $ for $ 1 \leq j < b_i $, and $ c_{i,b_i} \to c_{i,1} $.
Let $ K \in \mathbb{Z}^+ $ be the number of compound operations.
For each $ i \in \{1, \dots, K\} $, let $ l_i \in \mathbb{Z}^+ $ denote the number of chains in compound operation $ i $, and let $ \mathbf{o}_i = ((o_{i,1}, t_{i,1}), \dots, (o_{i,l_i}, t_{i,l_i})) $ be a sequence of pairs where $ o_{i,j} \in \{1, \dots, M\} $ and $ t_{i,j} \in \mathbb{Z}^+ $, meaning compound operation $ i $ applies chain $ o_{i,j} $ exactly $ t_{i,j} $ times in sequence.
Let $ L \in \mathbb{Z}^+ $ be the number of experiments.
For each $ i \in \{1, \dots, L\} $, let $ e_i \in \mathbb{Z}^+ $ denote the number of compound operations in experiment $ i $, and let $ \mathbf{p}_i = ((p_{i,1}, s_{i,1}), \dots, (p_{i,e_i}, s_{i,e_i})) $ be a sequence of pairs where $ p_{i,j} \in \{1, \dots, K\} $ and $ s_{i,j} \in \mathbb{Z}^+ $, meaning experiment $ i $ applies compound operation $ p_{i,j} $ exactly $ s_{i,j} $ times in sequence.
Let $ \sigma_0 = \text{id} \in S_N $ be the initial permutation: $ \sigma_0(j) = j $ for all $ j \in \{1, \dots, N\} $.
**Constraints**
1. $ 1 \leq N \leq 100 $
2. $ 1 \leq M \leq 100 $, each chain $ \mathbf{c}_i $ is a cyclic permutation of distinct elements in $ \{1, \dots, N\} $
3. $ 1 \leq K \leq 100 $, each compound operation has $ 1 \leq l_i \leq 100 $, and $ 1 \leq t_{i,j} \leq 10^9 $
4. $ 1 \leq L \leq 100 $, each experiment has $ 1 \leq e_i \leq 100 $, and $ 1 \leq s_{i,j} \leq 10^9 $
**Objective**
For each experiment $ i \in \{1, \dots, L\} $, compute the final permutation $ \sigma_i \in S_N $ obtained by applying the sequence of compound operations as specified:
$$
\sigma_i = \prod_{j=1}^{e_i} \left( \prod_{k=1}^{l_{p_{i,j}}} \mathbf{c}_{o_{p_{i,j},k}}^{s_{i,j}} \right)
$$
where each $ \mathbf{c}_m $ is interpreted as a permutation, exponentiation denotes composition power, and multiplication denotes composition of permutations (right to left).
Output $ \sigma_i(1), \sigma_i(2), \dots, \sigma_i(N) $ for each experiment $ i $.