#include <iostream>
#include <vector>
#include <set>
#include <queue>
#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;
}
};
struct Candidate {
int min_dist; // minimum squared distance to occupied seats
Seat seat;
Candidate(int d, Seat s) : min_dist(d), seat(s) {}
bool operator<(const Candidate& other) const {
if (min_dist != other.min_dist) return min_dist < other.min_dist;
if (seat.row != other.seat.row) return seat.row > other.seat.row;
return seat.col > other.seat.col;
}
};
int squared_dist(int r1, int c1, int r2, int c2) {
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
class TramSeating {
private:
int N;
set<Seat> occupied;
priority_queue<Candidate> candidate_heap;
void update_candidates_after_enter(const Seat& new_seat) {
// Check all adjacent free seats to update their min distances
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int r = new_seat.row + dr;
int c = new_seat.col + dc;
if (r >= 1 && r <= N && c >= 1 && c <= 2) {
Seat neighbor(r, c);
if (occupied.find(neighbor) == occupied.end()) {
int new_dist = squared_dist(r, c, new_seat.row, new_seat.col);
update_seat_distance(neighbor, new_dist);
}
}
}
}
}
void update_seat_distance(const Seat& seat, int new_dist) {
// We'd need to update the heap, but since we can't efficiently update,
// we'll use a lazy approach: push new candidate and ignore outdated ones
candidate_heap.push(Candidate(new_dist, seat));
}
int calculate_min_distance(const Seat& seat) {
if (occupied.empty()) return 1e9;
int min_dist = 1e9;
// Check all occupied seats (this is O(M) but M <= 30,000)
for (const Seat& occ : occupied) {
int dist = squared_dist(seat.row, seat.col, occ.row, occ.col);
if (dist < min_dist) {
min_dist = dist;
}
if (min_dist == 1) break; // Can't get smaller
}
return min_dist;
}
public:
TramSeating(int n) : N(n) {}
Seat add_passenger() {
if (occupied.empty()) {
Seat new_seat(1, 1);
occupied.insert(new_seat);
// Initialize heap with all seats
initialize_heap();
return new_seat;
}
// Find best seat using heap (lazy deletion)
while (true) {
Candidate best = candidate_heap.top();
candidate_heap.pop();
// Check if seat is still free and distance is still valid
if (occupied.find(best.seat) != occupied.end()) continue;
int actual_dist = calculate_min_distance(best.seat);
if (actual_dist == best.min_dist) {
// This candidate is valid
occupied.insert(best.seat);
update_candidates_after_enter(best.seat);
return best.seat;
} else {
// Push updated candidate
candidate_heap.push(Candidate(actual_dist, best.seat));
}
}
}
void remove_passenger(const Seat& seat) {
occupied.erase(seat);
// When removing, we need to update distances of nearby seats
// For simplicity, we'll just push them back to heap with recalculated distances
update_candidates_after_leave(seat);
}
void update_candidates_after_leave(const Seat& removed_seat) {
// Update all seats in nearby rows
for (int r = max(1, removed_seat.row - 2); r <= min(N, removed_seat.row + 2); r++) {
for (int c = 1; c <= 2; c++) {
Seat seat(r, c);
if (occupied.find(seat) == occupied.end()) {
int dist = calculate_min_distance(seat);
candidate_heap.push(Candidate(dist, seat));
}
}
}
}
void initialize_heap() {
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= 2; c++) {
Seat seat(r, c);
if (occupied.find(seat) == occupied.end()) {
int dist = calculate_min_distance(seat);
candidate_heap.push(Candidate(dist, seat));
}
}
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M;
TramSeating tram(N);
vector<Seat> passenger_seat(M + 1);
vector<bool> active(M + 1, false);
int passenger_id = 0;
for (int event_id = 1; event_id <= M; event_id++) {
char type;
cin >> type;
if (type == 'E') {
passenger_id++;
Seat seat = tram.add_passenger();
passenger_seat[passenger_id] = seat;
active[passenger_id] = true;
cout << seat.row << " " << seat.col << "\n";
} else { // 'L'
int p;
cin >> p;
if (active[p]) {
tram.remove_passenger(passenger_seat[p]);
active[p] = false;
}
}
}
return 0;
}
