{"problem":{"name":"Sandglass","description":{"content":"We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb $A$ or $B$ lies on top of the other and becomes the _upp","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc082_d"},"statements":[{"statement_type":"Markdown","content":"We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb $A$ or $B$ lies on top of the other and becomes the _upper bulb_. The other bulb becomes the _lower bulb_.\nThe sand drops from the upper bulb to the lower bulb at a rate of $1$ gram per second. When the upper bulb no longer contains any sand, nothing happens.\nInitially at time $0$, bulb A is the upper bulb and contains $a$ grams of sand; bulb B contains $X-a$ grams of sand (for a total of $X$ grams).\nWe will turn over the sandglass at time $r_1,r_2,..,r_K$. Assume that this is an instantaneous action and takes no time. Here, time $t$ refer to the time $t$ seconds after time $0$.\nYou are given $Q$ queries. Each query is in the form of $(t_i,a_i)$. For each query, assume that $a=a_i$ and find the amount of sand that would be contained in bulb A at time $t_i$.\n\n## Constraints\n\n*   $1≤X≤10^9$\n*   $1≤K≤10^5$\n*   $1≤r_1<r_2< .. <r_K≤10^9$\n*   $1≤Q≤10^5$\n*   $0≤t_1<t_2< .. <t_Q≤10^9$\n*   $0≤a_i≤X (1≤i≤Q)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$X$\n$K$\n$r_1$ $r_2$ .. $r_K$\n$Q$\n$t_1$ $a_1$\n$t_2$ $a_2$\n$:$\n$t_Q$ $a_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc082_d","tags":[],"sample_group":[["180\n3\n60 120 180\n3\n30 90\n61 1\n180 180","60\n1\n120\n\nIn the first query, $30$ out of the initial $90$ grams of sand will drop from bulb A, resulting in $60$ grams. In the second query, the initial $1$ gram of sand will drop from bulb A, and nothing will happen for the next $59$ seconds. Then, we will turn over the sandglass, and $1$ second after this, bulb $A$ contains $1$ gram of sand at the time in question."],["100\n1\n100000\n4\n0 100\n90 100\n100 100\n101 100","100\n10\n0\n0\n\nIn every query, the upper bulb initially contains $100$ grams, and the question in time comes before we turn over the sandglass."],["100\n5\n48 141 231 314 425\n7\n0 19\n50 98\n143 30\n231 55\n342 0\n365 100\n600 10","19\n52\n91\n10\n58\n42\n100"]],"created_at":"2026-03-03 11:01:14"}}