Rightsizing

Many tech companies have realized that they "over-hired". Looking at their books, they realize they might have to let go of some employees. To protect the bottom line, a company always fires the employee earning the highest annual salary at the time. If several employees share the same maximum salary, the one whose name comes first alphabetically is fired.

Employees can still get raises to keep morale up, which makes deciding whom to fire trickier.

Given a set of employees with their initial annual salaries, followed by a sequence of actions (either firing an employee or giving a raise to a current employee), determine which employee is fired at each firing event.

The first line contains two integers $n$ ($1 \le n \le 10^5$) and $a$ ($1 \le a \le 2 \times 10^5$), the number of employees and the number of actions.

The next $n$ lines each contain a name $e$ and an annual salary $s$ ($1 \le s \le 10^9$). Each name is unique and has 1 to 20 lowercase letters.

The next $a$ lines describe the actions. A line starting with 1 gives a raise: it is followed by a name $e$ and a raise amount $r$ ($1 \le r \le 10^9$). Each employee who receives a raise is from the original list and has not been fired yet. A line starting with 2 fires the employee with the highest current salary, breaking ties by alphabetical order of name. There are at most $n$ lines starting with 2.

For each firing event, print one line with the name of the fired employee and their annual salary at the time they were fired, separated by a space.