#1135094 (C#) No.3363 Two Closest Numbers

• 問題: No.3363 Two Closest Numbers
• ユーザー: 👑 b1agmpo1e
• 提出日時: 2025-11-19 17:45:22
• 言語: C# (.NET 8.0.404)
• 結果: WA
• 実行時間: -
• コード長: 40,380 bytes
• コンパイル時間: 14,399 ms
• コンパイル使用メモリ: 171,688 KB
• 実行使用メモリ: 218,300 KB
• 最終ジャッジ日時: 2025-11-19 17:46:09
• 合計ジャッジ時間: 41,018 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 53 WA * 6

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (90 ミリ秒)。
/home/judge/data/code/Main.cs(625,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(692,20): warning CS8981: 型名 'mod' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(288,23): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(715,20): warning CS8981: 型名 'toolbox' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

namespace test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            cin = new input();
            mod = new mod(998244353);
            toolbox = new toolbox();
            Priority_Queue = new Priority_Queue(true);
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            toolbox.StartTimer();

            int n=cin.intreed();
            var arr=cin.arrayint(n);
            var dic=new Dictionary<int,int>();
            
            if(arr.Length%2==0)
            {
                //throw new Exception("偶数は知らんて");
                //知らんけど、奇数個しかない値がヤバイ(偶数部分は打ち消しでok)
                //といっても全て奇数の最悪ケースでも1~9の9個しかない　9個を分割っておかしくない？　長さが変わるやんけ<=大嘘　arr.Length%2==0なので奇数要素は偶数個しか存在しない　なので、奇数のパターンは考えなくていい
                foreach(var i in arr)
                {
                    dic.safe_addtion_for_dictionary_int(i);
                }

                var nokori=new List<int>();
                foreach(var i in dic)
                {
                    if(i.Value%2==1)
                    {
                        nokori.Add(i.Key);
                    }

                }
                long ans=int.MaxValue;
                var nokori_arr=nokori.OrderBy(i=>i).ToArray();
                var cnt=nokori.Count/2;
                do
                {
                    //System.Console.WriteLine(string.Join(" ", nokori_arr));
                    long a=0;
                    long b=0;
                    for(int i=0; i<cnt; i++)
                    {
                        a=a*10+nokori_arr[i];
                        b=b*10+nokori_arr[cnt+i];
                    }
                    ans.chmin(Math.Abs(a-b));
                    //System.Console.WriteLine($"{a}:{b}");
                }while(toolbox.NextPermutation<int>(nokori_arr));
                System.Console.WriteLine(ans);
            }
            else
            {
                // 正しい構築イメージ（コメント用ダミーコード）:
                // var sorted = arr.OrderBy(x => x).ToArray();
                // int k = arr.Length / 2;
                // long A = 0; // k+1 桁、最小化したい
                // long B = 0; // k 
                // 、最大化したい

                // for (int i = 0; i <= k; i++) { A = A * 10 + sorted[i]; }              // 小さい値だけで構築
                // for (int i = 0; i < k; i++) { B = B * 10 + sorted[arr.Length-1-i]; }   // 大きい値だけで構築
                // Console.WriteLine(Math.Abs(A - B));
                long a=0;//ケタ数が大きい 各位はできるだけ小さい値で組む
                long b=0;//ケタ数が小さい 各位はできるだけ大きい値で組む
                var que=new Deque<long>((int)Math.Ceiling(Math.Log2(arr.Length)));
                foreach(var i in arr.OrderBy(i=>i))
                {
                    que.AddLast(i);
                }
                a=que.RemoveFirst();
                int cnt=arr.Length-1;
                cnt/=2;
                for(int i=0; i<cnt; i++)
                {
                    a=(a*10+que.RemoveFirst())%998244353;
                }
                for(int i=0; i<cnt; i++)
                {
                    b=(b*10+que.RemoveLast())%998244353;
                }
                System.Console.WriteLine((a-b+998244353)%998244353);
            }
            


            toolbox.PrintElapsedTime();
            Console.Out.Flush();
        }
        static input cin;
        static mod mod;
        static toolbox toolbox;
        static Priority_Queue Priority_Queue;
    }

/// <summary>
/// 高速なリングバッファベースの両端キュー（Deque）実装
/// O(1)での先頭・末尾への挿入・削除とインデックスアクセスが可能
/// </summary>
/// <typeparam name="T">格納する要素の型</typeparam>
    public class Deque<T>
    {
        private T[] buffer;
        private int head;
        private int tail;
        private int count;
        private int mask;

        /// <summary>
        /// 指定した初期容量でDequeを初期化する
        /// </summary>
        /// <param name="powerOfTwo">初期容量を2の冪乗で指定（デフォルト：4 = 16要素）</param>
        public Deque(int powerOfTwo = 4)
        {
            int capacity = 1 << powerOfTwo;
            buffer = new T[capacity];
            mask = capacity - 1;
            head = 0;
            tail = 0;
            count = 0;
        }

        /// <summary>
        /// 現在格納されている要素数を取得する
        /// </summary>
        public int Count => count;

        /// <summary>
        /// Dequeが空かどうかを取得する
        /// </summary>
        public bool IsEmpty => count == 0;

        /// <summary>
        /// 先頭に要素を追加する（O(1)）
        /// </summary>
        /// <param name="item">追加する要素</param>
        public void AddFirst(T item)
        {
            if (count == buffer.Length) Resize();
            head = (head - 1) & mask;
            buffer[head] = item;
            count++;
        }

        /// <summary>
        /// 末尾に要素を追加する（O(1)）
        /// </summary>
        /// <param name="item">追加する要素</param>
        public void AddLast(T item)
        {
            if (count == buffer.Length) Resize();
            buffer[tail] = item;
            tail = (tail + 1) & mask;
            count++;
        }

        /// <summary>
        /// 先頭の要素を削除して返す（O(1)）
        /// </summary>
        /// <returns>削除された先頭要素</returns>
        public T RemoveFirst()
        {
            var item = buffer[head];
            buffer[head] = default(T);
            head = (head + 1) & mask;
            count--;
            if (count > 0 && count <= buffer.Length >> 2) Shrink();
            return item;
        }

        /// <summary>
        /// 末尾の要素を削除して返す（O(1)）
        /// </summary>
        /// <returns>削除された末尾要素</returns>
        public T RemoveLast()
        {
            tail = (tail - 1) & mask;
            var item = buffer[tail];
            buffer[tail] = default(T);
            count--;
            if (count > 0 && count <= buffer.Length >> 2) Shrink();
            return item;
        }

        /// <summary>
        /// 先頭の要素を削除せずに取得する
        /// </summary>
        public T First => buffer[head];

        /// <summary>
        /// 末尾の要素を削除せずに取得する
        /// </summary>
        public T Last => buffer[(tail - 1) & mask];

        /// <summary>
        /// 先頭の要素を削除せずに取得する（O(1)）
        /// </summary>
        /// <returns>先頭要素</returns>
        public T PeekFirst() => buffer[head];

        /// <summary>
        /// 末尾の要素を削除せずに取得する（O(1)）
        /// </summary>
        /// <returns>末尾要素</returns>
        public T PeekLast() => buffer[(tail - 1) & mask];

        /// <summary>
        /// 指定したインデックスの要素にアクセスする（O(1)）
        /// </summary>
        /// <param name="index">アクセスするインデックス（0が先頭）</param>
        /// <returns>指定位置の要素</returns>
        public T this[int index]
        {
            get => buffer[(head + index) & mask];
            set => buffer[(head + index) & mask] = value;
        }

        /// <summary>
        /// バッファサイズを2倍に拡張する（内部使用）
        /// </summary>
        private void Resize()
        {
            int newCapacity = buffer.Length << 1;
            var newBuffer = new T[newCapacity];

            if (head < tail)
            {
                Array.Copy(buffer, head, newBuffer, 0, count);
            }
            else
            {
                int headLen = buffer.Length - head;
                Array.Copy(buffer, head, newBuffer, 0, headLen);
                Array.Copy(buffer, 0, newBuffer, headLen, tail);
            }

            buffer = newBuffer;
            mask = newCapacity - 1;
            head = 0;
            tail = count;
        }

        /// <summary>
        /// バッファサイズを半分に縮小する（内部使用）
        /// 要素数が容量の1/4以下になった場合に自動実行
        /// </summary>
        private void Shrink()
        {
            int newCapacity = buffer.Length >> 1;
            if (newCapacity < 16) return;

            var newBuffer = new T[newCapacity];

            if (head < tail)
            {
                Array.Copy(buffer, head, newBuffer, 0, count);
            }
            else
            {
                int headLen = buffer.Length - head;
                Array.Copy(buffer, head, newBuffer, 0, headLen);
                Array.Copy(buffer, 0, newBuffer, headLen, tail);
            }

            buffer = newBuffer;
            mask = newCapacity - 1;
            head = 0;
            tail = count;
        }

        /// <summary>
        /// 全ての要素を削除してDequeを空にする（O(1)）
        /// </summary>
        public void Clear()
        {
            Array.Clear(buffer, 0, buffer.Length);
            head = tail = count = 0;
        }
    }

    public class Treap
    {
        //1-indexです!!!!!!
        private class node
        {
            public long val;
            public node left;//小さい
            public node right;//大きい
            public long cnt;//部分木の大きさ
            public long same;//このvalが何個入っているのか
            public int priority;//優先度

            public node(long val, int priority, long same, node left = null, node right = null)
            {
                this.val = val;
                this.priority = priority;
                this.left = left;
                this.right = right;
                this.same = same;
            }

            public long update()
            {
                cnt = same;
                if (left != null) cnt += left.cnt;
                if (right != null) cnt += right.cnt;
                return cnt;
            }
        }

        private node root;
        private Random rand;
        public Treap(int seed = 998244353)
        {
            root = null;
            rand = new Random(seed);
        }

        //内部向け

        //key未満のノードとkey以上のノードに分割する
        private void Split(node t, long key, out node left, out node right)
        {
            if (t == null)
            {
                left = null;
                right = null;
                return;
            }
            else if (key <= t.val)
            {
                //key以上なので、今回のノードと右側部分木は右に行く
                Split(t.left, key, out left, out t.left);
                right = t;
            }
            else
            {
                //key未満なので、今回のノードと右側部分木は右に行く
                Split(t.right, key, out t.right, out right);
                left = t;
            }

            t.update();
        }

        //左と右を合体した新たな木(t)を作る
        private void Marge(ref node t, node left, node right)
        {
            if (left == null || right == null)
            {
                t = left ?? right;
            }
            else if (left.priority > right.priority)
            {
                //leftの方が優先度高い
                Marge(ref left.right, left.right, right);
                t = left;
            }
            else
            {
                //rightの方が優先度高い
                Marge(ref right.left, left, right.left);
                t = right;
            }
            if (t != null) t.update();
        }

        private void Insert(ref node t, node item)
        {
            if (t == null)
            {
                t = item;
            }
            else if (t.val == item.val)
            {
                t.same += item.same;
            }
            else if (item.priority > t.priority)
            {
                //itemの方が優先度高い このノードをitemに置き換える　今のノードtはledtかrightに入る
                Split(t, item.val, out item.left, out item.right);
                t = item;
            }
            else
            {
                //こいつは優先度がヒープになることに反するので、下に潜る
                Insert(ref item.val < t.val ? ref t.left : ref t.right, item);
            }
            t.update();
        }

        private void Erase(ref node t, long key, long same)
        {
            if (t == null) return;
            if (t.val == key)
            {
                t.same -= same;
                if (t.same == 0)
                {
                    //今いるノードを消す　このノードを子供をマージしてできた木に置き換える
                    Marge(ref t, t.left, t.right);
                }
            }
            else
            {
                //このノードは消したいノードじゃない
                Erase(ref key < t.val ? ref t.left : ref t.right, key, same);
            }
            if (t != null) t.update();
        }

        private bool Find(node t, long key)
        {
            if (t == null) return false;
            if (t.val == key) return true;
            return Find(key < t.val ? t.left : t.right, key);
        }


        private long GetKth(node t, long k)
        {
            if (t == null || k < 1 || k > t.cnt)
                throw new ArgumentOutOfRangeException(nameof(k));

            long leftCount = t.left != null ? t.left.cnt : 0;
            if (k <= leftCount)
            {
                return GetKth(t.left, k);
            }
            else if (k <= leftCount + t.same)
            {
                return t.val;
            }
            else
            {
                return GetKth(t.right, k - leftCount - t.same);
            }
        }
        //left以上 right未満の世界でk番目に小さい要素を取得する
        private long GetKth(long l, long r, int k)
        {
            // Split は「< key / >= key」
            Split(root, l, out node LessThanLeft, out node LeftOrMore);   // (<l) と (>=l)
            Split(LeftOrMore, r, out node inLR, out node MoreThanR);         // ([l,r)) と (>=r)

            if (inLR == null || k < 1 || k > inLR.cnt)
                throw new ArgumentOutOfRangeException(nameof(k));

            var nd = GetKth(inLR, k);

            // 必ず元に戻す（例外時も含めて復元）
            node back = null;
            Marge(ref back, inLR, MoreThanR);        // back = (>=l) を復元
            Marge(ref root, LessThanLeft, back);  // root を復元
            return nd;
        }

        private long FastGetKth(long l, long r, int k) => GetKth(root, CountLower(l) + k);
        // 要素 < val の個数を数える（非再帰・O(log N)）
        private long CountLower(long val)
        {
            long cnt = 0;
            var t = root;
            while (t != null)
            {
                if (t.val < val)
                {
                    cnt += (t.left?.cnt ?? 0) + t.same;
                    t = t.right;
                }
                else
                {
                    t = t.left;
                }
            }
            return cnt;
        }

        // k(1-indexed) 番目のノードを返すワーカー。見つからなければ null
        private node GetNode(node t, long k)
        {
            while (t != null)
            {
                long lc = t.left?.cnt ?? 0;
                if (k <= lc)
                {
                    t = t.left;
                }
                else if (k <= lc + t.same)
                {
                    return t;
                }
                else
                {
                    k -= lc + t.same;
                    t = t.right;
                }
            }
            return null;
        }

        // val 以上の最初の要素のインデックス（1-indexed）。なければ Count()+1
        private long LowerBoundIndex(long val) => CountLower(val) + 1;

        // val より大きい最初の要素のインデックス（1-indexed）。なければ Count()+1
        private long UpperBoundIndex(long val) => CountLower(checked(val + 1)) + 1;

        // ノード版：見つからなければ null
        private node LowerBoundNode(long val)
        {
            long idx = LowerBoundIndex(val);
            return (idx <= Count()) ? GetNode(root, idx) : null;
        }

        private node UpperBoundNode(long val)
        {
            long idx = UpperBoundIndex(val);
            return (idx <= Count()) ? GetNode(root, idx) : null;
        }

        //外部向け
        public void Insert(long key) => Insert(ref root, new node(key, rand.Next(), 1));
        public void Insert(long key, long same) => Insert(ref root, new node(key, rand.Next(), same));


        public void Erase(long key) => Erase(ref root, key, 1);
        public void Erase(long key, long same) => Erase(ref root, key, same);


        public bool Find(long key) => Find(root, key);

        public long Count() => root?.cnt ?? 0;

        public long this[int index] => GetKth(root, index);

        //public long GetKth(long l, long r, int k) => this.GetKth(l, r, k); 名前ぶつかっちゃった　悲しいね
        public long this[long l, long r, int k] => FastGetKth(l, r, k);

        public void test()
        {
            for (int i = 1; i <= 10; i++)
            {
                Insert(i);
            }

            Split(root, 5, out var left, out var right);
            for (int i = 1; i <= 5; i++)
            {
                System.Console.WriteLine($"{i},==>{Find(left, i)}");
            }
            System.Console.WriteLine("---");
            for (int i = 5; i <= 10; i++)
            {
                System.Console.WriteLine($"{i},==>{Find(right, i)}");
            }
            System.Console.WriteLine("===");

            Marge(ref root, left, right);
            for (int i = 1; i <= 10; i++)
            {
                System.Console.WriteLine($"{i},==>{Find(root, i)}");
            }
        }
    }

    public static class Extensions
    {
        public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
        {
            if (dic.ContainsKey(key))
                dic[key]++;
            else
                dic.Add(key, 1);
            return dic;
        }

        public static Dictionary<T, long> safe_addtion_for_dictionary_long<T>(this Dictionary<T, long> dic, T key)
        {
            if (dic.ContainsKey(key))
                dic[key]++;
            else
                dic.Add(key, 1);
            return dic;
        }

        public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
        {
            if (dic.ContainsKey(key))
                dic[key].Add(value);
            else
                dic.Add(key, new List<T2>() { value });
            return dic;
        }

        public static T list_pop_back<T>(this List<T> a)
        {
            var k = a[a.Count - 1];
            a.RemoveAt(a.Count - 1);
            return k;
        }

        public static T chmin<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) > 0)
                return a = b;
            else
                return a;
        }
        public static T chmax<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) < 0)
                return a = b;
            else
                return a;
        }

    }

    internal class input
    {
        string[] soloinput;
        int t;
        public input()
        {
            soloinput = new string[0];
            t = 0;
        }
        public string soloreed()
        {
            if (t < soloinput.Length)
            {
                return soloinput[t++];
            }
            string input = Console.ReadLine();
            while (input == "")
            {
                input = Console.ReadLine();
            }
            soloinput = input.Split(" ");
            t = 0;
            return soloinput[t++];
        }
        public int intreed()
        {
            return int.Parse(soloreed());
        }
        public int[] arrayint(int N)
        {
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = intreed();
            }
            return A;
        }
        public long longreed()
        {
            return long.Parse(soloreed());
        }
        public long[] arraylong(long N)
        {
            long[] A = new long[N];
            for (long i = 0; i < N; i++)
            {
                A[i] = longreed();
            }
            return A;
        }
        public decimal decimalreed()
        {
            return decimal.Parse(soloreed());
        }
        public decimal[] arraydecimal(long N)
        {
            decimal[] A = new decimal[N];
            for (decimal i = 0; i < N; i++)
            {
                A[(long)i] = decimalreed();
            }
            return A;
        }


    }

    internal class mod
    {
        public long T { get; set; }
        public mod(long mod = 1000000007)
        {
            T = mod;
        }
        public long addition(long A, long B)
        {
            long C = A + B;
            return (long)C % T;
        }
        public long subtraction(long A, long B)
        {
            return ((A % T) - (B % T) + T) % T;
        }
        public long multiplication(long A, long B)
        {
            return ((A % T) * (B % T)) % T;
        }

    }

    internal class toolbox
    {

        string Y = "Yes";
        string N = "No";
        static input cin;
        private DateTime? startTime;
        public toolbox()
        {
            cin = new input();
        }

        public long[] CumulativeSum(long[] A, bool mode = true)
        {
            if (mode == false) Array.Reverse(A);
            long[] back = new long[A.Length + 1];
            back[0] = 0;
            for (int i = 1; i <= A.Length; i++)
            {
                back[i] = back[i - 1] + A[i - 1];
            }
            if (mode == false) Array.Reverse(A);
            return back;
        }

        public long[] Eratosthenes(long A)
        {
            A++;
            var back = new List<long>();
            bool[] ch = new bool[A];
            for (int i = 2; i < A; i++) ch[i] = true;
            for (long i = 2; i < Math.Sqrt(A); i++)
            {
                if (ch[i] == true)
                {
                    back.Add(i);
                    for (long t = 1; i * t < A; t++)
                    {
                        ch[i * t] = false;
                    }
                }
            }
            for (long i = 0; i < A; i++)
            {
                if (ch[i] == true) back.Add(i);
            }
            return back.Distinct().ToArray();
        }
        public void Swap<T>(ref T a, ref T b)
        {
            var i = a;
            a = b;
            b = i;
        }

        public void LSwap<T>(ref List<T> A, int a, int b)
        {
            var i = A[a];
            A[a] = A[b];
            A[b] = i;
        }

        public long Gcd(long A, long B)
        {
            while (A != 0)
            {
                B %= A;
                Swap(ref A, ref B);
            }
            return B;
        }

        public long[] AllDivisors(long N)
        {
            var back = new List<long>();
            for (int i = 1; Math.Pow(i, 2) <= N; i++)
            {
                if (N % i == 0)
                {
                    back.Add(i);
                    back.Add(N / i);
                }
            }
            return back.Distinct().ToArray();
        }

        public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
        {
            if (indata.Count() == 1) yield return new T[] { indata.First() };
            foreach (var i in indata)
            {
                var used = new T[] { i };
                var unused = indata.Except(used);
                foreach (var t in ExhaustiveEnumeration(unused))
                    yield return used.Concat(t).ToArray();
            }
            //How to use
            //var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
        }

        public bool[,] bitallsearch(int N)
        {
            bool[,] back = new bool[(int)Math.Pow(2, N), N];
            for (int i = 0; i < Math.Pow(2, N); i++)
            {
                for (int t = 0; t < N; t++)
                {
                    var k = (i >> t) & 1;
                    if (k == 1)
                    {
                        back[i, t] = true;
                    }
                }
            }
            return back;
        }

        public static int BS<T>(T[] A, T key)
            where T : IComparable
        {
            //このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
            int left = 0;
            int right = A.Length;
            int mid = 0;
            while (left < right)
            {
                mid = (left + right) / 2;
                if (A[mid].CompareTo(key) == 0)
                    return mid;
                else if (A[mid].CompareTo(key) > 0)
                    right = mid;
                else if (A[mid].CompareTo(key) < 0)
                    left = mid + 1;
            }
            return -1;
        }

        public static int lower_bound<T>(T[] a, T v)
        {
            return lower_bound(a, v, Comparer<T>.Default);
        }

        public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
        {
            int left = 0;
            int right = A.Length - 1;
            int mid = 0;
            var W = 0;
            while (left <= right)
            {
                mid = (left + right) / 2;
                W = v.Compare(A[mid], key);
                if (W == -1)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return left;
        }

        public long[] prime_factorize(long N)
        {
            long T = N;
            var back = new List<long>();
            for (long i = 2; i * i <= T; i++)
            {
                if (T % i != 0) continue;
                while (T % i == 0)
                {
                    back.Add(i);
                    T /= i;
                }
            }
            if (T != 1) back.Add(T);
            return back.ToArray();
        }

        public long[] One_dimensional_Coordinate_Compression(long[] A)
        {
            long[] back = new long[A.Length];
            var T = A.Distinct().ToList();
            T.Sort();
            for (int i = 0; i < A.Length; i++)
                back[i] = T.BinarySearch(A[i]);
            return back;
        }

        public void setYN(string A = "Yes", string B = "No")
        {
            Y = A;
            N = B;
        }

        public void YN(bool ans)
        {
            if (ans)
                Console.WriteLine(Y);
            else
                Console.WriteLine(N);
        }

        public string[] x_dekakou(int H, int W)
        {
            var s = new string[H + 2];
            for (int i = 0; i < W + 2; i++)
            {
                s[0] += "x";
                s[H + 1] += "x";
            }
            for (int i = 1; i < H + 1; i++)
            {
                //x場外　.白　#黒
                s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
            }
            return s;
        }

        public List<List<char>> x_dekakou_char(int H, int W)
        {
            var grid = new List<List<char>>(H + 2);

            var border = new List<char>(W + 2);
            for (int i = 0; i < W + 2; i++)
                border.Add('x');
            grid.Add(new List<char>(border));

            for (int i = 0; i < H; i++)
            {
                var line = Console.ReadLine()?.Replace(" ", "") ?? string.Empty;
                var row = new List<char>(W + 2);
                row.Add('x');
                foreach (var c in line)
                    row.Add(c);
                row.Add('x');
                grid.Add(row);
            }

            grid.Add(new List<char>(border));
            return grid;
        }

        public List<List<int>> x_dekakou_string(int H, int W)
        {
            var back = new List<List<int>>();
            for (int i = 0; i < H + 2; i++)
                back.Add(Enumerable.Repeat<int>(-1, W + 2).ToList());
            for (int i = 0; i < W + 2; i++)
            {
                back[0][i] = -1;
                back[H + 1][i] = -1;
            }
            for (int i = 1; i <= H; i++)
            {
                back[i][0] = -1;
                back[i][W + 1] = -1;
                for (int t = 1; t <= W; t++)
                    back[i][t] = cin.intreed();
            }
            return back;
        }
        /// <summary>
        /// 配列の指定位置以降を反転する
        /// </summary>
        /// <param name="array">反転対象の配列</param>
        /// <param name="begin">反転開始位置（この位置以降が反転される）</param>
        private void Reverse<T>(T[] array, int begin) where T : IComparable<T>
        {
            // 反転する要素が2個未満の場合は何もしない
            if (array.Length - begin < 2) return;

            // 両端から中央に向かって要素を交換
            int left = begin;
            int right = array.Length - 1;
            while (left < right)
            {
                Swap(ref array[left], ref array[right]);
                left++;
                right--;
            }
        }

        /// <summary>
        /// 配列を辞書順で次の順列に変更する
        /// 全ての順列を列挙するには、事前に Array.Sort() でソートした配列を渡すこと
        /// </summary>
        /// <param name="array">順列を生成する配列（事前ソート必須）</param>
        /// <returns>次の順列が存在する場合true、最大順列の場合false</returns>
        public bool NextPermutation<T>(T[] array) where T : IComparable<T>
        {
            // 辞書順で次に大きい順列を生成

            // 1. 右端から降順でない位置を探す
            int pivotIndex = -1;
            for (int i = array.Length - 2; i >= 0; i--)
            {
                if (array[i].CompareTo(array[i + 1]) < 0) // 昇順ペア発見
                {
                    pivotIndex = i;
                    break;
                }
            }

            // 最大順列に到達している場合
            if (pivotIndex == -1) return false;

            // 2. pivotより大きい最右の要素と交換
            for (int j = array.Length - 1; j > pivotIndex; j--)
            {
                if (array[pivotIndex].CompareTo(array[j]) < 0)
                {
                    Swap(ref array[pivotIndex], ref array[j]);
                    break;
                }
            }

            // 3. pivot以降を昇順に並べ直し
            Reverse(array, pivotIndex + 1);
            return true;

            // how to use
            // do{}while(NextPermutation)
        }

        /// <summary>
        /// 回文判定のコア処理（配列版）
        /// </summary>
        private bool IsPalindromeCore<T>(T[] array, int left, int right) where T : IComparable<T>
        {
            while (left < right)
            {
                if (array[left].CompareTo(array[right]) != 0)
                    return false;
                left++;
                right--;
            }
            return true;
        }

        /// <summary>
        /// 回文判定のコア処理（文字列版）
        /// </summary>
        private bool IsPalindromeCore(string str, int left, int right)
        {
            while (left < right)
            {
                if (str[left] != str[right])
                    return false;
                left++;
                right--;
            }
            return true;
        }

        /// <summary>
        /// 配列全体が回文かどうかを判定
        /// </summary>
        public bool IsPalindrome<T>(T[] array) where T : IComparable<T>
        {
            return IsPalindromeCore(array, 0, array.Length - 1);
        }

        /// <summary>
        /// 文字列全体が回文かどうかを判定
        /// </summary>
        public bool IsPalindrome(string str)
        {
            return IsPalindromeCore(str, 0, str.Length - 1);
        }

        /// <summary>
        /// 指定範囲が回文かどうかを判定（配列版）
        /// </summary>
        public bool IsPalindrome<T>(T[] array, int start, int end) where T : IComparable<T>
        {
            return IsPalindromeCore(array, start, end);
        }

        /// <summary>
        /// 指定範囲が回文かどうかを判定（文字列版）
        /// </summary>
        public bool IsPalindrome(string str, int start, int end)
        {
            return IsPalindromeCore(str, start, end);
        }

        /// <summary>
        /// 指定長さの部分配列に回文が含まれるかを判定
        /// </summary>
        public bool HasPalindrome<T>(T[] array, int length) where T : IComparable<T>
        {
            for (int i = 0; i <= array.Length - length; i++)
            {
                if (IsPalindromeCore(array, i, i + length - 1))
                    return true;
            }
            return false;
        }

        /// <summary>
        /// 指定長さの部分文字列に回文が含まれるかを判定
        /// </summary>
        public bool HasPalindrome(string str, int length)
        {
            for (int i = 0; i <= str.Length - length; i++)
            {
                if (IsPalindromeCore(str, i, i + length - 1))
                    return true;
            }
            return false;
        }


        public long modpow(long x, long p, long mod = 1000000007)
        {
            long result = 1;
            x %= mod;
            while (p > 0)
            {
                if (p % 2 == 1)        // pが奇数の場合
                {
                    result = (result * x) % mod;
                }
                x = (x * x) % mod;      // xを二乗（これが繰り返し二乗）
                p /= 2;                 // pを半分にする
            }
            return result;
        }

        public void StartTimer()
        {
            startTime = DateTime.Now;
        }

        public void PrintElapsedTime(bool error_output = true)
        {
            //標準出力ではなくて標準エラー出力を使ってるのでatcoderのジャッジはこの出力を無視する　つまり消さなくてok　便利だね
            if (startTime.HasValue)
            {
                var elapsed = DateTime.Now - startTime.Value;
                if (error_output)
                    Console.Error.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
                else
                    Console.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");


            }
            else
            {
                Console.Error.WriteLine("Timer was not started.");
            }
        }
    }

    internal class Priority_Queue
    {
        toolbox toolbox = new toolbox();
        public List<(long, long)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, long)>();
            revase = cnt;
        }

        public void Enqueue(long a, long b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, long) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }

        public (long, long) GetPeek() => (revase ? Queue[0].Item1 : Queue[0].Item1 * -1, Queue[0].Item2);
    }

    internal class Generic_Priority_Queue<T>
    {
        toolbox toolbox = new toolbox();
        public List<(long, T)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Generic_Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, T)>();
            revase = cnt;
        }

        public void Enqueue(long a, T b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, T) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }

        public (long, T) get_first()
        {
            if (Queue.Count == 0)
                return (default(long), default(T));
            else
                return Queue[0];
        }
    }

}