{"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\u003eThe hierarchical structure of the new office of Galactical Ministry of Bureacracy is very complicated. Office has \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e departments, numbered by sequential integers from 1 to \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eInitially all departments are empty. Then two types of the events may happen: \u003c/p\u003e\u003col\u003e \u003cli\u003e Arrival: new person is moved from old offices into some department. For this person are known his name and birthday. Assume this event is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-th arrival event for this department. Then person\u0027s local id is set to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e.\u003c/li\u003e\u003cli\u003e Departure: selected person in some department with local id \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e is moved out this department to the old offices. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThe head of each department is defined by the following way:\u003c/p\u003e\u003cul\u003e \u003cli\u003e If some person is strictly older, than than all other people who are currently working in this department, he became the head of the department. \u003c/li\u003e\u003cli\u003e In case of tie (two or more oldest employees), the one with \u003cspan class\u003d\"tex-font-style-underline\"\u003eleast\u003c/span\u003e local id in this department became the head of the department. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe head of office is defined by the following way:\u003c/p\u003e\u003cul\u003e \u003cli\u003e If some person who currently works in new office is strictly older, than all other people who currently are working in the new office, this person is the head of the office. \u003c/li\u003e\u003cli\u003e In case of tie person, who is working in the department with \u003cspan class\u003d\"tex-font-style-underline\"\u003eleast number\u003c/span\u003e, have priority. \u003c/li\u003e\u003cli\u003e In case of tie person with \u003cspan class\u003d\"tex-font-style-underline\"\u003eleast\u003c/span\u003e local id on this department have priority. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYou are asked to write a program which after each event prints name of the head of office and head of department, which is related to this event.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst line of the input contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e — number of events (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e). Then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e events follow.\u003c/p\u003e\u003cp\u003eFirst line of the event description contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e — type of event (\u003cspan class\u003d\"tex-span\"\u003e|\u003ci\u003et\u003c/i\u003e| \u003d 1\u003c/span\u003e). \u003c/p\u003e\u003cp\u003eIf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d 1\u003c/span\u003e, then new person is moved to the new office. Then second line contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e — number of department, where new person is coming (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), next line contains non-empty string composed of no more than 10 lowercase English letters — name of the person, and next line contains his date of birth in Unified Decimal Galaxy Time format \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003edd\u003c/i\u003e: \u003ci\u003emm\u003c/i\u003e: \u003ci\u003eyyyy\u003c/i\u003e\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003edd\u003c/i\u003e\u003c/span\u003e is for day, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emm\u003c/i\u003e\u003c/span\u003e — for month and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eyyyy\u003c/i\u003e\u003c/span\u003e — for year, \u003cspan class\u003d\"tex-span\"\u003e00 ≤ \u003ci\u003edd\u003c/i\u003e, \u003ci\u003emm\u003c/i\u003e ≤ 99\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0001 ≤ \u003ci\u003eyyyy\u003c/i\u003e ≤ 9999\u003c/span\u003e. You may assume that all names in the input file are pairwise distinct.\u003c/p\u003e\u003cp\u003eIf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d - 1\u003c/span\u003e, then some person is moved back to the old offices. In this case second line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e — number of department and local id of person who is moved (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). It is guaranteed that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e does not exceed total number of people who were moved to this department at the moment of event and that all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e in the requests with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d - 1\u003c/span\u003e are pairwise different.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eAfter each event print two space-separated strings: name of the head of the new office and name of head of department, which is related to this event. If new office or department contains no employees, printf \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVacant\u003c/span\u003e\" instead.\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\u003e8\n1\n10\nrab\n01:01:0001\n1\n1000000000\ntor\n02:01:0001\n-1\n10 1\n1\n10\ntur\n01:01:0001\n-1\n10 2\n-1\n1000000000 1\n1\n5\nbor\n99:99:9999\n1\n5\nrot\n99:99:9999\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003erab rab\nrab tor\ntor Vacant\ntur tur\ntor Vacant\nVacant Vacant\nbor bor\nbor bor\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\u003eLets check what happened in the sample.\u003c/p\u003e\u003cp\u003eFirst event: in department 10 arrived new employee \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e. He got local id 1 in this department, became the head of department and head of office.\u003c/p\u003e\u003cp\u003eSecond event: in office \u003cspan class\u003d\"tex-span\"\u003e1000000000\u003c/span\u003e arrived new employee \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e. He got local id 1 in this department, became the head of department, but because \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e\u0027s birthday is \u003cspan class\u003d\"tex-span\"\u003e01: 01: 0001\u003c/span\u003e, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e\u0027s only \u003cspan class\u003d\"tex-span\"\u003e02: 01: 0001\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e is younger and does not became the head of office.\u003c/p\u003e\u003cp\u003eThird event: from department 10 removed employee with local id 1, i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e. Department is empty, so we are printing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVacant\u003c/span\u003e\". In other departments only \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e is working, so he became the head of office.\u003c/p\u003e\u003cp\u003eFourth event: in department 10 arrived new employee \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etur\u003c/i\u003e\u003c/span\u003e. He got local id 2 in this department, became the head of department (because department was empty) and became the new head of the office, because his birthday is \u003cspan class\u003d\"tex-span\"\u003e01: 01: 0001\u003c/span\u003e, so he is older, than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eFifth event: from department 10 removed employee with local id 2, i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etur\u003c/i\u003e\u003c/span\u003e. Department is empty, so we are printing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVacant\u003c/span\u003e\". In other departments only \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e is working, so he became new head of office.\u003c/p\u003e\u003cp\u003eSixth event: from department \u003cspan class\u003d\"tex-span\"\u003e1000000000\u003c/span\u003e removed employee with local id 1, i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e. Department is empty, so we are printing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVacant\u003c/span\u003e\". Office is empty, so we are printing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVacant\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eSeventh event: in department 5 arrived new employee \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e. He got local id 1 in this department, became the head of department and head of office. Eight event: in department 5 arrived new employee \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erot\u003c/i\u003e\u003c/span\u003e. He got local id 2 in this department. His birthday is the as the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e\u0027s, but his local id is greater, so \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e keeps his position as head of the department. Similarly, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erot\u003c/i\u003e\u003c/span\u003e have same birthday as \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e, they are working in same department, but his local id is greater, so \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e keeps his position as head of the office.\u003c/p\u003e"}}]}