{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere is a bus stop near the university. The lessons are over, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e students come to the stop. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th student will appear at the bus stop at time \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u0027s are distinct).\u003c/p\u003e\u003cp\u003eWe shall assume that the stop is located on the coordinate axis \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eOx\u003c/i\u003e\u003c/span\u003e, at point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e \u003d 0\u003c/span\u003e, and the bus goes along the ray \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eOx\u003c/i\u003e\u003c/span\u003e, that is, towards the positive direction of the coordinate axis, and back. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th student needs to get to the point with coordinate \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026gt; 0\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe bus moves by the following algorithm. Initially it is at point 0. The students consistently come to the stop and get on it. The bus has a seating capacity which is equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e passengers. At the moment when \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e students get on the bus, it starts moving in the positive direction of the coordinate axis. Also it starts moving when the last (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e-th) student gets on the bus. The bus is moving at a speed of 1 unit of distance per 1 unit of time, i.e. it covers distance \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e in time \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eEvery time the bus passes the point at which at least one student needs to get off, it stops and these students get off the bus. The students need \u003cspan class\u003d\"tex-span\"\u003e1 + [\u003ci\u003ek\u003c/i\u003e / 2]\u003c/span\u003e units of time to get off the bus, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e is the number of students who leave at this point. Expression \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ek\u003c/i\u003e / 2]\u003c/span\u003e denotes rounded down \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e / 2\u003c/span\u003e. As soon as the last student leaves the bus, the bus turns around and goes back to the point \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e \u003d 0\u003c/span\u003e. It doesn\u0027t make any stops until it reaches the point. At the given point the bus fills with students once more, and everything is repeated.\u003c/p\u003e\u003cp\u003eIf students come to the stop when there\u0027s no bus, they form a line (queue) and get on the bus in the order in which they came. Any number of students get on the bus in negligible time, you should assume that it doesn\u0027t take any time. Any other actions also take no time. The bus has no other passengers apart from the students.\u003c/p\u003e\u003cp\u003eWrite a program that will determine for each student the time when he got off the bus. The moment a student got off the bus is the moment the bus stopped at the student\u0027s destination stop (despite the fact that the group of students need some time to get off).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — the number of students and the number of passengers the bus can transport, correspondingly. Next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contain descriptions of the students, one per line. Each line contains a pair of integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e, 1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e4\u003c/sup\u003e\u003c/span\u003e). The lines are given in the order of strict increasing of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Values of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e can coincide.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e — the moment of time when the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th student got off the bus. Print the numbers on one line and separate them with single spaces.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 10\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1\n3 5\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8 19\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 4\n3 5\n4 5\n5 5\n6 5\n7 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11 11 11 11 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e20 4\n28 13\n31 13\n35 6\n36 4\n52 6\n53 4\n83 2\n84 4\n87 1\n93 6\n108 4\n113 6\n116 1\n125 2\n130 2\n136 13\n162 2\n166 4\n184 1\n192 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample the bus waits for the first student for \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e units of time and drives him to his destination in additional \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e units of time. So the student leaves the bus at the moment of time \u003cspan class\u003d\"tex-span\"\u003e3 + 5 \u003d 8\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second sample the capacity of the bus equals \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, that\u0027s why it will drive the first student alone. This student is the same as the student from the first sample. So the bus arrives to his destination at the moment of time \u003cspan class\u003d\"tex-span\"\u003e8\u003c/span\u003e, spends \u003cspan class\u003d\"tex-span\"\u003e1 + [1 / 2] \u003d 1\u003c/span\u003e units of time on getting him off, and returns back to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e in additional \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e units of time. That is, the bus returns to the bus stop at the moment of time \u003cspan class\u003d\"tex-span\"\u003e14\u003c/span\u003e. By this moment the second student has already came to the bus stop. So he immediately gets in the bus, and is driven to his destination in additional \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e units of time. He gets there at the moment \u003cspan class\u003d\"tex-span\"\u003e14 + 5 \u003d 19\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eIn the third sample the bus waits for the fourth student for \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e units of time, then drives for \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e units of time, then gets the passengers off for \u003cspan class\u003d\"tex-span\"\u003e1 + [4 / 2] \u003d 3\u003c/span\u003e units of time, then returns for \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e units of time, and then drives the fifth student for \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e unit of time.\u003c/p\u003e"}}]}