{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eHaibara is one of Conan\u0027s best friends. Conan sent her as a spy in order to discover the killer in one of his investigations. Haibara was on her first mission as a spy. Unfortunately, her mission did not go as planned, and she has been compromised. Haibara got panicked and she forgot what she learned from Conan. So, it is your time to help her to avoid arrest. Your task is to help Haibara find the best safe house for her based on her current situation. There are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e safe houses around Haibara\u0027s location. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e house is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e kilometers away from Haibara, and it contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e coins.\u003c/p\u003e\u003cp\u003eAccording to the manual, the best safe house must be at distance no more than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and must contain at least \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e coins. If there is more than one safe house satisfying these conditions, you must choose the nearest one. If there is more than one safe house at the same distance, you must choose the one that contains the biggest amount of coins. Finally, if there is more than one safe house satisfying all the previous conditions, you must choose the one with minimum index.\u003c/p\u003e\u003cp\u003eDo not forget that Haibara is in a real danger, so you must find the best safe house for her as soon as possible. Conan will be very happy if you rescue Haibara. Can you do this?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 500\u003c/span\u003e), in which \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e is the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 500\u003c/span\u003e) (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ 1000\u003c/span\u003e), in which \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e is the number of safe houses, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e are the values from the manual as described in the statement. \u003c/p\u003e\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines follow, each line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\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\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 1000\u003c/span\u003e), in which \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the distance to the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003eth\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e safe house, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the amount of coins it contains. Safe houses are numbered from 1 to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e in the order given in the input.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print a single line containing \u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003e if there is no suitable safe house for Haibara. Otherwise, print the index of the safe house you have chosen for her. \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\u003e2\n3 5 3\n4 2\n7 1\n5 7\n4 4 6\n3 7\n3 8\n2 4\n5 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\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 second test case, you need to find a safe house at distance no more than \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and must contain at least \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e coins. You can choose the \u003cspan class\u003d\"tex-span\"\u003e1\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003est\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003end\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e safe houses, but according to the manual, the \u003cspan class\u003d\"tex-span\"\u003e2\u003csup class\u003d\"upper-index\"\u003e\u003ci\u003end\u003c/i\u003e\u003c/sup\u003e\u003c/span\u003e safe house is the most suitable.\u003c/p\u003e"}}]}