Dining Room
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 the dinner.
The dining room in this company can be represented as a rectangular grid N×M. In other words, each point with integer coordinates x, y (0 ≤ x ≤ N, 0 ≤ y ≤ M) contains a table. Each table is for one person.
We say that the (Euclidean) distance between points with coordinates (x_1, y_1) and (x_2, y_2) is equal to .
When an introvert comes to the dining room, he selects such a free table that the minimal distance from it to the nearest occupied table is as large as possible. If there are several tables with the largest minimal distance, he selects the one of them with the smallest x coordinate. If there are still several tables, he selects the one of them with the minimal y coordinate.
When an extrovert comes to the dining room, he selects such a free table that the maximal distance from it to the farthest occupied table is as small as possible. If there are several tables with the smallest maximal distance, he selects the one of them with the smallest x coordinate. If there are still several tables, he selects the one of them with the minimal y coordinate.
You are given the size of the dining room and the description of Q events. Each event is either an arrival or a departure of one person. For each arrival you have to find the table that he occupies.
Input
The first line on the input contains integers N, M, Q separated by spaces (1 ≤ N, M ≤ 5000, 0 ≤ Q ≤ 100). Next Q lines describe events. If the i'th event is an arrival of an extrovert, the i'th line contains single string "ext"; if the event is an arrival of an introvert, the line contains single string "int"; if the event is a departure of some person, the line contains the 1-based index (among all events) of the event that describes his arrival.
It is guaranteed that the input data is correct, i.e. for each arriving human there is at least one empty table in the dining room at the moment of his arrival, and for each event of the departure the index described in the line corresponds to an event of arrival and the person arrived in this event is still inside the dining room.
Output
For each arrival print a line containing two space-separated integers - the coordinates of the table being occupied.