{"problem":{"name":"H. Hierarchy","description":{"content":"The hierarchical structure of the new office of Galactical Ministry of Bureacracy is very complicated. Office has 109 departments, numbered by sequential integers from 1 to 109.  Initially all depart","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10091H"},"statements":[{"statement_type":"Markdown","content":"The hierarchical structure of the new office of Galactical Ministry of Bureacracy is very complicated. Office has 109 departments, numbered by sequential integers from 1 to 109. \n\nInitially all departments are empty. Then two types of the events may happen: \n\nThe head of each department is defined by the following way:\n\nThe head of office is defined by the following way:\n\nYou 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.\n\nFirst line of the input contains one integer n — number of events (1 ≤ n ≤ 105). Then n events follow.\n\nFirst line of the event description contains one integer t — type of event (|t| = 1). \n\nIf t = 1, then new person is moved to the new office. Then second line contains one integer D — number of department, where new person is coming (1 ≤ D ≤ 109), 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 dd: mm: yyyy, where dd is for day, mm — for month and yyyy — for year, 00 ≤ dd, mm ≤ 99, 0001 ≤ yyyy ≤ 9999. You may assume that all names in the input file are pairwise distinct.\n\nIf t =  - 1, then some person is moved back to the old offices. In this case second line contains two integers D and k — number of department and local id of person who is moved (1 ≤ D ≤ 109). It is guaranteed that k does not exceed total number of people who were moved to this department at the moment of event and that all k in the requests with t =  - 1 are pairwise different.\n\nAfter 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 \"_Vacant_\" instead.\n\nLets check what happened in the sample.\n\nFirst event: in department 10 arrived new employee rab. He got local id 1 in this department, became the head of department and head of office.\n\nSecond event: in office 1000000000 arrived new employee tor. He got local id 1 in this department, became the head of department, but because rab's birthday is 01: 01: 0001, and tor's only 02: 01: 0001, tor is younger and does not became the head of office.\n\nThird event: from department 10 removed employee with local id 1, i.e. rab. Department is empty, so we are printing \"_Vacant_\". In other departments only tor is working, so he became the head of office.\n\nFourth event: in department 10 arrived new employee tur. 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 01: 01: 0001, so he is older, than tor.\n\nFifth event: from department 10 removed employee with local id 2, i.e. tur. Department is empty, so we are printing \"_Vacant_\". In other departments only tor is working, so he became new head of office.\n\nSixth event: from department 1000000000 removed employee with local id 1, i.e. tor. Department is empty, so we are printing \"_Vacant_\". Office is empty, so we are printing \"_Vacant_\".\n\nSeventh event: in department 5 arrived new employee bor. 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 rot. He got local id 2 in this department. His birthday is the as the bor's, but his local id is greater, so bor keeps his position as head of the department. Similarly, rot have same birthday as bor, they are working in same department, but his local id is greater, so bor keeps his position as head of the office.\n\n## Input\n\nFirst line of the input contains one integer n — number of events (1 ≤ n ≤ 105). Then n events follow.First line of the event description contains one integer t — type of event (|t| = 1). If t = 1, then new person is moved to the new office. Then second line contains one integer D — number of department, where new person is coming (1 ≤ D ≤ 109), 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 dd: mm: yyyy, where dd is for day, mm — for month and yyyy — for year, 00 ≤ dd, mm ≤ 99, 0001 ≤ yyyy ≤ 9999. You may assume that all names in the input file are pairwise distinct.If t =  - 1, then some person is moved back to the old offices. In this case second line contains two integers D and k — number of department and local id of person who is moved (1 ≤ D ≤ 109). It is guaranteed that k does not exceed total number of people who were moved to this department at the moment of event and that all k in the requests with t =  - 1 are pairwise different.\n\n## Output\n\nAfter 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 \"_Vacant_\" instead.\n\n[samples]\n\n## Note\n\nLets check what happened in the sample.First event: in department 10 arrived new employee rab. He got local id 1 in this department, became the head of department and head of office.Second event: in office 1000000000 arrived new employee tor. He got local id 1 in this department, became the head of department, but because rab's birthday is 01: 01: 0001, and tor's only 02: 01: 0001, tor is younger and does not became the head of office.Third event: from department 10 removed employee with local id 1, i.e. rab. Department is empty, so we are printing \"_Vacant_\". In other departments only tor is working, so he became the head of office.Fourth event: in department 10 arrived new employee tur. 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 01: 01: 0001, so he is older, than tor.Fifth event: from department 10 removed employee with local id 2, i.e. tur. Department is empty, so we are printing \"_Vacant_\". In other departments only tor is working, so he became new head of office.Sixth event: from department 1000000000 removed employee with local id 1, i.e. tor. Department is empty, so we are printing \"_Vacant_\". Office is empty, so we are printing \"_Vacant_\".Seventh event: in department 5 arrived new employee bor. 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 rot. He got local id 2 in this department. His birthday is the as the bor's, but his local id is greater, so bor keeps his position as head of the department. Similarly, rot have same birthday as bor, they are working in same department, but his local id is greater, so bor keeps his position as head of the office.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of events.  \nLet $ \\mathcal{D} $ be the set of departments, where each department $ d \\in \\mathcal{D} $ is identified by an integer $ 1 \\le d \\le 10^9 $.  \nEach department $ d $ maintains an ordered list $ L_d = [(p_1, b_1), (p_2, b_2), \\dots] $ of personnel, where:  \n- $ p_i $ is a unique string (name) of the person,  \n- $ b_i $ is their date of birth in format $ (dd, mm, yyyy) $,  \n- The list is ordered by increasing local ID $ i $ (i.e., arrival order).  \n\nLet $ H_d $ be the head of department $ d $, defined as the person in $ L_d $ with:  \n- **Oldest** birth date (earliest $ (dd, mm, yyyy) $ lexicographically),  \n- If tied, **smallest** local ID.  \n\nLet $ H_{\\text{office}} $ be the head of the entire office, defined as the person among all $ \\bigcup_{d \\in \\mathcal{D}} L_d $ with:  \n- **Oldest** birth date,  \n- If tied, **smallest** local ID (across all departments).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. For each event:  \n   - If $ t = 1 $:  \n     - $ 1 \\le D \\le 10^9 $  \n     - Name: non-empty string of ≤10 lowercase English letters  \n     - Date: $ dd:mm:yyyy $, $ 00 \\le dd, mm \\le 99 $, $ 0001 \\le yyyy \\le 9999 $  \n   - If $ t = -1 $:  \n     - $ 1 \\le D \\le 10^9 $, $ k \\ge 1 $, and $ k \\le |L_D| $ at time of event  \n     - All $ k $ in $ t = -1 $ events are distinct per department  \n\n**Objective**  \nAfter each event, output:  \n- $ H_{\\text{office}} $'s name or \"_Vacant_\" if no one in office,  \n- $ H_D $'s name for the department $ D $ involved in the event, or \"_Vacant_\" if $ L_D = \\emptyset $.  \n\n**Operations**  \n- **Event $ t = 1 $, department $ D $, person $ (p, b) $:**  \n  Append $ (p, b) $ to $ L_D $ with local ID $ |L_D| + 1 $.  \n  Recompute $ H_D $ and $ H_{\\text{office}} $.  \n\n- **Event $ t = -1 $, department $ D $, local ID $ k $:**  \n  Remove the $ k $-th person (1-indexed) from $ L_D $.  \n  Recompute $ H_D $ and $ H_{\\text{office}} $.  \n\n**Output**  \nAfter each event, print:  \n$$ \\texttt{[} H_{\\text{office}} \\texttt{] [} H_D \\texttt{]} $$  \nwhere each is either the person’s name or \"_Vacant_\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10091H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}