#include <bits/stdc++.h>
using namespace std;
struct Seat {
int row, col;
};
struct Candidate {
long long dist2; // lưu bình phương khoảng cách để so sánh
int row, col;
int L, R; // interval boundaries (occupied rows around)
bool operator<(const Candidate& o) const {
if (dist2 != o.dist2) return dist2 < o.dist2; // max-heap
if (row != o.row) return row > o.row;
return col > o.col;
}
};
int N, M;
vector<Seat> answer; // lưu ghế đã chọn cho mỗi event E
vector<bool> isEnter; // đánh dấu sự kiện nào là E
vector<vector<bool>> taken; // taken[row][col]
priority_queue<Candidate> pq;
set<int> occRows;
bool validCandidate(const Candidate& c) {
if (c.row < 1 || c.row > N) return false;
if (taken[c.row][c.col]) return false;
// kiểm tra interval còn hợp lệ
auto itL = occRows.lower_bound(c.L);
if (itL == occRows.end() || *itL != c.L) return false;
auto itR = occRows.lower_bound(c.R);
if (itR == occRows.end() || *itR != c.R) return false;
return true;
}
// thêm ứng viên cho interval (L,R)
void addInterval(int L, int R) {
if (L > R) return;
int mid = (L + R) / 2;
// ta thử cả 2 cột
for (int col = 1; col <= 2; col++) {
long long dL = 1LL*(mid-L)*(mid-L) + (col==1?0:1);
long long dR = 1LL*(R-mid)*(R-mid) + (col==2?0:1);
long long mind = min(dL, dR);
Candidate c = {mind, mid, col, L, R};
pq.push(c);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
answer.resize(M+1);
isEnter.resize(M+1);
taken.assign(N+1, vector<bool>(3,false));
for (int k = 1; k <= M; k++) {
char t;
cin >> t;
if (t == 'E') {
isEnter[k] = true;
Seat chosen;
if (occRows.empty()) {
chosen = {1,1};
} else {
// lấy ứng viên hợp lệ nhất
while (!pq.empty() && !validCandidate(pq.top())) pq.pop();
Candidate best = pq.top(); pq.pop();
chosen = {best.row, best.col};
}
taken[chosen.row][chosen.col] = true;
answer[k] = chosen;
cout << chosen.row << " " << chosen.col << "\n";
// cập nhật occRows và intervals
if (!occRows.count(chosen.row)) {
// lần đầu có người ở row này
auto it = occRows.insert(chosen.row).first;
int L = (it==occRows.begin()?1:*prev(it));
int R = (next(it)==occRows.end()?N:*next(it));
// thêm interval trái
if (it != occRows.begin()) addInterval(L, chosen.row);
// thêm interval phải
if (next(it) != occRows.end()) addInterval(chosen.row, R);
// nếu biên
if (it == occRows.begin()) addInterval(1, chosen.row);
if (next(it) == occRows.end()) addInterval(chosen.row, N);
}
} else { // L
int p; cin >> p;
Seat s = answer[p];
taken[s.row][s.col] = false;
// nếu cả 2 ghế hàng đó trống thì xóa row khỏi occRows
if (!taken[s.row][1] && !taken[s.row][2]) {
auto it = occRows.find(s.row);
int L = (it==occRows.begin()?1:*prev(it));
int R = (next(it)==occRows.end()?N:*next(it));
occRows.erase(it);
// merge interval
addInterval(L,R);
}
}
}
return 0;
}
