using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Training20200928.Algorithms;
using Training20200928.Collections;
using Training20200928.Numerics;
using Training20200928.Questions;

namespace Training20200928.Questions
{
    public class QuestionA : AtCoderQuestionBase
    {
        public override void Solve(IOManager io)
        {
            var m1 = io.ReadInt();
            var d1 = io.ReadInt();
            var m2 = io.ReadInt();
            var d2 = io.ReadInt();

            if (m1 < m2)
            {
                io.WriteLine(1);
            }
            else
            {
                io.WriteLine(0);
            }
        }
    }
}

namespace Training20200928
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionA();
            using var io = new IOManager(Console.OpenStandardInput(), Console.OpenStandardOutput());
            question.Solve(io);
        }
    }
}

#region Base Class

namespace Training20200928.Questions
{

    public interface IAtCoderQuestion
    {
        string Solve(string input);
        void Solve(IOManager io);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public string Solve(string input)
        {
            var inputStream = new MemoryStream(Encoding.UTF8.GetBytes(input));
            var outputStream = new MemoryStream();
            using var manager = new IOManager(inputStream, outputStream);

            Solve(manager);
            manager.Flush();

            outputStream.Seek(0, SeekOrigin.Begin);
            var reader = new StreamReader(outputStream);
            return reader.ReadToEnd();
        }

        public abstract void Solve(IOManager io);
    }

    public class IOManager : IDisposable
    {
        private readonly StreamReader _reader;
        private readonly StreamWriter _writer;
        private bool _disposedValue;
        private Queue<ReadOnlyMemory<char>> _stringQueue;

        const char ValidFirstChar = '!';
        const char ValidLastChar = '~';

        public IOManager(Stream input, Stream output)
        {
            _reader = new StreamReader(input);
            _writer = new StreamWriter(output) { AutoFlush = false };
            _stringQueue = new Queue<ReadOnlyMemory<char>>();
        }

        public ReadOnlySpan<char> ReadCharSpan()
        {
            while (_stringQueue.Count == 0)
            {
                var line = _reader.ReadLine().AsMemory().Trim();
                var s = line.Span;

                if (s.Length > 0)
                {
                    var begin = 0;
                    for (int i = 0; i < s.Length; i++)
                    {
                        if (begin < 0 && IsValidChar(s[i]))
                        {
                            begin = i;
                        }
                        else if (!IsValidChar(s[i]))
                        {
                            _stringQueue.Enqueue(line[begin..i]);
                            begin = -1;
                        }
                    }
                    _stringQueue.Enqueue(line[begin..line.Length]);
                }
            }

            return _stringQueue.Dequeue().Span;
        }

        public string ReadString() => ReadCharSpan().ToString();

        public int ReadInt() => (int)ReadLong();

        public long ReadLong()
        {
            long result = 0;
            bool isPositive = true;

            int i = 0;
            var s = ReadCharSpan();
            if (s[i] == '-')
            {
                isPositive = false;
                i++;
            }

            while (i < s.Length)
            {
                result = result * 10 + (s[i++] - '0');
            }

            return isPositive ? result : -result;
        }

        public double ReadDouble() => double.Parse(ReadCharSpan());
        public decimal ReadDecimal() => decimal.Parse(ReadCharSpan());

        public int[] ReadIntArray(int n)
        {
            var a = new int[n];
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = ReadInt();
            }
            return a;
        }

        public long[] ReadLongArray(int n)
        {
            var a = new long[n];
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = ReadLong();
            }
            return a;
        }

        public double[] ReadDoubleArray(int n)
        {
            var a = new double[n];
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = ReadDouble();
            }
            return a;
        }

        public decimal[] ReadDecimalArray(int n)
        {
            var a = new decimal[n];
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = ReadDecimal();
            }
            return a;
        }

        public void WriteLine<T>(T value) => _writer.WriteLine(value.ToString());

        public void WriteLine<T>(IEnumerable<T> values, char separator)
        {
            var e = values.GetEnumerator();
            if (e.MoveNext())
            {
                _writer.Write(e.Current.ToString());

                while (e.MoveNext())
                {
                    _writer.Write(separator);
                    _writer.Write(e.Current.ToString());
                }
            }

            _writer.WriteLine();
        }

        public void Flush() => _writer.Flush();

        private static bool IsValidChar(char c) => ValidFirstChar <= c && c <= ValidLastChar;

        protected virtual void Dispose(bool disposing)
        {
            if (!_disposedValue)
            {
                if (disposing)
                {
                    _reader.Dispose();
                    _writer.Flush();
                    _writer.Dispose();
                }

                _disposedValue = true;
            }
        }

        public void Dispose()
        {
            Dispose(disposing: true);
            GC.SuppressFinalize(this);
        }
    }
}

#endregion

#region Algorithm

namespace Training20200928.Numerics
{
    public static class NumericalAlgorithms
    {
        public static long Gcd(long a, long b)
        {
            if (a < b)
            {
                (a, b) = (b, a);
            }

            if (b > 0)
            {
                return Gcd(b, a % b);
            }
            else if (b == 0)
            {
                return a;
            }
            else
            {
                throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。");
            }
        }

        public static long Lcm(long a, long b)
        {
            if (a < 0 || b < 0)
            {
                throw new ArgumentOutOfRangeException($"{nameof(a)}, {nameof(b)}は0以上の整数である必要があります。");
            }

            return a / Gcd(a, b) * b;
        }

        public static long Factorial(int n)
        {
            if (n < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{n}は0以上の整数でなければなりません。");
            }

            long result = 1;
            for (int i = 2; i <= n; i++)
            {
                result *= i;
            }
            return result;
        }

        public static long Permutation(int n, int r)
        {
            CheckNR(n, r);
            long result = 1;
            for (int i = 0; i < r; i++)
            {
                result *= n - i;
            }
            return result;
        }

        public static long Combination(int n, int r)
        {
            CheckNR(n, r);
            r = Math.Min(r, n - r);

            // See https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations
            long result = 1;
            for (int i = 1; i <= r; i++)
            {
                result *= n--;
                result /= i;
            }
            return result;
        }

        public static long CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);

        public static IEnumerable<(int prime, int count)> PrimeFactorization(int n)
        {
            if (n <= 1)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{n}は2以上の整数でなければなりません。");
            }

            var dictionary = new Dictionary<int, int>();
            for (int i = 2; i * i <= n; i++)
            {
                while (n % i == 0)
                {
                    if (dictionary.ContainsKey(i))
                    {
                        dictionary[i]++;
                    }
                    else
                    {
                        dictionary[i] = 1;
                    }

                    n /= i;
                }
            }

            if (n > 1)
            {
                dictionary[n] = 1;
            }

            return dictionary.Select(p => (p.Key, p.Value));
        }

        private static void CheckNR(int n, int r)
        {
            if (n <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は正の整数でなければなりません。");
            }
            if (r < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");
            }
            if (n < r)
            {
                throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");
            }
        }
    }

    public readonly struct Modular : IEquatable<Modular>, IComparable<Modular>
    {
        private const int DefaultMod = 1000000007;
        public int Value { get; }
        public static int Mod { get; set; } = DefaultMod;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public Modular(long value)
        {
            if (unchecked((ulong)value) < unchecked((ulong)Mod))
            {
                Value = (int)value;
            }
            else
            {
                Value = (int)(value % Mod);
                if (Value < 0)
                {
                    Value += Mod;
                }
            }
        }

        private Modular(int value) => Value = value;
        public static Modular Zero => new Modular(0);
        public static Modular One => new Modular(1);

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Modular operator +(Modular a, Modular b)
        {
            var result = a.Value + b.Value;
            if (result >= Mod)
            {
                result -= Mod;    // 剰余演算を避ける
            }
            return new Modular(result);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Modular operator -(Modular a, Modular b)
        {
            var result = a.Value - b.Value;
            if (result < 0)
            {
                result += Mod;    // 剰余演算を避ける
            }
            return new Modular(result);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Modular operator *(Modular a, Modular b) => new Modular((long)a.Value * b.Value);

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Modular operator /(Modular a, Modular b) => a * Pow(b.Value, Mod - 2);

        // 需要は不明だけど一応
        public static bool operator ==(Modular left, Modular right) => left.Equals(right);
        public static bool operator !=(Modular left, Modular right) => !(left == right);
        public static bool operator <(Modular left, Modular right) => left.CompareTo(right) < 0;
        public static bool operator <=(Modular left, Modular right) => left.CompareTo(right) <= 0;
        public static bool operator >(Modular left, Modular right) => left.CompareTo(right) > 0;
        public static bool operator >=(Modular left, Modular right) => left.CompareTo(right) >= 0;

        public static implicit operator Modular(long a) => new Modular(a);
        public static explicit operator int(Modular a) => a.Value;
        public static explicit operator long(Modular a) => a.Value;

        public static Modular Pow(int a, int n)
        {
            if (n == 0)
            {
                return Modular.One;
            }
            else if (n == 1)
            {
                return a;
            }
            else if (n > 0)
            {
                var p = Pow(a, n >> 1);             // m / 2
                return p * p * Pow(a, n & 0x01);    // m % 2
            }
            else
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。");
            }
        }

        private static List<int> _factorialCache;
        private static List<int> FactorialCache => _factorialCache ??= new List<int>() { 1 };
        private static int[] FactorialInverseCache { get; set; }
        const int defaultMaxFactorial = 1000000;

        public static Modular Factorial(int n)
        {
            if (n < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");
            }

            for (int i = FactorialCache.Count; i <= n; i++)  // Countが1（0!までキャッシュ済み）のとき1!～n!まで計算
            {
                FactorialCache.Add((int)((long)FactorialCache[i - 1] * i % Mod));
            }
            return new Modular(FactorialCache[n]);
        }

        public static Modular Permutation(int n, int r)
        {
            CheckNR(n, r);
            return Factorial(n) / Factorial(n - r);
        }

        public static Modular Combination(int n, int r)
        {
            CheckNR(n, r);
            r = Math.Min(r, n - r);
            try
            {
                return new Modular(FactorialCache[n]) * new Modular(FactorialInverseCache[r]) * new Modular(FactorialInverseCache[n - r]);
            }
            catch (Exception ex) when (ex is NullReferenceException || ex is ArgumentOutOfRangeException)
            {
                throw new InvalidOperationException($"{nameof(Combination)}を呼び出す前に{nameof(InitializeCombinationTable)}により前計算を行う必要があります。", ex);
            }
        }

        public static void InitializeCombinationTable(int max = defaultMaxFactorial)
        {
            Factorial(max);
            FactorialInverseCache = new int[max + 1];

            var fInv = (Modular.One / Factorial(max)).Value;
            FactorialInverseCache[max] = fInv;
            for (int i = max - 1; i >= 0; i--)
            {
                fInv = (int)((long)fInv * (i + 1) % Mod);
                FactorialInverseCache[i] = fInv;
            }
        }

        public static Modular CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);

        private static void CheckNR(int n, int r)
        {
            if (n < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");
            }
            if (r < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");
            }
            if (n < r)
            {
                throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");
            }
        }

        public override string ToString() => Value.ToString();
        public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false;
        public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value;
        public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value.CompareTo(other.Value);
        public override int GetHashCode() => Value.GetHashCode();
    }

    public class ModMatrix
    {
        readonly Modular[] _values;
        public int Height { get; }
        public int Width { get; }

        public Span<Modular> this[int row]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get => _values.AsSpan(row * Width, Width);
        }

        public Modular this[int row, int column]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                if (unchecked((uint)row) >= Height)
                    ThrowsArgumentOutOfRangeException(nameof(row));
                else if (unchecked((uint)column) >= Width)
                    ThrowsArgumentOutOfRangeException(nameof(column));
                return _values[row * Width + column];
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                if (unchecked((uint)row) >= Height)
                    ThrowsArgumentOutOfRangeException(nameof(row));
                else if (unchecked((uint)column) >= Width)
                    ThrowsArgumentOutOfRangeException(nameof(column));
                _values[row * Width + column] = value;
            }
        }

        public ModMatrix(int n) : this(n, n) { }

        public ModMatrix(int height, int width)
        {
            if (height <= 0)
                throw new ArgumentOutOfRangeException(nameof(height));
            if (width <= 0)
                throw new ArgumentOutOfRangeException(nameof(width));
            Height = height;
            Width = width;
            _values = new Modular[height * width];
        }

        public ModMatrix(Modular[][] values) : this(values.Length, values[0].Length)
        {
            for (int row = 0; row < Height; row++)
            {
                if (Width != values[row].Length)
                    throw new ArgumentException($"{nameof(values)}の列数は揃っている必要があります。");
                var span = _values.AsSpan(row * Width, Width);
                values[row].AsSpan().CopyTo(span);
            }
        }

        public ModMatrix(Modular[,] values) : this(values.GetLength(0), values.GetLength(1))
        {
            for (int row = 0; row < Height; row++)
            {
                var span = _values.AsSpan(row * Width, Width);
                for (int column = 0; column < span.Length; column++)
                {
                    span[column] = values[row, column];
                }
            }
        }

        public ModMatrix(ModMatrix matrix)
        {
            Height = matrix.Height;
            Width = matrix.Width;
            _values = new Modular[matrix._values.Length];
            matrix._values.AsSpan().CopyTo(_values);
        }

        public static ModMatrix GetIdentity(int dimension)
        {
            var result = new ModMatrix(dimension);
            for (int i = 0; i < dimension; i++)
            {
                result._values[i * result.Width + i] = 1;
            }
            return result;
        }

        public static ModMatrix operator +(ModMatrix a, ModMatrix b)
        {
            CheckSameShape(a, b);

            var result = new ModMatrix(a.Height, a.Width);
            for (int i = 0; i < result._values.Length; i++)
            {
                result._values[i] = a._values[i] + b._values[i];
            }
            return result;
        }

        public static ModMatrix operator -(ModMatrix a, ModMatrix b)
        {
            CheckSameShape(a, b);

            var result = new ModMatrix(a.Height, a.Width);
            for (int i = 0; i < result._values.Length; i++)
            {
                result._values[i] = a._values[i] - b._values[i];
            }
            return result;
        }

        public static ModMatrix operator *(ModMatrix a, ModMatrix b)
        {
            if (a.Width != b.Height)
                throw new ArgumentException($"{nameof(a)}の列数と{nameof(b)}の行数は等しくなければなりません。");

            var result = new ModMatrix(a.Height, b.Width);
            for (int i = 0; i < result.Height; i++)
            {
                var aSpan = a._values.AsSpan(i * a.Width, a.Width);
                var resultSpan = result._values.AsSpan(i * result.Width, result.Width);
                for (int k = 0; k < aSpan.Length; k++)
                {
                    var bSpan = b._values.AsSpan(k * b.Width, b.Width);
                    for (int j = 0; j < resultSpan.Length; j++)
                    {
                        resultSpan[j] += aSpan[k] * bSpan[j];
                    }
                }
            }
            return result;
        }

        public static ModVector operator *(ModMatrix matrix, ModVector vector)
        {
            if (matrix.Width != vector.Length)
                throw new ArgumentException($"{nameof(matrix)}の列数と{nameof(vector)}の行数は等しくなければなりません。");

            var result = new ModVector(vector.Length);
            for (int i = 0; i < result.Length; i++)
            {
                var matrixSpan = matrix[i];
                for (int k = 0; k < matrixSpan.Length; k++)
                {
                    result[i] += matrixSpan[k] * vector[k];
                }
            }
            return result;
        }

        public ModMatrix Pow(long pow)
        {
            if (Height != Width)
                throw new ArgumentException("累乗を行う行列は正方行列である必要があります。");
            if (pow < 0)
                throw new ArgumentException($"{nameof(pow)}は0以上の整数である必要があります。");

            var powMatrix = new ModMatrix(this);
            var result = GetIdentity(Height);
            while (pow > 0)
            {
                if ((pow & 1) > 0)
                {
                    result *= powMatrix;
                }
                powMatrix *= powMatrix;
                pow >>= 1;
            }
            return result;
        }

        private static void CheckSameShape(ModMatrix a, ModMatrix b)
        {
            if (a.Height != b.Height)
                throw new ArgumentException($"{nameof(a)}の行数と{nameof(b)}の行数は等しくなければなりません。");
            else if (a.Width != b.Width)
                throw new ArgumentException($"{nameof(a)}の列数と{nameof(b)}の列数は等しくなければなりません。");
        }

        private void ThrowsArgumentOutOfRangeException(string paramName) => throw new ArgumentOutOfRangeException(paramName);
        public override string ToString() => $"({Height}x{Width})matrix";
    }

    public class ModVector
    {
        readonly Modular[] _values;
        public int Length => _values.Length;

        public ModVector(int length)
        {
            if (length <= 0)
                throw new ArgumentOutOfRangeException(nameof(length));
            _values = new Modular[length];
        }

        public ModVector(ReadOnlySpan<Modular> vector)
        {
            _values = new Modular[vector.Length];
            vector.CopyTo(_values);
        }

        public ModVector(ModVector vector) : this(vector._values) { }

        public Modular this[int index]
        {
            get => _values[index];
            set => _values[index] = value;
        }

        public static ModVector operator +(ModVector a, ModVector b)
        {
            if (a.Length != b.Length)
                throw new ArgumentException($"{nameof(a)}と{nameof(b)}の次元は等しくなければなりません。");

            var result = new ModVector(a.Length);
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = a[i] + b[i];
            }
            return result;
        }

        public static ModVector operator -(ModVector a, ModVector b)
        {
            if (a.Length != b.Length)
                throw new ArgumentException($"{nameof(a)}と{nameof(b)}の次元は等しくなければなりません。");

            var result = new ModVector(a.Length);
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = a[i] - b[i];
            }
            return result;
        }

        public static Modular operator *(ModVector a, ModVector b)
        {
            if (a.Length != b.Length)
                throw new ArgumentException($"{nameof(a)}と{nameof(b)}の次元は等しくなければなりません。");

            var result = Modular.Zero;
            for (int i = 0; i < a.Length; i++)
            {
                result += a[i] * b[i];
            }
            return result;
        }

        public override string ToString() => $"({Length})vector";
    }

    public class Eratosthenes
    {
        /// <summary>
        /// Smallest Prime Factorを保存した配列
        /// </summary>
        readonly int[] _spf;

        public Eratosthenes(int max)
        {
            _spf = Enumerable.Range(0, max + 1).ToArray();
            for (int i = 2; i * i <= max; i++)
            {
                if (_spf[i] == i)
                {
                    for (int mul = i << 1; mul <= max; mul += i)
                    {
                        if (_spf[mul] == mul)
                        {
                            _spf[mul] = i;
                        }
                    }
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool IsPrime(int n) => n >= 2 && _spf[n] == n;

        public IEnumerable<PrimeAndCount> PrimeFactorize(int n)
        {
            if (n <= 0 || _spf.Length <= n)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は[0, {_spf.Length})の間でなければなりません");
            }
            else if (n == 1)
            {
                yield break;
            }
            else
            {
                var last = _spf[n];
                var streak = 0;
                while (n > 1)
                {
                    if (_spf[n] == last)
                    {
                        streak++;
                    }
                    else
                    {
                        yield return new PrimeAndCount(last, streak);
                        last = _spf[n];
                        streak = 1;
                    }

                    n /= last;
                }
                yield return new PrimeAndCount(last, streak);
            }
        }

        public IEnumerable<int> GetDivisiors(int n)
        {
            if (n <= 0 || _spf.Length <= n)
            {
                throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は[0, {_spf.Length})の間でなければなりません");
            }
            else
            {
                var primes = PrimeFactorize(n).ToArray();
                return GetDivisiors(primes, 0);
            }
        }

        IEnumerable<int> GetDivisiors(PrimeAndCount[] primes, int depth)
        {
            if (depth == primes.Length)
            {
                yield return 1;
            }
            else
            {
                var current = 1;
                var children = GetDivisiors(primes, depth + 1).ToArray();

                foreach (var child in children)
                {
                    yield return child;
                }

                for (int i = 0; i < primes[depth].Count; i++)
                {
                    current *= primes[depth].Prime;
                    foreach (var child in children)
                    {
                        yield return current * child;
                    }
                }
            }
        }
    }

    public static class Divisiors
    {
        public static IEnumerable<long> GetDivisiors(long n)
        {
            var lastHalf = new Stack<long>();
            for (long i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    yield return i;
                    if (i * i != n)
                    {
                        lastHalf.Push(n / i);
                    }
                }
            }

            while (lastHalf.Count > 0)
            {
                yield return lastHalf.Pop();
            }
        }
    }

    [StructLayout(LayoutKind.Auto)]
    public readonly struct PrimeAndCount
    {
        public int Prime { get; }
        public int Count { get; }

        public PrimeAndCount(int prime, int count)
        {
            Prime = prime;
            Count = count;
        }

        public void Deconstruct(out int prime, out int count) => (prime, count) = (Prime, Count);
        public override string ToString() => $"{nameof(Prime)}: {Prime}, {nameof(Count)}: {Count}";
    }

    public readonly struct Fraction : IEquatable<Fraction>, IComparable<Fraction>
    {
        /// <summary>分子</summary>
        public long Numerator { get; }
        /// <summary>分母</summary>
        public long Denominator { get; }

        public static Fraction Nan => new Fraction(0, 0);
        public static Fraction PositiveInfinity => new Fraction(1, 0);
        public static Fraction NegativeInfinity => new Fraction(-1, 0);
        public bool IsNan => Numerator == 0 && Denominator == 0;
        public bool IsInfinity => Numerator != 0 && Denominator == 0;
        public bool IsPositiveInfinity => Numerator > 0 && Denominator == 0;
        public bool IsNegativeInfinity => Numerator < 0 && Denominator == 0;

        /// <summary>
        /// <c>Fraction</c>クラスの新しいインスタンスを生成します。
        /// </summary>
        /// <param name="numerator">分子</param>
        /// <param name="denominator">分母</param>
        public Fraction(long numerator, long denominator)
        {
            if (denominator == 0)
            {
                Numerator = Math.Sign(numerator);
                Denominator = 0;
            }
            else if (numerator == 0)
            {
                Numerator = 0;
                Denominator = 1;
            }
            else
            {
                var sign = Math.Sign(numerator) * Math.Sign(denominator);
                numerator = Math.Abs(numerator);
                denominator = Math.Abs(denominator);
                var gcd = NumericalAlgorithms.Gcd(numerator, denominator);
                Numerator = sign * numerator / gcd;
                Denominator = denominator / gcd;
            }
        }

        public static Fraction operator +(in Fraction left, in Fraction right)
        {
            if (left.IsNan || right.IsNan)
            {
                return Nan;
            }
            else if (left.IsInfinity || right.IsInfinity)
            {
                if (!right.IsInfinity)
                {
                    return left;
                }
                else if (!left.IsInfinity)
                {
                    return right;
                }
                else
                {
                    return new Fraction(left.Numerator + right.Numerator, 0);
                }
            }
            else
            {
                var lcm = NumericalAlgorithms.Lcm(left.Denominator, right.Denominator);
                return new Fraction(left.Numerator * (lcm / left.Denominator) + right.Numerator * (lcm / right.Denominator), lcm);
            }
        }
        public static Fraction operator -(in Fraction left, in Fraction right) => left + -right;
        public static Fraction operator *(in Fraction left, in Fraction right) => new Fraction(left.Numerator * right.Numerator, left.Denominator * right.Denominator);
        public static Fraction operator /(in Fraction left, in Fraction right) => new Fraction(left.Numerator * right.Denominator, left.Denominator * right.Numerator);
        public static Fraction operator +(in Fraction right) => right;
        public static Fraction operator -(in Fraction right) => new Fraction(-right.Numerator, right.Denominator);
        public static bool operator ==(in Fraction left, in Fraction right) => left.Equals(right);
        public static bool operator !=(in Fraction left, in Fraction right) => !(left == right);
        public static implicit operator double(in Fraction right)
        {
            if (right.IsNan)
            {
                return double.NaN;
            }
            else if (right.IsPositiveInfinity)
            {
                return double.PositiveInfinity;
            }
            else if (right.IsNegativeInfinity)
            {
                return double.NegativeInfinity;
            }
            else
            {
                return (double)right.Numerator / right.Denominator;
            }
        }

        public override string ToString()
        {
            if (IsNan)
            {
                return "NaN";
            }
            else if (IsPositiveInfinity)
            {
                return "Inf";
            }
            else if (IsNegativeInfinity)
            {
                return "-Inf";
            }
            else
            {
                return $"{Numerator}/{Denominator}";
            }
        }

        public override bool Equals(object obj) => obj is Fraction fraction && Equals(fraction);
        public bool Equals(Fraction other) => Numerator == other.Numerator && Denominator == other.Denominator;
        public override int GetHashCode() => HashCode.Combine(Numerator, Denominator);
        public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Fraction other) => ((double)this).CompareTo(other);
    }

    public interface ISemigroup<TSet> where TSet : ISemigroup<TSet>
    {
        public TSet Merge(TSet other);
    }

    public interface IMonoid<TSet> : ISemigroup<TSet> where TSet : IMonoid<TSet>, new()
    {
        public TSet Identity { get; }
    }

    public interface IMonoidWithAct<TMonoid, TOperator> : IMonoid<TOperator>
        where TMonoid : IMonoid<TMonoid>, new()
        where TOperator : IMonoid<TOperator>, new()
    {
        public TMonoid Act(TMonoid monoid);
    }

    public interface IGroup<TSet> : IMonoid<TSet> where TSet : IGroup<TSet>, new()
    {
        public TSet Invert();
        public static TSet operator ~(IGroup<TSet> a) => a.Invert();
    }
}

namespace Training20200928.Algorithms
{
    public static class ZAlgorithm
    {
        public static int[] SearchAll(string s) => SearchAll(s.AsSpan());

        public static int[] SearchAll<T>(ReadOnlySpan<T> s) where T : IEquatable<T>
        {
            var z = new int[s.Length];
            z[0] = s.Length;
            var offset = 1;
            var length = 0;

            while (offset < s.Length)
            {
                while (offset + length < s.Length && s[length].Equals(s[offset + length]))
                {
                    length++;
                }
                z[offset] = length;

                if (length == 0)
                {
                    offset++;
                    continue;
                }

                int copyLength = 1;
                while (copyLength < length && copyLength + z[copyLength] < length)
                {
                    z[offset + copyLength] = z[copyLength];
                    copyLength++;
                }
                offset += copyLength;
                length -= copyLength;
            }

            return z;
        }
    }

    /// <summary>
    /// MP法（文字列検索アルゴリズム）
    /// </summary>
    public class MorrisPratt<T> where T : IEquatable<T>
    {
        readonly T[] _searchSequence;
        readonly int[] _matchLength;

        public ReadOnlySpan<T> SearchSequence => _searchSequence.AsSpan();

        /// <summary>
        /// 検索データ列の前処理を行います。
        /// </summary>
        /// <param name="searchSequence">検索データ列</param>
        public MorrisPratt(ReadOnlySpan<T> searchSequence)
        {
            _searchSequence = searchSequence.ToArray();
            _matchLength = new int[_searchSequence.Length + 1];
            _matchLength[0] = -1;
            int j = -1;
            for (int i = 0; i < _searchSequence.Length; i++)
            {
                while (j != -1 && !_searchSequence[j].Equals(_searchSequence[i]))
                {
                    j = _matchLength[j];
                }
                j++;
                _matchLength[i + 1] = j;
            }
        }

        /// <summary>
        /// 与えられた対象データ列の部分列のうち、検索データ列にマッチする部分列の開始インデックスを取得します。
        /// </summary>
        /// <param name="targetSequence">検索対象データ列</param>
        /// <returns></returns>
        public List<int> SearchAll(ReadOnlySpan<T> targetSequence)
        {
            var results = new List<int>();
            int j = 0;
            for (int i = 0; i < targetSequence.Length; i++)
            {
                while (j != -1 && !_searchSequence[j].Equals(targetSequence[i]))
                {
                    j = _matchLength[j];
                }
                j++;
                if (j == _searchSequence.Length)
                {
                    results.Add(i - j + 1);
                    j = _matchLength[j];
                }
            }
            return results;
        }
    }

    /// <summary>
    /// 参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    /// ジェネリクスに対応させるにはGetHashCode()を足していく？実装によっては重そうなのでとりあえずパス。
    /// </summary>
    public class RollingHash
    {
        const ulong Mask30 = (1UL << 30) - 1;
        const ulong Mask31 = (1UL << 31) - 1;
        const ulong Mod = (1UL << 61) - 1;
        const ulong Positivizer = Mod * ((1UL << 3) - 1);   // 引き算する前に足すことでmodが負になることを防ぐやつ
        static readonly uint base1;
        static readonly uint base2;
        static readonly List<ulong> pow1;
        static readonly List<ulong> pow2;

        static RollingHash()
        {
            var random = new Random();
            base1 = (uint)random.Next(129, int.MaxValue >> 2);
            base2 = (uint)random.Next(int.MaxValue >> 2, int.MaxValue); // 32bit目は0にしておく
            pow1 = new List<ulong>() { 1 };
            pow2 = new List<ulong>() { 1 };
        }

        ulong[] hash1;
        ulong[] hash2;
        public string RawString { get; }
        public int Length => RawString.Length;

        public RollingHash(string s)
        {
            RawString = s;
            hash1 = new ulong[s.Length + 1];
            hash2 = new ulong[s.Length + 1];

            for (int i = pow1.Count; i < s.Length + 1; i++)
            {
                pow1.Add(CalculateModular(Multiply(pow1[i - 1], base1)));
                pow2.Add(CalculateModular(Multiply(pow2[i - 1], base2)));
            }

            for (int i = 0; i < s.Length; i++)
            {
                hash1[i + 1] = CalculateModular(Multiply(hash1[i], base1) + s[i]);
                hash2[i + 1] = CalculateModular(Multiply(hash2[i], base2) + s[i]);
            }
        }

        public (ulong, ulong) this[Range range]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                var (offset, length) = range.GetOffsetAndLength(Length);
                return Slice(offset, length);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public (ulong, ulong) Slice(int begin, int length)
        {
            var result1 = CalculateModular(hash1[begin + length] + Positivizer - Multiply(hash1[begin], pow1[length]));
            var result2 = CalculateModular(hash2[begin + length] + Positivizer - Multiply(hash2[begin], pow2[length]));
            return (result1, result2);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static ulong Multiply(ulong l, ulong r)
        {
            var lu = l >> 31;
            var ll = l & Mask31;
            var ru = r >> 31;
            var rl = r & Mask31;
            var mid = ll * ru + lu * rl;
            return ((lu * ru) << 1) + ll * rl + ((mid & Mask30) << 31) + (mid >> 30);   // a * 2^61 ≡ a (mod 2^61 - 1)を使う
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static ulong Multiply(ulong l, uint r)
        {
            var lu = l >> 31;
            var mid = lu * r;
            return (l & Mask31) * r + ((mid & Mask30) << 31) + (mid >> 30); // rの32bit目は0としている
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static ulong CalculateModular(ulong value)
        {
            value = (value & Mod) + (value >> 61);
            if (value >= Mod)
            {
                value -= Mod;
            }
            return value;
        }

        public override string ToString() => RawString;
    }

    public class XorShift
    {
        ulong _x;

        public XorShift() : this((ulong)DateTime.Now.Ticks) { }

        public XorShift(ulong seed)
        {
            _x = seed;
        }

        /// <summary>
        /// [0, (2^64)-1)の乱数を生成します。
        /// </summary>
        /// <returns></returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public ulong Next()
        {
            _x = _x ^ (_x << 13);
            _x = _x ^ (_x >> 7);
            _x = _x ^ (_x << 17);
            return _x;
        }

        /// <summary>
        /// [0, <c>exclusiveMax</c>)の乱数を生成します。
        /// </summary>
        /// <param name="exclusiveMax"></param>
        /// <returns></returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Next(int exclusiveMax) => (int)(Next() % (uint)exclusiveMax);

        /// <summary>
        /// [0.0, 1.0)の乱数を生成します。
        /// </summary>
        /// <returns></returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public double NextDouble()
        {
            const ulong max = 1UL << 50;
            const ulong mask = max - 1;
            return (double)(Next() & mask) / max;
        }
    }

    public static class AlgorithmHelpers
    {
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void UpdateWhenSmall<T>(ref T value, T other) where T : IComparable<T>
        {
            if (other.CompareTo(value) < 0)
            {
                value = other;
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void UpdateWhenLarge<T>(ref T value, T other) where T : IComparable<T>
        {
            if (other.CompareTo(value) > 0)
            {
                value = other;
            }
        }
    }

    public class CoordinateShrinker<T> : IEnumerable<(int shrinkedIndex, T rawIndex)> where T : IComparable<T>, IEquatable<T>
    {
        Dictionary<T, int> _shrinkMapper;
        T[] _expandMapper;
        public int Count => _expandMapper.Length;

        public CoordinateShrinker(IEnumerable<T> data)
        {
            _expandMapper = data.Distinct().ToArray();
            Array.Sort(_expandMapper);

            _shrinkMapper = new Dictionary<T, int>();
            for (int i = 0; i < _expandMapper.Length; i++)
            {
                _shrinkMapper.Add(_expandMapper[i], i);
            }
        }

        public int Shrink(T rawCoordinate) => _shrinkMapper[rawCoordinate];
        public T Expand(int shrinkedCoordinate) => _expandMapper[shrinkedCoordinate];

        public IEnumerator<(int shrinkedIndex, T rawIndex)> GetEnumerator()
        {
            for (int i = 0; i < _expandMapper.Length; i++)
            {
                yield return (i, _expandMapper[i]);
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
    }
}

#endregion

#region Collections

namespace Training20200928.Collections
{
    // See https://kumikomiya.com/competitive-programming-with-c-sharp/
    public class UnionFindTree
    {
        private UnionFindNode[] _nodes;
        public int Count => _nodes.Length;
        public int Groups { get; private set; }

        public UnionFindTree(int count)
        {
            _nodes = Enumerable.Range(0, count).Select(i => new UnionFindNode(i)).ToArray();
            Groups = _nodes.Length;
        }

        public void Unite(int index1, int index2)
        {
            var succeed = _nodes[index1].Unite(_nodes[index2]);
            if (succeed)
            {
                Groups--;
            }
        }

        public bool IsInSameGroup(int index1, int index2) => _nodes[index1].IsInSameGroup(_nodes[index2]);
        public int GetGroupSizeOf(int index) => _nodes[index].GetGroupSize();

        private class UnionFindNode
        {
            private int _height;        // rootのときのみ有効
            private int _groupSize;     // 同上
            private UnionFindNode _parent;
            public int ID { get; }

            public UnionFindNode(int id)
            {
                _height = 0;
                _groupSize = 1;
                _parent = this;
                ID = id;
            }

            public UnionFindNode FindRoot()
            {
                if (_parent != this) // not ref equals
                {
                    var root = _parent.FindRoot();
                    _parent = root;
                }

                return _parent;
            }

            public int GetGroupSize() => FindRoot()._groupSize;

            public bool Unite(UnionFindNode other)
            {
                var thisRoot = this.FindRoot();
                var otherRoot = other.FindRoot();

                if (thisRoot == otherRoot)
                {
                    return false;
                }

                if (thisRoot._height < otherRoot._height)
                {
                    thisRoot._parent = otherRoot;
                    otherRoot._groupSize += thisRoot._groupSize;
                    otherRoot._height = Math.Max(thisRoot._height + 1, otherRoot._height);
                    return true;
                }
                else
                {
                    otherRoot._parent = thisRoot;
                    thisRoot._groupSize += otherRoot._groupSize;
                    thisRoot._height = Math.Max(otherRoot._height + 1, thisRoot._height);
                    return true;
                }
            }

            public bool IsInSameGroup(UnionFindNode other) => this.FindRoot() == other.FindRoot();

            public override string ToString() => $"{ID} root:{FindRoot().ID}";
        }
    }

    public class Deque<T> : IReadOnlyCollection<T>
    {
        public int Count { get; private set; }
        private T[] _data;
        private int _first;
        private int _mask;

        public Deque() : this(4) { }

        public Deque(int minCapacity)
        {
            if (minCapacity <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(minCapacity), $"{nameof(minCapacity)}は0より大きい値でなければなりません。");
            }
            var capacity = GetPow2Over(minCapacity);
            _data = new T[capacity];
            _first = 0;
            _mask = capacity - 1;
        }

        public Deque(IEnumerable<T> collection)
        {
            var dataArray = collection.ToArray();
            var capacity = GetPow2Over(dataArray.Length);
            _data = new T[capacity];
            _first = 0;
            _mask = capacity - 1;

            for (int i = 0; i < dataArray.Length; i++)
            {
                _data[i] = dataArray[i];
                Count++;
            }
        }

        public T this[Index index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                var offset = index.GetOffset(Count);
                if (unchecked((uint)offset) >= Count)
                {
                    ThrowArgumentOutOfRangeException(nameof(index), $"{nameof(index)}がコレクションの範囲外です。");
                }
                return _data[(_first + offset) & _mask];
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnqueueFirst(T item)
        {
            if (_data.Length == Count)
            {
                Resize();
            }

            _first = (_first - 1) & _mask;
            _data[_first] = item;
            Count++;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnqueueLast(T item)
        {
            if (_data.Length == Count)
            {
                Resize();
            }

            _data[(_first + Count++) & _mask] = item;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T DequeueFirst()
        {
            if (Count == 0)
            {
                ThrowInvalidOperationException("Queueが空です。");
            }

            var value = _data[_first];
            _data[_first++] = default;
            _first &= _mask;
            Count--;
            return value;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T DequeueLast()
        {
            if (Count == 0)
            {
                ThrowInvalidOperationException("Queueが空です。");
            }

            var index = (_first + --Count) & _mask;
            var value = _data[index];
            _data[index] = default;
            return value;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T PeekFirst()
        {
            if (Count == 0)
            {
                ThrowInvalidOperationException("Queueが空です。");
            }

            return _data[_first];
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public T PeekLast()
        {
            if (Count == 0)
            {
                ThrowInvalidOperationException("Queueが空です。");
            }

            return _data[(_first + Count - 1) & _mask];
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Resize()
        {
            var newArray = new T[_data.Length << 1];
            var span = _data.AsSpan();
            var firstHalf = span[_first..];
            var lastHalf = span[.._first];
            firstHalf.CopyTo(newArray);
            lastHalf.CopyTo(newArray.AsSpan(firstHalf.Length));
            _data = newArray;
            _first = 0;
            _mask = _data.Length - 1;
        }

        private void ThrowArgumentOutOfRangeException(string paramName, string message) => throw new ArgumentOutOfRangeException(paramName, message);
        private void ThrowInvalidOperationException(string message) => throw new InvalidOperationException(message);

        private int GetPow2Over(int n)
        {
            n--;
            var result = 1;
            while (n != 0)
            {
                n >>= 1;
                result <<= 1;
            }
            return result;
        }

        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < Count; i++)
            {
                var offset = (_first + i) & _mask;
                yield return _data[offset];
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class PriorityQueue<T> : IEnumerable<T> where T : IComparable<T>
    {
        private List<T> _heap = new List<T>();
        private readonly int _reverseFactor;
        public int Count => _heap.Count;
        public bool IsDescending => _reverseFactor == 1;

        public PriorityQueue(bool descending) : this(descending, null) { }

        public PriorityQueue(bool descending, IEnumerable<T> collection)
        {
            _reverseFactor = descending ? 1 : -1;
            _heap = new List<T>();

            if (collection != null)
            {
                foreach (var item in collection)
                {
                    Enqueue(item);
                }
            }
        }

        public void Enqueue(T item)
        {
            _heap.Add(item);
            UpHeap();
        }

        public T Dequeue()
        {
            var item = _heap[0];
            DownHeap();
            return item;
        }

        public T Peek() => _heap[0];

        private void UpHeap()
        {
            var child = Count - 1;
            while (child > 0)
            {
                int parent = (child - 1) / 2;

                if (Compare(_heap[child], _heap[parent]) > 0)
                {
                    SwapAt(child, parent);
                    child = parent;
                }
                else
                {
                    break;
                }
            }
        }

        private void DownHeap()
        {
            _heap[0] = _heap[Count - 1];
            _heap.RemoveAt(Count - 1);

            var parent = 0;
            while (true)
            {
                var leftChild = 2 * parent + 1;

                if (leftChild > Count - 1)
                {
                    break;
                }

                var target = (leftChild < Count - 1) && (Compare(_heap[leftChild], _heap[leftChild + 1]) < 0) ? leftChild + 1 : leftChild;

                if (Compare(_heap[parent], _heap[target]) < 0)
                {
                    SwapAt(parent, target);
                }
                else
                {
                    break;
                }

                parent = target;
            }
        }

        private int Compare(T a, T b) => _reverseFactor * a.CompareTo(b);

        private void SwapAt(int n, int m) => (_heap[n], _heap[m]) = (_heap[m], _heap[n]);

        public IEnumerator<T> GetEnumerator()
        {
            var copy = new List<T>(_heap);
            try
            {
                while (Count > 0)
                {
                    yield return Dequeue();
                }
            }
            finally
            {
                _heap = copy;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class SegmentTree<TMonoid> : IEnumerable<TMonoid> where TMonoid : IMonoid<TMonoid>, new()
    {
        private readonly TMonoid[] _data;
        private readonly TMonoid _identityElement;

        private readonly int _leafOffset;   // n - 1
        private readonly int _leafLength;   // n (= 2^k)

        public int Length { get; }          // 実データ長
        public ReadOnlySpan<TMonoid> Data => _data.AsSpan(_leafOffset, Length);

        public SegmentTree(ICollection<TMonoid> data)
        {
            Length = data.Count;
            _leafLength = GetMinimumPow2(data.Count);
            _leafOffset = _leafLength - 1;
            _data = new TMonoid[_leafOffset + _leafLength];
            _identityElement = new TMonoid().Identity;

            data.CopyTo(_data, _leafOffset);
            BuildTree();
        }

        public TMonoid this[int index]
        {
            get => Data[index];
            set
            {
                if (index < 0 || index >= Length)
                {
                    throw new IndexOutOfRangeException($"{nameof(index)}がデータの範囲外です。");
                }
                index += _leafOffset;
                _data[index] = value;
                while (index > 0)
                {
                    // 一つ上の親の更新
                    index = (index - 1) / 2;
                    _data[index] = _data[index * 2 + 1].Merge(_data[index * 2 + 2]);
                }
            }
        }

        public TMonoid Query(Range range)
        {
            var (offset, length) = range.GetOffsetAndLength(Length);
            if (length <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(range), $"{nameof(range)}の長さは0より大きくなければなりません。");
            }
            return Query(offset, offset + length);
        }

        public TMonoid Query(int begin, int end)
        {
            if (begin < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(begin), $"{nameof(begin)}は0以上の数でなければなりません。");
            }
            if (end > Length)
            {
                throw new ArgumentOutOfRangeException(nameof(end), $"{nameof(end)}は{nameof(Length)}以下でなければなりません。");
            }
            if (begin >= end)
            {
                throw new ArgumentException($"{nameof(begin)},{nameof(end)}", $"{nameof(end)}は{nameof(begin)}より大きい数でなければなりません。");
            }
            return Query(begin, end, 0, 0, _leafLength);
        }

        private TMonoid Query(int begin, int end, int index, int left, int right)
        {
            if (right <= begin || end <= left)      // 範囲外
            {
                return _identityElement;
            }
            else if (begin <= left && right <= end) // 全部含まれる
            {
                return _data[index];
            }
            else    // 一部だけ含まれる
            {
                var leftValue = Query(begin, end, index * 2 + 1, left, (left + right) / 2);     // 左の子
                var rightValue = Query(begin, end, index * 2 + 2, (left + right) / 2, right);   // 右の子
                return leftValue.Merge(rightValue);
            }
        }

        private void BuildTree()
        {
            foreach (ref var unusedLeaf in _data.AsSpan()[(_leafOffset + Length)..])
            {
                unusedLeaf = _identityElement;  // 単位元埋め
            }

            for (int i = _leafLength - 2; i >= 0; i--)  // 葉の親から順番に一つずつ上がっていく
            {
                _data[i] = _data[2 * i + 1].Merge(_data[2 * i + 2]); // f(left, right)
            }
        }

        private int GetMinimumPow2(int n)
        {
            var p = 1;
            while (p < n)
            {
                p *= 2;
            }
            return p;
        }

        public IEnumerator<TMonoid> GetEnumerator()
        {
            var upperIndex = _leafOffset + Length;
            for (int i = _leafOffset; i < upperIndex; i++)
            {
                yield return _data[i];
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
    }

    public class LazySegmentTree<TMonoid, TOperator>
        where TMonoid : IMonoid<TMonoid>, new()
        where TOperator : IMonoidWithAct<TMonoid, TOperator>, IEquatable<TOperator>, new()
    {
        private readonly TMonoid[] _data;
        private readonly TOperator[] _lazy;
        private readonly TMonoid _monoidIdenty;
        private readonly TOperator _operatorIdentity;

        private readonly int _leafOffset;  // n - 1
        private readonly int _leafLength;  // n (= 2^k)

        public int Length { get; }

        public LazySegmentTree(ICollection<TMonoid> data)
        {
            Length = data.Count;
            _leafLength = GetMinimumPow2(data.Count);
            _leafOffset = _leafLength - 1;
            _data = new TMonoid[_leafOffset + _leafLength];
            _monoidIdenty = new TMonoid().Identity;
            _operatorIdentity = new TOperator().Identity;

            data.CopyTo(_data, _leafOffset);
            BuildTree();
            _lazy = Enumerable.Repeat(_operatorIdentity, _data.Length).ToArray();
        }

        private void LazyEvaluate(int index)
        {
            if (_lazy[index].Equals(_operatorIdentity))
            {
                return;
            }
            else if (index < _leafOffset) // 葉でない場合は子に伝播
            {
                var left = (index << 1) + 1;
                var right = left + 1;
                _lazy[left] = _lazy[index].Merge(_lazy[left]);
                _lazy[right] = _lazy[index].Merge(_lazy[right]);
            }

            // 自身を更新
            _data[index] = _lazy[index].Act(_data[index]);
            _lazy[index] = _operatorIdentity;
        }

        public void Update(int begin, int end, TOperator op)
        {
            if (begin < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(begin));
            }
            if (end > Length)
            {
                throw new ArgumentOutOfRangeException(nameof(end));
            }
            if (begin >= end)
            {
                throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
            }
            Update(begin, end, op, 0, 0, _leafLength);
        }

        private void Update(int begin, int end, TOperator op, int index, int left, int right)
        {
            LazyEvaluate(index);
            if (begin <= left && right <= end) // 全部含まれる
            {
                _lazy[index] = _lazy[index].Merge(op);
                LazyEvaluate(index);
            }
            else if (begin < right && left < end) // 一部だけ含まれる
            {
                var l = (index << 1) + 1;
                var r = l + 1;
                Update(begin, end, op, l, left, (left + right) / 2);
                Update(begin, end, op, r, (left + right) / 2, right);
                _data[index] = _data[l].Merge(_data[r]);
            }
        }

        public TMonoid Query(int begin, int end)
        {
            if (begin < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(begin));
            }
            if (end > Length)
            {
                throw new ArgumentOutOfRangeException(nameof(end));
            }
            if (begin >= end)
            {
                throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
            }
            return Query(begin, end, 0, 0, _leafLength);
        }

        private TMonoid Query(int begin, int end, int index, int left, int right)
        {
            LazyEvaluate(index);
            if (right <= begin || end <= left)      // 範囲外
            {
                return _monoidIdenty;
            }
            else if (begin <= left && right <= end) // 全部含まれる
            {
                return _data[index];
            }
            else    // 一部だけ含まれる
            {
                var l = (index << 1) + 1;
                var r = l + 1;
                var leftValue = Query(begin, end, l, left, (left + right) / 2);     // 左の子
                var rightValue = Query(begin, end, r, (left + right) / 2, right);   // 右の子
                return leftValue.Merge(rightValue);
            }
        }

        private void BuildTree()
        {
            foreach (ref var unusedLeaf in _data.AsSpan()[(_leafOffset + Length)..])
            {
                unusedLeaf = _monoidIdenty;  // 単位元埋め
            }

            for (int i = _leafLength - 2; i >= 0; i--)  // 葉の親から順番に一つずつ上がっていく
            {
                var left = (i << 1) + 1;
                var right = left + 1;
                _data[i] = _data[left].Merge(_data[right]); // f(left, right)
            }
        }

        private int GetMinimumPow2(int n)
        {
            var p = 1;
            while (p < n)
            {
                p <<= 1;
            }
            return p;
        }
    }

    public class BinaryIndexedTree
    {
        long[] _data;
        public int Length { get; }

        public BinaryIndexedTree(int length)
        {
            _data = new long[length + 1];   // 内部的には1-indexedにする
            Length = length;
        }

        public BinaryIndexedTree(IEnumerable<long> data, int length) : this(length)
        {
            var count = 0;
            foreach (var n in data)
            {
                AddAt(count++, n);
            }
        }

        public BinaryIndexedTree(ICollection<long> collection) : this(collection, collection.Count) { }

        public long this[Index index]
        {
            get => Sum(index..(index.GetOffset(Length) + 1));
            set
            {
                if (value < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(value), $"{nameof(value)}は0以上の値である必要があります。");
                }
                AddAt(index, value - this[index]);
            }
        }

        /// <summary>
        /// BITの<c>index</c>番目の要素に<c>n</c>を加算します。
        /// </summary>
        /// <param name="index">加算するインデックス（0-indexed）</param>
        /// <param name="value">加算する数</param>
        public void AddAt(Index index, long value)
        {
            var i = index.GetOffset(Length);
            unchecked
            {
                if ((uint)i >= (uint)Length)
                {
                    throw new ArgumentOutOfRangeException(nameof(index));
                }
            }

            i++;  // 1-indexedにする

            while (i <= Length)
            {
                _data[i] += value;
                i += i & -i;    // LSBの加算
            }
        }

        /// <summary>
        /// [0, <c>end</c>)の部分和を返します。
        /// </summary>
        /// <param name="end">部分和を求める半開区間の終了インデックス</param>
        /// <returns>区間の部分和</returns>
        public long Sum(Index end)
        {
            var i = end.GetOffset(Length);  // 0-indexedの半開区間＝1-indexedの閉区間なので+1は不要
            unchecked
            {
                if ((uint)i >= (uint)_data.Length)
                {
                    throw new ArgumentOutOfRangeException(nameof(end));
                }
            }

            long sum = 0;
            while (i > 0)
            {
                sum += _data[i];
                i -= i & -i;    // LSBの減算
            }
            return sum;
        }

        /// <summary>
        /// <c>range</c>の部分和を返します。
        /// </summary>
        /// <param name="range">部分和を求める半開区間</param>
        /// <returns>区間の部分和</returns>
        public long Sum(Range range) => Sum(range.End) - Sum(range.Start);

        /// <summary>
        /// [<c>start</c>, <c>end</c>)の部分和を返します。
        /// </summary>
        /// <param name="start">部分和を求める半開区間の開始インデックス</param>
        /// <param name="end">部分和を求める半開区間の終了インデックス</param>
        /// <returns>区間の部分和</returns>
        public long Sum(int start, int end) => Sum(end) - Sum(start);

        /// <summary>
        /// [0, <c>index</c>)の部分和が<c>sum</c>未満になる最大の<c>index</c>を返します。
        /// BIT上の各要素は0以上の数である必要があります。
        /// </summary>
        /// <param name="sum"></param>
        /// <returns></returns>
        public int GetLowerBound(long sum)
        {
            int index = 0;
            for (int offset = GetMostSignificantBitOf(Length); offset > 0; offset >>= 1)
            {
                if (index + offset < _data.Length && _data[index + offset] < sum)
                {
                    index += offset;
                    sum -= _data[index];
                }
            }

            return index;

            int GetMostSignificantBitOf(int n)
            {
                int k = 1;
                while ((k << 1) <= n)
                {
                    k <<= 1;
                };
                return k;
            }
        }
    }

    public class BinaryIndexedTree2D
    {
        long[,] _data;
        public int Height { get; }
        public int Width { get; }

        public BinaryIndexedTree2D(int height, int width)
        {
            Height = height;
            Width = width;
            _data = new long[height + 1, width + 1];
        }

        public long this[Index row, Index column]
        {
            get => Sum(row..(row.GetOffset(Height) + 1), column..(column.GetOffset(Width) + 1));
            set
            {
                if (value < 0)
                {
                    throw new ArgumentOutOfRangeException(nameof(value), $"{nameof(value)}は0以上の値である必要があります。");
                }
                AddAt(row, column, value - this[row, column]);
            }
        }

        /// <summary>
        /// 2次元BITの[<c>row</c>, <c>column</c>]に<c>value</c>を足します。
        /// </summary>
        /// <param name="row">加算する行（0-indexed）</param>
        /// <param name="column">加算する列（0-indexed）</param>
        /// <param name="value">加算する値</param>
        public void AddAt(Index row, Index column, long value)
        {
            var initI = row.GetOffset(Height);
            var initJ = column.GetOffset(Width);
            unchecked
            {
                if ((ulong)initI >= (ulong)Height)
                {
                    throw new ArgumentOutOfRangeException(nameof(row));
                }
                if ((ulong)initJ >= (ulong)Width)
                {
                    throw new ArgumentOutOfRangeException(nameof(column));
                }
            }

            initI++;    // 1-indexed
            initJ++;

            for (int i = initI; i <= Height; i += i & -i)
            {
                for (int j = initJ; j <= Width; j += j & -j)
                {
                    _data[i, j] += value;
                }
            }
        }

        /// <summary>
        /// 指定した半開区間の部分和を返します。
        /// </summary>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <returns></returns>
        public long Sum(Index row, Index column)
        {
            long sum = 0;
            var initI = row.GetOffset(Height);
            var initJ = column.GetOffset(Width);
            unchecked
            {
                if ((ulong)initI >= (ulong)(Height + 1))
                {
                    throw new ArgumentOutOfRangeException(nameof(row));
                }
                if ((ulong)initJ >= (ulong)(Width + 1))
                {
                    throw new ArgumentOutOfRangeException(nameof(column));
                }
            }

            for (int i = initI; i > 0; i -= i & -i)
            {
                for (int j = initJ; j > 0; j -= j & -j)
                {
                    sum += _data[i, j];
                }
            }
            return sum;
        }

        /// <summary>
        /// 指定した半開区間の部分和を返します。
        /// </summary>
        /// <param name="rows"></param>
        /// <param name="columns"></param>
        /// <returns></returns>
        public long Sum(Range rows, Range columns) => Sum(rows.End, columns.End) - Sum(rows.Start, columns.End) - Sum(rows.End, columns.Start) + Sum(rows.Start, columns.Start);

        /// <summary>
        /// 指定した半開区間の部分和を返します。
        /// </summary>
        /// <param name="beginRow"></param>
        /// <param name="endRow"></param>
        /// <param name="beginColumn"></param>
        /// <param name="endColumn"></param>
        /// <returns></returns>
        public long Sum(int beginRow, int endRow, int beginColumn, int endColumn) => Sum(beginRow..endRow, beginColumn..endColumn);
    }

    /// <summary>
    /// <para>Red-Black tree which allows duplicated values (like multiset).</para>
    /// <para>Based on .NET Runtime https://github.com/dotnet/runtime/blob/master/src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs </para>
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// 
    /// .NET Runtime
    ///   Copyright (c) .NET Foundation and Contributors
    ///   Released under the MIT license
    ///   https://github.com/dotnet/runtime/blob/master/LICENSE.TXT
    public class RedBlackTree<T> : ICollection<T>, IReadOnlyCollection<T> where T : IComparable<T>
    {
        public int Count { get; private set; }

        public bool IsReadOnly => false;

        protected Node _root;

        public T this[Index index]
        {
            get
            {
                var i = index.GetOffset(Count);
                if (unchecked((uint)i) >= Count)
                {
                    throw new ArgumentOutOfRangeException(nameof(index));
                }

                var current = _root;
                while (true)
                {
                    var leftCount = current.Left?.Count ?? 0;
                    if (leftCount == i)
                    {
                        return current.Item;
                    }
                    else if (leftCount > i)
                    {
                        current = current.Left;
                    }
                    else
                    {
                        i -= leftCount + 1;
                        current = current.Right;
                    }
                }
            }
        }

        /// <summary>
        /// 最小の要素を返します。要素が空の場合、default値を返します。
        /// </summary>
        public T Min
        {
            get
            {
                if (_root == null)
                {
                    return default;
                }
                else
                {
                    var current = _root;
                    while (current.Left != null)
                    {
                        current = current.Left;
                    }
                    return current.Item;
                }
            }
        }

        /// <summary>
        /// 最大の要素を返します。要素が空の場合、default値を返します。
        /// </summary>
        public T Max
        {
            get
            {
                if (_root == null)
                {
                    return default;
                }
                else
                {
                    var current = _root;
                    while (current.Right != null)
                    {
                        current = current.Right;
                    }
                    return current.Item;
                }
            }
        }

        #region ICollection<T> members

        public void Add(T item)
        {
            if (_root == null)
            {
                _root = new Node(item, NodeColor.Black);
                Count = 1;
                return;
            }

            Node current = _root;
            Node parent = null;
            Node grandParent = null;        // 親、祖父はRotateで直接いじる
            Node greatGrandParent = null;   // 曾祖父はRotate後のつなぎ替えで使う（2回Rotateすると曾祖父がcurrentの親になる）

            var order = 0;
            while (current != null)
            {
                current.Count++;    // 部分木サイズ++
                order = item.CompareTo(current.Item);

                if (current.Is4Node)
                {
                    // 4-node (RBR) の場合は2-node x 2 (BRB) に変更
                    current.Split4Node();
                    if (Node.IsNonNullRed(parent))
                    {
                        // Splitの結果親と2連続でRRになったら修正
                        InsertionBalance(current, ref parent, grandParent, greatGrandParent);
                    }
                }

                greatGrandParent = grandParent;
                grandParent = parent;
                parent = current;
                current = order <= 0 ? current.Left : current.Right;
            }

            var newNode = new Node(item, NodeColor.Red);
            if (order <= 0)
            {
                parent.Left = newNode;
            }
            else
            {
                parent.Right = newNode;
            }

            if (parent.IsRed)
            {
                // Redの親がRedのときは修正
                InsertionBalance(newNode, ref parent, grandParent, greatGrandParent);
            }

            _root.Color = NodeColor.Black;  // rootは常にBlack（Red->Blackとなったとき木全体の黒高さが1増える）
            Count++;
        }

        public void Clear()
        {
            _root = null;
            Count = 0;
        }

        public bool Contains(T item)
        {
            var current = _root;
            while (current != null)
            {
                var order = item.CompareTo(current.Item);
                if (order == 0)
                {
                    return true;
                }
                else
                {
                    current = order <= 0 ? current.Left : current.Right;
                }
            }
            return false;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            foreach (var value in this)
            {
                array[arrayIndex++] = value;
            }
        }

        public bool Remove(T item)
        {
            // .NET RuntimeのSortedSet<T>はややトリッキーな実装をしている。
            // 値の検索を行う際、検索パスにある全ての2-nodeを3-nodeまたは4-nodeに変更しつつ進んでいくのだが、
            // 各ノードに部分木のサイズを持たせたい場合、実装が難しくなるため、一般的な実装を用いることとする。
            // （削除が失敗した場合はサイズが変わらず、成功した場合のみサイズが変更となるため、パスを保存しておきたいのだが、
            // 　木を回転させながら検索を行うと木の親子関係が変化するため、パスも都度変更となってしまう。）

            var found = false;
            Node current = _root;
            var parents = new Stack<Node>(2 * Log2(Count + 1));  // 親ノードのスタック
            parents.Push(null); // 番兵

            while (current != null)
            {
                parents.Push(current);
                var order = item.CompareTo(current.Item);
                if (order == 0)
                {
                    found = true;
                    break;
                }
                else
                {
                    current = order < 0 ? current.Left : current.Right;
                }
            }

            if (!found)
            {
                // 見付からなければreturn
                return false;
            }

            // 子を2つ持つ場合
            if (current.Left != null && current.Right != null)
            {
                // 右部分木の最小ノードを探す
                parents.Push(current.Right);
                var minNode = GetMinNode(current.Right, parents);

                // この最小値の値だけもらってしまい、あとはこの最小値ノードを削除することを考えればよい
                current.Item = minNode.Item;
                current = minNode;
            }

            // 通ったパス上にある部分木のサイズを全て1だけデクリメント
            parents.Pop();  // これは今から消すので不要
            Count--;
            foreach (var node in parents)
            {
                if (node != null)
                {
                    node.Count--;
                }
            }

            // 切り離した部分をくっつける。子を2つ持つ場合については上で考えたため、子を0or1つ持つ場合を考えればよい
            // 二分木の黒高さが全て等しいという条件より、片方だけ2個以上伸びているということは起こり得ない
            var parent = parents.Peek();
            ReplaceChildOrRoot(parent, current, current.Left ?? current.Right);  // L/Rのどちらかnullでない方。どちらもnullならnullが入る

            // 削除するノードが赤の場合は修正不要
            if (current.IsRed)
            {
                return true;
            }

            // つなぎ替えられた方の子
            current = current.Left ?? current.Right;

            while ((parent = parents.Pop()) != null)
            {
                var toFix = DeleteBalance(current, parent, out var newParent);
                ReplaceChildOrRoot(parents.Peek(), parent, newParent);

                if (!toFix)
                {
                    break;
                }
                current = newParent;
            }

            if (_root != null)
            {
                _root.Color = NodeColor.Black;
            }
            return true;
        }

        private static Node GetMinNode(Node current, Stack<Node> parents)
        {
            while (current.Left != null)
            {
                current = current.Left;
                parents.Push(current);
            }
            return current;
        }

        public IEnumerator<T> GetEnumerator()
        {
            if (_root != null)
            {
                var stack = new Stack<Node>(2 * Log2(Count + 1));
                PushLeft(stack, _root);

                while (stack.Count > 0)
                {
                    var current = stack.Pop();
                    yield return current.Item;
                    PushLeft(stack, current.Right);
                }
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();

        #endregion

        /// <summary>
        /// [inclusiveMin, exclusiveMax)を満たす要素を昇順に列挙します。
        /// </summary>
        /// <param name="inclusiveMin">区間の最小値（それ自身を含む）</param>
        /// <param name="exclusiveMax">区間の最大値（それ自身を含まない）</param>
        /// <returns></returns>
        public IEnumerable<T> EnumerateRange(T inclusiveMin, T exclusiveMax)
        {
            if (_root != null)
            {
                var stack = new Stack<Node>(2 * Log2(Count + 1));
                var current = _root;
                while (current != null)
                {
                    var order = current.Item.CompareTo(inclusiveMin);
                    if (order >= 0)
                    {
                        stack.Push(current);
                        current = current.Left;
                    }
                    else
                    {
                        current = current.Right;
                    }
                }

                while (stack.Count > 0)
                {
                    current = stack.Pop();
                    var order = current.Item.CompareTo(exclusiveMax);
                    if (order >= 0)
                    {
                        yield break;
                    }
                    else
                    {
                        yield return current.Item;
                        PushLeft(stack, current.Right);
                    }
                }
            }
        }

        private static void PushLeft(Stack<Node> stack, Node node)
        {
            while (node != null)
            {
                stack.Push(node);
                node = node.Left;
            }
        }

        private static int Log2(int n)
        {
            int result = 0;
            while (n > 0)
            {
                result++;
                n >>= 1;
            }
            return result;
        }

        // After calling InsertionBalance, we need to make sure `current` and `parent` are up-to-date.
        // It doesn't matter if we keep `grandParent` and `greatGrandParent` up-to-date, because we won't
        // need to split again in the next node.
        // By the time we need to split again, everything will be correctly set.
        private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent)
        {
            Debug.Assert(parent != null);
            Debug.Assert(grandParent != null);

            var parentIsOnRight = grandParent.Right == parent;
            var currentIsOnRight = parent.Right == current;

            Node newChildOfGreatGrandParent;
            if (parentIsOnRight == currentIsOnRight)
            {
                // LL or RRなら1回転でOK
                newChildOfGreatGrandParent = currentIsOnRight ? grandParent.RotateLeft() : grandParent.RotateRight();
            }
            else
            {
                // LR or RLなら2回転
                newChildOfGreatGrandParent = currentIsOnRight ? grandParent.RotateLeftRight() : grandParent.RotateRightLeft();
                // 1回転ごとに1つ上に行くため、2回転させると曾祖父が親になる
                // リンク先「挿入操作」を参照 http://wwwa.pikara.ne.jp/okojisan/rb-tree/index.html
                parent = greatGrandParent;
            }

            // 祖父は親の子（1回転）もしくは自分の子（2回転）のいずれかになる
            // この時点で色がRRBもしくはBRRになっているため、BRBに修正
            // リンク先「挿入操作」を参照 http://wwwa.pikara.ne.jp/okojisan/rb-tree/index.html
            grandParent.Color = NodeColor.Red;
            newChildOfGreatGrandParent.Color = NodeColor.Black;

            ReplaceChildOrRoot(greatGrandParent, grandParent, newChildOfGreatGrandParent);
        }

        private bool DeleteBalance(Node current, Node parent, out Node newParent)
        {
            // 削除パターンは大きく分けて4つ
            // See: http://wwwa.pikara.ne.jp/okojisan/rb-tree/index.html

            // currentはもともと黒なので（黒でなければ修正する必要がないため）、兄弟はnullにはなり得ない
            var sibling = parent.GetSibling(current);
            if (sibling.IsBlack)
            {
                if (Node.IsNonNullRed(sibling.Left) || Node.IsNonNullRed(sibling.Right))
                {
                    var parentColor = parent.Color;
                    var siblingRedChild = Node.IsNonNullRed(sibling.Left) ? sibling.Left : sibling.Right;
                    var currentIsOnRight = parent.Right == current;
                    var siblingRedChildIsRight = sibling.Right == siblingRedChild;

                    if (currentIsOnRight != siblingRedChildIsRight)
                    {
                        // 1回転
                        parent.Color = NodeColor.Black;
                        sibling.Color = parentColor;
                        siblingRedChild.Color = NodeColor.Black;
                        newParent = currentIsOnRight ? parent.RotateRight() : parent.RotateLeft();
                    }
                    else
                    {
                        // 2回転
                        parent.Color = NodeColor.Black;
                        siblingRedChild.Color = parentColor;
                        newParent = currentIsOnRight ? parent.RotateLeftRight() : parent.RotateRightLeft();
                    }

                    return false;
                }
                else
                {
                    var needToFix = parent.IsBlack;
                    parent.Color = NodeColor.Black;
                    sibling.Color = NodeColor.Red;
                    newParent = parent;
                    return needToFix;
                }
            }
            else
            {
                if (current == parent.Right)
                {
                    newParent = parent.RotateRight();
                }
                else
                {
                    newParent = parent.RotateLeft();
                }

                parent.Color = NodeColor.Red;
                sibling.Color = NodeColor.Black;
                DeleteBalance(current, parent, out var newChildOfParent);  // 再帰は1回限り
                ReplaceChildOrRoot(newParent, parent, newChildOfParent);
                return false;
            }
        }

        /// <summary>
        /// 親ノードの子を新しいものに差し替える。ただし親がいなければrootとする。
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="child"></param>
        /// <param name="newChild"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void ReplaceChildOrRoot(Node parent, Node child, Node newChild)
        {
            if (parent != null)
            {
                parent.ReplaceChild(child, newChild);
            }
            else
            {
                _root = newChild;
            }
        }

        #region Debugging

        [Conditional("DEBUG")]
        internal void PrintTree() => PrintTree(_root, 0);

        [Conditional("DEBUG")]
        private void PrintTree(Node node, int depth)
        {
            const int Space = 6;
            if (node != null)
            {
                PrintTree(node.Right, depth + 1);
                if (node.IsRed)
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.Write(string.Concat(Enumerable.Repeat(' ', Space * depth)));
                    Console.WriteLine($"{node.Item} ({node.Count})");
                    Console.ResetColor();
                }
                else
                {
                    Console.Write(string.Concat(Enumerable.Repeat(' ', Space * depth)));
                    Console.WriteLine($"{node.Item} ({node.Count})");
                }
                PrintTree(node.Left, depth + 1);
            }
        }

        [Conditional("DEBUG")]
        internal void AssertCorrectRedBrackTree() => AssertCorrectRedBrackTree(_root);

        private int AssertCorrectRedBrackTree(Node node)
        {
            if (node != null)
            {
                // Redが2つ繋がっていないか？
                Debug.Assert(!(node.IsRed && Node.IsNonNullRed(node.Left)));
                Debug.Assert(!(node.IsRed && Node.IsNonNullRed(node.Right)));

                // 左右の黒高さは等しいか？
                var left = AssertCorrectRedBrackTree(node.Left);
                var right = AssertCorrectRedBrackTree(node.Right);
                Debug.Assert(left == right);
                if (node.IsBlack)
                {
                    left++;
                }
                return left;
            }
            else
            {
                return 0;
            }
        }

        #endregion

        protected enum NodeColor : byte
        {
            Black,
            Red
        }

        [DebuggerDisplay("Item = {Item}, Size = {Count}")]
        protected sealed class Node
        {
            public T Item { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }
            public NodeColor Color { get; set; }
            /// <summary>部分木のサイズ</summary>
            public int Count { get; set; }

            public bool IsBlack => Color == NodeColor.Black;
            public bool IsRed => Color == NodeColor.Red;
            public bool Is2Node => IsBlack && IsNullOrBlack(Left) && IsNullOrBlack(Right);
            public bool Is4Node => IsNonNullRed(Left) && IsNonNullRed(Right);

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private void UpdateCount() => Count = GetCountOrDefault(Left) + GetCountOrDefault(Right) + 1;
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public static bool IsNonNullBlack(Node node) => node != null && node.IsBlack;
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public static bool IsNonNullRed(Node node) => node != null && node.IsRed;
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public static bool IsNullOrBlack(Node node) => node == null || node.IsBlack;
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            private static int GetCountOrDefault(Node node) => node?.Count ?? 0;    // C# 6.0 or later

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public Node(T item, NodeColor color)
            {
                Item = item;
                Color = color;
                Count = 1;
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public void Split4Node()
            {
                Color = NodeColor.Red;
                Left.Color = NodeColor.Black;
                Right.Color = NodeColor.Black;
            }

            // 各種Rotateでは位置関係だけ修正する。色までは修正しない。
            // 親になったノード（部分木の根）を返り値とする。
            // childとかgrandChildとかは祖父（Rotate前の3世代中一番上）目線での呼び方
            public Node RotateLeft()
            {
                // 右の子が自分の親になる
                var child = Right;
                Right = child.Left;
                child.Left = this;
                UpdateCount();
                child.UpdateCount();
                return child;
            }

            public Node RotateRight()
            {
                // 左の子が自分の親になる
                var child = Left;
                Left = child.Right;
                child.Right = this;
                UpdateCount();
                child.UpdateCount();
                return child;
            }

            public Node RotateLeftRight()
            {
                var child = Left;
                var grandChild = child.Right;

                Left = grandChild.Right;
                grandChild.Right = this;
                child.Right = grandChild.Left;
                grandChild.Left = child;
                UpdateCount();
                child.UpdateCount();
                grandChild.UpdateCount();
                return grandChild;
            }

            public Node RotateRightLeft()
            {
                var child = Right;
                var grandChild = child.Left;

                Right = grandChild.Left;
                grandChild.Left = this;
                child.Left = grandChild.Right;
                grandChild.Right = child;
                UpdateCount();
                child.UpdateCount();
                grandChild.UpdateCount();
                return grandChild;
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public void ReplaceChild(Node child, Node newChild)
            {
                if (Left == child)
                {
                    Left = newChild;
                }
                else
                {
                    Right = newChild;
                }
            }

            /// <summary>
            /// 兄弟を取得する。
            /// </summary>
            /// <param name="node"></param>
            /// <returns></returns>
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public Node GetSibling(Node node) => node == Left ? Right : Left;

            /// <summary>
            /// 左右の2-nodeを4-nodeにマージする。
            /// </summary>
            public void Merge2Nodes()
            {
                Color = NodeColor.Black;
                Left.Color = NodeColor.Red;
                Right.Color = NodeColor.Red;
            }
        }
    }

    public class Counter<T> : IEnumerable<(T key, long count)> where T : IEquatable<T>
    {
        private Dictionary<T, long> _innerDictionary;

        public Counter()
        {
            _innerDictionary = new Dictionary<T, long>();
        }

        public IEnumerator<(T key, long count)> GetEnumerator()
        {
            foreach (var pair in _innerDictionary)
            {
                yield return (key: pair.Key, count: pair.Value);
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();

        public long this[T key]
        {
            get
            {
                _innerDictionary.TryGetValue(key, out var count);
                return count;
            }
            set
            {
                _innerDictionary[key] = value;
            }
        }
    }

    public readonly struct BitSet : IEquatable<BitSet>
    {
        readonly uint _value;

        public BitSet(uint value)
        {
            _value = value;
        }
        public bool this[int digit]
        {
            get => ((_value >> digit) & 1) > 0;
        }
        public bool Any => _value > 0;
        public bool None => _value == 0;
        public BitSet SetAt(int digit, bool value) => value ? new BitSet(_value | (1u << digit)) : new BitSet(_value & ~(1u << digit));
        public BitSet Lsb() { unchecked { return new BitSet(_value & (uint)-(int)_value); } }
        public BitSet Reverse()
        {
            unchecked
            {
                uint v = _value;
                v = (v & 0x55555555) << 1 | (v >> 1 & 0x55555555);
                v = (v & 0x33333333) << 2 | (v >> 2 & 0x33333333);
                v = (v & 0x0f0f0f0f) << 4 | (v >> 4 & 0x0f0f0f0f);
                v = (v & 0x00ff00ff) << 8 | (v >> 8 & 0x00ff00ff);
                v = (v & 0x0000ffff) << 16 | (v >> 16 & 0x0000ffff);
                return new BitSet(v);
            }
        }
        public int Count()
        {
            unchecked
            {
                // Hardware Intrinsics未使用
                uint v = _value;
                v = (v & 0x55555555) + (v >> 1 & 0x55555555);
                v = (v & 0x33333333) + (v >> 2 & 0x33333333);
                v = (v & 0x0f0f0f0f) + (v >> 4 & 0x0f0f0f0f);
                v = (v & 0x00ff00ff) + (v >> 8 & 0x00ff00ff);
                v = (v & 0x0000ffff) + (v >> 16 & 0x0000ffff);
                return (int)v;
            }
        }

        public static BitSet Zero => new BitSet(0);
        public static BitSet One => new BitSet(1);
        public static BitSet All => new BitSet(~0u);
        public static BitSet At(int digit) => new BitSet(1u << digit);
        public static BitSet CreateMask(int digit) => new BitSet((1u << digit) - 1);
        public static BitSet operator ++(BitSet bitSet) => new BitSet(bitSet._value + 1);
        public static BitSet operator --(BitSet bitSet) => new BitSet(bitSet._value - 1);
        public static BitSet operator ~(BitSet bitSet) => new BitSet(~bitSet._value);
        public static BitSet operator &(BitSet left, BitSet right) => new BitSet(left._value & right._value);
        public static BitSet operator |(BitSet left, BitSet right) => new BitSet(left._value | right._value);
        public static BitSet operator ^(BitSet left, BitSet right) => new BitSet(left._value ^ right._value);
        public static BitSet operator <<(BitSet bitSet, int n) => new BitSet(bitSet._value << n);
        public static BitSet operator >>(BitSet bitSet, int n) => new BitSet(bitSet._value >> n);
        public static bool operator <(BitSet left, BitSet right) => left._value < right._value;
        public static bool operator <=(BitSet left, BitSet right) => left._value <= right._value;
        public static bool operator >(BitSet left, BitSet right) => left._value > right._value;
        public static bool operator >=(BitSet left, BitSet right) => left._value >= right._value;
        public static bool operator ==(BitSet left, BitSet right) => left.Equals(right);
        public static bool operator !=(BitSet left, BitSet right) => !(left == right);
        public static implicit operator uint(BitSet bitSet) => bitSet._value;

        public override bool Equals(object obj) => obj is BitSet set && Equals(set);
        public bool Equals(BitSet other) => _value == other._value;
        public override string ToString() => Convert.ToString(_value, 2);
        public override int GetHashCode() => _value.GetHashCode();
    }

    public class ExpandableArray<T>
    {
        const int DefaultCapacity = 4;
        private T[] _data;
        public Span<T> Span => _data.AsSpan(0, Count);

        public int Count { get; private set; }

        public ExpandableArray() => Allocate(DefaultCapacity);

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public ExpandableArray(int capacity)
        {
            capacity = Math.Max(capacity, DefaultCapacity);
            Allocate(capacity);
        }

        public ExpandableArray(IEnumerable<T> collection)
        {
            if (collection is ICollection<T> c)
            {
                Allocate(c.Count);
                c.CopyTo(_data, 0);
                Count = c.Count;
            }
            else
            {
                Allocate(DefaultCapacity);
                foreach (var item in collection)
                {
                    Add(item);
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Allocate(int minCapacity)
        {
            var length = 1 << System.Numerics.BitOperations.Log2((uint)(minCapacity - 1)) + 1;
            _data = new T[length];
        }

        public T this[Index index]
        {
            get => Span[index];
            set => Span[index] = value;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add(T item)
        {
            if (Count == _data.Length)
            {
                Expand();
            }

            _data[Count++] = item;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void RemoveLast()
        {
            if (Count == 0)
            {
                ThrowInvalidOperationException("要素が空です。");
            }

            _data[Count--] = default;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Expand()
        {
            var length = _data.Length << 1;
            var newData = new T[length];
            Span.CopyTo(newData);
            _data = newData;
        }

        private static void ThrowInvalidOperationException(string message) => throw new InvalidOperationException(message);
        public override string ToString() => $"{nameof(T)}[{Count}]";
        public static implicit operator Span<T>(ExpandableArray<T> array) => array.Span;
        public static implicit operator ReadOnlySpan<T>(ExpandableArray<T> array) => array.Span;
    }

    public static class SearchExtensions
    {
        class LowerBoundComparer<T> : IComparer<T> where T : IComparable<T>
        {
            public int Compare(T x, T y) => 0 <= x.CompareTo(y) ? 1 : -1;
        }

        class UpperBoundComparer<T> : IComparer<T> where T : IComparable<T>
        {
            public int Compare(T x, T y) => 0 < x.CompareTo(y) ? 1 : -1;
        }

        // https://trsing.hatenablog.com/entry/2019/08/27/211038
        public static int GetGreaterEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMin) where T : IComparable<T> => ~span.BinarySearch(inclusiveMin, new UpperBoundComparer<T>());
        public static int GetGreaterThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMin) where T : IComparable<T> => ~span.BinarySearch(exclusiveMin, new LowerBoundComparer<T>());
        public static int GetLessEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMax) where T : IComparable<T> => ~span.BinarySearch(inclusiveMax, new LowerBoundComparer<T>()) - 1;
        public static int GetLessThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMax) where T : IComparable<T> => ~span.BinarySearch(exclusiveMax, new UpperBoundComparer<T>()) - 1;
        public static int GetGreaterEqualIndex<T>(this Span<T> span, T inclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterEqualIndex(inclusiveMin);
        public static int GetGreaterThanIndex<T>(this Span<T> span, T exclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterThanIndex(exclusiveMin);
        public static int GetLessEqualIndex<T>(this Span<T> span, T inclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessEqualIndex(inclusiveMax);
        public static int GetLessThanIndex<T>(this Span<T> span, T exclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessThanIndex(exclusiveMax);

        public static int BoundaryBinarySearch(Predicate<int> predicate, int ok, int ng)
        {
            // めぐる式二分探索
            while (Math.Abs(ok - ng) > 1)
            {
                int mid = (ok + ng) / 2;
                if (predicate(mid))
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }
            return ok;
        }

        public static long BoundaryBinarySearch(Predicate<long> predicate, long ok, long ng)
        {
            while (Math.Abs(ok - ng) > 1)
            {
                long mid = (ok + ng) / 2;
                if (predicate(mid))
                {
                    ok = mid;
                }
                else
                {
                    ng = mid;
                }
            }
            return ok;
        }

        public static double Bisection(Func<double, double> f, double a, double b, double eps = 1e-9)
        {
            if (f(a) * f(b) >= 0)
            {
                throw new ArgumentException("f(a)とf(b)は異符号である必要があります。");
            }

            const int maxLoop = 100;
            double mid = (a + b) / 2;

            for (int i = 0; i < maxLoop; i++)
            {
                if (f(a) * f(mid) < 0)
                {
                    b = mid;
                }
                else
                {
                    a = mid;
                }
                mid = (a + b) / 2;
                if (Math.Abs(b - a) < eps)
                {
                    break;
                }
            }
            return mid;
        }
    }

    public static class PermutationAlgorithms
    {
        public static IEnumerable<ReadOnlyMemory<T>> GetPermutations<T>(IEnumerable<T> collection) where T : IComparable<T> => GetPermutations(collection, false);

        public static IEnumerable<ReadOnlyMemory<T>> GetPermutations<T>(IEnumerable<T> collection, bool isSorted) where T : IComparable<T>
        {
            var a = collection.ToArray();

            if (!isSorted && a.Length > 1)
            {
                Array.Sort(a);
            }

            yield return a; // ソート済み初期配列

            if (a.Length <= 2)
            {
                if (a.Length == 2 && a[0].CompareTo(a[1]) != 0)
                {
                    (a[0], a[1]) = (a[1], a[0]);
                    yield return a;
                    yield break;
                }

                yield break;
            }

            bool flag = true;
            while (flag)
            {
                flag = false;
                for (int i = a.Length - 2; i >= 0; i--)
                {
                    // iよりi+1の方が大きい（昇順）なら
                    if (a[i].CompareTo(a[i + 1]) < 0)
                    {
                        // 後ろから見ていってi<jとなるところを探して
                        int j;
                        for (j = a.Length - 1; a[i].CompareTo(a[j]) >= 0; j--) { }

                        // iとjを入れ替えて
                        (a[i], a[j]) = (a[j], a[i]);

                        // i+1以降を反転
                        if (i < a.Length - 2)
                        {
                            var sliced = a.AsSpan().Slice(i + 1);
                            sliced.Reverse();
                        }

                        flag = true;
                        yield return a;
                        break;
                    }
                }
            }
        }
    }

    public static class EnumerableExtensions
    {
        public static IEnumerable<(T1 v1, T2 v2)> Zip<T1, T2>(this (IEnumerable<T1> First, IEnumerable<T2> Second) t)
            => t.First.Zip(t.Second, (v1, v2) => (v1, v2));

        public static IEnumerable<(T1 v1, T2 v2, T3 v3)> Zip<T1, T2, T3>(this (IEnumerable<T1> First, IEnumerable<T2> Second, IEnumerable<T3> Third) t)
            => (t.First, t.Second).Zip().Zip(t.Third, (v12, v3) => (v12.v1, v12.v2, v3));

        public static IEnumerable<(T item, int index)> WithIndex<T>(this IEnumerable<T> source) => source.Select((item, index) => (item, index));
    }

    public static class ArrayExtensions
    {
        public static T[,] Fill<T>(this T[,] array, T value)
        {
            var length0 = array.GetLength(0);
            var length1 = array.GetLength(1);
            for (int i = 0; i < length0; i++)
                for (int j = 0; j < length1; j++)
                    array[i, j] = value;
            return array;
        }

        public static T[,,] Fill<T>(this T[,,] array, T value)
        {
            var length0 = array.GetLength(0);
            var length1 = array.GetLength(1);
            var length2 = array.GetLength(2);
            for (int i = 0; i < length0; i++)
                for (int j = 0; j < length1; j++)
                    for (int k = 0; k < length2; k++)
                        array[i, j, k] = value;
            return array;
        }

        public static T[,,,] Fill<T>(this T[,,,] array, T value)
        {
            var length0 = array.GetLength(0);
            var length1 = array.GetLength(1);
            var length2 = array.GetLength(2);
            var length3 = array.GetLength(3);
            for (int i = 0; i < length0; i++)
                for (int j = 0; j < length1; j++)
                    for (int k = 0; k < length2; k++)
                        for (int l = 0; l < length3; l++)
                            array[i, j, k, l] = value;
            return array;
        }
    }
}

#endregion

#region Graphs

namespace Training20200928.Graphs
{
    public interface IEdge
    {
        int To { get; }
    }

    public interface IWeightedEdge : IEdge
    {
        long Weight { get; }
    }

    public interface IGraph<TEdge> where TEdge : IEdge
    {
        ReadOnlySpan<TEdge> this[int node] { get; }
        int NodeCount { get; }
    }

    public interface IWeightedGraph<TEdge> : IGraph<TEdge> where TEdge : IWeightedEdge { }

    public readonly struct BasicEdge : IEdge
    {
        public int To { get; }

        public BasicEdge(int to)
        {
            To = to;
        }

        public override string ToString() => To.ToString();
        public static implicit operator BasicEdge(int edge) => new BasicEdge(edge);
        public static implicit operator int(BasicEdge edge) => edge.To;
    }

    [StructLayout(LayoutKind.Auto)]
    public readonly struct WeightedEdge : IWeightedEdge
    {
        public int To { get; }
        public long Weight { get; }

        public WeightedEdge(int to) : this(to, 1) { }

        public WeightedEdge(int to, long weight)
        {
            To = to;
            Weight = weight;
        }

        public override string ToString() => $"[{Weight}]-->{To}";
        public void Deconstruct(out int to, out long weight) => (to, weight) = (To, Weight);
    }

    public class BasicGraph : IGraph<BasicEdge>
    {
        private readonly ExpandableArray<ExpandableArray<BasicEdge>> _edges;
        public ReadOnlySpan<BasicEdge> this[int node] => _edges[node].Span;
        public int NodeCount => _edges.Count;

        public BasicGraph(int nodeCount)
        {
            _edges = new ExpandableArray<ExpandableArray<BasicEdge>>(nodeCount);
            for (int i = 0; i < nodeCount; i++)
            {
                _edges.Add(new ExpandableArray<BasicEdge>());
            }
        }

        public void AddEdge(int from, int to) => _edges[from].Add(to);
        public void AddNode() => _edges.Add(new ExpandableArray<BasicEdge>());
    }

    public class WeightedGraph : IGraph<WeightedEdge>
    {
        private readonly ExpandableArray<ExpandableArray<WeightedEdge>> _edges;
        public ReadOnlySpan<WeightedEdge> this[int node] => _edges[node].Span;
        public int NodeCount => _edges.Count;

        public WeightedGraph(int nodeCount)
        {
            _edges = new ExpandableArray<ExpandableArray<WeightedEdge>>(nodeCount);
            for (int i = 0; i < nodeCount; i++)
            {
                _edges.Add(new ExpandableArray<WeightedEdge>());
            }
        }

        public void AddEdge(int from, int to, long weight) => _edges[from].Add(new WeightedEdge(to, weight));
        public void AddNode() => _edges.Add(new ExpandableArray<WeightedEdge>());
    }

    namespace Algorithms
    {
        public class Dijkstra
        {
            private readonly WeightedGraph _graph;

            public Dijkstra(WeightedGraph graph)
            {
                _graph = graph;
            }

            public long[] GetDistancesFrom(int startNode)
            {
                const long Inf = 1L << 60;
                var distances = Enumerable.Repeat(Inf, _graph.NodeCount).ToArray();
                distances[startNode] = 0;
                var todo = new PriorityQueue<State>(false);
                todo.Enqueue(new State(startNode, 0));

                while (todo.Count > 0)
                {
                    var current = todo.Dequeue();
                    if (current.Distance > distances[current.Node])
                    {
                        continue;
                    }

                    foreach (var edge in _graph[current.Node])
                    {
                        var nextDistance = current.Distance + edge.Weight;
                        if (distances[edge.To] > nextDistance)
                        {
                            distances[edge.To] = nextDistance;
                            todo.Enqueue(new State(edge.To, nextDistance));
                        }
                    }
                }

                return distances;
            }

            private readonly struct State : IComparable<State>
            {
                public int Node { get; }
                public long Distance { get; }

                public State(int node, long distance)
                {
                    Node = node;
                    Distance = distance;
                }

                public int CompareTo(State other) => Distance.CompareTo(other.Distance);
                public void Deconstruct(out int node, out long distance) => (node, distance) = (Node, Distance);
            }
        }

        public class BellmanFord
        {
            private readonly ExpandableArray<Edge> _edges = new ExpandableArray<Edge>();
            protected readonly int _nodeCount;

            public BellmanFord(int nodeCount)
            {
                _nodeCount = nodeCount;
            }

            public BellmanFord(WeightedGraph graph)
            {
                _nodeCount = graph.NodeCount;

                for (int from = 0; from < graph.NodeCount; from++)
                {
                    foreach (var edge in graph[from])
                    {
                        AddEdge(from, edge.To, edge.Weight);
                    }
                }
            }


            public void AddEdge(int from, int to, long weight) => _edges.Add(new Edge(from, to, weight));

            public (long[] distances, bool[] isNegativeCycle) GetDistancesFrom(int startNode)
            {
                const long Inf = long.MaxValue >> 1;
                var distances = new long[_nodeCount];
                distances.AsSpan().Fill(Inf);
                var isNegativeCycle = new bool[_nodeCount];
                distances[startNode] = 0;

                for (int i = 1; i <= 2 * _nodeCount; i++)
                {
                    foreach (var edge in _edges.Span)
                    {
                        // そもそも出発点に未到達なら無視
                        if (distances[edge.From] < Inf)
                        {
                            if (i <= _nodeCount)
                            {
                                var newCost = distances[edge.From] + edge.Weight;
                                if (distances[edge.To] > newCost)
                                {
                                    distances[edge.To] = newCost;
                                    // N回目に更新されたやつにチェックを付けて、追加でN回伝播させる
                                    if (i == _nodeCount)
                                    {
                                        isNegativeCycle[edge.To] = true;
                                    }
                                }
                            }
                            else if (isNegativeCycle[edge.From])
                            {
                                isNegativeCycle[edge.To] = true;
                            }
                        }
                    }
                }

                // 一応キレイにしておく
                for (int i = 0; i < _nodeCount; i++)
                {
                    if (isNegativeCycle[i])
                    {
                        distances[i] = long.MinValue;
                    }
                    else if (distances[i] >= Inf)
                    {
                        distances[i] = long.MaxValue;
                    }
                }

                return (distances, isNegativeCycle);
            }

            [StructLayout(LayoutKind.Auto)]
            readonly struct Edge
            {
                public int From { get; }
                public int To { get; }
                public long Weight { get; }

                public Edge(int from, int to, long cost)
                {
                    From = from;
                    To = to;
                    Weight = cost;
                }

                public void Deconstruct(out int from, out int to, out long cost) => (from, to, cost) = (From, To, Weight);
                public override string ToString() => $"{nameof(From)}: {From}, {nameof(To)}: {To}, {nameof(Weight)}: {Weight}";
            }
        }

        public interface ITreeDpState<TSet> : IMonoid<TSet> where TSet : ITreeDpState<TSet>, new()
        {
            public TSet AddRoot();
        }

        public class Rerooting<TEdge, TDp> where TEdge : IEdge where TDp : unmanaged, ITreeDpState<TDp>
        {
            readonly IGraph<TEdge> _graph;
            readonly TDp _identity;
            readonly TDp[][] _dp;
            readonly TDp[] _result;

            public Rerooting(IGraph<TEdge> graph)
            {
                _graph = graph;
                _identity = new TDp().Identity;
                _dp = new TDp[graph.NodeCount][];
                _result = new TDp[_graph.NodeCount];
                _result.AsSpan().Fill(_identity);
            }

            public TDp[] Solve()
            {
                DepthFirstSearch(0, -1);
                Reroot(0, -1, _identity);
                return _result;
            }

            private TDp DepthFirstSearch(int current, int parent)
            {
                var sum = _identity;
                _dp[current] = new TDp[_graph[current].Length];

                var edges = _graph[current];

                for (int i = 0; i < edges.Length; i++)
                {
                    var next = edges[i].To;
                    if (next == parent)
                        continue;
                    _dp[current][i] = DepthFirstSearch(next, current);
                    sum = sum.Merge(_dp[current][i]);
                }

                return sum.AddRoot();
            }

            private void Reroot(int current, int parent, TDp toAdd)
            {
                var edges = _graph[current];
                for (int i = 0; i < edges.Length; i++)
                {
                    if (edges[i].To == parent)
                    {
                        _dp[current][i] = toAdd;
                        break;
                    }
                }

                var dp = GetPrefixSum(current, edges);

                for (int i = 0; i < edges.Length; i++)
                {
                    var next = edges[i].To;
                    if (next == parent)
                        continue;
                    Reroot(next, current, dp[i].AddRoot());
                }
            }

            private TDp[] GetPrefixSum(int root, ReadOnlySpan<TEdge> edges)
            {
                const int StackallocLimit = 512;

                // 左右からの累積和
                int sumSize = edges.Length + 1;
                Span<TDp> sumLeft = sumSize <= StackallocLimit ? stackalloc TDp[sumSize] : new TDp[sumSize];
                Span<TDp> sumRight = sumSize <= StackallocLimit ? stackalloc TDp[sumSize] : new TDp[sumSize];

                sumLeft[0] = _identity;
                for (int i = 0; i < edges.Length; i++)
                {
                    sumLeft[i + 1] = sumLeft[i].Merge(_dp[root][i]);
                }

                sumRight[^1] = _identity;
                for (int i = edges.Length - 1; i >= 0; i--)
                {
                    sumRight[i] = sumRight[i + 1].Merge(_dp[root][i]);
                }

                // 頂点vの答え
                _result[root] = sumLeft[^1].AddRoot();

                // 頂点iを除いた累積
                var dp = new TDp[edges.Length];
                for (int i = 0; i < dp.Length; i++)
                {
                    dp[i] = sumLeft[i].Merge(sumRight[i + 1]);
                }

                return dp;
            }
        }
    }
}

#endregion


Measured memory_bytes: 26360