402841: GYM100917 H Hierarchy

The hierarchical structure of the new office of Galactical Ministry of Bureacracy is very complicated. Office has 10⁹ departments, numbered by sequential integers from 1 to 10⁹.

Initially all departments are empty. Then two types of the events may happen:

1. Arrival: new person is moved from old offices into some department. For this person are known his name and birthday. Assume this event is k-th arrival event for this department. Then person's local id is set to k.
2. Departure: selected person in some department with local id k is moved out this department to the old offices.

The head of each department is defined by the following way:

• 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.
• In case of tie (two or more oldest employees), the one with least local id in this department became the head of the department.

The head of office is defined by the following way:

• 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.
• In case of tie person, who is working in the department with least number, have priority.
• In case of tie person with least local id on this department have priority.

You 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.

First line of the input contains one integer n — number of events (1 ≤ n ≤ 10⁵). 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 ≤ 10⁹), 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 ≤ 10⁹). 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.

After 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.

8
1
10
rab
01:01:0001
1
1000000000
tor
02:01:0001
-1
10 1
1
10
tur
01:01:0001
-1
10 2
-1
1000000000 1
1
5
bor
99:99:9999
1
5
rot
99:99:9999

rab rab
rab tor
tor Vacant
tur tur
tor Vacant
Vacant Vacant
bor bor
bor bor

Lets 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.