#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;
struct Seat {
int row, col;
Seat(int r = 0, int c = 0) : row(r), col(c) {}
bool operator<(const Seat& other) const {
if (row != other.row) return row < other.row;
return col < other.col;
}
};
// For maintaining gaps between occupied rows
struct Gap {
int start, end; // row numbers
int size() const { return end - start - 1; }
bool operator<(const Gap& other) const {
if (size() != other.size()) return size() > other.size();
return start < other.start;
}
};
int squared_dist(int r1, int c1, int r2, int c2) {
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
int min_dist_to_occupied(const Seat& s, const set<Seat>& occupied) {
int min_dist = 1e9;
// Check same row, different column
Seat other_col(s.row, 3 - s.col);
if (occupied.find(other_col) != occupied.end()) {
min_dist = min(min_dist, 1);
}
// Find nearest occupied seats using binary search
auto it = occupied.lower_bound(s);
// Check next occupied seats
if (it != occupied.end()) {
min_dist = min(min_dist, squared_dist(s.row, s.col, it->row, it->col));
}
// Check previous occupied seats
if (it != occupied.begin()) {
--it;
min_dist = min(min_dist, squared_dist(s.row, s.col, it->row, it->col));
}
return min_dist;
}
Seat find_best_in_gap(int start_row, int end_row, const set<Seat>& occupied) {
Seat best(0, 0);
int best_dist = -1;
// Only check boundary rows for efficiency
vector<int> rows_to_check = {start_row + 1, end_row - 1, (start_row + end_row) / 2};
for (int r : rows_to_check) {
if (r <= start_row || r >= end_row) continue;
for (int c = 1; c <= 2; c++) {
Seat candidate(r, c);
if (occupied.find(candidate) == occupied.end()) {
int dist = min_dist_to_occupied(candidate, occupied);
if (dist > best_dist ||
(dist == best_dist && (r < best.row || (r == best.row && c < best.col)))) {
best_dist = dist;
best = candidate;
}
}
}
}
return best;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
set<Seat> occupied;
set<int> occupied_rows;
map<int, int> enter_event_to_passenger;
vector<Seat> passenger_seat(M + 1);
int passenger_count = 0;
// Add boundary rows
occupied_rows.insert(0);
occupied_rows.insert(N + 1);
for (int event_id = 1; event_id <= M; event_id++) {
char type;
cin >> type;
if (type == 'E') {
passenger_count++;
enter_event_to_passenger[event_id] = passenger_count;
if (occupied.empty()) {
// First passenger gets (1, 1)
Seat seat(1, 1);
occupied.insert(seat);
occupied_rows.insert(1);
passenger_seat[passenger_count] = seat;
cout << "1 1\n";
continue;
}
// Find best seat by checking gaps between occupied rows
Seat best_seat(0, 0);
int best_min_dist = -1;
// Check all gaps
auto it = occupied_rows.begin();
int prev = *it;
++it;
while (it != occupied_rows.end()) {
int curr = *it;
if (curr - prev > 1) {
// This is a gap of free rows
Seat candidate = find_best_in_gap(prev, curr, occupied);
int dist = min_dist_to_occupied(candidate, occupied);
if (dist > best_min_dist ||
(dist == best_min_dist &&
(candidate.row < best_seat.row ||
(candidate.row == best_seat.row && candidate.col < best_seat.col)))) {
best_min_dist = dist;
best_seat = candidate;
}
}
prev = curr;
++it;
}
occupied.insert(best_seat);
occupied_rows.insert(best_seat.row);
passenger_seat[passenger_count] = best_seat;
cout << best_seat.row << " " << best_seat.col << "\n";
} else { // type == 'L'
int enter_event;
cin >> enter_event;
int passenger_id = enter_event_to_passenger[enter_event];
Seat seat = passenger_seat[passenger_id];
occupied.erase(seat);
// Check if row still has occupied seats
bool row_still_occupied = false;
Seat other_col(seat.row, 3 - seat.col);
if (occupied.find(other_col) != occupied.end()) {
row_still_occupied = true;
}
if (!row_still_occupied) {
occupied_rows.erase(seat.row);
}
}
}
return 0;
}
