#include #include #include #include #include #include #include #include #include #include using namespace std; template class BinaryIndexedTree_0_indexed{ void init(const vector &A){ for(int i=0; i tree; int N; BinaryIndexedTree_0_indexed(const int n) : tree(n+1,0), N(n){ } BinaryIndexedTree_0_indexed(const vector &A) : tree(A.size()+1,0), N(A.size()){ init(A); } //caution : position "i" must be 0-indexed void add(int i, const T x){ i += 1; while(i <= N){ tree[i] += x; i += i & -i; } } //get sums [0,i] T get_sum(int i){ i += 1; T ret=0; while(i>0){ ret += tree[i]; i -= i & -i; } return ret; } //get sums [from,to] T get_sums_range(const int from, const int to){ return get_sum(to) - get_sum(from-1); } //get at [i] T get_at(const int i){ return get_sum(i) - get_sum(i-1); } void print(){ for(int i=0; i> N >> Q; vector> BIT(2, BinaryIndexedTree_0_indexed(N*2)); for(int t=1; t<=Q; t++){ string x; int y,z; cin >> x >> y >> z; if(x=="R"){ y += N; y = y - t%(2*N); if(y<0) y += 2*N; BIT[0].add(y, z); }else if(x=="L"){ y += N; y = y + t%(2*N); if(y>=2*N) y -= 2*N; BIT[1].add(y, z); }else{ z--; long long ans = 0; for(int k=0; k<2; k++){ vector L(2); vector R(2); L[0] = -z + (N-1) + (k%2==0?-1:+1)*t%(2*N) ; R[0] = -y + (N-1) + (k%2==0?-1:+1)*t%(2*N) ; L[1] = +y + N + (k%2==0?-1:+1)*t%(2*N) ; R[1] = +z + N + (k%2==0?-1:+1)*t%(2*N) ; for(int i=0; i<2; i++){ if(L[i] < 0) L[i] += 2*N; if(L[i] >= 2*N) L[i] -= 2*N; if(R[i] < 0) R[i] += 2*N; if(R[i] >= 2*N) R[i] -= 2*N; if(L[i] > R[i]){ ans += BIT[k].get_sums_range(L[i],2*N-1); ans += BIT[k].get_sums_range(0,R[i]); }else{ ans += BIT[k].get_sums_range(L[i],R[i]); } } } cout << ans << endl; } /* for(int i=0; i<2; i++){ BIT[i].print(); } */ } return 0; }