#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Seat {
int row, col;
};
int squared_distance(int r1, int c1, int r2, int c2) {
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
int main() {
int N, M;
cin >> N >> M;
vector<vector<bool>> occupied(N + 1, vector<bool>(3, false));
vector<Seat> passenger_seat(M + 1);
vector<bool> active(M + 1, false);
int passenger_count = 0;
for (int event_id = 1; event_id <= M; event_id++) {
char type;
cin >> type;
if (type == 'E') {
passenger_count++;
int current_passenger = passenger_count;
if (passenger_count == 1) {
passenger_seat[current_passenger] = {1, 1};
occupied[1][1] = true;
cout << "1 1\n";
active[current_passenger] = true;
continue;
}
Seat best_seat = {0, 0};
int best_min_dist = -1;
// Duyệt qua tất cả ghế trống
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= 2; c++) {
if (!occupied[r][c]) {
// Tính khoảng cách NHỎ NHẤT từ ghế (r,c) tới bất kỳ ghế occupied nào
int min_dist = 1000000000;
for (int rr = 1; rr <= N; rr++) {
for (int cc = 1; cc <= 2; cc++) {
if (occupied[rr][cc]) {
int dist = squared_distance(r, c, rr, cc);
if (dist < min_dist) {
min_dist = dist;
}
}
}
}
// So sánh theo yêu cầu: min_dist lớn nhất, r nhỏ nhất, c nhỏ nhất
if (min_dist > best_min_dist ||
(min_dist == best_min_dist && r < best_seat.row) ||
(min_dist == best_min_dist && r == best_seat.row && c < best_seat.col)) {
best_min_dist = min_dist;
best_seat = {r, c};
}
}
}
}
passenger_seat[current_passenger] = best_seat;
occupied[best_seat.row][best_seat.col] = true;
cout << best_seat.row << " " << best_seat.col << "\n";
active[current_passenger] = true;
} else { // 'L'
int p;
cin >> p;
if (active[p]) {
Seat seat = passenger_seat[p];
occupied[seat.row][seat.col] = false;
active[p] = false;
}
}
}
return 0;
}
