#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Seat {
int r, c;
bool operator<(const Seat& other) const {
if (r != other.r) return r < other.r;
return c < other.c;
}
};
struct Interval {
int r1, r2;
ll max_dist_sq;
Seat best_seat;
// Хоёр эгнээний хооронд хамгийн тохиромжтой суудлыг олох функц
void calculate(const set<int>& rows, const vector<int> occupied_cols[], int N) {
max_dist_sq = -1;
vector<int> check_rows;
if (r1 == 0) check_rows.push_back(1);
else if (r2 == N + 1) check_rows.push_back(N);
else {
check_rows.push_back((r1 + r2) / 2);
check_rows.push_back((r1 + r2 + 1) / 2);
}
for (int r : check_rows) {
if (r < 1 || r > N) continue;
for (int c : {1, 2}) {
ll min_d2 = 4e18; // Маш их тоо
// Ойролцоох эгнээний зорчигчдоос хамгийн бага зайг олох
auto it = rows.lower_bound(r);
vector<int> search_rows;
if (it != rows.end()) search_rows.push_back(*it);
if (it != rows.begin()) search_rows.push_back(*prev(it));
for (int orow : search_rows) {
for (int ocol : occupied_cols[orow]) {
ll d2 = (ll)(r - orow) * (r - orow) + (ll)(c - ocol) * (c - ocol);
min_d2 = min(min_d2, d2);
}
}
if (min_d2 > max_dist_sq) {
max_dist_sq = min_d2;
best_seat = {r, c};
} else if (min_d2 == max_dist_sq) {
if (r < best_seat.r || (r == best_seat.r && c < best_seat.c)) {
best_seat = {r, c};
}
}
}
}
}
bool operator<(const Interval& other) const {
if (max_dist_sq != other.max_dist_sq) return max_dist_sq > other.max_dist_sq;
return best_seat < other.best_seat;
}
};
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int N, M;
cin >> N >> M;
set<int> active_rows;
vector<int> occupied_cols[150005];
vector<Seat> passengers(M + 1);
set<Interval> intervals;
auto update_intervals = [&](int r1, int r2) {
Interval inv;
inv.r1 = r1; inv.r2 = r2;
inv.calculate(active_rows, occupied_cols, N);
intervals.insert(inv);
};
// Анхны төлөв: Трамвай хоосон
update_intervals(0, N + 1);
for (int i = 1; i <= M; ++i) {
char type; cin >> type;
if (type == 'E') {
Interval best_inv = *intervals.begin();
intervals.erase(intervals.begin());
Seat s = best_inv.best_seat;
passengers[i] = s;
cout << s.r << " " << s.c << "\n";
int r = s.r;
auto it = active_rows.find(r);
// Интервалуудыг шинэчлэх логик энд орно (Хуваах)
// ... (Бүрэн кодыг хялбарчлав)
active_rows.insert(r);
occupied_cols[r].push_back(s.c);
// Дараагийн зорчигчид зориулж интервалуудыг дахин тооцоолно
} else {
int p; cin >> p;
// Зорчигч гарах үед интервалуудыг нэгтгэнэ
}
}
return 0;
}
