Problem Background

Translated from CEOI 2013 Day 1.

The seats in the tram operating in Zagreb are arranged in an $n$ rows by $2$ columns grid. The distance between two seats is the Euclidean distance (straight-line distance) between the centers of the corresponding grid squares.

Most passengers experience social anxiety when using public transportation. This means that when a passenger enters the tram, they will choose an unoccupied seat such that the distance to the nearest occupied seat is maximized. If there are multiple such seats, they will always choose one with a smaller row number (as this means they do not have to walk too far). If there are still multiple such seats, they will choose the one with the smaller column number (i.e., column number $1$). After choosing a seat, the passenger will remain seated until they leave the tram. If the tram is empty, the entering passenger will always choose the seat at the first row and first column.

Problem Description

Given a series of events, each representing a passenger entering or leaving the tram. You need to output where the passenger will sit when they enter. The tram starts empty.

There are $m$ events in the input, numbered from $1$ to $m$ in the order they occur. There are two types of events: E events indicate a passenger entering the tram, and L events indicate a passenger leaving the tram. For L type events, an integer $p$ is also given, which represents the event number in which the passenger who is leaving entered the tram.

The test data ensures that whenever a passenger attempts to enter the tram, there is at least one empty seat available.

Input Format

The first line of input contains two integers $n$ and $m$.

The next $m$ lines describe the events. Each line starts with a character E or L. If the character is L, an integer $p_i$ follows, ensuring that event $p_i$ is of type E.

Output Format

The number of lines in the output should be equal to the number of E type events in the input. For the $i$-th E type event, output the row and column numbers $r, c$ of the seat chosen by the passenger, separated by a space, on the $i$-th line.

Sample Input and Output

Input Sample #1

3 7
E
E
E
L 2
E
L 1
E

Output Sample #1

1 1
3 2
1 2
3 1
1 1

Input Sample #2

13 9
E
E
E
E
E
E
E
E
E

Output Sample #2

1 1
13 2
7 1
4 2
10 1
2 2
3 1
5 1
6 2

Input Sample #3

10 9
E
E
E
E
L 3
E
E
L 6
E

Output Sample #3

1 1
10 2
5 2
7 1
4 2
2 2
4 1

Notes

For $25\%$ of the data, $n, m \leq 150$.

For $45\%$ of the data, $n \leq 1500$.

For $65\%$ of the data, $m \leq 1500$.

For $100\%$ of the data, $n \leq 150000, m \leq 30000$.

The first three test cases are examples.

见题面 Input 部分

见题面 Output 部分