#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() template class BIT { public: std::vector data; // [1,n] BIT() {} BIT(int n) { init(n); } void init(int n) { data.resize((1LL<<(int)ceil(log2(n))), 0); } // a[i] += x O(log(n)) void add(int i, int x) { int maxN = data.size()+1; // 2 冪 for (int k = i+1; k <= maxN; k += (k & -k)) data[k-1] += x; } // a[0]+...+a[i] O(log(n)) T sum(int i) { T s = 0; for (int k = i+1; k > 0; k -= (k & -k)) s += data[k-1]; return s; } T operator[](int i) { return sum(i)-sum(i-1); } }; using namespace std; class SegmentFishing { public: void solve(void) { int N,Q; cin>>N>>Q; int t = 0; int B = 2*N; // 配列に含まれる魚を移動するのではなくて,魚の格納インデックスが時間毎に // 変化すると考える。 // 長さ 2*N の配列を考えて N-1 -> N, 2*N -> 0 とリング上につながっていて、 // 0~N-1 が右向き、N~2*n-1 が左向きとみなすことで端の魚の向きの反転を表現できる。 // 区間の総和を計算するには BIT をつかえばよい。 BIT ring(B); // O(Q*log(N)) while (Q--) { char x; int y,z; cin>>x>>y>>z; switch (x) { case 'R': ring.add((y-t+B)%B, z); break; case 'L': ring.add((B-1-y-t+B)%B, z); break; case 'C': { int cnt = 0; --z; // [y,z) -> [y,z-1] 閉区間で扱う for (int i = 0; i < 2; ++i) { int l,r; if (i == 0) { l = (y-t+B)%B; r = (z-t+B)%B; } else { r = (B-1-y-t+B)%B; l = (B-1-z-t+B)%B; } int add = ring.sum(r) - ring.sum(l-1); // 配列の末尾をまたぐケース if (r < l) add += ring.sum(B-1); cnt += add; } cout< B) t -= B; } } }; #if 1 int main(int argc, char *argv[]) { ios::sync_with_stdio(false); auto obj = new SegmentFishing(); obj->solve(); delete obj; return 0; } #endif