Background

Translated from CEOI 2013 Day 1。

The seats in the trams operating in Zagreb form a grid with $n$ rows and $2$ columns. The distance between two seats is the Euclidean distance (straight-line distance) between the centers of the corresponding grid squares.

Most passengers are socially anxious when using public transport. That is, when a passenger enters the tram, they choose an empty seat such that the distance to the nearest occupied seat is as large as possible. If there are multiple such seats, they always choose a seat with a smaller row number (because then they do not need to walk too far). If there are still multiple such seats, they choose the seat with the smaller column number (i.e., column $1$). After choosing a seat, the passenger stays there until they leave the tram. If the tram is empty, an entering passenger will always choose the seat in row $1$, column $1$.

Problem Description

You are given a sequence of events. Each event is either a passenger entering the tram or a passenger leaving the tram. You need to output where the passenger will sit when they enter. The tram is initially empty.

There are $m$ events in the input, numbered from $1$ to $m$ in the order they occur. There are two types of events: an E event means a passenger enters the tram, and an L event means a passenger leaves the tram. For an L event, an integer $p$ is also given, meaning that the passenger leaving in this event is the passenger who entered in event $p$.

The testdata guarantees that whenever a passenger tries to enter the tram, there is at least one empty seat in the tram.

Input Format

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

The next $m$ lines describe the events. Line $i$ describes event $i$: first a character E or L is given, and if the character is L, then a number $p_i$ is given. It is guaranteed 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 events in the input. For the $i$-th E event, output on line $i$ the seat number $r,c$ (row and column) chosen by that passenger, separated by a space.

3 7
E
E
E
L 2
E
L 1
E

1 1
3 2
1 2
3 1
1 1

13 9
E
E
E
E
E
E
E
E
E

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

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

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

Hint

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

For $45\%$ of the data, $n\le1500$.

For $65\%$ of the data, $m\le1500$.

For $100\%$ of the data, $n\le150000,m\le30000$.

The first three test points are samples.

Translated by ChatGPT 5