{"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 div.sampleinteractionread {\n width: 60%;\n margin: 3px 0px 3px 0px;\n }\n div.sampleinteractionread pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n div.sampleinteractionwrite {\n width: 60%;\n margin: 3px 0px 3px 0px;\n margin-left: auto;\n }\n div.sampleinteractionwrite pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n table.sample {\n width: 100%;\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\u003eIt’s exam time in Mirko’s village. Everyone wants to pass\n the exam with as little effort as possible, which is not easy.\n Mirko realized that it would be best for him to find someone\n who knows more than him and learn from them. Everyone followed\n and now everyone is looking for someone to learn from. We can\n model how well a student is prepared for the exam with two\n integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$B.$\u003c/span\u003e The number\n \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e represents how well a\n student understands the subject, while the number \u003cspan class\u003d\"tex2jax_process\"\u003e$B$\u003c/span\u003e is proportional to the quantity of\n their knowledge.\u003c/p\u003e\n\n \u003cp\u003eAs the head of the village, Mirko decided that a student\n will ask another student for help only if that student has both\n numbers greater than or equal to the first student’s numbers\n (no student will ask someone who doesn’t understand the subject\n as well as themselves or who knows less). Additionally,\n students will try to minimize the difference in knowledge\n quantity (so that students don’t bother those that are way\n better). If this choice is not unique, they will try to\n minimize the difference in understanding.\u003c/p\u003e\n\n \u003cp\u003eMirko’s village has recently become a very popular suburb\n and new students keep moving in (in time for the exam). With\n Mirko’s strict rules, they get confused about Mirko’s rules and\n don’t know where to go). They decided to ask a programmer from\n a neighbouring village for help.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1\n \\le N \\le 200\\, 000)$\u003c/span\u003e, the number of queries and\n arrivals in the village. Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e lines contains either:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003e\"D \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$B$\u003c/span\u003e\", a student has moved in whose\n knowledge is \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$B$\u003c/span\u003e\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\"P \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e\", the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th student to move\n in wants to know whom to ask for help\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eThe numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$B$\u003c/span\u003e are between 1 and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2\\cdot 10^9$\u003c/span\u003e. No two\n students have both numbers equal.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each query (\"P \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e\"\n line), output which student the \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th student should ask for help.\n The students are numbered in the order they moved into the\n village (starting from 1). If a student cannot be helped,\n output \"NE\".\u003c/p\u003e\n\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\u003e6\nD 3 1\nD 2 2\nD 1 3\nP 1\nP 2\nP 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNE\nNE\nNE\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\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\u003e6\nD 8 8\nD 2 4\nD 5 6\nP 2\nD 6 2\nP 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 3\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\u003e7\nD 5 2\nD 5 3\nP 1\nD 7 1\nD 8 7\nP 3\nP 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}