{"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\u003eBizon the Champion has recently finished painting his wood fence. The fence consists of a sequence of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e panels of \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e meter width and of arbitrary height. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th panel\u0027s height is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e meters. The adjacent planks follow without a gap between them.\u003c/p\u003e\u003cp\u003eAfter Bizon painted the fence he decided to put a \"for sale\" sign on it. The sign will be drawn on a rectangular piece of paper and placed on the fence so that the sides of the sign are parallel to the fence panels and are also aligned with the edges of some panels. Bizon the Champion introduced the following constraints for the sign position:\u003c/p\u003e\u003col\u003e \u003cli\u003e The width of the sign should be exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e meters. \u003c/li\u003e\u003cli\u003e The sign must fit into the segment of the fence from the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e-th to the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e-th panels, inclusive (also, it can\u0027t exceed the fence\u0027s bound in vertical direction). \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThe sign will be really pretty, So Bizon the Champion wants the sign\u0027s height to be as large as possible.\u003c/p\u003e\u003cp\u003eYou are given the description of the fence and several queries for placing sign. For each query print the maximum possible height of the sign that can be placed on the corresponding segment of the fence with the given fixed width of the sign.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— the number of panels in the fence (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e). \u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e,\u0026nbsp;— the heights of the panels (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). \u003c/p\u003e\u003cp\u003eThe third line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— the number of the queries (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e). \u003c/p\u003e\u003cp\u003eThe next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines contain the descriptions of the queries, each query is represented by three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003er\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e - \u003ci\u003el\u003c/i\u003e + 1\u003c/span\u003e)\u0026nbsp;— the segment of the fence and the width of the sign respectively.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query print the answer on a separate line\u0026nbsp;— the maximum height of the sign that can be put in the corresponding segment of the fence with all the conditions being satisfied.\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\u003e5\n1 2 2 3 3\n3\n2 5 3\n2 5 2\n1 5 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n1\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\u003eThe fence described in the sample looks as follows: \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b1fca3d6f33dd0458b8f51f4be5afd35?v\u003d1714220822\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eThe possible positions for the signs for all queries are given below.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/69da7fba4894dd712f78b7185701b22b?v\u003d1714220822\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The optimal position of the sign for the first query. \u003c/center\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f7325e9485ada65099c20ed83b2a8d24?v\u003d1714220822\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The optimal position of the sign for the second query. \u003c/center\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/3a5e65b93f3a1545089a47d8afcb65a5?v\u003d1714220822\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The optimal position of the sign for the third query. \u003c/center\u003e"}}]}