#include <bits/stdc++.h>   using namespace std;   template <typename T>   struct Segtree {     int N;     vector<T> seg, lazy;     Segtree(int _n) : N(_n) {       seg.resize(4 * N, 0);       lazy.resize(4 * N, 0);     }     T join(T x, T y) { return max(x, y); }     void push(int x, int s, int e) {       if (!lazy[x]) return;       seg[x] = max(seg[x], lazy[x]);       if (s != e) {         lazy[2 * x] = max(lazy[2 * x], lazy[x]);         lazy[2 * x + 1] = max(lazy[2 * x + 1], lazy[x]);       }       lazy[x] = 0;     }     void build(int x, int s, int e) {       if (s == e) {         seg[x] = 0;         return;       }       int mid = (s + e) >> 1;       build(2 * x, s, mid);       build(2 * x + 1, mid + 1, e);       seg[x] = join(seg[2 * x], seg[2 * x + 1]);     }     void update(int x, int s, int e, int l, int r, T val) {       push(x, s, e);       if (s > r || e < l) return;       if (s >= l && e <= r) {         lazy[x] = val;         push(x, s, e);         return;       }       int mid = (s + e) >> 1;       update(2 * x, s, mid, l, r, val);       update(2 * x + 1, mid + 1, e, l, r, val);       seg[x] = join(seg[2 * x], seg[2 * x + 1]);     }     T query(int x, int s, int e, int l, int r) {       push(x, s, e);       if (e < l || s > r) return 0;       if (s >= l && e <= r) {         return seg[x];       }       int mid = (s + e) >> 1;       return join(query(2 * x, s, mid, l, r), query(2 * x + 1, mid + 1, e, l, r));     }     void update(int l, int r, T val) { update(1, 0, N - 1, l, r, val); }     T query(int l, int r) { return query(1, 0, N - 1, l, r); }   };   int main() {     ios::sync_with_stdio(0);     cin.tie(0);     int n, q;     cin >> n >> q;     vector<int> x(q), y(q), d(q), cc(1, 0);     for (int i = 0; i < q; ++i) {       char c;       cin >> x[i] >> y[i] >> c;       d[i] = (c ==  U );       cc.push_back(x[i]);       cc.push_back(y[i]);       cc.push_back(n + 1 - x[i]);       cc.push_back(n + 1 - y[i]);     }     sort(cc.begin(), cc.end());     cc.erase(unique(cc.begin(), cc.end()), cc.end());     Segtree<int> left(cc.size() + 1), up(cc.size() + 1);     for (int i = 0; i < q; ++i) {       x[i] = lower_bound(cc.begin(), cc.end(), x[i]) - cc.begin();       y[i] = lower_bound(cc.begin(), cc.end(), y[i]) - cc.begin();       if (d[i]) {         int id = up.query(y[i], y[i]);         up.update(y[i], y[i], y[i]);         cout << cc[y[i]] - cc[id] <<   n ;         id = lower_bound(cc.begin(), cc.end(), n + 1 - cc[id]) - cc.begin();         y[i] = lower_bound(cc.begin(), cc.end(), n + 1 - cc[y[i]]) - cc.begin();         left.update(y[i], id, x[i]);       } else {         int id = left.query(x[i], x[i]);         left.update(x[i], x[i], x[i]);         cout << cc[x[i]] - cc[id] <<   n ;         id = lower_bound(cc.begin(), cc.end(), n + 1 - cc[id]) - cc.begin();         x[i] = lower_bound(cc.begin(), cc.end(), n + 1 - cc[x[i]]) - cc.begin();         up.update(x[i], id, y[i]);       }     }   }   