{"raw_statement":[{"iden":"statement","content":"Jeronimo the bear loves numbers and he is planning to write n numbers in his notebook.\n\nAfter writing the first m numbers, Jeronimo felt that he was spending a lot of time thinking new numbers, so he wrote the next n - m missing numbers as the sum modulo 3 × 107 of the numbers in the i - m and i - m + 1 positions for m < i ≤ n\n\nWhile Jeronimo was writing, his sister Lupe arrived and asked him q questions. The i - th question consist of a number bi, Jeronimo has to say what would be the number in the position bi if all the numbers were sorted in ascending order. Jeronimo wants to answer each question as soon as possible but he spends a lot of time counting so he ask your help.\n\nThe first line of the input has three integers n (3 ≤ n ≤ 3 × 107), m (3 ≤ m ≤ min(100, n)) and q (1 ≤ q ≤ 10000).\n\nThe second line contains m numbers a1, a2, ..., am, (0 ≤ ai < 3 × 107), The first m numbers that Jeronimo wrote.\n\nThe third line contains q questions b1, b2, ..., bq (1 ≤ bi ≤ n)\n\nPrint q lines. The i - th line must be the answer of the i - th question made by Lupe.\n\n"},{"iden":"input","content":"The first line of the input has three integers n (3 ≤ n ≤ 3 × 107), m (3 ≤ m ≤ min(100, n)) and q (1 ≤ q ≤ 10000).The second line contains m numbers a1, a2, ..., am, (0 ≤ ai < 3 × 107), The first m numbers that Jeronimo wrote.The third line contains q questions b1, b2, ..., bq (1 ≤ bi ≤ n)"},{"iden":"output","content":"Print q lines. The i - th line must be the answer of the i - th question made by Lupe."},{"iden":"examples","content":"Input6 3 61 2 31 2 3 4 5 6Output123356Input10 4 31 2 9 101 5 10Output11030"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 3 \\leq n \\leq 3 \\times 10^7 $, $ 3 \\leq m \\leq \\min(100, n) $, and $ 1 \\leq q \\leq 10^4 $.  \nLet $ A = (a_1, a_2, \\dots, a_m) $ be the initial sequence of $ m $ integers, where $ 0 \\leq a_i < 3 \\times 10^7 $.  \nDefine a sequence $ S = (s_1, s_2, \\dots, s_n) $ as follows:  \n- $ s_i = a_i $ for $ 1 \\leq i \\leq m $,  \n- $ s_i = (s_{i-m} + s_{i-m+1}) \\mod (3 \\times 10^7) $ for $ m < i \\leq n $.  \n\nLet $ B = (b_1, b_2, \\dots, b_q) $ be a sequence of query indices, where $ 1 \\leq b_j \\leq n $.\n\n**Constraints**  \n1. $ 3 \\leq n \\leq 3 \\times 10^7 $  \n2. $ 3 \\leq m \\leq \\min(100, n) $  \n3. $ 1 \\leq q \\leq 10^4 $  \n4. $ 0 \\leq a_i < 3 \\times 10^7 $ for all $ i \\in \\{1, \\dots, m\\} $  \n5. $ 1 \\leq b_j \\leq n $ for all $ j \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFor each query $ b_j $, compute the value of the $ b_j $-th smallest element in the sorted sequence $ S $.  \nThat is, let $ S_{\\text{sorted}} $ be the sequence $ S $ sorted in non-decreasing order. Output $ S_{\\text{sorted}}[b_j] $ for each $ j \\in \\{1, \\dots, q\\} $.","simple_statement":"Jeronimo writes n numbers. The first m are given. For positions m+1 to n, each number is the sum of the two numbers m and m-1 positions back, modulo 3×10⁷.  \nLupe asks q questions: for each query bi, find the bi-th smallest number in the full list of n numbers.  \nPrint the answer for each query.","has_page_source":false}