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(); for (int i = 0; i < N; i++) { L.Insert(i, 0); R.Insert(i, 0); } 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 class Node { public Node L, R; public int Count; public long Val; //public long Min; //public long Max; public long Sum; public bool Reversed; public readonly uint Priority; static readonly XorShift random = new XorShift(); public Node(long val) { Val = val; Count = 1; Priority = random.Next(); //Min = val; //Max = val; Sum = val; } } public class XorShift { uint m = 2463534242; public uint Next() { m = m ^ m << 13; m = m ^ m >> 17; return m = m ^ m << 5; } } public Node Root; public int Count { get { return Root == null ? 0 : Root.Count; } } public static int Size(Node node) { return node == null ? 0 : node.Count; } //static long Min(Node node) { return node == null ? long.MaxValue : node.Min; } //static long Max(Node node) { return node == null ? long.MinValue : node.Max; } static long Sum(Node node) { return node == null ? 0 : node.Sum; } Node GenNode(long val) { return new Node(val); } static Node Update(Node node) { node.Count = 1 + Size(node.L) + Size(node.R); //node.Min = Math.Min(node.Val, Math.Min(Min(node.L), Min(node.R))); //node.Max = Math.Max(node.Val, Math.Max(Max(node.L), Max(node.R))); node.Sum = node.Val + Sum(node.L) + Sum(node.R); return node; } public long this[int i] { get { return GetRec(Root, i); } set { SetRec(Root, i, value); } } long GetRec(Node node, int index) { Debug.Assert(node != null); if (node.Reversed) PushDownReversed(node); int Lsize = Size(node.L); if (index == Lsize) return node.Val; if (index < Lsize) return GetRec(node.L, index); return GetRec(node.R, index - Lsize - 1); } void SetRec(Node node, int index, long val) { Debug.Assert(node != null); if (node.Reversed) PushDownReversed(node); int Lsize = Size(node.L); if (index == Lsize) node.Val = val; else if (index < Lsize) SetRec(node.L, index, val); else SetRec(node.R, index - Lsize - 1, val); Update(node); } public static Node Merge(Node L, Node R) { if (L == null) return R; if (R == null) return L; if (L.Reversed) PushDownReversed(L); if (R.Reversed) PushDownReversed(R); if (L.Priority > R.Priority) { L.R = Merge(L.R, R); return Update(L); } else { R.L = Merge(L, R.L); return Update(R); } } public static void Split(Node node, int index, out Node L, out Node R) { if (node == null) { L = R = null; return; } if (node.Reversed) PushDownReversed(node); int Lsize = Size(node.L); if (index == Lsize) { L = node.L; R = node; node.L = null; Update(node); return; } Node a, b; if (index < Lsize) { Split(node.L, index, out a, out b); node.L = b; L = a; R = Update(node); } else { Split(node.R, index - Lsize - 1, out a, out b); node.R = a; L = Update(node); R = b; } } public static void Split(Node node, int L, int R, out Node a, out Node b, out Node c) { Node t; Split(node, R, out t, out c); Split(t, L, out a, out b); } public void Insert(int index, long val) { Root = Insert(Root, GenNode(val), index); } Node Insert(Node node, Node newNode, int index) { if (node == null) return newNode; if (node.Reversed) PushDownReversed(node); if (newNode.Priority > node.Priority) { Node L, R; Split(node, index, out L, out R); return Merge(Merge(L, newNode), 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); return Update(node); } } public void RemoveAt(int index) { Root = RemoveAt(Root, index); } Node RemoveAt(Node node, int index) { if (node.Reversed) PushDownReversed(node); int Lsize = Size(node.L); if (index == Lsize) return Merge(node.L, node.R); if (index < Lsize) node.L = RemoveAt(node.L, index); else node.R = RemoveAt(node.R, index - Lsize - 1); return Update(node); } 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 == node.Count) return nF(node); if (node.Reversed) PushDownReversed(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 Reverse(int L = 0, int R = -1) { Root = Reverse(Root, L, R == -1 ? Count : 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)); } static void PushDownReversed(Node node) { Debug.Assert(node.Reversed); if (node.L != null) node.L.Reversed ^= true; if (node.R != null) node.R.Reversed ^= true; Node t = node.L; node.L = node.R; node.R = t; node.Reversed = false; Update(node); } } } 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; } }