{"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\u003eA estrutura hierárquica do novo escritório do Ministério Galáctico da Burocracia é muito complicada. O escritório tem \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e departamentos, numerados por inteiros sequenciais de 1 a \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eInicialmente, todos os departamentos estão vazios. Então, dois tipos de eventos podem acontecer: \u003c/p\u003e\u003col\u003e \u003cli\u003e Chegada: uma nova pessoa é transferida de antigos escritórios para algum departamento. Para essa pessoa, são conhecidos seu nome e data de nascimento. Suponha que este evento é o \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-ésimo evento de chegada para este departamento. Então, o id local da pessoa é definido como \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e.\u003c/li\u003e\u003cli\u003e Partida: a pessoa selecionada em algum departamento com id local \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e é transferida para os antigos escritórios. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eO chefe de cada departamento é definido da seguinte maneira:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Se alguma pessoa for estritamente mais velha do que todas as outras pessoas que atualmente trabalham neste departamento, ela se torna o chefe do departamento. \u003c/li\u003e\u003cli\u003e Em caso de empate (dois ou mais funcionários mais velhos), aquele com \u003cspan class\u003d\"tex-font-style-underline\"\u003emenor\u003c/span\u003e id local neste departamento se torna o chefe do departamento. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eO chefe do escritório é definido da seguinte maneira:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Se alguma pessoa que atualmente trabalha no novo escritório for estritamente mais velha do que todas as outras pessoas que atualmente trabalham no novo escritório, essa pessoa é o chefe do escritório. \u003c/li\u003e\u003cli\u003e Em caso de empate, a pessoa que trabalha no departamento com \u003cspan class\u003d\"tex-font-style-underline\"\u003emenor número\u003c/span\u003e tem prioridade. \u003c/li\u003e\u003cli\u003e Em caso de empate, a pessoa com \u003cspan class\u003d\"tex-font-style-underline\"\u003emenor\u003c/span\u003e id local neste departamento tem prioridade. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eVocê é solicitado a escrever um programa que, após cada evento, imprima o nome do chefe do escritório e o nome do chefe do departamento relacionado a este evento.\u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eA primeira linha da entrada contém um inteiro \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e — número de eventos (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e). Então, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e eventos seguem.\u003c/p\u003e\u003cp\u003eA primeira linha da descrição do evento contém um inteiro \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e — tipo de evento (\u003cspan class\u003d\"tex-span\"\u003e|\u003ci\u003et\u003c/i\u003e| \u003d 1\u003c/span\u003e). \u003c/p\u003e\u003cp\u003eSe \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d 1\u003c/span\u003e, então uma nova pessoa é transferida para o novo escritório. Então, a segunda linha contém um inteiro \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e — número do departamento, onde a nova pessoa está chegando (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e), a próxima linha contém uma string não vazia composta por no máximo 10 letras minúsculas em inglês — nome da pessoa, e a próxima linha contém sua data de nascimento no formato de Tempo Decimal Unificado da Galáxia \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003edd\u003c/i\u003e: \u003ci\u003emm\u003c/i\u003e: \u003ci\u003eyyyy\u003c/i\u003e\u003c/span\u003e, onde \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003edd\u003c/i\u003e\u003c/span\u003e é para o dia, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emm\u003c/i\u003e\u003c/span\u003e — para o mês e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eyyyy\u003c/i\u003e\u003c/span\u003e — para o ano, \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. Você pode assumir que todos os nomes no arquivo de entrada são distintos entre si.\u003c/p\u003e\u003cp\u003eSe \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d - 1\u003c/span\u003e, então alguma pessoa é transferida de volta para os antigos escritórios. Neste caso, a segunda linha contém dois inteiros \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e — número do departamento e id local da pessoa que está sendo transferida (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eD\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). É garantido que \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e não excede o número total de pessoas que foram transferidas para este departamento no momento do evento e que todos \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e nas solicitações com \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d - 1\u003c/span\u003e são distintos entre si.\u003c/p\u003e"}},{"title":"Saída","value":{"format":"HTML","content":"\u003cp\u003eApós cada evento, imprima duas strings separadas por espaço: nome do chefe do novo escritório e nome do chefe do departamento relacionado a este evento. Se o novo escritório ou departamento não contiver funcionários, imprima \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVago\u003c/span\u003e\" em vez disso.\u003c/p\u003e"}},{"title":"Exemplos","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"}},{"title":"Nota","value":{"format":"HTML","content":"\u003cp\u003eVamos verificar o que aconteceu no exemplo.\u003c/p\u003e\u003cp\u003ePrimeiro evento: no departamento 10 chegou um novo funcionário \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e. Ele recebeu o id local 1 neste departamento, tornou-se o chefe do departamento e chefe do escritório.\u003c/p\u003e\u003cp\u003eSegundo evento: no escritório \u003cspan class\u003d\"tex-span\"\u003e1000000000\u003c/span\u003e chegou um novo funcionário \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e. Ele recebeu o id local 1 neste departamento, tornou-se o chefe do departamento, mas porque o aniversário de \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e é \u003cspan class\u003d\"tex-span\"\u003e01: 01: 0001\u003c/span\u003e, e o de \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e é apenas \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 é mais jovem e não se torna o chefe do escritório.\u003c/p\u003e\u003cp\u003eTerceiro evento: do departamento 10 foi removido o funcionário com id local 1, ou seja, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erab\u003c/i\u003e\u003c/span\u003e. O departamento está vazio, então estamos imprimindo \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVago\u003c/span\u003e\". Nos outros departamentos, apenas \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e está trabalhando, então ele se tornou o chefe do escritório.\u003c/p\u003e\u003cp\u003eQuarto evento: no departamento 10 chegou um novo funcionário \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etur\u003c/i\u003e\u003c/span\u003e. Ele recebeu o id local 2 neste departamento, tornou-se o chefe do departamento (porque o departamento estava vazio) e se tornou o novo chefe do escritório, porque seu aniversário é \u003cspan class\u003d\"tex-span\"\u003e01: 01: 0001\u003c/span\u003e, então ele é mais velho do que \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eQuinto evento: do departamento 10 foi removido o funcionário com id local 2, ou seja, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etur\u003c/i\u003e\u003c/span\u003e. O departamento está vazio, então estamos imprimindo \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVago\u003c/span\u003e\". Nos outros departamentos, apenas \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e está trabalhando, então ele se tornou o novo chefe do escritório.\u003c/p\u003e\u003cp\u003eSexto evento: do departamento \u003cspan class\u003d\"tex-span\"\u003e1000000000\u003c/span\u003e foi removido o funcionário com id local 1, ou seja, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003etor\u003c/i\u003e\u003c/span\u003e. O departamento está vazio, então estamos imprimindo \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVago\u003c/span\u003e\". O escritório está vazio, então estamos imprimindo \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eVago\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eSétimo evento: no departamento 5 chegou um novo funcionário \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e. Ele recebeu o id local 1 neste departamento, tornou-se o chefe do departamento e chefe do escritório. Oitavo evento: no departamento 5 chegou um novo funcionário \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erot\u003c/i\u003e\u003c/span\u003e. Ele recebeu o id local 2 neste departamento. Seu aniversário é o mesmo que o de \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e, mas seu id local é maior, então \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e mantém sua posição como chefe do departamento. Da mesma forma, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003erot\u003c/i\u003e\u003c/span\u003e tem o mesmo aniversário que \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e, eles estão trabalhando no mesmo departamento, mas seu id local é maior, então \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ebor\u003c/i\u003e\u003c/span\u003e mantém sua posição como chefe do escritório.\u003c/p\u003e"}}]}