Dining Room#2573
One famous company has employees of two types: extroverts and introverts. These two kinds of people differ in many ways, and in this problem, we consider the difference in their behavior during dinner.
The dining room in this company is represented as a rectangular grid of size N \times M. In other words, each point with integer coordinates (0 \leq x \leq N, 0 \leq y \leq M) contains a table. Each table is for one person.
The (Euclidean) distance between points (x_1, y_1) and (x_2, y_2) is calculated as \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.
When an introvert arrives in the dining room, they select a free table such that the minimum distance to the nearest occupied table is as large as possible. If there are several tables with the largest minimum distance, they pick the one with the smallest coordinate. If there is still more than one, they pick the one with the smallest coordinate.
When an extrovert arrives in the dining room, they select a free table such that the maximum distance to the farthest occupied table is as small as possible. If there are several tables with the smallest maximum distance, they pick the one with the smallest coordinate. If there is still more than one, they pick the one with the smallest coordinate.
You are given the size of the dining room and the description of events. Each event is either the arrival or departure of a person. For each arrival, you must determine which table they occupy.
The first line contains integers , , separated by spaces (1 \leq N, M \leq 5000, 0 \leq Q \leq 100). The next lines describe the events. If the -th event is the arrival of an extrovert, the -th line contains the string ext; if it is the arrival of an introvert, the line contains int; if the event is a departure, the line contains a -based index (among all events) of the event describing their arrival.
It is guaranteed that the input is valid: for every arriving person, there is always at least one free table at the moment of arrival, and for every departure, the index refers to a valid arrival event and that person is still in the dining room.
For each arrival, print a line containing two integers, separated by a space, the coordinates of the occupied table.
Example 1