using System; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Collections.Generic; using System.Diagnostics; using System.Numerics; using Enu = System.Linq.Enumerable; public class Program { public void Solve() { int N = Reader.Int(), Q = Reader.Int(); int last = 0; var L = new Treap(); var R = new Treap(); L.Build(new long[N]); R.Build(new long[N]); Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var q in Reader.StringTable(Q)) { int t = int.Parse(q[1]), x = int.Parse(q[2]), y = int.Parse(q[3]); int diff = t - last; last = t; Treap.Node La, Lb, Ra, Rb; int mid = diff % N; Treap.Split(L.Root, mid, out La, out Lb); Treap.Split(R.Root, N - mid, out Ra, out Rb); if (diff / N % 2 == 0) { L.Root = Treap.Merge(Lb, Treap.Reverse(Rb)); R.Root = Treap.Merge(Treap.Reverse(La), Ra); } else { L.Root = Treap.Merge(Treap.Reverse(Ra), La); R.Root = Treap.Merge(Rb, Treap.Reverse(Lb)); } if (q[0] == "L") L[x] += y; else if (q[0] == "R") R[x] += y; else Console.WriteLine(L.Sum(x, y) + R.Sum(x, y)); } Console.Out.Flush(); } public class Treap { public Node Root; public class Node { static readonly Random random = new Random(0); public Node _L, _R; public int Count; public long Val; public long RangeAdded; public long Min; public long Max; public long Sum; public bool Reversed; public readonly int Priority; public Node(long val) { Val = val; Count = 1; Priority = random.Next(); Min = val; Max = val; Sum = val; } public Node L { get { PushDown(); return _L; } set { PushDown(); _L = value; } } public Node R { get { PushDown(); return _R; } set { PushDown(); _R = value; } } public void PushDown() { if (!Reversed && RangeAdded == 0) return; if (_L != null) { _L.RangeAdded += RangeAdded; _L.Min += RangeAdded; _L.Max += RangeAdded; _L.Sum += RangeAdded * _L.Count; _L.Reversed ^= Reversed; } if (_R != null) { _R.RangeAdded += RangeAdded; _R.Min += RangeAdded; _R.Max += RangeAdded; _R.Sum += RangeAdded * _R.Count; _R.Reversed ^= Reversed; } if (Reversed) { var t = _L; _L = _R; _R = t; Reversed = false; } Val += RangeAdded; RangeAdded = 0; Update(this); } public override string ToString() { return Val + (_L == null ? "" : " L:" + _L.Val) + (_R == null ? "" : " R:" + _R.Val); } } public void Build(long[] A, int L = 0, int R = -1) { Root = BuildRec(A, L, R == -1 ? A.Length : R); } Node BuildRec(long[] A, int L, int R) { if (R == -1) R = A.Length; if (R - L <= 0) return null; int mid = L + R >> 1; var node = new Node(A[mid]); node.L = BuildRec(A, L, mid); node.R = BuildRec(A, mid + 1, R); Update(node); return node; } public int Count { get { return Size(Root); } } static int Size(Node n) { return n == null ? 0 : n.Count; } static Node Update(Node n) { n.Count = 1 + (n._L == null ? 0 : n._L.Count) + (n._R == null ? 0 : n._R.Count); n.Min = n.Val; n.Max = n.Val; if (n._L != null) { n.Min = Math.Min(n.Min, n._L.Min); n.Max = Math.Max(n.Max, n._L.Max); } if (n._R != null) { n.Min = Math.Min(n.Min, n._R.Min); n.Max = Math.Max(n.Max, n._R.Max); } n.Min += n.RangeAdded; n.Max += n.RangeAdded; n.Sum = n.Val + n.RangeAdded * n.Count + (n._L == null ? 0 : n._L.Sum) + (n._R == null ? 0 : n._R.Sum); return n; } long RangeQuery(Node node, int L, int R, long init, Func nF, Func F) { if (node == null || L >= R) return init; if (L == 0 && R == Size(node)) return nF(node); long res = init; int Lsize = Size(node.L); if (Lsize >= L && Lsize < R) res = node.Val; if (L < Lsize) res = F(res, RangeQuery(node.L, L, Math.Min(R, Lsize), init, nF, F)); if (R - Lsize - 1 > 0) res = F(res, RangeQuery(node.R, Math.Max(0, L - Lsize - 1), R - Lsize - 1, init, nF, F)); return res; } public long Min(int L, int R) { return RangeQuery(Root, L, R, long.MaxValue, n => n.Min, Math.Min); } public long Max(int L, int R) { return RangeQuery(Root, L, R, long.MinValue, n => n.Max, Math.Max); } public long Sum(int L, int R) { return RangeQuery(Root, L, R, 0, n => n.Sum, (a, b) => a + b); } public void RangeAdd(int L, int R, long val) { RangeAdd(Root, L, R, val); } void RangeAdd(Node node, int L, int R, long val) { if (node == null || L >= R) return; if (L == 0 && R == node.Count) { node.RangeAdded += val; Update(node); return; } int Lsize = Size(node.L); if (Lsize >= L && Lsize < R) node.Val += val; if (L < Lsize) RangeAdd(node.L, L, Math.Min(R, Lsize), val); if (R - Lsize - 1 > 0) RangeAdd(node.R, Math.Max(0, L - Lsize - 1), R - Lsize - 1, val); Update(node); } public long this[int index] { get { Debug.Assert(index >= 0 && index < Size(Root)); var node = Root; while (index != Size(node.L)) if (index < Size(node.L)) node = node.L; else { index -= Size(node.L) + 1; node = node.R; } return node.Val; } set { if (index < Size(Root)) RemoveAt(index); Insert(index, value); } } public static Node Merge(Node L, Node R) { if (L == null) return R; if (R == null) return L; if (L.Priority > R.Priority) { L.R = Merge(L.R, R); return Update(L); } R.L = Merge(L, R.L); return Update(R); } public static void Split(Node n, int index, out Node L, out Node R) { if (n == null) { L = R = null; return; } Node a, b; if (index <= Size(n.L)) { Split(n.L, index, out a, out b); n.L = b; L = a; R = Update(n); } else { Split(n.R, index - Size(n.L) - 1, out a, out b); n.R = a; L = Update(n); R = b; } } public static void Split(Node n, int L, int R, out Node a, out Node b, out Node c) { Node t; Split(n, R, out t, out c); Split(t, L, out a, out b); } public void Insert(int index, long val) { Root = Insert(Root, new Node(val), index); } public Node Insert(Node node, Node newNode, int index) { if (node == null || index == Size(node.L) || newNode.Priority > node.Priority) { Node L, R; Split(node, index, out L, out R); node = Merge(L, newNode); node = Merge(node, R); } else { if (index < Size(node.L)) node.L = Insert(node.L, newNode, index); else node.R = Insert(node.R, newNode, index - Size(node.L) - 1); Update(node); } return node; } public void RemoveAt(int index) { Root = RemoveAt(Root, index); } Node RemoveAt(Node node, int index) { if (node == null || index == Size(node.L)) { Node L1, R1, L2, R2; Split(node, index, out L1, out R1); Split(R1, 1, out L2, out R2); node = Merge(L1, R2); } else { if (index < Size(node.L)) node.L = RemoveAt(node.L, index); else node.R = RemoveAt(node.R, index - Size(node.L) - 1); Update(node); } return node; } public void Reverse(int L, int R) { Root = Reverse(Root, L, R); } public static Node Reverse(Node node, int L = 0, int R = -1) { if (node == null) return null; if (R == -1) R = Size(node); Node a, b, c; Split(node, L, R, out a, out b, out c); b.Reversed ^= true; return Merge(a, Merge(b, c)); } } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { A = new string[0]; } public static void Set(TextReader r) { reader = r; Init(); } public static void Set(string file) { reader = new StreamReader(file); Init(); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } static string[] Split(string s) { return s.Split(separator, op); } static T[] Range(int N, Func f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }