結果

問題 No.3018 目隠し宝探し
ユーザー Nauclhlt🪷
提出日時 2025-01-25 14:21:46
言語 C#
(.NET 8.0.404)
結果
RE  
実行時間 -
コード長 63,560 bytes
コンパイル時間 8,730 ms
コンパイル使用メモリ 170,408 KB
実行使用メモリ 53,504 KB
平均クエリ数 2.00
最終ジャッジ日時 2025-01-25 23:16:58
合計ジャッジ時間 18,382 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (114 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
プレゼンテーションモードにする

using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections;
using System.Text;
using System.Text.RegularExpressions;
using static Tmpl;
using static CPDebug;
using System.Collections.Specialized;
using System.Globalization;
using System.Diagnostics;
StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));
Console.SetOut(writer);
//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));
//Console.SetIn(reader);
Solver.Solve();
Console.Out.Flush();
public static class Solver
{
    private static readonly AtCoderIO cin = new AtCoderIO();
    public static unsafe void Solve()
    {
        int H = cin.Int();
        int W = cin.Int();
        fprint("1 1");
        long d1 = cin.Long();
        fprint($"1 {W}");
        long d2 = cin.Long();
        fprint($"{H} 1");
        long d3 = cin.Long();
        for (int y = 1; y <= H; y++)
        {
            for (int x = 1; x <= W; x++)
            {
                //check(dist(x, y, 1, 1));
                if (dist(x, y, 1, 1) == d1 && dist(x, y, W, 1) == d2 && dist(x, y, 1, H) == d3)
                {
                    fprint($"! {y} {x}");
                    return;
                }
            }
        }
    }
    static long dist(long x1, long y1, long x2, long y2)
    {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
}
struct Border : IComparable<Border>
{
    public long Y;
    public bool IsCyan;
    public Border(long y, bool cyan)
    {
        Y = y;
        IsCyan = cyan;
    }
    public int CompareTo(Border other)
    {
        return Y.CompareTo(other.Y);
    }
}
// 平衡二分探索木を利用してソートされた集合を管理する.
public sealed class Set<T> where T : IComparable<T>
{
    private AVLTree<T> _tree;
    public T Max => _tree.Max();
    public T Min => _tree.Min();
    public int Count => _tree.Count;
    public Set()
    {
        _tree = new();
    }
    // 要素を追加する.
    // O(logN)
    public void Add(T item)
    {
        _tree.Add(item);
    }
    // 要素を削除する.
    // O(logN)
    public void Remove(T item)
    {
        _tree.Remove(item);
    }
    // 要素が含まれているかを返す.
    // O(logN)
    public bool Contains(T item)
    {
        return _tree.Contains(item);
    }
    // itemのインデックスを返す.
    // O(logN)
    public int IndexOf(T item)
    {
        return _tree.IndexOf(item);
    }
    // 値がvalue以上となる最初のインデックスを返す.
    public int LowerBound(T value)
    {
        return _tree.LowerBound(value);
    }
    public T LowerBoundValue(T value, T fallback)
    {
        return _tree.LowerBoundValue(value, fallback);
    }
    // インデックスで値を取得する.
    public T GetByIndex(int index)
    {
        return _tree.GetByIndex(index);
    }
    public void RemoveByIndex(int index)
    {
        _tree.RemoveByIndex(index);
    }
    // 昇順ソートされたリストを返す.
    public List<T> OrderAscending()
    {
        return _tree.OrderAscending();
    }
    // 降順ソートされたリストを返す.
    public List<T> OrderDescending()
    {
        return _tree.OrderDescending();
    }
    public void DebugPrintTree()
    {
        _tree.PrintTree();
    }
}
// AVL木, 平衡二分探索木.
// 参考: https://zenn.dev/student_blog/articles/670eee14e04d46
public sealed class AVLTree<T> where T : IComparable<T>
{
    private sealed class Node
    {
        private T _value;
        private Node _left;
        private Node _right;
        private int _bias;
        private int _height;
        private int _size;
        public bool Has2Children => _left is not null && _right is not null;
        public bool HasOnlyLeft => _left is not null && _right is null;
        public bool HasOnlyRight => _left is null && _right is not null;
        public bool HasNoChild => _left is null && _right is null;
        public Node(T value)
        {
            _value = value;
            _left = null;
            _right = null;
            _bias = 0;
            _height = 1;
            _size = 1;
        }
        public T Value
        {
            get => _value;
            set => _value = value;
        }
        public Node Left
        {
            get => _left;
            set => _left = value;
        }
        public Node Right
        {
            get => _right;
            set => _right = value;
        }
        public int Bias
        {
            get => _bias;
            set => _bias = value;
        }
        public int Height
        {
            get => _height;
            set => _height = value;
        }
        public int Size
        {
            get => _size;
            set => _size = value;
        }
        public int LeftHeight() => _left is not null ? _left.Height : 0;
        public int RightHeight() => _right is not null ? _right.Height : 0;
        public int LeftSize() => _left is not null ? _left.Size : 0;
        public int RightSize() => _right is not null ? _right.Size : 0;
    }
    private Node _rootNode = null;
    public int Count => SizeOf(_rootNode);
    public AVLTree()
    {
        _rootNode = null;
    }
    public void Add(T value)
    {
        _rootNode = AddRecursive(_rootNode, value);
    }
    public void Remove(T value)
    {
        _rootNode = RemoveRecursive(_rootNode, value);
    }
    private Node RemoveRecursive(Node current, T value)
    {
        if (current is null)
        {
            return null;
        }
        if (current.Value.CompareTo(value) == 0)
        {
            // 消す
            return InternalRemoveNode(current);
        }
        if (value.CompareTo(current.Value) == -1)
        {
            current.Left = RemoveRecursive(current.Left, value);
            Update(current.Left);
            Update(current);
            current = Balance(current);
            Update(current);
            return current;
        }
        else
        {
            current.Right = RemoveRecursive(current.Right, value);
            Update(current.Right);
            Update(current);
            current = Balance(current);
            Update(current);
            return current;
        }
    }
    private Node InternalRemoveNode(Node target)
    {
        if (target.Has2Children)
        {
            Node max = GetMaxNode(target.Left);
            T val = max.Value;
            
            if (target.Left == max)
            {
                target.Left = target.Left.Left;
            }
            else
            {
                target.Left = DeleteRightNode(target.Left, max);
            }
            
            target.Value = val;
            Update(target.Left);
            Update(target.Right);
            Update(target);
            target = Balance(target);
            Update(target);
            return target;
        }
        else if (target.HasOnlyLeft)
        {
            target = target.Left;
            Update(target.Left);
            Update(target.Right);
            Update(target);
            target = Balance(target);
            Update(target);
            return target;
        }
        else if (target.HasOnlyRight)
        {
            target = target.Right;
            Update(target.Left);
            Update(target.Right);
            Update(target);
            target = Balance(target);
            Update(target);
            return target;
        }
        else
        {
            return null;
        }
    }
    private Node AddRecursive(Node current, T value)
    {
        if (current is null)
        {
            current = new Node(value);
            
            Update(current);
            return current;
        }
        if (value.CompareTo(current.Value) == -1)
        {
            current.Left = AddRecursive(current.Left, value);
            Update(current.Left);
            Update(current);
            current = Balance(current);
            Update(current);
        }
        else
        {
            current.Right = AddRecursive(current.Right, value);
            Update(current.Right);
            Update(current);
            current = Balance(current);
            Update(current);
        }
        return current;
    }
    private Node Balance(Node node)
    {
        if (node.Bias == 0)
        {
            return node;
        }
        if (node.Bias == 1 || node.Bias == -1)
        {
            return node;
        }
        if (node.Bias >= 2)
        {
            if (node.Left.Bias > 0)
            {
                node = RotateRight(node);
                node.Bias = 0;
                return node;
            }
            else
            {
                node.Left = RotateLeft(node.Left);
                node = RotateRight(node);
                node.Bias = 0;
                return node;
            }
        }
        else
        {
            if (node.Right.Bias < 0)
            {
                node = RotateLeft(node);
                node.Bias = 0;
                return node;
            }
            else
            {
                node.Right = RotateRight(node.Right);
                node = RotateLeft(node);
                node.Bias = 0;
                return node;
            }
        }
    }
    private Node DeleteRightNode(Node root, Node target)
    {
        if (root is null) return null;
        if (root.Right == target)
        {
            root.Right = root.Right.Left;
            Update(root.Right);
            Update(root);
            root = Balance(root);
            Update(root);
            return root;
        }
        else
        {
            int sz = root.Size;
            root.Right = DeleteRightNode(root.Right, target);
            
            Update(root.Right);
            Update(root.Left);
            Update(root);
            root = Balance(root);
            if (sz - root.Size == 2)
            {
                Console.WriteLine("ERR");
            }
            Update(root);
            return root;
        }
    }
    private Node GetMaxNode(Node node)
    {
        Node cur = node;
        while (cur.Right is not null) cur = cur.Right;
        return cur;
    }
    private Node GetMinNode(Node node)
    {
        Node cur = node;
        while (cur.Left is not null) cur = cur.Left;
        return cur;
    }
    // 新しい部分木の根を返す
    private Node RotateLeft(Node node)
    {
        Node right = node.Right;
        node.Right = right.Left;
        right.Left = node;
        Update(right.Left);
        Update(right.Right);
        Update(right);
        return right;
    }
    // 新しい部分木の根を返す
    private Node RotateRight(Node node)
    {
        Node left = node.Left;
        node.Left = left.Right;
        left.Right = node;
        Update(left.Left);
        Update(left.Right);
        Update(left);
        
        return left;
    }
    private void Update(Node node)
    {
        if (node is null) return;
        node.Height = HeightOf(node);
        node.Size = SizeOf(node);
        node.Bias = node.LeftHeight() - node.RightHeight();
    }
    private int HeightOf(Node node)
    {
        if (node is null) return 0;
        int left = node.LeftHeight();
        int right = node.RightHeight();
        return int.Max(left, right) + 1;
    }
    private int SizeOf(Node node)
    {
        if (node is null) return 0;
        int left = node.LeftSize();
        int right = node.RightSize();
        return left + right + 1;
    }
    public void PrintTree()
    {
        static void PrintNode(Node node, int depth)
        {
            if (node is null) return;
            PrintNode(node.Right, depth + 1);
            Console.WriteLine(new string('\t', depth) + node.Value + $"({node.Bias}; {node.Height}; {node.Size})");
            PrintNode(node.Left, depth + 1);
        }
        PrintNode(_rootNode, 0);
    }
    public bool Contains(T value)
    {
        Node current = _rootNode;
        while (current is not null)
        {
            if (current.Value.CompareTo(value) == 0) return true;
            if (value.CompareTo(current.Value) == -1) current = current.Left;
            else current = current.Right;
        }
        return false;
    }
    public T Max()
    {
        return GetMaxNode(_rootNode).Value;
    }
    public T Min()
    {
        return GetMinNode(_rootNode).Value;
    }
    public T GetByIndex(int index)
    {
        if (_rootNode is null)
        {
            throw new IndexOutOfRangeException();
        }
        if (index < 0 || index >= Count)
        {
            throw new IndexOutOfRangeException();
        }
        return GetByIndexRecursive(_rootNode, index);
    }
    public void RemoveByIndex(int index)
    {
        if (_rootNode is null) return;
        if (index < 0 || index >= Count)
        {
            throw new IndexOutOfRangeException();
        }
        _rootNode = RemoveByIndexRecursive(_rootNode, index);
    }
    private Node RemoveByIndexRecursive(Node current, int offset)
    {
        if (current is null)
        {
            Console.WriteLine($"! current was null. offset={offset}  count={Count}");
            return default;
        }
        
        int left = current.LeftSize();
        if (left == offset)
        {
            return InternalRemoveNode(current);
        }
        if (offset < left)
        {
            current.Left = RemoveByIndexRecursive(current.Left, offset);
            Update(current);
            current = Balance(current);
            Update(current);
            return current;
        }
        else
        {
            current.Right = RemoveByIndexRecursive(current.Right, offset - left - 1);
            Update(current);
            current = Balance(current);
            Update(current);
            return current;
        }
    }
    private T GetByIndexRecursive(Node current, int offset)
    {
        if (current is null)
        {
            Console.WriteLine($"! current was null. offset={offset}  count={Count}");
            return default;
        }
        int left = current.LeftSize();
        if (left == offset)
        {
            return current.Value;
        }
        if (offset < left)
        {
            return GetByIndexRecursive(current.Left, offset);
        }
        else
        {
            return GetByIndexRecursive(current.Right, offset - left - 1);
        }
    }
    public int IndexOf(T value)
    {
        int index = _rootNode.LeftSize();
        Node current = _rootNode;
        while (true)
        {
            // left
            int c = value.CompareTo(current.Value);
            if (c == -1)
            {
                if (current.Left is null) return -1;
                else
                {
                    current = current.Left;
                    index -= current.RightSize() + 1;
                }
            }
            else if (c == 0) return index;
            else
            {
                if (current.Right is null) return -1;
                else
                {
                    current = current.Right;
                    index += current.LeftSize() + 1;
                }
            }
        }
    }
    public T LowerBoundValue(T value, T fallback)
    {
        if (_rootNode is null) return fallback;
        int res = _rootNode.Size;
        Node current = _rootNode;
        T lowerbound = default;
        int index = _rootNode.LeftSize();
        while (true)
        {
            int cmp = value.CompareTo(current.Value);
            if (cmp <= 0)
            {
                res = int.Min(res, index);
                lowerbound = current.Value;
                if (current.Left is null) break;
                index -= current.Left.RightSize() + 1;
                current = current.Left;
            }
            else
            {
                if (current.Right is null) break;
                index += current.Right.LeftSize() + 1;
                current = current.Right;
            }
        }
        return res < Count ? lowerbound : fallback;
    }
    public int LowerBound(T value)
    {
        if (_rootNode is null) return 0;
        int res = _rootNode.Size;
        Node current = _rootNode;
        int index = _rootNode.LeftSize();
        while (true)
        {
            int cmp = value.CompareTo(current.Value);
            if (cmp <= 0)
            {
                res = int.Min(res, index);
                if (current.Left is null) break;
                index -= current.Left.RightSize() + 1;
                current = current.Left;
            }
            else
            {
                if (current.Right is null) break;
                index += current.Right.LeftSize() + 1;
                current = current.Right;
            }
        }
        return res;
        // Node root = _rootNode;
        // var torg = root;
        // if (root is null) return -1;
        // var idx = root.Size - root.RightSize() - 1;
        // var ret = Int32.MaxValue;
        // while (root is not null)
        // {
        //     if (root.Value.CompareTo(value) >= 0)
        //     {
        //         if (root.Value.CompareTo(value) == 0) ret = int.Min(ret, idx);
        //         root = root.Left;
        //         if (root == null) ret = Math.Min(ret, idx);
        //         idx -= root is null ? 0 : (root.RightSize() + 1);
        //     }
        //     else
        //     {
        //         root = root.Right;
        //         idx += (root is null ? 1 : root.LeftSize() + 1);
        //         if (root == null) return idx;
        //     }
        // }
        // return ret == Int32.MaxValue ? torg.Size : ret;
    }
    public List<T> OrderAscending()
    {
        if (_rootNode is null) return new List<T>();
        List<T> res = new(_rootNode.Size);
        void extract(Node node)
        {
            if (node is null) return;
            extract(node.Left);
            res.Add(node.Value);
            extract(node.Right);
        }
        return res;
    }
    public List<T> OrderDescending()
    {
        if (_rootNode is null) return new List<T>();
        List<T> res = new(_rootNode.Size);
        void extract(Node node)
        {
            if (node is null) return;
            extract(node.Right);
            res.Add(node.Value);
            extract(node.Left);
        }
        return res;
    }
}
static class Constants
{
    public const long Mod = 998244353L;
    //public const long Mod = 10007L;
    //public const long Mod = 1000000007L;
}
public readonly struct Point
{
    public readonly int X;
    public readonly int Y;
    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
    public override int GetHashCode() => (X, Y).GetHashCode();
    public override string ToString()
    {
        return $"({X}, {Y})";
    }
}
public sealed class ReverseComparer<T> : IComparer<T>
{
    public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);
    public static ReverseComparer<T> Reverse(IComparer<T> comparer)
    {
        return new ReverseComparer<T>(comparer);
    }
    private readonly IComparer<T> comparer = Default;
    private ReverseComparer(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }
    public int Compare(T x, T y)
    {
        return comparer.Compare(y, x);
    }
}
public sealed class AtCoderIO
{
    Queue<string> _readQueue = new Queue<string>();
    private void LoadQueue()
    {
        if (_readQueue.Count > 0) return;
        string line = Console.ReadLine();
        string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
    }
    private void Guard()
    {
        if (_readQueue.Count == 0)
        {
            throw new Exception("NO DATA TO READ");
        }
    }
    public int Int()
    {
        LoadQueue();
        Guard();
        return int.Parse(_readQueue.Dequeue());
    }
    public long Long()
    {
        LoadQueue();
        Guard();
        return long.Parse(_readQueue.Dequeue());
    }
    public string String()
    {
        LoadQueue();
        Guard();
        return _readQueue.Dequeue();
    }
    public short Short()
    {
        LoadQueue();
        Guard();
        return short.Parse(_readQueue.Dequeue());
    }
    public byte Byte()
    {
        LoadQueue();
        Guard();
        return byte.Parse(_readQueue.Dequeue());
    }
    public char Char()
    {
        LoadQueue();
        Guard();
        return char.Parse(_readQueue.Dequeue());
    }
    public double Double()
    {
        LoadQueue();
        Guard();
        return double.Parse(_readQueue.Dequeue());
    }
    public float Float()
    {
        LoadQueue();
        Guard();
        return float.Parse(_readQueue.Dequeue());
    }
    public ModInt ModInt()
    {
        return new ModInt(Long());
    }
    public T Read<T>()
    {
        Type type = typeof(T);
        if (type == typeof(int)) return (T)(object)Int();
        else if (type == typeof(long)) return (T)(object)Long();
        else if (type == typeof(float)) return (T)(object)Float();
        else if (type == typeof(double)) return (T)(object)Double();
        else if (type == typeof(short)) return (T)(object)Short();
        else if (type == typeof(byte)) return (T)(object)Byte();
        else if (type == typeof(char)) return (T)(object)Char();
        else if (type == typeof(string)) return (T)(object)String();
        else if (type == typeof(ModInt)) return (T)(object)ModInt();
        else return default(T);
    }
    public int[] IntArray(int n)
    {
        if (n == 0) return Array.Empty<int>();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int();
        }
        return arr;
    }
    public int[] ZeroIndexedPermutation(int n)
    {
        if (n == 0) return Array.Empty<int>();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int() - 1;
        }
        return arr;
    }
    public long[] LongArray(int n)
    {
        if (n == 0) return Array.Empty<long>();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Long();
        }
        return arr;
    }
    public double[] DoubleArray(int n)
    {
        if (n == 0) return Array.Empty<double>();
        double[] arr = new double[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Double();
        }
        return arr;
    }
    public ModInt[] ModIntArray(int n)
    {
        if (n == 0) return Array.Empty<ModInt>();
        ModInt[] arr = new ModInt[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = (ModInt)Long();
        }
        return arr;
    }
    public T[] ReadArray<T>(int n)
    {
        if (n == 0) return Array.Empty<T>();
        T[] arr = new T[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Read<T>();
        }
        return arr;
    }
}
public static class CPDebug
{
    public static void check<T>(T value, [CallerArgumentExpression(nameof(value))] string name = "value")
    {
#if DEBUG
        Console.WriteLine($"[DEBUG] {name}={value.ToString()}");
#endif
    }
    public static void check<T>(IEnumerable<T> value, [CallerArgumentExpression(nameof(value))] string name = "value")
    {
#if DEBUG
        Console.WriteLine($"[DEBUG] {name}=({string.Join(' ', value)})");
#endif
    }
}
public static class Tmpl
{
    public static int combination(int n, int r)
    {
        int c = 1;
        for (int i = 1; i <= r; i++)
        {
            c = c * (n - i + 1) / i;
        }
        return c;
    }
    public static long combination(long n, long r)
    {
        long c = 1;
        for (long i = 1; i <= r; i++)
        {
            c = c * (n - i + 1) / i;
        }
        return c;
    }
    public static long pow(long b, long exp)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b;
        long m = pow(b, exp / 2L);
        m *= m;
        if (exp % 2L == 1) m *= b;
        return m;
    }
    public static long modpow(long b, long exp, long mod)
    {
        if (exp == 0) return 1;
        if (exp == 1) return b % mod;
        long m = modpow(b, exp / 2L, mod);
        m *= m;
        m %= mod;
        if (exp % 2L == 1) m *= b % mod;
        m %= mod;
        return m;
    }
    static long modinv( long a, long mod )
    {
        long b = mod, u = 1, v = 0;
        while ( b > 0 )
        {
            long t = a / b;
            a -= t * b; swap( ref a, ref b );
            u -= t * v; swap( ref u, ref v );
        }
        u %= mod;
        if (u < 0) u += mod;
        return u;
    }
    public static long calcLcm(long a, long b)
    {
        return a * b / calcGcd(a, b);
    }
    public static long calcGcd(long a, long b)
    {
        if (a % b == 0) return b;
        return calcGcd(b, a % b);
    }
    // ax ≡ b (mod m)なる最小のxを求める
    public static bool solveModLinear(long a, long b, long m, out long minSolution)
    {
        long gcd = calcGcd(calcGcd(a, b), m);
        a /= gcd;
        b /= gcd;
        m /= gcd;
        if (calcGcd(a, m) == 1)
        {
            long inv = modinv(a, m);
            minSolution = (b * inv) % m;
            return true;
        }
        minSolution = 0;
        return false;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YesNo(bool t)
    {
        Console.WriteLine(t ? "Yes" : "No");
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void YESNO(bool t)
    {
        Console.WriteLine(t ? "YES" : "NO");
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void yesno(bool t)
    {
        Console.WriteLine(t ? "yes" : "no");
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool checkBit(int bit, int n)
    {
        return ((1 << n) & bit) != 0;
    }
    public static bool nextCombination(int n, int r, int[] array)
    {
        int i = array.Length - 1;
        while (i >= 0 && array[i] == i + n - r)
        {
            i--;
        }
        if (i < 0) return false;
        array[i]++;
        for (int j = i + 1; j < r; j++)
        {
            array[j] = array[j - 1] + 1;
        }
        return true;
    }
    public static bool nextPermutation<T>(T[] array, int start, int length) where T : IComparable<T>
    {
        int end = start + length - 1;
        if (end <= start) return false;
        int last = end;
        while (true)
        {
            int pos = last--;
            
            if (array[last].CompareTo(array[pos]) < 0)
            {
                int i;
                for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
                T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
                Array.Reverse(array, pos, end - pos + 1);
                return true;
            }
            if (last == start)
            {
                Array.Reverse(array, start, end - start);
                return false;
            }
        }
        throw new Exception("NextPermutation: Fatal error");
    }
    public static unsafe Dictionary<char, int> cntCharOcc(string s)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();
        fixed (char* ptr = s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                if (dict.ContainsKey(ptr[i]))
                {
                    dict[ptr[i]] += 1;
                }
                else
                {
                    dict[ptr[i]] = 1;
                }
            }
        }
        return dict;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void chmax<T> (ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value > target)
        {
            target = value;
        }
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void chmin<T>(ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        if (value < target)
        {
            target = value;
        }
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void arrMod<T>(T[] array, T b) where T : IModulusOperators<T, T, T>
    {
        for (int i = 0; i < array.Length; i++)
        {
            array[i] %= b;
        }
    }
    public static ReadOnlySpan<T> spanOf<T>(List<T> list)
    {
        return CollectionsMarshal.AsSpan(list);
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(T[] array, int i, int j) where T : struct
    {
        (array[i], array[j]) = (array[j], array[i]);
    }
    public static void shuffle<T>(T[] array) where T : struct
    {
        Random random = new Random();
        for (int i = array.Length - 1; i > 0; i--)
        {
            int index = random.Next(0, i + 1);
            swap(array, index, i);
        }
    }
    public static int lowerBound<T>(T[] array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }
        if (low == array.Length - 1 && array[low] < value)
        {
            return array.Length;
        }
        return low;
    }
    public static int lowerBound<T>(List<T> array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
    { 
        int low = start;
        int high = end;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid;
        }
        if (low == array.Count - 1 && array[low] < value)
        {
            return array.Count;
        }
        return low;
    }
    public static int upperBound<T>(T[] array, T value) where T : struct, IComparisonOperators<T, T, bool>
    {
        var l = 0;
        var r = array.Length - 1;
        while (l <= r)
        {
            var mid = l + (r - l) / 2;
            if (array[mid] <= value) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void swap<T>(ref T a, ref T b) where T : struct
    {
        T temp = a;
        a = b;
        b = temp;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool dbleq(double a, double b)
    {
        return Math.Abs(a - b) < double.Epsilon;
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int dblAsInt(double d)
    {
        return (int)Math.Round(d, 0);
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static long dblAsLong(double d)
    {
        return (long)Math.Round(d, 0);
    }
    public static int[] compressCoords<T>(T[] a) where T : struct, IComparisonOperators<T, T, bool>
    {
        T[] b = a.OrderBy(x => x).Distinct().ToArray();
        int[] result = new int[a.Length];
        for (int i = 0; i < a.Length; i++)
        {
            result[i] = lowerBound(b, 0, b.Length - 1, a[i]);
        }
        return result;
    }
    public static List<RunLengthElement<T>> compressRunLength<T>(T[] array) where T : struct, IEquatable<T>
    {
        List<RunLengthElement<T>> list = new List<RunLengthElement<T>>();
        int count = 1;
        int start = 0;
        T prev = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (prev.Equals(array[i]))
            {
                count++;
            }
            else
            {
                list.Add(new RunLengthElement<T>(start, count, prev));
                start = i;
                count = 1;
            }
            prev = array[i];
        }
        list.Add(new RunLengthElement<T>(start, count, prev));
        return list;
    }
    public static char[] alphabetsLower()
    {
        return new[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 
            'z' };
    }
    public static char[] alphebetsUpper()
    {
        return new[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 
            'Z'};
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        Console.WriteLine(string.Join(delimiter, array));
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint<T>(IEnumerable<T> array, char delimiter = ' ')
    {
        print(array);
        Console.Out.Flush();
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(string msg)
    {
        Console.WriteLine(msg);
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(string msg)
    {
        Console.WriteLine(msg);
        Console.Out.Flush();
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(int val)
    {
        print(val.ToString());
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(long val)
    {
        print(val.ToString());
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void print(ModInt val)
    {
        print(val.ToString());
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(int val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(long val)
    {
        print(val.ToString());
        Console.Out.Flush();
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static void fprint(ModInt val)
    {
        fprint(val.ToString());
        Console.Out.Flush();
    }
    public static void print<T>(T[,] grid)
    {
        for (int y = 0; y < grid.GetLength(0); y++)
        {
            for (int x = 0; x < grid.GetLength(1); x++)
            {
                Console.Write(grid[y, x] + "\t");
            }
            Console.WriteLine();
        }
    }
    public static void print01(bool t)
    {
        Console.WriteLine(t ? "1" : "0");
    }
    public static TSrc lowerBoundKth<TSrc, TCnt>(TSrc min, TSrc max, Func<TSrc, TCnt> f, TCnt bound)
        where TSrc: struct, INumber<TSrc> where TCnt: struct, INumber<TCnt>
    {
        TSrc left = min;
        TSrc right = max;
        TSrc two = TSrc.CreateChecked(2);
        TSrc one = TSrc.CreateChecked(1);
        while (right > left)
        {
            TSrc mid = left + (right - left) / two;
            TCnt c = f(mid);
            if (c < bound)
            {
                left = mid + one;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
    public static bool isSquareNumber(long n)
    {
        long q = (long)Math.Floor(Math.Sqrt(n));
        return q * q == n;
    }
}
public readonly struct RunLengthElement<T> where T : struct
{
    public readonly int Count;
    public readonly int StartIndex;
    public readonly T Value;
    public RunLengthElement(int startIndex, int count, T value)
    {
        this.StartIndex = startIndex;
        this.Count = count;
        this.Value = value;
    }
}
public readonly struct Edge<T> : IEquatable<Edge<T>>, IComparable<Edge<T>> where T : struct, INumber<T>
{
    public readonly int To;
    public readonly int From;
    public readonly T Weight;
    public Edge(int to, T weight)
    {
        this.To = to;
        this.Weight = weight;
    }
    public Edge(int from, int to, T weight)
    {
        this.To = to;
        this.From = from;
        this.Weight = weight;
    }
    public override bool Equals(object obj)
    {
        if (obj is Edge<T> edge)
        {
            return this.Equals(edge);
        }
        else
        {
            return false;
        }
    }
    public int CompareTo(Edge<T> other)
    {
        return Weight.CompareTo(other.Weight);
    }
    public bool Equals(Edge<T> edge)
    {
        return To == edge.To && From == edge.From && Weight == edge.Weight;
    }
    public override int GetHashCode()
    {
        return (To, From, Weight).GetHashCode();
    }
    public static bool operator ==(Edge<T> left, Edge<T> right)
    {
        return left.Equals(right);
    }
    public static bool operator !=(Edge<T> left, Edge<T> right)
    {
        return !left.Equals(right);
    }
}
public readonly struct ModInt : IEquatable<ModInt>, IAdditionOperators<ModInt, ModInt, ModInt>, ISubtractionOperators<ModInt, ModInt, ModInt>, 
    IAdditiveIdentity<ModInt, ModInt>
{
    private readonly long Value;
    public static ModInt One => (ModInt)1L;
    public static ModInt Zero => (ModInt)0L;
    public static ModInt AdditiveIdentity => Zero;
    public ModInt(long value)
    {
        Value = SafeMod(value);
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static long SafeMod(long a)
    {
        a %= Constants.Mod;
        if (a < 0) a += Constants.Mod;
        return a;
    }
    public ModInt Power(long exp)
    {
        if (exp <= -1) return this;
        if (exp == 0) return 1;
        if (exp == 1) return this;
        ModInt m = Power(exp / 2);
        m *= m;
        if (exp % 2 == 1) m *= this;
        return m;
    }
    public ModInt Inv()
    {
        return this.Power(Constants.Mod - 2L);
    }
    public static ModInt operator +(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value + right.Value));
    }
    public static ModInt operator -(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value - right.Value));
    }
    public static ModInt operator *(ModInt left, ModInt right)
    {
        return new ModInt(SafeMod(left.Value * right.Value));
    }
    public static ModInt operator /(ModInt left, ModInt right)
    {
        if (right.Value == 0L)
        {
            return Zero;
        }
        ModInt inv = right.Inv();
        return SafeMod(left * inv);
    }
    public static ModInt operator %(ModInt left, ModInt right)
    {
        if (right.Value == 0L)
        {
            return Zero;
        }
        return new ModInt(SafeMod(left.Value % right.Value));
    }
    public static bool operator ==(ModInt left, ModInt right)
    {
        return left.Value == right.Value;
    }
    public static bool operator != (ModInt left, ModInt right)
    {
        return !(left == right);
    }
    public bool Equals(ModInt other)
    {
        return Value == other.Value;
    }
    public override bool Equals(object other)
    {
        if (other is ModInt m)
        {
            return this == m;
        }
        else return false;
    }
    public override int GetHashCode()
    {
        return Value.GetHashCode();
    }
    public static implicit operator ModInt(long v)
    {
        return new ModInt(v);
    }
    public static implicit operator ModInt(int v)
    {
        return new ModInt(v);
    }
    public static implicit operator long(ModInt m)
    {
        return m.Value;
    }
    public static implicit operator int(ModInt m)
    {
        return (int)m.Value;
    }
    public long Raw() => Value;
    public override string ToString()
    {
        return Value.ToString();
    }
}
public delegate T Monoid<T>(T a, T b);
public delegate T Apply<T, M>(T x, M m, int len);
// 一点に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(2N)
// 時間計算量:
// - 構築: O(N)
// - 操作: O(logN)
// - クエリ: O(logN)
public sealed class SegmentTree<T> where T : struct
{
    private int _treeSize;
    private int _dataSize;
    private int _originalDataSize;
    private T[] _data;
    private Monoid<T> _operator;
    private Monoid<T> _apply;
    private T _identity;
    public int OriginalDataSize => _originalDataSize;
    public int TreeSize => _treeSize;
    public T Identity => _identity;
    public T this[int index]
    {
        get
        {
            return _data[_dataSize - 1 + index];
        }
    }
    public SegmentTree(int n, Monoid<T> op, Monoid<T> apply, T identity)
    {
        _originalDataSize = n;
        int size = 1;
        while (n > size)
        {
            size <<= 1;
        }
        _dataSize = size;
        _treeSize = 2 * size - 1;
        _data = new T[_treeSize];
        _identity = identity;
        _operator = op;
        _apply = apply;
    }
    public void Build(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = array[i];
        }
        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }
    public void Apply(int index, T value)
    {
        index += _dataSize - 1;
        _data[index] = _apply(_data[index], value);
        while (index > 0)
        {
            index = (index - 1) >> 1;
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
    }
    public T Query(int left, int right)
    {
        return QueryRec(left, right, 0, 0, _dataSize);
    }
    private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
    {
        if (left >= nodeRight || right <= nodeLeft)
        {
            return _identity;
        }
        if (left <= nodeLeft && nodeRight <= right)
        {
            return _data[index];
        }
        T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
        T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
        return _operator(leftChild, rightChild);
    }
    // 返されたArraySegment<T>は変更してはいけない.
    public ArraySegment<T> GetData()
    {
        return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
    }
}
// 区間に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(4N)
// 時間計算量:
// - 構築: O(N)
// - 操作: O(logN)
// - クエリ: O(logN)
// - 一点参照: O(logN)
// operator: クエリに対応する二項演算をする
// mapping: 作用素を作用させる
// composition: 作用素を合成する
public sealed class LazySegmentTree<T, M> where T : struct, IEquatable<T>  where M : struct, IEquatable<M>
{
    private int _treeSize;
    private int _dataSize;
    private int _originalDataSize;
    private T[] _data;
    private M?[] _lazy;
    private Monoid<T> _operator;
    private Apply<T, M> _mapping;
    private Monoid<M> _composition;
    private T _identity;
    public T this[int index]
    {
        get
        {
            return GetByIndex(index);
        }
    }
    public LazySegmentTree(int n, Monoid<T> op, Apply<T, M> mapping, Monoid<M> composition, T identity)
    {
        _originalDataSize = n;
        int size = 1;
        while (n > size)
        {
            size <<= 1;
        }
        _dataSize = size;
        _treeSize = 2 * size - 1;
        _data = new T[_treeSize];
        _data.AsSpan().Fill(_identity);
        _lazy = new M?[_treeSize];
        _identity = identity;
        _operator = op;
        _mapping = mapping;
        _composition = composition;
    }
    public void Build(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = array[i];
        }
        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }
    private void Evaluate(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            return;
        }
        if (index < _dataSize - 1)
        {
            _lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            _lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
        }
        _data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        _lazy[index] = null;
    }
    private M GuardComposition(M? a, M? b)
    {
        if (a is null)
        {
            return (M)b;
        }
        else
        {
            return _composition((M)a, (M)b);
        }
    }
    private void ApplyRec(int a, int b, M m, int index, int l, int r)
    {
        Evaluate(index, l, r);
        if (a <= l && r <= b)
        {
            _lazy[index] = GuardComposition(_lazy[index], m);
            Evaluate(index, l, r);
        }
        else if (a < r && l < b)
        {
            ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);
            ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
    }
    public void Apply(int left, int right, M m)
    {
        ApplyRec(left, right, m, 0, 0, _dataSize);
    }
    public T Query(int left, int right)
    {
        return QueryRec(left, right, 0, 0, _dataSize);
    }
    private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
    {
        Evaluate(index, nodeLeft, nodeRight);
        if (left >= nodeRight || right <= nodeLeft)
        {
            return _identity;
        }
        if (left <= nodeLeft && nodeRight <= right)
        {
            return _data[index];
        }
        T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
        T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
        return _operator(leftChild, rightChild);
    }
    public T GetByIndex(int target)
    {
        if (target < 0 || target >= _originalDataSize)
        {
            throw new Exception("Index is out of range.");
        }
        return AccessRec(target, 0, 0, _dataSize);
    }
    private T AccessRec(int target, int index, int l, int r)
    {
        Evaluate(index, l, r);
        if (index >= _dataSize - 1)
        {
            return _data[index];
        }
        int mid = (l + r) / 2;
        if (target < mid)
        {
            return AccessRec(target, (index << 1) + 1, l, mid);
        }
        else
        {
            return AccessRec(target, (index << 1) + 2, mid, r);
        }
    }
    // index以下のノードをすべて即時に評価する.
    private void EvaluateAll(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            if (index < _dataSize - 1)
            {
                EvaluateAll((index << 1) + 1, l, (l + r) / 2);
                EvaluateAll((index << 1) + 2, (l + r) / 2, r);
            }
            return;
        }
        if (index < _dataSize - 1)
        {
            _lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            _lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
            EvaluateAll((index << 1) + 1, l, (l + r) / 2);
            EvaluateAll((index << 1) + 2, (l + r) / 2, r);
        }
        _data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        _lazy[index] = null;
    }
    // 返されたArraySegment<T>は変更してはいけない.
    public ArraySegment<T> GetData()
    {
        EvaluateAll(0, 0, _dataSize);
        return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
    }
}
public struct BeatsNode<T> where T : struct, IEquatable<T>
{
    public T Value;
    public bool Failed;
    public BeatsNode(T value)
    {
        Failed = false;
        Value = value;
    }
}
// 区間に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(4N)
// 時間計算量:
// - 構築: O(N)
// - 操作: (操作に依存した計算量)
// - クエリ: O(logN)
// operator: クエリに対応する二項演算をする. 必ず計算ができる必要がある.
// mapping: 作用素を作用させる. 計算が出来なければFailed←trueとして返す. この際, 子ノードに対する評価が実行される.
// composition: 作用素を合成する
public sealed class SegmentTreeBeats<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>
{
    private int _treeSize;
    private int _dataSize;
    private int _originalDataSize;
    private BeatsNode<T>[] _data;
    private M?[] _lazy;
    private Monoid<BeatsNode<T>> _operator;
    private Apply<BeatsNode<T>, M> _mapping;
    private Monoid<M> _composition;
    private T _identity;
    private BeatsNode<T> _identityNode;
    public T this[int index]
    {
        get{
            return GetByIndex(index);
        }
    }
    public SegmentTreeBeats(int n, Monoid<BeatsNode<T>> op, Apply<BeatsNode<T>, M> mapping, Monoid<M> composition, T identity)
    {
        _originalDataSize = n;
        int size = 1;
        while (n > size)
        {
            size <<= 1;
        }
        _dataSize = size;
        _treeSize = 2 * size - 1;
        _data = new BeatsNode<T>[_treeSize];
        _identityNode = new BeatsNode<T>(_identity);
        _data.AsSpan().Fill(_identityNode);
        _lazy = new M?[_treeSize];
        _identity = identity;
        _operator = op;
        _mapping = mapping;
        _composition = composition;
    }
    public void Build(T[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            _data[i + _dataSize - 1] = new BeatsNode<T>(array[i]);
        }
        for (int i = _dataSize - 2; i >= 0; i--)
        {
            _data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
        }
    }
    private void Evaluate(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            return;
        }
        if (index < _dataSize - 1)
        {
            //_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            //_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
            if (_lazy[(index << 1) + 1] is not null)
            {
                Evaluate((index << 1) + 1, l, (l + r) / 2);
            }
            _lazy[(index << 1) + 1] = _lazy[index];
            if (_lazy[(index << 1) + 2] is not null)
            {
                Evaluate((index << 1) + 2, (l + r) / 2, r);
            }
            _lazy[(index << 1) + 2] = _lazy[index];
        }
        //_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        // 計算してみる
        BeatsNode<T> val = _mapping(_data[index], (M)_lazy[index], r - l);
        
        // 計算出来なければ
        if (val.Failed)
        {
            if (index >= _dataSize - 1)
            {
                throw new Exception("葉ノードに対するmappingは失敗してはいけません");
            }
            // 子ノードを即評価
            Evaluate((index << 1) + 1, l, (l + r) / 2);
            Evaluate((index << 1) + 2, (l + r) / 2, r);
            // 子ノードの結果から親を更新
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
        else
        {
            // 計算できればそのまま更新
            _data[index] = val;
        }
        _lazy[index] = null;
    }
    private M GuardComposition(M? a, M? b)
    {
        if (a is null)
        {
            return (M)b;
        }
        else
        {
            return _composition((M)a, (M)b);
        }
    }
    private void ApplyRec(int a, int b, M m, int index, int l, int r)
    {
        Evaluate(index, l, r);
        if (a <= l && r <= b)
        {
            _lazy[index] = GuardComposition(_lazy[index], m);
            Evaluate(index, l, r);
        }
        else if (a < r && l < b)
        {
            ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);
            ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);
            _data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
        }
    }
    public void Apply(int left, int right, M m)
    {
        ApplyRec(left, right, m, 0, 0, _dataSize);
    }
    public T Query(int left, int right)
    {
        return QueryRec(left, right, 0, 0, _dataSize).Value;
    }
    private BeatsNode<T> QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
    {
        Evaluate(index, nodeLeft, nodeRight);
        if (left >= nodeRight || right <= nodeLeft)
        {
            return _identityNode;
        }
        if (left <= nodeLeft && nodeRight <= right)
        {
            return _data[index];
        }
        BeatsNode<T> leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
        BeatsNode<T> rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
        return _operator(leftChild, rightChild);
    }
    public T GetByIndex(int target)
    {
        if (target < 0 || target >= _originalDataSize)
        {
            throw new Exception("Index is out of range.");
        }
        return AccessRec(target, 0, 0, _dataSize);
    }
    private T AccessRec(int target, int index, int l, int r)
    {
        Evaluate(index, l, r);
        if (index >= _dataSize - 1)
        {
            return _data[index].Value;
        }
        int mid = (l + r) / 2;
        if (target < mid)
        {
            return AccessRec(target, (index << 1) + 1, l, mid);
        }
        else
        {
            return AccessRec(target, (index << 1) + 2, mid, r);
        }
    }
    // index以下のノードをすべて即時に評価する.
    private void EvaluateAll(int index, int l, int r)
    {
        if (_lazy[index] is null)
        {
            if (index < _dataSize - 1)
            {
                EvaluateAll((index << 1) + 1, l, (l + r) / 2);
                EvaluateAll((index << 1) + 2, (l + r) / 2, r);
            }
            return;
        }
        if (index < _dataSize - 1)
        {
            //_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
            //_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
            if (_lazy[(index << 1) + 1] is not null)
            {
                Evaluate((index << 1) + 1, l, (l + r) / 2);
            }
            _lazy[(index << 1) + 1] = _lazy[index];
            if (_lazy[(index << 1) + 2] is not null)
            {
                Evaluate((index << 1) + 2, (l + r) / 2, r);
            }
            _lazy[(index << 1) + 2] = _lazy[index];
                
            EvaluateAll((index << 1) + 1, l, (l + r) / 2);
            EvaluateAll((index << 1) + 2, (l + r) / 2, r);
        }
        _data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
        _lazy[index] = null;
    }
    // 返されたArraySegment<T>は変更してはいけない.
    public void GetData(T[] destination)
    {
        if (destination.Length < _originalDataSize)
        {
            throw new Exception("書き込み先配列の大きさが足りない");
        }
        EvaluateAll(0, 0, _dataSize);
        //return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
        for (int i = 0; i < _originalDataSize; i++)
        {
            destination[i] = _data[_dataSize - 1 + i].Value;
        }
    }
}
public struct ChangeNode<T> : IEquatable<ChangeNode<T>> where T : struct, INumber<T>, IMinMaxValue<T>
{
    public T Max;
    public int MaxCount;
    public T SecondMax;
    public T Min;
    public int MinCount;
    public T SecondMin;
    public T Sum;
    public bool Equals(ChangeNode<T> other)
    {
        return this.Equals(other);
    }
    public static ChangeNode<R> MakeLeaf<R>(R value) where R : struct, INumber<R>, IMinMaxValue<R>
    {
        return new ChangeNode<R>()
        {
            Max = value,
            MaxCount = 1,
            SecondMax = R.MinValue,
            Min = value,
            MinCount = 1,
            SecondMin = R.MaxValue,
            Sum = value
        };
    }
}
public static class SegmentTreeBuilder
{
    public static LazySegmentTree<T, T> RangeAddMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Max,
        (x, m, l) =>
        {
            return x + m;
        },
        (a, b) => { return a + b; },
        identity);
    }
    public static LazySegmentTree<T, T> RangeUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Max,
        (x, m, l) =>
        {
            return m;
        },
        (x, y) => { return y; },
        identity);
    }
    public static LazySegmentTree<T, T> RangeAddMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Min,
        (x, m, l) =>
        {
            return x + m;
        },
        (a, b) => { return a + b; },
        identity);
    }
    public static LazySegmentTree<T, T> RangeUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, T.Min,
        (x, m, l) =>
        {
            return m;
        },
        (x, y) => { return y; },
        identity);
    }
    public static LazySegmentTree<T, T> RangeAddSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, (x, y) => x + y,
        (x, m, l) =>
        {
            return x + m * T.CreateChecked(l);
        },
        (a, b) => { return a + b; },
        identity);
    }
    public static LazySegmentTree<T, T> RangeUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new LazySegmentTree<T, T>(n, (x, y) => x + y,
        (x, m, l) =>
        {
            return m * T.CreateChecked(l);
        },
        (a, b) => { return b; },
        identity);
    }
    public static SegmentTree<T> PointUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Max, (a, b) => b, identity);
    }
    public static SegmentTree<T> PointAddMax<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Max, (a, b) => a + b, identity);
    }
    public static SegmentTree<T> PointUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Min, (a, b) => b, identity);
    }
    public static SegmentTree<T> PointAddMin<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, T.Min, (a, b) => a + b, identity);
    }
    public static SegmentTree<T> PointUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => b, identity);
    }
    public static SegmentTree<T> PointAddSum<T>(int n, T identity) where T : struct, INumber<T>
    {
        return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => a + b, identity);
    }
}
public sealed class PrefixSum2D<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>
{
    private T[,] _sums;
    public PrefixSum2D(T[,] sequence)
    {
        int height = sequence.GetLength(0);
        int width = sequence.GetLength(1);
        _sums = new T[height + 1, width + 1];
        // build prefix sum
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                _sums[y + 1, x + 1] = _sums[y + 1, x] + _sums[y, x + 1] - _sums[y, x] + sequence[y, x];
            }
        }
    }
    public T Sum(int startInclX, int startInclY, int endExclX, int endExclY)
    {
        return _sums[endExclY, endExclX] + _sums[startInclY, startInclX] - _sums[startInclY, endExclX] - _sums[endExclY, startInclX];
    }
    public T AllSum()
    {
        return _sums[_sums.GetLength(0) - 1, _sums.GetLength(1) - 1];
    }
}
public sealed class PrefixSum<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T>
{
    private T[] _sums;
    public PrefixSum(T[] sequence)
    {
        _sums = new T[sequence.Length + 1];
        _sums[0] = T.AdditiveIdentity;
        for (int i = 0; i < sequence.Length; i++)
        {
            _sums[i + 1] = _sums[i] + sequence[i];
        }
    }
    // [a, b)
    public T Sum(int aIncl, int bExcl)
    {
        return _sums[bExcl] - _sums[aIncl];
    }
    public T AllSum()
    {
        return _sums[^1];
    }
    public T[] GetArray()
    {
        return _sums;
    }
}
public sealed class UnionFind
{
    private int[] _parents;
    private int[] _size;
    private int _vertexCount;
    public int VertexCount => _vertexCount;
    public UnionFind(int n)
    {
        _vertexCount = n;
        _parents = new int[n];
        _size = new int[n];
        for (int i = 0; i < n; i++)
        {
            _parents[i] = i;
            _size[i] = 1;
        }
    }
    public int Root(int x)
    {
        if (_parents[x] == x)
            return x;
        return _parents[x] = Root(_parents[x]);
    }
    public void Unite(int x, int y)
    {
        int rootX = Root(x);
        int rootY = Root(y);
        if (rootX == rootY)
            return;
        int from = rootX;
        int to = rootY;
        // merge from to to
        if (_size[from] > _size[to])
        {
            (from, to) = (to, from);
        }
        _size[to] += _size[from];
        _parents[from] = to;
    }
    public List<int> Find(int x)
    {
        int rootX = Root(x);
        List<int> set = new List<int>();
        for (int i = 0; i < _vertexCount; i++)
        {
            if (Root(i) == rootX)
                set.Add(i);
        }
        return set;
    }
    public Dictionary<int, List<int>> FindAll()
    {
        Dictionary<int, List<int>> sets = new Dictionary<int, List<int>>();
        for (int i = 0; i < _vertexCount; i++)
        {
            int root = Root(i);
            if (sets.ContainsKey(root))
                sets[root].Add(i);
            else
                sets[root] = new List<int>() { i };
        }
        return sets;
    }
    public bool Same(int x, int y)
    {
        int rootX = Root(x);
        int rootY = Root(y);
        return rootX == rootY;
    }
    public int Size(int v)
    {
        return _size[Root(v)];
    }
    public void Clear()
    {
        for (int i = 0; i < _vertexCount; i++)
        {
            _parents[i] = i;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0