{"raw_statement":[{"iden":"statement","content":"Mislav and Marko have devised a new game, creatively named Rotate. First, Marko imagines a number sequence of length N and divides it into sections, with each section containing K numbers (K evenly divides N). The first section contains numbers in the first K positions in the sequence, the second section the following K positions, and so on.\n\nThen, Marko asks Mislav to apply a number of operations on the sequence, with each operation being one of the following two types:\n\nNotice that an operation of type 2 can change the numbers belonging to each section. After applying all the operations, Mislav reveals the final sequence to Marko. Marko's task is finding Mislav's starting sequence. He has asked you for help.\n\nThe first line of input contains three positive integers: N (1 ≤ N ≤ 105), the length of the sequence, K (1 ≤ K ≤ 105), the size of each section, and Q (1 ≤ Q ≤ 105), the number of operations.\n\nEach of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X ( - 105 ≤ X ≤ 105), the number of positions to rotate by. A negative number represents rotation to the left, while a positive one represents rotation to the right.\n\nThe last line of input contains N space-separated integers Zi (0 ≤ Zi ≤ 105) representing the final sequence (after applying all operations).\n\nThe first and only line of output must contain the required starting sequence.\n\nClarification of the first example: the starting sequence is _0 1 2 3_. After the first operation, the sequence is _2 3 0 1_, and after the second operation, it becomes _3 2 1 0_. Ths corresponds to the final sequence.\n\n"},{"iden":"input","content":"The first line of input contains three positive integers: N (1 ≤ N ≤ 105), the length of the sequence, K (1 ≤ K ≤ 105), the size of each section, and Q (1 ≤ Q ≤ 105), the number of operations.Each of the following Q lines contains two integers: A (1 ≤ A ≤ 2), the operation type, and X ( - 105 ≤ X ≤ 105), the number of positions to rotate by. A negative number represents rotation to the left, while a positive one represents rotation to the right.The last line of input contains N space-separated integers Zi (0 ≤ Zi ≤ 105) representing the final sequence (after applying all operations)."},{"iden":"output","content":"The first and only line of output must contain the required starting sequence."},{"iden":"examples","content":"Input4 2 22 21 13 2 1 0Output0 1 2 3 Input8 4 41 31 151 -52 -16 10 14 19 2 16 17 1Output6 10 14 1 2 16 17 19 Input9 3 51 12 -82 91 12 -43 1 8 7 4 5 2 6 9Output5 3 6 9 7 1 8 2 4 "},{"iden":"note","content":"Clarification of the first example: the starting sequence is _0 1 2 3_. After the first operation, the sequence is _2 3 0 1_, and after the second operation, it becomes _3 2 1 0_. Ths corresponds to the final sequence."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, K, Q \\in \\mathbb{Z}^+ $ with $ K \\mid N $.  \nLet $ Z = (z_1, z_2, \\dots, z_N) \\in \\mathbb{Z}^N $ be the final sequence.  \nLet the sequence be partitioned into $ m = \\frac{N}{K} $ contiguous sections $ S_1, S_2, \\dots, S_m $, where $ S_j = (a_{(j-1)K+1}, \\dots, a_{jK}) $.  \n\nEach operation is a **section-wise rotation**:  \n- Type 1: Rotate section $ \\left\\lceil \\frac{X}{K} \\right\\rceil $ by $ X \\mod K $ positions (right if positive, left if negative).  \n- Type 2: Rotate **all** sections **simultaneously** by $ X $ positions **cyclically** (i.e., shift section indices: section $ i $ moves to position $ i + X \\mod m $).  \n\nLet $ O = (o_1, \\dots, o_Q) $ be the sequence of operations, where each $ o_i = (A_i, X_i) $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $, $ 1 \\leq K \\leq 10^5 $, $ K \\mid N $, $ 1 \\leq Q \\leq 10^5 $  \n2. $ -10^5 \\leq X_i \\leq 10^5 $ for all $ i $  \n3. $ 0 \\leq z_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, N\\} $  \n\n**Objective**  \nRecover the initial sequence $ A = (a_1, \\dots, a_N) $ such that applying operations $ o_1, \\dots, o_Q $ in order yields $ Z $.  \n\nEquivalently, **invert** the composition of operations:  \nLet $ T = o_Q \\circ \\cdots \\circ o_1 $ be the total transformation.  \nThen $ A = T^{-1}(Z) $.  \n\nCompute $ A $ by applying the **inverse** of each operation in **reverse order**.","simple_statement":"You are given a sequence of N numbers divided into sections of size K.  \nQ operations are applied, each rotating the entire sequence left or right by X positions.  \nYou are given the final sequence after all operations.  \nFind the original sequence before any rotations.","has_page_source":false}