{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eA big reservoir was built on Red River using a dam. Assume\n that the reservoir is a rectangular box with unit length width.\n The reservoir consists of many tanks. An example a cross\n section of an empty reservoir along its length and height\n dimensions is shown in the picture below:\u003c/p\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/4ed24af67b657aa7922a0e579fc5eac8?v\u003d1715357798\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{1.jpg}\" style\u003d\"width:30.00%\"\u003e\n \u003c/center\u003e\n \u003cp\u003eWater flows in from the top left gate into the reservoir.\n The tanks in the reservoir are constructed using walls. Each\n wall is one unit thick (along the width dimension) and is\n shorter than the height of the reservoir.\u003c/p\u003e\n \u003cp\u003eGiven the locations and the heights of the walls and the\n unit volume \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e of water\n flowing in, your task is to figure out the last wall water\n flows over.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of several datasets. The first line of\n the input contains the number of datasets, which is a positive\n number and is not greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e. The following lines describe the\n datasets.\u003c/p\u003e\n \u003cp\u003eEach dataset is described by the following lines:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first line contains one positive integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e – the number of\n walls separating the tanks \u003cspan class\u003d\"tex2jax_process\"\u003e$(N \\leq {10}^{5})$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe second line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e${L}_{i}$\u003c/span\u003e – the horizontal\n location (along the length dimension of the reservoir) of\n the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e\n wall \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq {L}_{i} \\leq\n {10}^{9}, {L}_{i} \u0026gt; {L}_{i-1} + 1$\u003c/span\u003e for\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026gt; 1)$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe third line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e positive integers \u003cspan class\u003d\"tex2jax_process\"\u003e${H}_{i}$\u003c/span\u003e – the height in unit\n length of the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm\n {th}$\u003c/span\u003e wall \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq\n {H}_{i} \\leq {10}^{5})$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe fourth line contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$Q$\u003c/span\u003e – the number of queries\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq Q \\leq\n {10}^{5})$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eIn the next \u003cspan class\u003d\"tex2jax_process\"\u003e$Q$\u003c/span\u003e\n lines, each line contains a positive integer \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e that is the unit volume of\n water flowing in the reservoir \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq K \\leq {10}^{15})$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each dataset, output \u003cspan class\u003d\"tex2jax_process\"\u003e$Q$\u003c/span\u003e lines where the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e contains the index\n of the last wall that water flows over for the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e query. If there is\n no wall that water flows over, output \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eExplanation for the Sample Dataset\u003c/h2\u003e\n \u003cdiv class\u003d\"figure\"\u003e\n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/85c6ef749f3c907e5756b4b02b401710?v\u003d1715357798\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{2.jpg}\" style\u003d\"width:30.00%\"\u003e \u003cimg src\u003d\"CDN_BASE_URL/b3d4e939963939624de0c7e2cbdf0404?v\u003d1715357798\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{3.jpg}\" style\u003d\"width:30.00%\"\u003e \u003cimg src\u003d\"CDN_BASE_URL/2eeb52aaaab6923d93252ec2023d435a?v\u003d1715357798\" alt\u003d\"\\includegraphics[width\u003d0.3\\textwidth ]{4.jpg}\" style\u003d\"width:30.00%\"\u003e\u003c/p\u003e\n \u003c/div\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\n4\n1 3 5 8\n2 5 3 1\n3\n3\n13\n17\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}