{"raw_statement":[{"iden":"statement","content":"During tea-drinking, Princess, amongst other things, asked why has such a good-natured and cute Dragon imprisoned Prince in the Castle? Dragon smiled enigmatically and answered that it is a big secret. After a pause, Dragon added:\n\n— We have a contract. A rental agreement. He always works all day long. He likes silence. Besides that, there are many more advantages of living here in the Castle. Say, it is easy to justify a missed call: a phone ring can't reach the other side of the Castle from where the phone has been left. So, the imprisonment is just a tale. Actually, he thinks about everything. He is smart. For instance, he started replacing incandescent lamps with energy-saving lamps in the whole Castle...\n\nPrince chose a model of energy-saving lamps and started the replacement as described below. He numbered all rooms in the Castle and counted how many lamps in each room he needs to replace.\n\nAt the beginning of each month, Prince buys m energy-saving lamps and replaces lamps in rooms according to his list. He chooses the first room in his list, in which lamps are not replaced yet. If Prince has enough lamps to replace all lamps in the room, he replaces all ones and takes the room out from the list. If there are still some energy-saving lamps unused, he considers replacement in the next room, which is the first in his list. This repeats while he still has some energy-saving lamps and number of lamps to replace in the next room is not greater than number of energy-saving lamps which Prince has in stock. Otherwise he postpones the replacement and saves the rest of energy-saving lamps for the next month.\n\nAs soon as all the work is done, he ceases buying new lamps. They are very high quality and have a very long life cycle.\n\nYour task is for a given number of month and descriptions of rooms to compute in how many rooms the old lamps will be replaced with energy-saving ones and how many energy-saving lamps will remain by the end of each month.\n\nThe first line contains integers n and m (1 ≤ n ≤ 1000,  1 ≤ m ≤ 100) — the number of rooms in the Castle and the number of energy-saving lamps, which Prince buys monthly.\n\nThe second line contains n integers k1, k2, ..., kn (1 ≤ kj ≤ 1000,  j = 1, 2, ..., n) — the number of lamps in the rooms of the Castle. The number in position #j is the number of lamps in #jth room. Room numbers are given in accordance with Prince's list.\n\nThe third line contains one integer q (1 ≤ q ≤ 105) — the number of queries.\n\nThe fourth line contains q integers d1, d2, ..., dq (1 ≤ dp ≤ 105,  p = 1, 2, ..., q) — numbers of months, in which queries are formed.\n\nMonths are numbered starting with 1; at the beginning of the first month Prince buys the first m energy-saving lamps.\n\nPrint q lines.\n\nLine #p contains two integers — the number of rooms, in which all old lamps are replaced already, and the number of remaining energy-saving lamps by the end of dpth month.\n\n"},{"iden":"input","content":"The first line contains integers n and m (1 ≤ n ≤ 1000,  1 ≤ m ≤ 100) — the number of rooms in the Castle and the number of energy-saving lamps, which Prince buys monthly.The second line contains n integers k1, k2, ..., kn (1 ≤ kj ≤ 1000,  j = 1, 2, ..., n) — the number of lamps in the rooms of the Castle. The number in position #j is the number of lamps in #jth room. Room numbers are given in accordance with Prince's list.The third line contains one integer q (1 ≤ q ≤ 105) — the number of queries.The fourth line contains q integers d1, d2, ..., dq (1 ≤ dp ≤ 105,  p = 1, 2, ..., q) — numbers of months, in which queries are formed.Months are numbered starting with 1; at the beginning of the first month Prince buys the first m energy-saving lamps."},{"iden":"output","content":"Print q lines.Line #p contains two integers — the number of rooms, in which all old lamps are replaced already, and the number of remaining energy-saving lamps by the end of dpth month."},{"iden":"examples","content":"Input5 43 10 5 2 7105 1 4 8 7 2 3 6 4 7Output4 01 12 35 15 11 51 94 42 35 1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rooms.  \nLet $ m \\in \\mathbb{Z}^+ $ be the monthly purchase of energy-saving lamps.  \nLet $ K = (k_1, k_2, \\dots, k_n) \\in (\\mathbb{Z}^+)^n $ be the sequence of lamp counts per room, in order of Prince's list.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ D = (d_1, d_2, \\dots, d_q) \\in (\\mathbb{Z}^+)^q $ be the query months.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. $ 1 \\leq m \\leq 100 $  \n3. $ 1 \\leq k_j \\leq 1000 $ for all $ j \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\leq q \\leq 10^5 $  \n5. $ 1 \\leq d_p \\leq 10^5 $ for all $ p \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nSimulate the replacement process over months:  \n- At the start of month $ t $, Prince acquires $ m $ lamps, adding to any leftover from previous months.  \n- He processes rooms in order $ j = 1, 2, \\dots, n $, replacing all lamps in room $ j $ if and only if the current stock $ \\geq k_j $.  \n- Upon replacement, remove the room from consideration and subtract $ k_j $ from stock.  \n- Stop processing rooms in a month when either:  \n  (i) no more rooms remain, or  \n  (ii) the next room requires more lamps than currently available.  \n- Remaining lamps are carried over to the next month.  \n- Once all rooms are replaced, no more lamps are purchased.  \n\nFor each query month $ d_p $, output:  \n- $ r_p $: number of rooms fully replaced by the end of month $ d_p $,  \n- $ s_p $: number of remaining lamps at the end of month $ d_p $.","simple_statement":"Prince replaces lamps in rooms monthly. Each month he buys `m` lamps. He goes through rooms in order: if he has enough lamps to replace all in a room, he does it and removes the room. He keeps doing this until he can’t replace the next room’s lamps. Leftover lamps are saved for next month. Given queries for specific months, output: number of rooms fully replaced and leftover lamps by that month.","has_page_source":false}