#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
struct Seat {
int row, col;
Seat(int r, int c) : row(r), col(c) {}
bool operator<(const Seat& other) const {
if (row != other.row) return row < other.row;
return col < other.col;
}
};
struct Event {
char type;
int passenger_id;
};
struct FreeSegment {
int start_row, end_row;
int min_distance;
Seat best_seat;
FreeSegment(int s, int e, int dist, Seat seat)
: start_row(s), end_row(e), min_distance(dist), best_seat(seat) {}
bool operator<(const FreeSegment& other) const {
if (min_distance != other.min_distance)
return min_distance < other.min_distance;
if (best_seat.row != other.best_seat.row)
return best_seat.row > other.best_seat.row;
return best_seat.col > other.best_seat.col;
}
};
int squared_distance(int r1, int c1, int r2, int c2) {
int dr = r1 - r2;
int dc = c1 - c2;
return dr * dr + dc * dc;
}
int compute_min_distance(const Seat& seat, const set<Seat>& occupied) {
if (occupied.empty()) return 1e9;
int min_dist = 1e9;
// Check nearby seats in both directions
auto it = occupied.lower_bound(seat);
// Check successor
if (it != occupied.end()) {
min_dist = min(min_dist, squared_distance(seat.row, seat.col, it->row, it->col));
}
// Check predecessor
if (it != occupied.begin()) {
--it;
min_dist = min(min_dist, squared_distance(seat.row, seat.col, it->row, it->col));
}
// Also check same row but different column
Seat other_col(seat.row, 3 - seat.col);
it = occupied.find(other_col);
if (it != occupied.end()) {
min_dist = min(min_dist, 1); // distance = 1
}
return min_dist;
}
Seat find_best_seat(int start_row, int end_row, const set<Seat>& occupied) {
Seat best_seat(0, 0);
int max_min_dist = -1;
for (int r = start_row; r <= end_row; r++) {
for (int c = 1; c <= 2; c++) {
Seat candidate(r, c);
if (occupied.find(candidate) == occupied.end()) {
int min_dist = compute_min_distance(candidate, occupied);
if (min_dist > max_min_dist ||
(min_dist == max_min_dist &&
(r < best_seat.row || (r == best_seat.row && c < best_seat.col)))) {
max_min_dist = min_dist;
best_seat = candidate;
}
}
}
}
return best_seat;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
vector<Event> events(M);
vector<Seat> passenger_seat(M + 1, Seat(0, 0)); // passenger_id -> seat
set<Seat> occupied;
set<int> occupied_rows;
// Initialize boundaries
occupied_rows.insert(0);
occupied_rows.insert(N + 1);
priority_queue<FreeSegment> segments;
for (int i = 0; i < M; i++) {
char type;
cin >> type;
if (type == 'E') {
Seat chosen(0, 0);
if (occupied.empty()) {
// First passenger always gets (1, 1)
chosen = Seat(1, 1);
} else {
// Find best seat by checking all free seats
int max_min_dist = -1;
// Check all rows and columns
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= 2; c++) {
Seat candidate(r, c);
if (occupied.find(candidate) == occupied.end()) {
int min_dist = compute_min_distance(candidate, occupied);
if (min_dist > max_min_dist ||
(min_dist == max_min_dist &&
(r < chosen.row || (r == chosen.row && c < chosen.col)))) {
max_min_dist = min_dist;
chosen = candidate;
}
}
}
}
}
occupied.insert(chosen);
occupied_rows.insert(chosen.row);
passenger_seat[i + 1] = chosen;
cout << chosen.row << " " << chosen.col << "\n";
} else { // type == 'L'
int passenger_id;
cin >> passenger_id;
Seat seat_to_free = passenger_seat[passenger_id];
occupied.erase(seat_to_free);
// Update occupied_rows if no other seats in this row are occupied
bool row_still_occupied = false;
for (int c = 1; c <= 2; c++) {
if (occupied.find(Seat(seat_to_free.row, c)) != occupied.end()) {
row_still_occupied = true;
break;
}
}
if (!row_still_occupied) {
occupied_rows.erase(seat_to_free.row);
}
}
}
return 0;
}
