Submission #19925793

---

Source Code Expand

using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive.IO;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
using static System.Math;
partial class Program
{
    partial void WriteBool(bool b) => cw.WriteLine(b ? "Yes" : "No");
    bool __ManyTestCases() => false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        int N = cr;
        var cnts = new (int r, int g, int b)[N];
        {
            var (sizes, colors) = cr.Repeat(N).SelectArray(cr => (cr.Int, cr.Char));
            Array.Sort(sizes, colors);

            int R = 0;
            int G = 0;
            int B = 0;
            int r = 0;
            for (int l = 0; l < sizes.Length; l++)
            {
                while (r < sizes.Length && sizes[r] < 2 * sizes[l])
                {
                    switch (colors[r++])
                    {
                        case 'R': ++R; break;
                        case 'G': ++G; break;
                        case 'B': ++B; break;
                    }
                }
                cnts[l] = (R, G + 1, B + 1);
                switch (colors[l])
                {
                    case 'R': --R; break;
                    case 'G': --G; break;
                    case 'B': --B; break;
                }
            }
            cnts.Sort();
        }
        GC.Collect();
        int ci = cnts.Length - 1;

        var set = new SetDictionary<int, int> { { 0, N + 10 }, { N + 10, 0 } };
        long area = 0;
        long res = -1;
        for (int rc = N + 1; rc >= 0; rc--)
        {
            while (ci >= 0 && cnts[ci].r == rc)
            {
                var (_, g, b) = cnts[ci--];
                bool fl = false;
                var items = set.EnumerateNode(set.FindNodeUpperBound(g), true)
                    .TakeWhile(n =>
                    {
                        if (fl) return false;
                        fl = b < n.Value;
                        return true;
                    }).ToArray();
                if (b <= items[0].Value) continue;

                area += (long)(g - items[1].Key) * (b - items[0].Value);
                for (int i = 1; i + 2 < items.Length; i++)
                {
                    area += (long)(items[i].Key - items[i + 1].Key) * (b - items[i].Value);
                    set.Remove(items[i].Key);
                }
                if (items.Length == 2)
                {
                    set.Add(g, b);
                    continue;
                }

                area += (long)(items[^2].Key - items[^1].Key) * (b - items[^2].Value);
                if (items[^2].Value == 0)
                    set.Add(g, b);
                else
                {
                    items[^2].Key = g;
                    items[^2].Value = b;
                }
            }
            if (rc % 100000 == 0) GC.Collect();
            res += area;
        }

        return res;
    }
}

struct Op : ILazySegtreeOperator<(int max, int cnt, long sum), int>
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (int max, int cnt, long sum) Operate((int max, int cnt, long sum) x, (int max, int cnt, long sum) y) => (Max(x.max, y.max), x.cnt + y.cnt, x.sum + y.sum);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public (int max, int cnt, long sum) Mapping(int f, (int max, int cnt, long sum) x) => (f, x.cnt, (long)x.cnt * f);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int Composition(int nf, int cf) => Max(nf, cf);

    public (int max, int cnt, long sum) Identity => (0, 0, 0);
    public int FIdentity => 0;
}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE: https://github.com/naminodarie/AtCoderProject/blob/master/LICENSE
namespace AtCoder{public interface ILazySegtreeOperator<T,F>{T Identity{get;}F FIdentity{get;}T Operate(T x,T y);T Mapping(F f,T x);F Composition(F nf,F cf);}public class LazySegtree<TValue,F,TOp>where TOp:struct,ILazySegtreeOperator<TValue,F>{private static readonly TOp op=default;public int Length{get;}internal readonly int log;internal readonly int size;public readonly TValue[]d;public readonly F[]lz;public LazySegtree(int n){Length=n;log=InternalBit.CeilPow2(n);size=1<<log;d=new TValue[2*size];lz=new F[size];Array.Fill(d,op.Identity);Array.Fill(lz,op.FIdentity);}public LazySegtree(TValue[]v):this(v.Length){for(int i=0;i<v.Length;i++)d[size+i]=v[i];for(int i=size-1;i>=1;i--){Update(i);}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Update(int k)=>d[k]=op.Operate(d[2*k],d[2*k+1]);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void AllApply(int k,F f){d[k]=op.Mapping(f,d[k]);if(k<size)lz[k]=op.Composition(f,lz[k]);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Push(int k){AllApply(2*k,lz[k]);AllApply(2*k+1,lz[k]);lz[k]=op.FIdentity;}public TValue this[int p]{[MethodImpl(MethodImplOptions.AggressiveInlining)]set{p+=size;for(int i=log;i>=1;i--)Push(p>>i);d[p]=value;for(int i=1;i<=log;i++)Update(p>>i);}[MethodImpl(MethodImplOptions.AggressiveInlining)]get{p+=size;for(int i=log;i>=1;i--)Push(p>>i);return d[p];}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public TValue Slice(int l,int len)=>Prod(l,l+len);[MethodImpl(MethodImplOptions.AggressiveInlining)]public TValue Prod(int l,int r){if(l==r)return op.Identity;l+=size;r+=size;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)Push(l>>i);if(((r>>i)<<i)!=r)Push(r>>i);}TValue sml=op.Identity,smr=op.Identity;while(l<r){if((l&1)!=0)sml=op.Operate(sml,d[l++]);if((r&1)!=0)smr=op.Operate(d[ --r],smr);l>>=1;r>>=1;}return op.Operate(sml,smr);}public TValue AllProd=>d[1];public void Apply(int p,F f){p+=size;for(int i=log;i>=1;i--)Push(p>>i);d[p]=op.Mapping(f,d[p]);for(int i=1;i<=log;i++)Update(p>>i);}public void Apply(int l,int r,F f){if(l==r)return;l+=size;r+=size;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)Push(l>>i);if(((r>>i)<<i)!=r)Push((r-1)>>i);}{int l2=l,r2=r;while(l<r){if((l&1)!=0)AllApply(l++,f);if((r&1)!=0)AllApply( --r,f);l>>=1;r>>=1;}l=l2;r=r2;}for(int i=1;i<=log;i++){if(((l>>i)<<i)!=l)Update(l>>i);if(((r>>i)<<i)!=r)Update((r-1)>>i);}}public int MaxRight(int l,Predicate<TValue>g){if(l==Length)return Length;l+=size;for(int i=log;i>=1;i--)Push(l>>i);TValue sm=op.Identity;do{while(l%2==0)l>>=1;if(!g(op.Operate(sm,d[l]))){while(l<size){Push(l);l=(2*l);if(g(op.Operate(sm,d[l]))){sm=op.Operate(sm,d[l]);l++;}}return l-size;}sm=op.Operate(sm,d[l]);l++;}while((l&-l)!=l);return Length;}public int MinLeft(int r,Predicate<TValue>g){if(r==0)return 0;r+=size;for(int i=log;i>=1;i--)Push((r-1)>>i);TValue sm=op.Identity;do{r--;while(r>1&&(r%2)!=0)r>>=1;if(!g(op.Operate(d[r],sm))){while(r<size){Push(r);r=(2*r+1);if(g(op.Operate(d[r],sm))){sm=op.Operate(d[r],sm);r--;}}return r+1-size;}sm=op.Operate(d[r],sm);}while((r&-r)!=r);return 0;}private struct DebugItem{public DebugItem(int l,int r,TValue value,F lazy){if(r-l==1)key=$"[{l}]";else key=$"[{l}-{r})";this.value=value;this.lazy=lazy;}private readonly string key;private readonly TValue value;private readonly F lazy;}private class DebugView{private readonly LazySegtree<TValue,F,TOp>segtree;public DebugView(LazySegtree<TValue,F,TOp>segtree){this.segtree=segtree;}public DebugItem[]Items{get{var items=new List<DebugItem>(segtree.Length);for(int len=segtree.size;len>0;len>>=1){int unit=segtree.size/len;for(int i=0;i<len;i++){int l=i*unit;int r=Math.Min(l+unit,segtree.Length);if(l<segtree.Length){int dataIndex=i+len;if((uint)dataIndex<segtree.lz.Length)items.Add(new DebugItem(l,r,segtree.d[dataIndex],segtree.lz[dataIndex]));else items.Add(new DebugItem(l,r,segtree.d[dataIndex],op.FIdentity));}}}return items.ToArray();}}}}}
namespace AtCoder{public class SetDictionary<TKey,TValue>:SetDictionary<TKey,TValue,DefaultComparerStruct<TKey>>where TKey:IComparable<TKey>{public SetDictionary(bool isMulti=false):base(new DefaultComparerStruct<TKey>(),isMulti){}public SetDictionary(IDictionary<TKey,TValue>dict,bool isMulti=false):base(dict,new DefaultComparerStruct<TKey>(),isMulti){}}public class SetDictionary<TKey,TValue,TOp>:IDictionary<TKey,TValue>,IReadOnlyDictionary<TKey,TValue>where TOp:struct,IComparer<TKey>{internal const string LISENCE=@"
Original is SortedSet<T>

Copyright (c) .NET Foundation and Contributors
Released under the MIT license
https://github.com/dotnet/runtime/blob/master/LICENSE.TXT
";public SetDictionary(bool isMulti=false):this(default(TOp),isMulti){}public SetDictionary(IDictionary<TKey,TValue>dict,bool isMulti=false):this(dict,default(TOp),isMulti){}public SetDictionary(TOp comparer,bool isMulti=false){this.comparer=comparer;IsMulti=isMulti;}public SetDictionary(IDictionary<TKey,TValue>dict,TOp comparer,bool isMulti=false){this.comparer=comparer;var arr=InitArray(dict);root=ConstructRootFromSortedArray(arr,0,arr.Length-1,null);IsMulti=isMulti;}public bool IsMulti{get;}public KeyValuePair<TKey,TValue>Min{get{if(root==null)return default;var cur=root;while(cur.Left!=null){cur=cur.Left;}return cur.Pair;}}public KeyValuePair<TKey,TValue>Max{get{if(root==null)return default;var cur=root;while(cur.Right!=null){cur=cur.Right;}return cur.Pair;}}public Node FindNode(TKey key){Node current=root;while(current!=null){int order=comparer.Compare(key,current.Key);if(order==0)return current;current=order<0?current.Left:current.Right;}return null;}public int Index(Node node){var ret=NodeSize(node.Left);Node prev=node;node=node.Parent;while(prev!=root){if(node.Left!=prev){ret+=NodeSize(node.Left)+1;}prev=node;node=node.Parent;}return ret;}public Node FindByIndex(int index){var current=root;var currentIndex=current.Size-NodeSize(current.Right)-1;while(currentIndex!=index){if(currentIndex>index){current=current.Left;if(current==null)break;currentIndex-=NodeSize(current.Right)+1;}else{current=current.Right;if(current==null)break;currentIndex+=NodeSize(current.Left)+1;}}return current;}public(Node node,int index)BinarySearch(TKey key,bool isLowerBound){Node right=null;Node current=root;if(current==null)return(null,-1);int ri=Count;int ci=NodeSize(current.Left);while(true){var order=comparer.Compare(key,current.Key);if(order<0||(isLowerBound&&order==0)){right=current;ri=ci;current=current.Left;if(current!=null)ci-=NodeSize(current.Right)+1;else break;}else{current=current.Right;if(current!=null)ci+=NodeSize(current.Left)+1;else break;}}return(right,ri);}public Node FindNodeLowerBound(TKey key)=>BinarySearch(key,true).node;public Node FindNodeUpperBound(TKey key)=>BinarySearch(key,false).node;public KeyValuePair<TKey,TValue>LowerBoundItem(TKey key)=>BinarySearch(key,true).node.Pair;public KeyValuePair<TKey,TValue>UpperBoundItem(TKey key)=>BinarySearch(key,false).node.Pair;public int LowerBoundIndex(TKey key)=>BinarySearch(key,true).index;public int UpperBoundIndex(TKey key)=>BinarySearch(key,false).index;public IEnumerable<KeyValuePair<TKey,TValue>>Reversed(){var e=new ValueEnumerator(this,true,null);while(e.MoveNext())yield return e.Current;}public IEnumerable<KeyValuePair<TKey,TValue>>EnumerateItem(Node from,bool reverse=false){if(from==null)yield break;var e=new ValueEnumerator(this,reverse,from);while(e.MoveNext())yield return e.Current;}public IEnumerable<Node>EnumerateNode(Node from,bool reverse=false){if(from==null)yield break;var e=new Enumerator(this,reverse,from);while(e.MoveNext())yield return e.Current;}protected KeyValuePair<TKey,TValue>[]InitArray(IEnumerable<KeyValuePair<TKey,TValue>>collection){var comparer=Comparer<KeyValuePair<TKey,TValue>>.Create((a,b)=>this.comparer.Compare(a.Key,b.Key));KeyValuePair<TKey,TValue>[]arr;if(IsMulti){arr=collection.ToArray();Array.Sort(arr,comparer);}else{var list=new List<KeyValuePair<TKey,TValue>>(collection);list.Sort(comparer);for(int i=list.Count-1;i>0;i--)if(this.comparer.Compare(list[i-1].Key,list[i].Key)==0)list.RemoveAt(i);arr=list.ToArray();}return arr;}public int Count=>NodeSize(root);protected static int NodeSize(Node node)=>node==null?0:node.Size;protected readonly TOp comparer;bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly=>false;ICollection<TKey>IDictionary<TKey,TValue>.Keys=>throw new NotSupportedException();ICollection<TValue>IDictionary<TKey,TValue>.Values=>throw new NotSupportedException();IEnumerable<TKey>IReadOnlyDictionary<TKey,TValue>.Keys=>throw new NotSupportedException();IEnumerable<TValue>IReadOnlyDictionary<TKey,TValue>.Values=>throw new NotSupportedException();public TValue this[TKey key]{get=>throw new NotSupportedException();set=>throw new NotSupportedException();}Node root;static Node ConstructRootFromSortedArray(KeyValuePair<TKey,TValue>[]arr,int startIndex,int endIndex,Node redNode){int size=endIndex-startIndex+1;Node root;switch(size){case 0:return null;case 1:root=new Node(arr[startIndex],false);if(redNode!=null){root.Left=redNode;}break;case 2:root=new Node(arr[startIndex],false){Right=new Node(arr[endIndex],true)};if(redNode!=null){root.Left=redNode;}break;case 3:root=new Node(arr[startIndex+1],false){Left=new Node(arr[startIndex],false),Right=new Node(arr[endIndex],false)};if(redNode!=null){root.Left.Left=redNode;}break;default:int midpt=((startIndex+endIndex)/2);root=new Node(arr[midpt],false){Left=ConstructRootFromSortedArray(arr,startIndex,midpt-1,redNode),Right=size%2==0?ConstructRootFromSortedArray(arr,midpt+2,endIndex,new Node(arr[midpt+1],true)):ConstructRootFromSortedArray(arr,midpt+1,endIndex,null)};break;}return root;}void IDictionary<TKey,TValue>.Add(TKey key,TValue value)=>Add(key,value);void ICollection<KeyValuePair<TKey,TValue>>.Add(KeyValuePair<TKey,TValue>pair)=>Add(pair.Key,pair.Value);public bool Add(TKey key,TValue value){if(root==null){root=new Node(key,value,false);return true;}Node current=root;Node parent=null;Node grandParent=null;Node greatGrandParent=null;int order=0;while(current!=null){order=comparer.Compare(key,current.Key);if(order==0&&!IsMulti){current.Key=key;root.IsRed=false;return false;}if(Is4Node(current)){Split4Node(current);if(IsNonNullRed(parent)==true){InsertionBalance(current,ref parent,grandParent,greatGrandParent);}}greatGrandParent=grandParent;grandParent=parent;parent=current;current=(order<0)?current.Left:current.Right;}Node node=new Node(key,value,true);if(order>=0)parent.Right=node;else parent.Left=node;if(parent.IsRed)InsertionBalance(node,ref parent,grandParent,greatGrandParent);root.IsRed=false;return true;}public void Remove(Node node){Node match=node;Node parentOfMatch=node.Parent;Node current=node;Node parent=parentOfMatch;Node grandParent=parentOfMatch?.Parent;while(current!=null){if(Is2Node(current)){if(parent==null){current.IsRed=true;}else{Node sibling=GetSibling(current,parent);if(sibling.IsRed){if(parent.Right==sibling)RotateLeft(parent);else RotateRight(parent);parent.IsRed=true;sibling.IsRed=false;ReplaceChildOrRoot(grandParent,parent,sibling);grandParent=sibling;if(parent==match)parentOfMatch=sibling;sibling=(parent.Left==current)?parent.Right:parent.Left;}if(Is2Node(sibling)){Merge2Nodes(parent);}else{TreeRotation rotation=GetRotation(parent,current,sibling);Node newGrandParent=Rotate(parent,rotation);newGrandParent.IsRed=parent.IsRed;parent.IsRed=false;current.IsRed=true;ReplaceChildOrRoot(grandParent,parent,newGrandParent);if(parent==match){parentOfMatch=newGrandParent;}}}}grandParent=parent;parent=current;current=current==match?current.Right:current.Left;}if(match!=null){ReplaceNode(match,parentOfMatch,parent,grandParent);}if(root!=null){root.IsRed=false;}}public bool Remove(TKey key){if(root==null)return false;Node current=root;Node parent=null;Node grandParent=null;Node match=null;Node parentOfMatch=null;bool foundMatch=false;while(current!=null){if(Is2Node(current)){if(parent==null){current.IsRed=true;}else{Node sibling=GetSibling(current,parent);if(sibling.IsRed){if(parent.Right==sibling)RotateLeft(parent);else RotateRight(parent);parent.IsRed=true;sibling.IsRed=false;ReplaceChildOrRoot(grandParent,parent,sibling);grandParent=sibling;if(parent==match)parentOfMatch=sibling;sibling=(parent.Left==current)?parent.Right:parent.Left;}if(Is2Node(sibling)){Merge2Nodes(parent);}else{TreeRotation rotation=GetRotation(parent,current,sibling);Node newGrandParent=Rotate(parent,rotation);newGrandParent.IsRed=parent.IsRed;parent.IsRed=false;current.IsRed=true;ReplaceChildOrRoot(grandParent,parent,newGrandParent);if(parent==match){parentOfMatch=newGrandParent;}}}}int order=foundMatch?-1:comparer.Compare(key,current.Key);if(order==0){foundMatch=true;match=current;parentOfMatch=parent;}grandParent=parent;parent=current;current=order<0?current.Left:current.Right;}if(match!=null){ReplaceNode(match,parentOfMatch,parent,grandParent);}if(root!=null){root.IsRed=false;}return foundMatch;}bool ICollection<KeyValuePair<TKey,TValue>>.Remove(KeyValuePair<TKey,TValue>pair){if(root==null)return false;Node current=root;Node parent=null;Node grandParent=null;Node match=null;Node parentOfMatch=null;bool foundMatch=false;while(current!=null){if(Is2Node(current)){if(parent==null){current.IsRed=true;}else{Node sibling=GetSibling(current,parent);if(sibling.IsRed){if(parent.Right==sibling)RotateLeft(parent);else RotateRight(parent);parent.IsRed=true;sibling.IsRed=false;ReplaceChildOrRoot(grandParent,parent,sibling);grandParent=sibling;if(parent==match)parentOfMatch=sibling;sibling=(parent.Left==current)?parent.Right:parent.Left;}if(Is2Node(sibling)){Merge2Nodes(parent);}else{TreeRotation rotation=GetRotation(parent,current,sibling);Node newGrandParent=Rotate(parent,rotation);newGrandParent.IsRed=parent.IsRed;parent.IsRed=false;current.IsRed=true;ReplaceChildOrRoot(grandParent,parent,newGrandParent);if(parent==match){parentOfMatch=newGrandParent;}}}}int order=foundMatch?-1:comparer.Compare(pair.Key,current.Key);if(order==0&&EqualityComparer<TValue>.Default.Equals(pair.Value,current.Value)){foundMatch=true;match=current;parentOfMatch=parent;}grandParent=parent;parent=current;current=order<0?current.Left:current.Right;}if(match!=null){ReplaceNode(match,parentOfMatch,parent,grandParent);}if(root!=null){root.IsRed=false;}return foundMatch;}public void Clear(){root=null;}public bool ContainsKey(TKey key)=>FindNode(key)!=null;bool ICollection<KeyValuePair<TKey,TValue>>.Contains(KeyValuePair<TKey,TValue>pair){var node=FindNodeLowerBound(pair.Key);if(node==null)return false;var e=new Enumerator(this,false,node);while(e.MoveNext()){if(comparer.Compare(pair.Key,e.Current.Key)!=0)break;if(EqualityComparer<TValue>.Default.Equals(pair.Value,e.Current.Value))return true;}return false;}public void CopyTo(KeyValuePair<TKey,TValue>[]array,int arrayIndex){foreach(var item in this)array[arrayIndex++]=item;}public bool TryGetValue(TKey key,out TValue value){var node=FindNode(key);if(node==null){value=default;return false;}value=node.Value;return true;}public ValueEnumerator GetEnumerator()=>new ValueEnumerator(this);IEnumerator<KeyValuePair<TKey,TValue>>IEnumerable<KeyValuePair<TKey,TValue>>.GetEnumerator()=>new ValueEnumerator(this);IEnumerator IEnumerable.GetEnumerator()=>new ValueEnumerator(this);static bool Is2Node(Node node)=>IsNonNullBlack(node)&&IsNullOrBlack(node.Left)&&IsNullOrBlack(node.Right);static bool Is4Node(Node node)=>IsNonNullRed(node.Left)&&IsNonNullRed(node.Right);static bool IsNonNullRed(Node node)=>node!=null&&node.IsRed;static bool IsNonNullBlack(Node node)=>node!=null&&!node.IsRed;static bool IsNullOrBlack(Node node)=>node==null||!node.IsRed;void ReplaceNode(Node match,Node parentOfMatch,Node succesor,Node parentOfSuccesor){if(succesor==match){succesor=match.Left;}else{if(succesor.Right!=null){succesor.Right.IsRed=false;}if(parentOfSuccesor!=match){parentOfSuccesor.Left=succesor.Right;succesor.Right=match.Right;}succesor.Left=match.Left;}if(succesor!=null){succesor.IsRed=match.IsRed;}ReplaceChildOrRoot(parentOfMatch,match,succesor);}static void Merge2Nodes(Node parent){parent.IsRed=false;parent.Left.IsRed=true;parent.Right.IsRed=true;}static void Split4Node(Node node){node.IsRed=true;node.Left.IsRed=false;node.Right.IsRed=false;}static Node GetSibling(Node node,Node parent){return parent.Left==node?parent.Right:parent.Left;}void InsertionBalance(Node current,ref Node parent,Node grandParent,Node greatGrandParent){bool parentIsOnRight=grandParent.Right==parent;bool currentIsOnRight=parent.Right==current;Node newChildOfGreatGrandParent;if(parentIsOnRight==currentIsOnRight){newChildOfGreatGrandParent=currentIsOnRight?RotateLeft(grandParent):RotateRight(grandParent);}else{newChildOfGreatGrandParent=currentIsOnRight?RotateLeftRight(grandParent):RotateRightLeft(grandParent);parent=greatGrandParent;}grandParent.IsRed=true;newChildOfGreatGrandParent.IsRed=false;ReplaceChildOrRoot(greatGrandParent,grandParent,newChildOfGreatGrandParent);}static Node Rotate(Node node,TreeRotation rotation){switch(rotation){case TreeRotation.Right:node.Left.Left.IsRed=false;return RotateRight(node);case TreeRotation.Left:node.Right.Right.IsRed=false;return RotateLeft(node);case TreeRotation.RightLeft:return RotateRightLeft(node);case TreeRotation.LeftRight:return RotateLeftRight(node);default:throw new InvalidOperationException();}}static Node RotateLeft(Node node){Node child=node.Right;node.Right=child.Left;child.Left=node;return child;}static Node RotateLeftRight(Node node){Node child=node.Left;Node grandChild=child.Right;node.Left=grandChild.Right;grandChild.Right=node;child.Right=grandChild.Left;grandChild.Left=child;return grandChild;}static Node RotateRight(Node node){Node child=node.Left;node.Left=child.Right;child.Right=node;return child;}static Node RotateRightLeft(Node node){Node child=node.Right;Node grandChild=child.Left;node.Right=grandChild.Left;grandChild.Left=node;child.Left=grandChild.Right;grandChild.Right=child;return grandChild;}void ReplaceChildOrRoot(Node parent,Node child,Node newChild){if(parent!=null){if(parent.Left==child){parent.Left=newChild;}else{parent.Right=newChild;}}else{root=newChild;}}static TreeRotation GetRotation(Node parent,Node current,Node sibling){if(IsNonNullRed(sibling.Left)){if(parent.Left==current){return TreeRotation.RightLeft;}return TreeRotation.Right;}else{if(parent.Left==current){return TreeRotation.Left;}return TreeRotation.LeftRight;}}public struct ValueEnumerator:IEnumerator<KeyValuePair<TKey,TValue>>{private Enumerator inner;internal ValueEnumerator(SetDictionary<TKey,TValue,TOp>set){inner=new Enumerator(set);}internal ValueEnumerator(SetDictionary<TKey,TValue,TOp>set,bool reverse,Node startNode){inner=new Enumerator(set,reverse,startNode);}public KeyValuePair<TKey,TValue>Current=>inner.Current switch{{}cur=>cur.Pair,_=>default,};object IEnumerator.Current=>Current;public void Dispose(){}public bool MoveNext()=>inner.MoveNext();public void Reset()=>throw new NotSupportedException();}public struct Enumerator:IEnumerator<Node>{readonly SetDictionary<TKey,TValue,TOp>tree;readonly Stack<Node>stack;Node current;readonly bool reverse;internal Enumerator(SetDictionary<TKey,TValue,TOp>set):this(set,false,null){}internal Enumerator(SetDictionary<TKey,TValue,TOp>set,bool reverse,Node startNode){tree=set;stack=new Stack<Node>(2*Log2(tree.Count+1));current=null;this.reverse=reverse;if(startNode==null)IntializeAll();else Intialize(startNode);}void IntializeAll(){var node=tree.root;while(node!=null){var next=reverse?node.Right:node.Left;stack.Push(node);node=next;}}void Intialize(Node startNode){if(startNode==null)throw new InvalidOperationException(nameof(startNode)+"is null");current=null;var node=startNode;var list=new List<Node>(Log2(tree.Count+1));var comparer=tree.comparer;if(reverse){while(node!=null){list.Add(node);var parent=node.Parent;if(parent==null||parent.Left==node){node=parent;break;}node=parent;}while(node!=null){var parent=node.Parent;if(parent==null||parent.Right==node){node=parent;break;}node=parent;}while(node!=null){if(comparer.Compare(startNode.Key,node.Key)>=0)list.Add(node);node=node.Parent;}}else{while(node!=null){list.Add(node);var parent=node.Parent;if(parent==null||parent.Right==node){node=parent;break;}node=parent;}while(node!=null){var parent=node.Parent;if(parent==null||parent.Left==node){node=parent;break;}node=parent;}while(node!=null){if(comparer.Compare(startNode.Key,node.Key)<=0)list.Add(node);node=node.Parent;}}list.Reverse();foreach(var n in list)stack.Push(n);}[MethodImpl(MethodImplOptions.AggressiveInlining)]static int Log2(int num)=>BitOperations.Log2((uint)num)+1;public Node Current=>current;public bool MoveNext(){if(stack.Count==0){current=null;return false;}current=stack.Pop();var node=reverse?current.Left:current.Right;while(node!=null){var next=reverse?node.Right:node.Left;stack.Push(node);node=next;}return true;}object IEnumerator.Current=>Current;public void Dispose(){}public void Reset()=>throw new NotSupportedException();}public class Node{public bool IsRed;public TKey Key;public TValue Value;public KeyValuePair<TKey,TValue>Pair=>KeyValuePair.Create(Key,Value);public Node Parent{get;private set;}Node _left;public Node Left{get{return _left;}set{_left=value;if(value!=null)value.Parent=this;for(var cur=this;cur!=null;cur=cur.Parent){if(!cur.UpdateSize())break;if(cur.Parent!=null&&cur.Parent.Left!=cur&&cur.Parent.Right!=cur){cur.Parent=null;break;}}}}Node _right;public Node Right{get{return _right;}set{_right=value;if(value!=null)value.Parent=this;for(var cur=this;cur!=null;cur=cur.Parent){if(!cur.UpdateSize())break;if(cur.Parent!=null&&cur.Parent.Left!=cur&&cur.Parent.Right!=cur){cur.Parent=null;break;}}}}public int Size{get;private set;}=1;public Node(KeyValuePair<TKey,TValue>pair,bool isRed){Key=pair.Key;Value=pair.Value;IsRed=isRed;}public Node(TKey key,TValue value,bool isRed){Key=key;Value=value;IsRed=isRed;}public bool UpdateSize(){var oldsize=Size;var size=1;if(Left!=null)size+=Left.Size;if(Right!=null)size+=Right.Size;Size=size;return oldsize!=size;}public override string ToString()=>$"Key = {Key}, Value = {Value}, Size = {Size}";}enum TreeRotation:byte{Left=1,Right=2,RightLeft=3,LeftRight=4,}private class DebugView{private readonly ICollection<KeyValuePair<TKey,TValue>>collection;public DebugView(SetDictionary<TKey,TValue,TOp>collection){this.collection=collection;}public KeyValuePair<TKey,TValue>[]Items=>collection.ToArray();}}}
namespace AtCoder{using static MethodImplOptions;public static class ArrayExtension{[MethodImpl(AggressiveInlining)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[MethodImpl(AggressiveInlining)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[MethodImpl(AggressiveInlining)]public static T[]Sort<T,U>(this T[]arr,Expression<Func<T,U>>selector)where U:IComparable<U> =>Sort(arr,ExComparer<T>.CreateExp(selector));[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[MethodImpl(AggressiveInlining)]public static ref T Get<T>(this T[]arr,int index){if(index<0)return ref arr[arr.Length+index];return ref arr[index];}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=1;if(__ManyTestCases())Q=cr;for(;Q>0;Q--){var res=Calc();if(res is double d)cw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)WriteBool(b);else if(res!=null)cw.WriteLine(res.ToString());}cw.Flush();}partial void WriteBool(bool b);object Calc(Program dum=null)=>dum;bool __ManyTestCases(Program dum=null)=>false;}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal void MoveNext(){if( ++pos>=len){len=input.Read(buffer,0,buffer.Length);if(len==0){buffer[0]=10;}pos=0;}}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;while(buffer[pos]<48){neg=buffer[pos]==45;MoveNext();}do{res=checked(res*10+(buffer[pos]^48));MoveNext();}while(48<=buffer[pos]);return neg?-res:res;}}public int Int0=>Int-1;public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;while(buffer[pos]<48){neg=buffer[pos]==45;MoveNext();}do{res=res*10+(buffer[pos]^48U);MoveNext();}while(48<=buffer[pos]);return neg?-res:res;}}public long Long0=>Long-1;public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;while(buffer[pos]<48)MoveNext();do{res=res*10+(buffer[pos]^48U);MoveNext();}while(48<=buffer[pos]);return res;}}public ulong ULong0=>ULong-1;public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();while(buffer[pos]<=32)MoveNext();do{sb.Add(buffer[pos]);MoveNext();}while(32<buffer[pos]);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();while(buffer[pos]<=32)MoveNext();do{sb.Append((char)buffer[pos]);MoveNext();}while(32<buffer[pos]);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();while(buffer[pos]<=32)MoveNext();do{sb.Add(buffer[pos]);MoveNext();}while(buffer[pos]!=10&&buffer[pos]!=13);return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{while(buffer[pos]<=32)MoveNext();char res=(char)buffer[pos];MoveNext();return res;}}public double Double=>double.Parse(Ascii);public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
namespace Kzrnm.Competitive.IO{public struct PropertyRepeatReader{internal readonly PropertyConsoleReader cr;internal readonly int count;internal PropertyRepeatReader(PropertyConsoleReader cr,int count){this.cr=cr;this.count=count;}public string[]Line{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Line;return arr;}}public string[]String{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.String;return arr;}}public string[]Ascii{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Ascii;return arr;}}public int[]Int{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int;return arr;}}public int[]Int0{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int0;return arr;}}public long[]Long{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long;return arr;}}public long[]Long0{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long0;return arr;}}public ulong[]ULong{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong;return arr;}}public ulong[]ULong0{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong0;return arr;}}public double[]Double{get{var arr=new double[count];for(var i=0;i<count;i++)arr[i]=cr.Double;return arr;}}public static implicit operator string[](PropertyRepeatReader rr)=>rr.Ascii;public static implicit operator int[](PropertyRepeatReader rr)=>rr.Int;public static implicit operator long[](PropertyRepeatReader rr)=>rr.Long;public static implicit operator ulong[](PropertyRepeatReader rr)=>rr.ULong;public static implicit operator double[](PropertyRepeatReader rr)=>rr.Double;}public static class PRepeatEx{public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new PropertyRepeatReader(cr,count);}}
namespace Kzrnm.Competitive.IO{public static class PropertyRepeatReaderSelectArray{public static(T1[],T2[])SelectArray<T1,T2>(this PropertyRepeatReader r,Func<PropertyConsoleReader,(T1,T2)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i])=factory(r.cr);return(arr1,arr2);}public static(T1[],T2[])SelectArray<T1,T2>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,(T1,T2)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i])=factory(r.cr,i);return(arr1,arr2);}public static(T1[],T2[],T3[])SelectArray<T1,T2,T3>(this PropertyRepeatReader r,Func<PropertyConsoleReader,(T1,T2,T3)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];var arr3=new T3[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i],arr3[i])=factory(r.cr);return(arr1,arr2,arr3);}public static(T1[],T2[],T3[])SelectArray<T1,T2,T3>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,(T1,T2,T3)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];var arr3=new T3[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i],arr3[i])=factory(r.cr,i);return(arr1,arr2,arr3);}public static(T1[],T2[],T3[],T4[])SelectArray<T1,T2,T3,T4>(this PropertyRepeatReader r,Func<PropertyConsoleReader,(T1,T2,T3,T4)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];var arr3=new T3[r.count];var arr4=new T4[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i],arr3[i],arr4[i])=factory(r.cr);return(arr1,arr2,arr3,arr4);}public static(T1[],T2[],T3[],T4[])SelectArray<T1,T2,T3,T4>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,(T1,T2,T3,T4)>factory){var arr1=new T1[r.count];var arr2=new T2[r.count];var arr3=new T3[r.count];var arr4=new T4[r.count];for(var i=0;i<r.count;i++)(arr1[i],arr2[i],arr3[i],arr4[i])=factory(r.cr,i);return(arr1,arr2,arr3,arr4);}}}
namespace AtCoder.Internal{public static class InternalBit{[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return(int)Bmi1.ExtractLowestSetBit((uint)n);}return n&-n;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static int BSF(uint n){return BitOperations.TrailingZeroCount(n);}public static int CeilPow2(int n){var un=(uint)n;if(un<=1)return 0;return BitOperations.Log2(un-1)+1;}}}
namespace AtCoder{public struct DefaultComparerStruct<T>:IComparer<T>where T:IComparable<T>{public static DefaultComparerStruct<T>Default{get;}=default;public int Compare(T x,T y)=>x.CompareTo(y);public override bool Equals(object obj)=>obj is ReverseComparerStruct<T>;public override int GetHashCode()=>GetType().GetHashCode();}}
namespace AtCoder{public static class ExComparer<T>{class ExpressionComparer<K>:IComparer<T>where K:IComparable<K>{private class ParameterReplaceVisitor:ExpressionVisitor{private readonly ParameterExpression from;private readonly ParameterExpression to;public ParameterReplaceVisitor(ParameterExpression from,ParameterExpression to){this.from=from;this.to=to;}protected override Expression VisitParameter(ParameterExpression node)=>node==from?to:base.VisitParameter(node);}readonly Comparison<T>func;public ExpressionComparer(Expression<Func<T,K>>expression){var paramA=expression.Parameters[0];var paramB=Expression.Parameter(typeof(T));var f2=(Expression<Func<T,K>>)new ParameterReplaceVisitor(expression.Parameters[0],paramB).Visit(expression);var compExp=Expression.Lambda<Comparison<T>>(Expression.Call(expression.Body,typeof(K).GetMethod(nameof(IComparable<K>.CompareTo),new[]{typeof(K)}),f2.Body),paramA,paramB);this.func=compExp.Compile();}public int Compare(T x,T y)=>func(x,y);public override bool Equals(object obj)=>obj is ExpressionComparer<K>c&&this.func==c.func;public override int GetHashCode()=>func.GetHashCode();}public static IComparer<T>CreateExp<K>(Expression<Func<T,K>>expression)where K:IComparable<K> =>new ExpressionComparer<K>(expression);}}
namespace AtCoder{public struct ReverseComparerStruct<T>:IComparer<T>where T:IComparable<T>{public static ReverseComparerStruct<T>Default{get;}=default;public int Compare(T x,T y)=>y.CompareTo(x);public override bool Equals(object obj)=>obj is ReverseComparerStruct<T>;public override int GetHashCode()=>GetType().GetHashCode();}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander

Submission Info

Judge Result