AtCoder入緑に使ったテンプレ（C#）

素敵な夜ですね。色々と死にかけ状態ですがなんとかAtCoder 入緑しました。C#テンプレを共有です。お部屋をお連れします。C#erはよろしければお使いください。

お借りした部分ばかりですが、何卒ご容赦頂けますと幸いです。

色変記事はこちらです

// ABC999999999999

using System;using System.Collections.Generic;
using System.IO;using System.Linq;using static System.Math;
using System.Text;using System.Threading;using System.Globalization;
using System.Runtime.CompilerServices;using ComproSimarmLib.Util;using System.Numerics;
using static System.Console;

public class Program
{

    public static void Problem() 
    { 
        var sc = new Scanner();
        long a = sc.Nl();
        long b = sc.Nl();
        long ans = 0;

        Console.WriteLine(ans);

    }



    public static void Main(string[] args)
    {

        Problem();

    }

    const int Mod1097 = 1000000007;

}

namespace ComproSimarmLib.Util
{

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';
        private Boolean fileInput = false;
        StreamReader file;

        //コンストラクタでindexを0に、lineを配列に初期化
        public Scanner(string type="console")
        {
            _line = new string[0];
            _index = 0;

            if (type == "file") {
                fileInput = true;
                string FileToRead = Console.ReadLine();
                file = new StreamReader(FileToRead);
            }
        }

        //以下借り物
        public string Next()
        {
            while (_index >= _line.Length)
            {
                if (fileInput == true)
                {
                    _line = file.ReadLine().Split(Separator);
                }
                else
                {
                    _line = Console.ReadLine().Split(Separator);
                }

                _index = 0;
            }

            return _line[_index++];
        }

        public int Ni() => int.Parse(Next());
        public long Nl() => long.Parse(Next());
        public double Ndo() => double.Parse(Next());
        public decimal Nde() => decimal.Parse(Next());
        public char Ncr() => Next()[0];
        public char[] Ncs() => Next().ToCharArray();


        public string[] Array()
        {
            if (fileInput == true)
            {
                _line = file.ReadLine().Split(Separator);
            }
            else
            {
                _line = Console.ReadLine().Split(Separator);
            }
            _index = _line.Length;
            return _line;
        }

        public int[] Ints() => Array().Select(int.Parse).ToArray();
        public long[] Longs() => Array().Select(long.Parse).ToArray();
        public double[] Doubles() => Array().Select(double.Parse).ToArray();
        public decimal[] Decimals() => Array().Select(decimal.Parse).ToArray();
        public char[] CharsSpaced() => Array().Select(x=>Convert.ToChar(x)).ToArray();
    }
    

    class LittleMethods
    {
        //整数二つを受け入れ、最大公約数を出す
        public long GreatestCommonDivisor(long a, long b)
        {
            // https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d

            long x = 0;

            while (1 == 1)
            {
                if (a % b == 0)
                {
                    return b;
                }
                else
                {
                    x = a % b;
                    a = b;
                    b = x;
                }

            }

        }

        //整数二つを入れ、最小公倍数を出す
        public long LeastCommonMultipul(long a, long b)
        {
            // https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d

            long x = GreatestCommonDivisor(a, b);
            return a * b / x;
        }

        //整数一つを入れ、素数ならtrueを返す
        public bool PrimeNumberOrNot(long x)
        {

            if (x == 1) { return false; }
            for (long i = 2; i * i <= x; i++)
            {
                if (x % i == 0) { return false; }
            }

            return true;
        }

        //整数一つを入れ、全ての約数をListで返す
        public List<long> AllDivisors(long x)
        {
            List<long> y = new List<long>();

            if (x == 1) { y.Add(1); return y; }

            for (long i = 1; i * i <= x; i++)
            {
                if (x % i == 0)
                {
                    y.Add(i);
                    if (x / i != i) { y.Add(x / i); }

                }

            }

            y.Sort();

            return y;

        }

        //https://stackoverflow.com/questions/4124189/
        //sqrtの精度に問題があると聞いたので。decimalを入れるとルートしてdecimalで返す。
        public decimal SuperSqrt(decimal x, decimal epsilon = 0.0M)
        {
            decimal cur = (decimal)Math.Sqrt((double)x), prev;

            do
            {
                prev = cur;
                if (prev == 0.0M) return 0;
                cur = (prev + x / prev) / 2;

            } while (Math.Abs(prev - cur) > epsilon);

            return cur;


        }

        //階乗して返す
        public long Multipul_Fuctrial(long x)
        {
            long a = 1;

            for (int i = 2; i <= x; i++)
            {
                a *= i;
            }

            return a;

        }

        //特定の数で毎回割りながら階乗する。
        public long Multipul_FuctrialRemainderer(long x)
        {
            long a = 1;
            long b = (long)Math.Pow(10, 9) + 7;//ここは問題に寄る

            for (int i = 2; i <= x; i++)
            {
                a *= i;
                a = a % b;
            }

            return a;

        }

        //順列総当り用　戻り値：1 2 3,1 3 2,などなど各順列のリストのリスト
        //本番中に作ったので参考URLを紛失。申し訳ございません。
        //重い！　注意
        public IEnumerable<T[]> Make_PermutationList<T>(IEnumerable<T> col)
        {

            if (col.Count() == 1) yield return new T[] { col.First() };

            foreach (var x in col)
            {
                var selected = new T[] { x };
                var unused = col.Except(selected);

                foreach (var y in Make_PermutationList(unused))
                {
                    yield return selected.Concat(y).ToArray();
                }
            }

        }

        // https://webbibouroku.com/Blog/Article/cs-permutation
        // 使い方：List<long[]> PermListList = lm.AllPermutation<long>(seed);
        public List<T[]> AllPermutation<T>(params T[] array) where T : IComparable
        {
            var a = new List<T>(array).ToArray();
            var res = new List<T[]>();
            res.Add(new List<T>(a).ToArray());
            var n = a.Length;
            var next = true;
            while (next)
            {
                next = false;

                // 1
                int i;
                for (i = n - 2; i >= 0; i--)
                {
                    if (a[i].CompareTo(a[i + 1]) < 0) break;
                }
                // 2
                if (i < 0) break;

                // 3
                var j = n;
                do
                {
                    j--;
                } while (a[i].CompareTo(a[j]) > 0);

                if (a[i].CompareTo(a[j]) < 0)
                {
                    // 4
                    var tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                    Array.Reverse(a, i + 1, n - i - 1);
                    res.Add(new List<T>(a).ToArray());
                    next = true;
                }
            }
            return res;
        }
        
        //int nを受け取り、数が少ない順で2^n以下全てのbitを記載したリストのリストを返す
        public List<List<int>> Make_BitList<T>(int n)
        {
            List<List<int>> allBit = new List<List<int>>();

            for (int i = 0; i < 1 << n; i++)
            {
                List<int> item = new List<int>();
                string bitString = Convert.ToString(i, 2).PadLeft(n, '0');
                foreach (char c in bitString)
                {
                    item.Add(c - 48);
                }
                allBit.Add(item);
            }

            return allBit;
        }
        //nCr　巨大数に弱い　考えて使うこと
        public long NumberOfCombination(long n, long r)
        {
            long x = 1;
            for (long i = 0; i < r; i++)
            {
                x *= n - i;
            }
            for (long i = r; i > 0; i--)
            {
                x /= i;
            }

            return x;

        }
        
        public long LongPow(long a,long b){
        	
        	long ret = 1;
        	
        	for(long i = 0;i<b;i++){
        		ret*=a;
        	}
        	
        	return ret;
        
        }

        public BigInteger BigPow(long a,long b){
        	
        	BigInteger ret = 1;
        	
        	for(long i = 0;i<b;i++){
        		ret*=a;
        	}
        	
        	return ret;
        
        }
        
        // ダイクストラ
        // tree=new List<Pair>[n];tree[first].Add(new Pair(second,cost));var time = lm.Dijkstra(0,tree);
        // のようにして使う
        // 各頂点への最短時間が配列として記録される
        public long[] Dijkstra(int start,List<Pair>[] tree){
            var q = new PriorityQueue<Pair>(tree.Length,false);
            var res = Enumerable.Repeat(long.MaxValue,tree.Length).ToArray();
            res[start] = 0;
            q.Enqueue(new Pair(start,0));
            while(q.Count>0){
                var cur = q.Dequeue();
                if(res[cur.Pos] != cur.Val) continue;
                foreach (var next in tree[cur.Pos])
                {
                    if(res[next.Pos]<= cur.Val + next.Val) continue;
                    res[next.Pos] = cur.Val + next.Val;
                    q.Enqueue(new Pair(next.Pos,cur.Val+next.Val));
                }
            }
            return res;
        } 

        

        // ワーシャルフロイド法（Floyd-Warshall Algorithm）
        // tree=new List<Pair>[n];tree[first].Add(new Pair(second,cost));
        // long[][] time = lm.FloydWarshall(tree,nodeCount);
        // 各頂点から各頂点への最短距離がジャグ配列として返る
        public long[][] FloydWarshall(List<Pair>[] tree,long n){

            long[][] dp = new long[n][];
            
            for(int i = 0;i<n;i++){
                dp[i] = Enumerable.Repeat(long.MaxValue / 1000,(int)n).ToArray();
            }

            for (int i = 0; i < tree.Length; i++)
            {
                foreach (var edge in tree[i])
                {
                    dp[i][edge.Pos] = edge.Val;
                }
            }

            for (int i = 0; i < n; i++)
            {
                dp[i][i] = 0;
            }

            for (int k = 0; k < n; k++)
            {
                for (int s = 0; s < n; s++)
                {
                    for (int t = 0; t < n; t++)
                    {
                        dp[s][t] = Math.Min(dp[s][t],dp[s][k]+dp[k][t]);
                    }
                }
            }

            return dp;
            
        }
        
        // 最小全域木判定　クラスカル法
        // https://atcoder.jp/contests/abc218/tasks/abc218_e
        // int[][] es = [[pointA,pointB,cost],[...],...]
        // var mes = Kruskal(int nodeNum,es); 
        // とするとint[][] mes = [[（必要なedge）],[...],...]が返る
        // 無向グラフは片道だけでOK
        // 応用していく場合はedges.Add(new List<long>(){a-1,b-1,c,？});でも動く
        public int[][] Kruskal(int n,int[][] edges){
            var uf = new UnionFind(n);
            var minSTreeNodes = new List<int[]>();
    
            foreach (var e in edges.OrderBy(e=>e[2]))
            {
                if(uf.Same(e[0],e[1])){continue;}
                uf.Unite(e[0],e[1]);
                minSTreeNodes.Add(e);
            }
            return minSTreeNodes.ToArray();
        }
        // 座標の入ったListを入れると、座標圧縮された後のListを返す（開始地点は1）。
        public List<long> positionComp(List<long> map){

            var mapSorted = new SortedSet<long>(map).ToList();
            
            var compedMap = new List<long>();

            foreach(var pos in map){
                compedMap.Add(mapSorted.BinarySearch(pos)+1);
            }

            return compedMap;
        }

        public long ketasuu(long x){
            return x.ToString().Length;
        }

        // https://atcoder.jp/contests/abc145/submissions/8472887
        // 2乗ずつかけていく少し高速なpow、第3引数はmod
        public long ModFastPow(long x,long n,long m){
            long ans = 1;
            while(n>0){
                if(n%2==1){
                    ans = ans * x % m;
                    n-=1;
                }
                x=x*x%m;
                n/=2;
            }
            return ans;
        }

        // 高速なpowを使って高速化した、modの世界でのみ成り立つnCr、第3引数はmod
        public long ModWorldNcr(long n,long r,long m){
            long ans = 1;
            for (var i = n-r+1; i <= n; i++)
                ans = ans * i % m;
            for (var i = 2; i<=r; i++)
                ans = ans * ModFastPow(i,m-2,m) %m;
            return ans;
        }

        // https://atcoder.jp/contests/abc142/submissions/18533628
        // 引数を素因数分解し、その内容でDictionaryを作る
        public Dictionary<long,long> PrimeFactorDictionary(long n){
            var dic = new Dictionary<long,long>();
            var tmp = n;
            
            while(tmp % 2 ==0){
                tmp /= 2;
                if(dic.ContainsKey(2)) ++dic[2];
                else dic.Add(2,1);    
            }

            for (var p = 3L; p*p <= n; p+=2)
            {
                while(tmp % p == 0){
                    tmp /= p;
                    if(dic.ContainsKey(p)) dic[p]++;
                    else dic.Add(p,1);
                }
                if (tmp == 1) break;
            }
            if (tmp > 1) dic.Add(tmp, 1);
            return dic;
        }

        // 二分探索関数。第二引数の配列の中から、最初にxより大きかった場所のインデックスを返す。
        public long BinarySearch_firstLarger(long x,long[] arrSorted){
        
            long l = 0;
            long r = arrSorted.Length;
            long m = 0;
        
            while(l+1<r){
                m = (l + r) / 2;
                if(arrSorted[m] > x) r = m;
                else l = m;
            }

            if(arrSorted[l]>=x) return l;
            else return r;

        }

        // 二分探索関数。第二引数の配列の中から、最後にxより小さかった場所のインデックスを返す。
        public long BinarySearch_lastSmaller(long x,long[] arrSorted){
        
            long l = 0;
            long r = arrSorted.Length;
            long m = 0;
        
            while(l+1<r){
                m = (l + r) / 2;
                if(arrSorted[m] >= x) r = m;
                else l = m;
            }

            if(r==arrSorted.Length) return l;
            else if(arrSorted[r]>=x) return l;
            else return r;

        }

        // ランレングス圧縮を行い、文字×文字数のタプルのリストを返す。
        public List<Tuple<string,long>> RunLengthEncode(string s){
            var ret = new List<Tuple<string,long>>();
            var count = 1;
            for(var i = 1 ; i < s.Length ; i++)
            {
                if(s[i] != s[i-1]){
                    ret.Add(new Tuple<string,long>(s.Substring(i-1,1),count));
                    count = 1;
                }else{
                    count++;
                }
            }
            ret.Add(new Tuple<string,long>(s.Substring(s.Length-1,1),count));
            return ret;

        }

        // 回転。Tuple<long,long> lotatedxy = littleLotate(回転前x,y,原点x,y,度数法の回転角度)
        public Tuple<double,double> littleLotate(double x1,double y1,double x0,double y0,double angle360){

            double dis = Sqrt((x0-x1) * (x0-x1) + (y0-y1) * (y0-y1));
            double startRad = Atan2(y1-y0,x1-x0);
            
            double newRad = startRad + 2 * Math.PI / (360 / angle360);

            double unitX = Math.Cos(newRad);
            double unitY = Math.Sin(newRad);
            
            return new Tuple<double,double>(x0+unitX*dis,y0+unitY*dis);

        }

        // 2点間の距離。
        public double twoPointsDistance(double x1,double y1,double x2,double y2){
            
            double dis = Sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
            return dis;
        }

        // p1、p2の2点でできた直線と点(x,y)の距離
        public double lineOfTwoPointsAndPointDistance(int p1x,int p1y,int p2x,int p2y,int x,int y){

            double a = p2y - p1y;
            double b = -(p2x - p1x);
            double c = (p2x - p1x) * p1y - (p2y - p1y) * p1x;

            double dist = Abs(a * x + b * y + c) / Sqrt(a * a + b * b);
            return dist;
        }


    }


}

// 優先度付きキュー用のPair型　CompareTo関数使用
class Pair : IComparable<Pair>{
    public long Pos;
    public long Val;
    public Pair(long pos, long val){
        Pos=pos;Val=val;
    }
    public int CompareTo(Pair b){
        return Val.CompareTo(b.Val);
    }
}

// 優先度付きキュー
// var q = new PriorityQueue<Pair>(tree.Length,false);　で呼び
// q.Enqueue(new Pair(pos,val));でEnqueue、q.Dequeue();でDequeue
// dijkstra、Pair、優先度付きキューは　https://atcoder.jp/contests/abc035/submissions/24032918　より
class PriorityQueue<T> where T : IComparable<T>{
    public T[] List;
    public int Count;
    bool IsTopMax;
    public PriorityQueue(int count,bool isTopMax = false){
        IsTopMax = isTopMax;
        List = new T[count];
    }

    public void Enqueue(T value){
        if(Count == List.Length){
            var newlist = new T[List.Length*2];
            for (int i = 0; i < List.Length; ++i)
            {
                newlist[i] = List[i];
            }
            List = newlist;
        }
        var pos = Count;
        List[pos] = value;
        ++Count;
        while(pos>0){
            var parent=(pos-1)/2;
            if(Calc(List[parent],List[pos],true)) break;
            Swap(parent,pos);
            pos = parent;
        }
    }

    public T Dequeue(){
        --Count;
        Swap(0,Count);
        var pos = 0;
        while(true){
            var child = pos * 2 + 1;
            if(child >= Count) break;
            if(child + 1 < Count && Calc(List[child+1],List[child],false)) ++child;
            if(Calc(List[pos],List[child],true)) break;
            Swap(pos,child);
            pos = child;
        }
        return List[Count];
    }

    bool Calc(T a, T b,bool equalVal){
        var ret = a.CompareTo(b);
        if(ret == 0 && equalVal) return true;
        return IsTopMax ? ret > 0 : ret < 0;
    }

    void Swap(int a,int b){
        var tmp = List[a];
        List[a] = List[b];
        List[b] = tmp;
    }


}

/*　個数不要な優先度付きキュー　https://yambe2002.hatenablog.com/entry/2018/12/24/140754
public class PriorityQueue<T> where T : IComparable
{
    private IComparer<T> _comparer = null;
    private int _type = 0;

    private T[] _heap;
    private int _sz = 0;

    private int _count = 0;

    /// <summary>
    /// Priority Queue with custom comparer
    /// </summary>
    public PriorityQueue(IComparer<T> comparer)
    {
        _heap = new T[128];
        _comparer = comparer;
    }

    /// <summary>
    /// Priority queue
    /// </summary>
    /// <param name="type">0: asc, 1:desc</param>
    public PriorityQueue(int type = 0)
    {
        _heap = new T[128];
        _type = type;
    }

    private int Compare(T x, T y)
    {
        if (_comparer != null) return _comparer.Compare(x, y);
        return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
    }

    public void Push(T x)
    {
        _count++;
        if (_count > _heap.Length)
        {
            var newheap = new T[_heap.Length * 2];
            for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
            _heap = newheap;
        }

        //node number
        var i = _sz++;

        while (i > 0)
        {
            //parent node number
            var p = (i - 1) / 2;

            if (Compare(_heap[p], x) <= 0) break;

            _heap[i] = _heap[p];
            i = p;
        }

        _heap[i] = x;
    }

    public T Pop()
    {
        _count--;

        T ret = _heap[0];
        T x = _heap[--_sz];

        int i = 0;
        while (i * 2 + 1 < _sz)
        {
            //children
            int a = i * 2 + 1;
            int b = i * 2 + 2;

            if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

            if (Compare(_heap[a], x) >= 0) break;

            _heap[i] = _heap[a];
            i = a;
        }

        _heap[i] = x;

        return ret;
    }

    public int Count()
    {
        return _count;
    }

    public T Peek()
    {
        return _heap[0];
    }

    public bool Contains(T x)
    {
        for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
        return false;
    }

    public void Clear()
    {
        while (this.Count() > 0) this.Pop();
    }

    public IEnumerator<T> GetEnumerator()
    {
        var ret = new List<T>();

        while (this.Count() > 0)
        {
            ret.Add(this.Pop());
        }

        foreach (var r in ret)
        {
            this.Push(r);
            yield return r;
        }
    }

    public T[] ToArray()
    {
        T[] array = new T[_sz];
        int i = 0;

        foreach (var r in this)
        {
            array[i++] = r;
        }

        return array;
    }
}
*/



// https://atcoder.jp/contests/abc097/submissions/2592272
public class UnionFind
{
    private int[] data;
    private int[] rank;
    private int[] size;

    public UnionFind(int n)
    {
        data = new int[n];
        rank = new int[n];
        size = new int[n];
        for(var i = 0; i < n; i++)
        {
            data[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    public int Root(int x)
    {
        return data[x] == x ? x : data[x] = Root(data[x]);
    }

    public bool Same(int x,int y)
    {
        return Root(x) == Root(y);
    }
    public int Size(int x)
    {
        return size[Root(x)];
    }

    public void Unite(int x,int y)
    {
        x = Root(x);
        y = Root(y);
        if (x == y) return;

        if (rank[x] < rank[y])
        {
            data[x] = y;
        }
        else
        {
            data[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
        int tmp = size[x];
        size[x] += size[y];
        size[y] += tmp;
    }
}
    // Array.Sort(s,new Comparer());の形で使う独自のComparer
class Comparer : IComparer<string>{
        
    public int Compare(string l,string m){
        
        return l.Length - m.Length;

    }


}
    
// var map = new Map<int, int>();
// https://atcoder.jp/contests/abc210/submissions/24288120
// https://qiita.com/Camypaper/items/de6d576fe5513743a50e
public class Map<TKey, TValue> : Dictionary<TKey, TValue>
{
    public new TValue this[TKey key]
    {
        get
        {
            TValue o;
            return TryGetValue(key, out o) ? o : default(TValue);
        }
        set { base[key] = value; }
    }
}

// 最短共通祖先
// var lca = new LeastCommonAncestorTree(int 頂点数,List<long>[n] map);で起動
// lca.dist(v1,v2)で２頂点間の距離を出せる
// https://atcoder.jp/contests/abc014/submissions/531033
// ※扱いやすいよう全変数をlong型にしているが、シフト処理の為内部的にはint以上の桁数は扱えない
class LeastCommonAncestorTree // no loop
{
    long n, m;
    long[][] parent;
    long[] dep;
    public LeastCommonAncestorTree(long n, List<long>[] e) // e : 0-indexed
    {
        this.n = n;
        parent = new long[n][];
        dep = new long[n];
        m = (long)Math.Log(n + 1, 2) + 1;
        for (long i = 0; i < n; i++)
        {
            parent[i] = new long[m];
            dep[i] = n + 1;
            for (long j = 0; j < m; j++)
                parent[i][j] = -1;
        }
        long depmax = 0;
        dep[0] = 0;
        var q = new Queue<long>();
        q.Enqueue(0);
        while (q.Count > 0)
        {
            var p = q.Dequeue();
            foreach (var item in e[p])
            {
                if (dep[item] > dep[p] + 1)
                {
                    dep[item] = dep[p] + 1;
                    depmax = Math.Max(depmax, dep[item]);
                    parent[item][0] = p;
                    q.Enqueue(item);
                }
            }
        }
        for (long i = 1; 1 << (int)i <= depmax; i++)
            for (long j = 0; j < n; j++)
                if (dep[j] >= 1 << (int)i)
                    parent[j][i] = parent[parent[j][i - 1]][i - 1];
    }
    long climb(long a, long d)
    {
        if (d == 0) return a;

        long i = 0;
        while (1 << (int)i <= d) ++i;

        --i;
        return climb(parent[a][i], d - (1 << (int)i));
    }
    long subdist(long a, long b)
    {
        if (a == b) return 0;
        if (parent[a][0] == parent[b][0]) return 2;

        for (long i = 1; i < m; i++)
            if (parent[a][i - 1] != parent[b][i - 1] && parent[a][i] == parent[b][i])
                return (1 << (int)i) + subdist(parent[a][i - 1], parent[b][i - 1]);

        return -1;
    }
    public long dist(long a, long b)
    {
        long p = a, q = b, c = 0;
        if (dep[p] < dep[q])
        {
            c += dep[q] - dep[p];
            q = climb(q, dep[q] - dep[p]);
        }
        else if (dep[p] > dep[q])
        {
            c += dep[p] - dep[q];
            p = climb(p, dep[p] - dep[q]);
        }
        return c + subdist(p, q);
    }
}


// 平衡二分探索木＋multiset
// https://yambe2002.hatenablog.com/entry/2017/02/07/122421

/// <summary>
/// Self-Balancing Binary Search Tree
/// (using Randamized BST)
/// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
    public class Node
    {
        public T Value;
        public Node LChild;
        public Node RChild;
        public int Count;     //size of the sub tree

        public Node(T v)
        {
            Value = v;
            Count = 1;
        }
    }

    static Random _rnd = new Random();

    public static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        return t;
    }

    public static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
        {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        else
        {
            r.LChild = Merge(l, r.LChild);
            return Update(r);
        }
    }

    /// <summary>
    /// split as [0, k), [k, n)
    /// </summary>
    public static Tuple<Node, Node> Split(Node t, int k)
    {
        if (t == null) return new Tuple<Node, Node>(null, null);
        if (k <= Count(t.LChild))
        {
            var s = Split(t.LChild, k);
            t.LChild = s.Item2;
            return new Tuple<Node, Node>(s.Item1, Update(t));
        }
        else
        {
            var s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.Item1;
            return new Tuple<Node, Node>(Update(t), s.Item2);
        }
    }

    public static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    public static Node RemoveAt(Node t, int k)
    {
        var s = Split(t, k);
        var s2 = Split(s.Item2, 1);
        return Merge(s.Item1, s2.Item2);
    }

    public static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    public static Node Find(Node t, T v)
    {
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    public static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        var currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            if (currentIdx == idx) return t;
            if (currentIdx > idx)
            {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else
            {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }

        return null;
    }

    public static int UpperBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var ret = Int32.MaxValue;
        var idx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
                
            if (cmp > 0)
            {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static int LowerBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var idx = Count(t) - Count(t.RChild) - 1;
        var ret = Int32.MaxValue;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp >= 0)
            {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static Node Insert(Node t, T v)
    {
        var ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        var s = Split(t, k);
        return Merge(Merge(s.Item1, new Node(v)), s.Item2);
    }

    public static IEnumerable<T> Enumerate(Node t)
    {
        var ret = new List<T>();
        Enumerate(t, ret);
        return ret;
    }

    static void Enumerate(Node t, List<T> ret)
    {
        if (t == null) return;
        Enumerate(t.LChild, ret);
        ret.Add(t.Value);
        Enumerate(t.RChild, ret);
    }
}
/// <summary>
/// C-like set
/// </summary>
public class Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    public T this[int idx]{ get { return ElementAt(idx); } }

    public int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    public virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else
        {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    public void Clear()
    {
        _root = null;
    }

    public void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    public bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    public T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    public int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    public Tuple<int, int> EqualRange(T v)
    {
        if (!Contains(v)) return new Tuple<int, int>(-1, -1);
        return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    public List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
    }
}
/// <summary>
/// C-like multiset
/// </summary>
public class MultiSet<T> : Set<T> where T : IComparable
{
    public override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}


// thanks
// https://atcoder.jp/contests/abc171/submissions/14526247
// https://atcoder.jp/contests/abc171/submissions/14526315
// https://atcoder.jp/contests/abc171/submissions/14527040
// https://atcoder.jp/contests/abc171/submissions/14527118