{"problem":{"name":"H. Polycarp and Chains","description":{"content":"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 com","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10083H"},"statements":[{"statement_type":"Markdown","content":"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.\n\nPolycarp 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.\n\nThe first line contains integer N, 1 ≤ N ≤ 100 — the number of slots and adornments. \n\nThe 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].\n\nThe 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.\n\nThe 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.\n\nOutput 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].\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput 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].\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of slots and adornments.  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of base operations (chains).  \nFor 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} $.  \n\nLet $ K \\in \\mathbb{Z}^+ $ be the number of compound operations.  \nFor 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.  \n\nLet $ L \\in \\mathbb{Z}^+ $ be the number of experiments.  \nFor 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.  \n\nLet $ \\sigma_0 = \\text{id} \\in S_N $ be the initial permutation: $ \\sigma_0(j) = j $ for all $ j \\in \\{1, \\dots, N\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 100 $  \n2. $ 1 \\leq M \\leq 100 $, each chain $ \\mathbf{c}_i $ is a cyclic permutation of distinct elements in $ \\{1, \\dots, N\\} $  \n3. $ 1 \\leq K \\leq 100 $, each compound operation has $ 1 \\leq l_i \\leq 100 $, and $ 1 \\leq t_{i,j} \\leq 10^9 $  \n4. $ 1 \\leq L \\leq 100 $, each experiment has $ 1 \\leq e_i \\leq 100 $, and $ 1 \\leq s_{i,j} \\leq 10^9 $  \n\n**Objective**  \nFor 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:  \n$$\n\\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)\n$$  \nwhere each $ \\mathbf{c}_m $ is interpreted as a permutation, exponentiation denotes composition power, and multiplication denotes composition of permutations (right to left).  \n\nOutput $ \\sigma_i(1), \\sigma_i(2), \\dots, \\sigma_i(N) $ for each experiment $ i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10083H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}