{"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\u003eIt is your first day in your new job and guesses what, your first task is already waiting for you! Your task is to build a memory management system.\u003c/p\u003e\u003cp\u003eIn this system, the memory will consist of $$$m$$$ bytes ordered from $$$1$$$ to $$$m$$$. Originally, there are $$$n$$$ files in the system, such that the $$$i^{th}$$$ file is occupying all bytes from $$$l_i$$$ to $$$r_i$$$ (inclusive). It is guaranteed that no two files share the same memory position (byte).\u003c/p\u003e\u003cp\u003eThe main goal of the system is to answer multiple queries such that each query consists of a file of size $$$k$$$ bytes, and the system must determine if there exist at least $$$k$$$ consecutive bytes that can be reserved and assigned to that file.\u003c/p\u003e\u003cp\u003eFormally, at the $$$j^{th}$$$ query, you are given an integer $$$k_j$$$ and your task is to find a pair of integers $$$l_j$$$ and $$$r_j$$$, such that: \u003c/p\u003e\u003cul\u003e \u003cli\u003e All bytes between $$$l_j$$$ and $$$r_j$$$ (inclusive) are free (not occupied). \u003c/li\u003e\u003cli\u003e $$$r_j - l_j + 1 \\geq k_j$$$. \u003c/li\u003e\u003cli\u003e If there are multiple solutions, find the one with the maximum $$$r_j$$$. If there are still multiple solutions, find the one with maximum $$$l_j$$$. \u003c/li\u003e\u003cli\u003e If the $$$j^{th}$$$ file cannot be saved in the system, both $$$l_j$$$ and $$$r_j$$$ must be $$$-1$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003ePlease note that you are not reserving the bytes for the files in the queries, you are just checking if there exists an empty space for the file in the system. So, an empty byte in the system can be assigned to multiple queries files. However, if a byte is originally occupied in the system, you cannot use it for the queries files.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$T$$$ ($$$1 \\le T \\le 10$$$) specifying the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$0 \\le n \\le m$$$, $$$1 \\le m \\le 10^5$$$, $$$1 \\le q \\le \\text{min}(10^5, m)$$$), in which $$$n$$$ is the number of files in the system originally, $$$m$$$ is the number of bytes the system contains, and $$$q$$$ is the number of queries. \u003c/p\u003e\u003cp\u003eThen $$$n$$$ lines follow, each line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \\le l_i \\le r_i \\le m$$$), giving the files in system. It is guaranteed that no two files share the same memory position (byte).\u003c/p\u003e\u003cp\u003eThen $$$q$$$ lines follow, each line contains an integer $$$k_j$$$ ($$$1 \\le k_j \\le m$$$), giving the queries.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query $$$j$$$, print two space-separated integers $$$l_j$$$ and $$$r_j$$$, as described in the problem statement. If there are multiple solutions, find the one with the maximum $$$r_j$$$. If there are still multiple solutions, find the one with maximum $$$l_j$$$. If the file cannot be saved in the system, both $$$l_j$$$ and $$$r_j$$$ must be $$$-1$$$.\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 9 2\n1 1\n5 5\n8 9\n3\n2\n2 5 3\n5 5\n1 2\n1\n2\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 4\n6 7\n4 4\n3 4\n-1 -1\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 test case, the memory system can be represented as \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eOFFFOFFOO\u003c/span\u003e\", in which \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eO\u003c/span\u003e\u0027 represent an occupied position and \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eF\u003c/span\u003e\u0027 represent a free position. \u003c/p\u003e\u003cul\u003e \u003cli\u003e The first file needs to occupy $$$3$$$ bytes. So, the only available answer is $$$2\\, 4$$$. \u003c/li\u003e\u003cli\u003e The second file needs to occupy 2 bytes. There are $$$3$$$ available intervals, which are: $$$2\\, 3$$$, $$$3\\, 4$$$, and $$$6\\, 7$$$. The interval that satisfies the problem conditions is $$$6\\, 7$$$. \u003c/li\u003e\u003c/ul\u003e"}}]}