using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using System.Text; using static System.Math; using static Extensions; using static MathExtensions; public static class Program { public struct Node { public long T, Index; } public struct Monoid : IMonoid { public Node? Unit => null; public Node? Append(Node? left, Node? right) { if (left is Node l && right is Node r) { var t = Max((r.Index - l.Index) * 3 + l.T, r.T); var i = Max(l.Index, r.Index); return new Node { T = t, Index = i }; } else return left ?? right; } } public struct Apply : IBinaryOperator { public Node? Operate(Node? left, long right) => left is Node node ? new Node { T = node.T + right, Index = node.Index } : left; } public static void Solve() { var n = I; var t = Repeat(n - 1, () => L).ToArray(); var segtree = new LazySegmentTree( t.Select((x, i) => new Node { T = x, Index = i }).Cast().ToArray()); var m = I; Repeat(m, () => { var (l, r, d) = (I - 1, I - 1, L); segtree[l, r].Apply(d); var ans = segtree[0, n - 1].Concat(); Console.WriteLine(ans.Value.T + 3); }); } #region Scanners static Scanner _scanner; static char C => _scanner.NextChar(); static string S => _scanner.NextString(); static int I => _scanner.NextInt(); static long L => _scanner.NextLong(); static BigInteger B => _scanner.NextBigInteger(); static double D => _scanner.NextDouble(); static decimal M => _scanner.NextDecimal(); #endregion public static void Main() { var sw = new StreamWriter(Console.OpenStandardOutput()); sw.NewLine = "\n"; #if DEBUG sw.AutoFlush = true; #else sw.AutoFlush = false; #endif Console.SetOut(sw); _scanner = new Scanner(Console.OpenStandardInput()); Solve(); Console.Out.Flush(); } } public static partial class Extensions { } #region Library // hotfixed public class Scanner { private readonly Stream _stream; private const int _bufferSize = 1024; private readonly byte[] _buf = new byte[_bufferSize]; private int _len, _ptr; public Scanner(Stream stream) { _stream = stream; } public byte ReadByte() { if (_ptr >= _len) { _len = _stream.Read(_buf, 0, _bufferSize); _ptr = 0; } return _buf[_ptr++]; } public char ReadChar() => (char)ReadByte(); public string ReadLine() { var r = new StringBuilder(); if (_ptr == 0) r.Append(ReadChar()); for (; _ptr < _len; _ptr++) r.Append((char)_buf[_ptr]); return r.ToString(); } public char NextChar() => char.Parse(NextString()); public string NextString() { var r = new StringBuilder(); var b = ReadChar(); #if DEBUG while (b != ' ' && b != '\r') { r.Append(b); b = ReadChar(); } if (b == '\r') ReadChar(); #else while (b != ' ' && b != '\n') { r.Append(b); b = ReadChar(); } #endif return r.ToString(); } public int NextInt() => (int)NextLong(); public long NextLong() { var r = 0L; var b = ReadByte(); var n = b == '-'; if (n) b = ReadByte(); #if DEBUG while (b != ' ' && b != '\r') #else while (b != ' ' && b != '\n') #endif { r = r * 10 + b - '0'; b = ReadByte(); } #if DEBUG if (b == '\r') ReadChar(); #endif return n ? -r : r; } public BigInteger NextBigInteger() { var r = new BigInteger(); var b = ReadByte(); var n = b == '-'; if (n) b = ReadByte(); #if DEBUG while (b != ' ' && b != '\r') #else while (b != ' ' && b != '\n') #endif { r = r * 10 + b - '0'; b = ReadByte(); } #if DEBUG if (b == '\r') ReadChar(); #endif return n ? -r : r; } public double NextDouble() { var i = 0L; var b = ReadByte(); var n = b == '-'; if (n) b = ReadByte(); #if DEBUG while (b != '.' && b != ' ' && b != '\r') #else while (b != '.' && b != ' ' && b != '\n') #endif { i = i * 10 + b - '0'; b = ReadByte(); } #if DEBUG if (b == '\r') ReadByte(); #endif if (b != '.') return n ? -i : i; b = ReadByte(); var f = 0L; var p = 0; #if DEBUG while (b != ' ' && b != '\r') #else while (b != ' ' && b != '\n') #endif { f = f * 10 + b - '0'; b = ReadByte(); p++; } #if DEBUG if (b == '\r') ReadByte(); #endif var r = i + (double)f / MathExtensions.Pow(10, p); return n ? -r : r; } public decimal NextDecimal() => decimal.Parse(NextString()); public T Next(Converter parser) => parser(NextString()); } public interface IMonoid { T Unit { get; } T Append(T left, T right); } public struct MinMonoid_Int32 : IMonoid { public int Unit => int.MaxValue; public int Append(int left, int right) => Min(left, right); } public struct MaxMonoid_Int32 : IMonoid { public int Unit => int.MinValue; public int Append(int left, int right) => Max(left, right); } public struct MinMonoid_Int64 : IMonoid { public long Unit => long.MaxValue; public long Append(long left, long right) => Min(left, right); } public struct MaxMonoid_Int64 : IMonoid { public long Unit => long.MinValue; public long Append(long left, long right) => Max(left, right); } public interface IGroup : IMonoid { T Invert(T value); } public struct SumGroup_Int32 : IGroup { public int Unit => 0; public int Append(int left, int right) => left + right; public int Invert(int value) => -value; } public struct SumGroup_Int64 : IGroup { public long Unit => 0L; public long Append(long left, long right) => left + right; public long Invert(long value) => -value; } public interface IBinaryOperator { TResult Operate(TLeft left, TRight right); } public class LazySegmentTree where TMonoid : struct, IMonoid where TOperandMonoid : struct, IMonoid where TOperator : struct, IBinaryOperator { public class Segment { [DebuggerBrowsable(DebuggerBrowsableState.Never)] private readonly LazySegmentTree _outer; public Segment(LazySegmentTree outer) { _outer = outer; } public int L { get; set; } public int R { get; set; } public void Apply(TOperand x) => Apply(0, 0, _outer._size, this.L, this.R, x); public T Concat() => Concat(0, 0, _outer._size, this.L, this.R); private void Apply(int i, int il, int ir, int l, int r, TOperand x) { if (ir <= l || r <= il) return; else if (l <= il && ir <= r) { _outer._t[i] = _operator.Operate(_outer._t[i], x); _outer._ope[i] = _opeMonoid.Append(x, _outer._ope[i]); } else { Apply((i << 1) + 1, il, (il + ir) >> 1, 0, _outer._size, _outer._ope[i]); Apply((i << 1) + 1, il, (il + ir) >> 1, l, r, x); Apply((i << 1) + 2, (il + ir) >> 1, ir, 0, _outer._size, _outer._ope[i]); Apply((i << 1) + 2, (il + ir) >> 1, ir, l, r, x); _outer._t[i] = _monoid.Append(_outer._t[(i << 1) + 1], _outer._t[(i << 1) + 2]); _outer._ope[i] = _opeMonoid.Unit; } } private T Concat(int i, int il, int ir, int l, int r) { if (ir <= l || r <= il) return _monoid.Unit; else if (l <= il && ir <= r) return _outer._t[i]; else return _operator.Operate(_monoid.Append( Concat((i << 1) + 1, il, (il + ir) >> 1, l, r), Concat((i << 1) + 2, (il + ir) >> 1, ir, l, r)), _outer._ope[i]); } } [DebuggerBrowsable(DebuggerBrowsableState.Never)] private static readonly TMonoid _monoid = default(TMonoid); [DebuggerBrowsable(DebuggerBrowsableState.Never)] private static readonly TOperandMonoid _opeMonoid = default(TOperandMonoid); [DebuggerBrowsable(DebuggerBrowsableState.Never)] private static readonly TOperator _operator = default(TOperator); [DebuggerBrowsable(DebuggerBrowsableState.Never)] private readonly Segment _segment; private readonly T[] _t; private readonly TOperand[] _ope; private readonly int _size; public LazySegmentTree(int length) : this() { if (length > (int.MaxValue >> 1) + 1) throw new ArgumentException(); _size = 1; while (_size < length) _size <<= 1; _t = Enumerable.Repeat(_monoid.Unit, _size << 1).ToArray(); _ope = Enumerable.Repeat(_opeMonoid.Unit, _size << 1).ToArray(); this.Length = length; } public LazySegmentTree(IReadOnlyList collection) : this() { if (collection.Count > (int.MaxValue >> 1) + 1) throw new ArgumentException(); _size = 1; while (_size < collection.Count) _size <<= 1; _t = new T[_size << 1]; for (var i = 0; i < _size; i++) _t[i + _size - 1] = i < collection.Count ? collection[i] : _monoid.Unit; for (var i = _size - 2; i >= 0; i--) _t[i] = _monoid.Append(_t[(i << 1) + 1], _t[(i << 1) + 2]); _ope = Enumerable.Repeat(_opeMonoid.Unit, _size << 1).ToArray(); this.Length = collection.Count; } private LazySegmentTree() { _segment = new Segment(this); } public int Length { get; } public Segment this[int i] => this[i, i]; public Segment this[int l, int r] { get { _segment.L = l; _segment.R = r + 1; return _segment; } } // for debug [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public IEnumerable Values { get { for (var i = 0; i < this.Length; i++) yield return this[i].Concat(); } } } [DebuggerStepThrough] public static partial class Extensions { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void Assert(bool condition) { if (!condition) throw new Exception("Assertion failed"); } public static string AsString(this IEnumerable source) => new string(source.ToArray()); public static Dictionary Bucket(this IEnumerable source) where T : IEquatable { var dict = new Dictionary(); foreach (var item in source) if (dict.ContainsKey(item)) dict[item]++; else dict[item] = 1; return dict; } public static int[] Bucket(this IEnumerable source, int maxValue, Func selector) { var arr = new int[maxValue + 1]; foreach (var item in source) arr[selector(item)]++; return arr; } public static IEnumerable CumSum(this IEnumerable source) { var sum = 0; foreach (var item in source) yield return sum += item; } public static IEnumerable CumSum(this IEnumerable source) { var sum = 0L; foreach (var item in source) yield return sum += item; } public static void Exit(int exitCode) { Console.Out.Flush(); Environment.Exit(exitCode); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void ForEach(this IEnumerable source, Action action) { foreach (var item in source) action(item); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void ForEach(this IEnumerable source, Func func) { foreach (var item in source) func(item); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void ForEach(this IEnumerable source, Action action) { var i = 0; foreach (var item in source) action(item, i++); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void ForEach(this IEnumerable source, Func func) { var i = 0; foreach (var item in source) func(item, i++); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void Repeat(int count, Action action) { for (var i = 0; i < count; i++) action(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void Repeat(int count, Action action) { for (var i = 0; i < count; i++) action(i); } public static IEnumerable Repeat(int count, Func func) { for (var i = 0; i < count; i++) yield return func(); } public static IEnumerable Repeat(int count, Func func) { for (var i = 0; i < count; i++) yield return func(i); } public static void Swap(ref T x, ref T y) { var tmp = x; x = y; y = tmp; } public static (T1[], T2[]) Unzip(this ICollection<(T1, T2)> source) { var ts1 = new T1[source.Count]; var ts2 = new T2[source.Count]; var i = 0; foreach (var (t1, t2) in source) { ts1[i] = t1; ts2[i] = t2; i++; } return (ts1, ts2); } public static (T1[], T2[], T3[]) Unzip(this ICollection<(T1, T2, T3)> source) { var ts1 = new T1[source.Count]; var ts2 = new T2[source.Count]; var ts3 = new T3[source.Count]; var i = 0; foreach (var (t1, t2, t3) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; i++; } return (ts1, ts2, ts3); } public static (T1[], T2[], T3[], T4[]) Unzip(this ICollection<(T1, T2, T3, T4)> source) { var ts1 = new T1[source.Count]; var ts2 = new T2[source.Count]; var ts3 = new T3[source.Count]; var ts4 = new T4[source.Count]; var i = 0; foreach (var (t1, t2, t3, t4) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; ts4[i] = t4; i++; } return (ts1, ts2, ts3, ts4); } public static IEnumerable Zip(this IEnumerable first, IEnumerable second, IEnumerable thrid, Func resultSelector) { using (var e1 = first.GetEnumerator()) using (var e2 = second.GetEnumerator()) using (var e3 = thrid.GetEnumerator()) { while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext()) yield return resultSelector(e1.Current, e2.Current, e3.Current); } } public static IEnumerable Zip(this IEnumerable first, IEnumerable second, IEnumerable thrid, IEnumerable fourth, Func resultSelector) { using (var e1 = first.GetEnumerator()) using (var e2 = second.GetEnumerator()) using (var e3 = thrid.GetEnumerator()) using (var e4 = fourth.GetEnumerator()) { while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext() && e4.MoveNext()) yield return resultSelector(e1.Current, e2.Current, e3.Current, e4.Current); } } } [DebuggerStepThrough] public static class MathExtensions { public static int DivCeil(int left, int right) => left / right + (left % right == 0 ? 0 : 1); public static long DivCeil(long left, long right) => left / right + (left % right == 0L ? 0L : 1L); public static int Gcd(int left, int right) { int r; while ((r = left % right) != 0) { left = right; right = r; } return right; } public static long Gcd(long left, long right) { long r; while ((r = left % right) != 0L) { left = right; right = r; } return right; } public static BigInteger Gcd(BigInteger left, BigInteger right) => BigInteger.GreatestCommonDivisor(left, right); public static int HighestOneBit(int x) { x |= x >> 01; x |= x >> 02; x |= x >> 04; x |= x >> 08; x |= x >> 16; return x - (x >> 1); } public static long HighestOneBit(long x) { x |= x >> 01; x |= x >> 02; x |= x >> 04; x |= x >> 08; x |= x >> 16; x |= x >> 32; return x - (x >> 1); } public static int Lcm(int left, int right) => left / Gcd(left, right) * right; public static long Lcm(long left, long right) => left / Gcd(left, right) * right; public static BigInteger Lcm(BigInteger left, BigInteger right) => left / Gcd(left, right) * right; public static int Pow(int value, int exponent) { var r = 1; while (exponent > 0) { if ((exponent & 1) == 1) r *= value; value *= value; exponent >>= 1; } return r; } public static long Pow(long value, int exponent) { var r = 1L; while (exponent > 0) { if ((exponent & 1) == 1) r *= value; value *= value; exponent >>= 1; } return r; } public static long Fact(int value) { var r = 1L; for (var i = 2; i <= value; i++) r *= i; return r; } } #endregion