Amin and Emil play a game#9778
Amin and Emil are playing a card game in Bravotown, where Amin must clear an old minefield from World War II.
The game board is a grid with rows and columns, where each square cell initially contains a buried mine. We refer to the cell located at the intersection of the -th row and -th column as (, ). Since the task of removing mines is quite tiring, Amin will occasionally ask Emil questions of a specific type. Amin will specify a cell (, ) and one of four directions (up, down, left, right), and Emil must determine the nearest cell in the specified direction that still contains a mine, or indicate that no such cell exists. Which cell will Emil choose?
The first line contains three integers , , and — representing the dimensions of the field and the number of queries (1 \le n, m \le 2000; 1 \le q \le 10^6). The subsequent lines contain the queries. Each query begins with a character, followed by two integers x_i and y_i (1 \le x_i \le n, 1 \le y_i \le m). If the character is "c", it indicates that Amin has removed a mine from the cell (x_i, y_i). It is guaranteed that each cell will have its mine removed at most once. Otherwise, Amin is asking Emil to find the nearest cell to (x_i, y_i) that still contains a mine in the specified direction. If the character is "u", the direction is up; if "d", the direction is down; if "l", the direction is left; and if "r", the direction is right.
For each query, output the coordinates of the required cell, or "-1" if no such cell exists.
Example 1