#1034378 (C#) No.9008 空白区切りで与えられる数値データの合計値を求める（テスト用）

• 問題: No.9008 空白区切りで与えられる数値データの合計値を求める（テスト用）
• ユーザー: ayutake
• 提出日時: 2025-01-07 00:58:14
• 言語: C# (.NET 8.0.404)
• 結果: AC
• 実行時間: 214 ms / 2,000 ms
• コード長: 27,078 bytes
• コンパイル時間: 7,523 ms
• コンパイル使用メモリ: 172,404 KB
• 実行使用メモリ: 196,564 KB
• 最終ジャッジ日時: 2025-01-07 00:58:27
• 合計ジャッジ時間: 10,613 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	53 ms; 30,820 KB
testcase_01	AC	51 ms; 30,784 KB
testcase_02	AC	53 ms; 30,688 KB
testcase_03	AC	54 ms; 30,936 KB
testcase_04	AC	54 ms; 30,676 KB
testcase_05	AC	57 ms; 30,988 KB
testcase_06	AC	56 ms; 31,256 KB
testcase_07	AC	66 ms; 35,024 KB
testcase_08	AC	78 ms; 45,236 KB
testcase_09	AC	80 ms; 51,360 KB
testcase_10	AC	170 ms; 91,992 KB
testcase_11	AC	174 ms; 92,132 KB
testcase_12	AC	173 ms; 92,888 KB
testcase_13	AC	214 ms; 93,308 KB
testcase_14	AC	196 ms; 94,396 KB
testcase_15	AC	193 ms; 95,024 KB
testcase_16	AC	206 ms; 97,480 KB
testcase_17	AC	57 ms; 30,932 KB
testcase_18	AC	56 ms; 196,564 KB

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (99 ミリ秒)。
/home/judge/data/code/Main.cs(234,26): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(903,47): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(1023,59): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/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/

ソースコード

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.IO.Compression;
using System.Dynamic;
using System.Runtime.CompilerServices;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using ModInt = ModInt<ModInt998244353>;
using System.Diagnostics;

class Runner
{
    public void Run()
    {
        var N = IO.Read<int>();
        var A = IO.ReadArray<long>(N);

        IO.Write(A.Sum());
    }
}

class Program
{
    static void Main()
    {
        try
        {
            var miiko = new Runner();
            do
            {
                miiko.Run();
                IO.Flush();
            }
            while(IO.HasNextInput);
        }
        catch
        {
            IO.Flush();
            throw;
        }
    }
}

static class IO
{
    private static readonly Queue<string> que;
    
    static IO()
    {
        que = new Queue<string>();

        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
    }

    public static bool HasNextInput => que.Count > 0 || TryReadNextLine();

    public static string Yes { get; set; } = "Yes";
    public static string No { get; set; } = "No";
    
    public static void Flush() => Console.Out.Flush();

    public static T Read<T>()
    {
        if(que.Count <= 0 && !TryReadNextLine()) throw new InvalidOperationException("Input is missing.");

        Func<string,T> converter =
        (
            typeof(T)==typeof(int)    ? (Func<string,T>)(object)(new Func<string,int>(int.Parse)) :
            typeof(T)==typeof(long)   ? (Func<string,T>)(object)(new Func<string,long>(long.Parse)) :
            typeof(T)==typeof(double) ? (Func<string,T>)(object)(new Func<string,double>(double.Parse)) :
            typeof(T)==typeof(string) ? (Func<string,T>)(object)(new Func<string,string>(x => x)) :
            typeof(T)==typeof(char)   ? (Func<string,T>)(object)(new Func<string,char>(x => x[0])) :
            null
        ) ?? throw new InvalidOperationException($"{nameof(T)} is not supported.");

        return converter.Invoke(que.Dequeue());
    }
    public static (T1,T2) Read<T1,T2>() => (Read<T1>(), Read<T2>());
    public static (T1,T2,T3) Read<T1,T2,T3>() => (Read<T1>(), Read<T2>(), Read<T3>());
    public static (T1,T2,T3,T4) Read<T1,T2,T3,T4>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>());
    public static (T1,T2,T3,T4,T5) Read<T1,T2,T3,T4,T5>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>(), Read<T5>());
    public static (T1,T2,T3,T4,T5,T6) Read<T1,T2,T3,T4,T5,T6>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>(), Read<T5>(), Read<T6>());

    public static T1[] ReadArray<T1>(int len)
    {
        var A1 = new T1[len];
        for(int i=0; i<len; i++) A1[i] = Read<T1>();
        return A1;
    }
    public static (T1[],T2[]) ReadArray<T1,T2>(int len)
    {
        var (A1,A2) = (new T1[len], new T2[len]);
        for(int i=0; i<len; i++) (A1[i],A2[i]) = Read<T1,T2>();
        return (A1,A2);
    }
    public static (T1[],T2[],T3[]) ReadArray<T1,T2,T3>(int len)
    {
        var (A1,A2,A3) = (new T1[len], new T2[len], new T3[len]);
        for(int i=0; i<len; i++) (A1[i],A2[i],A3[i]) = Read<T1,T2,T3>();
        return (A1,A2,A3);
    }
    public static (T1[],T2[],T3[],T4[]) ReadArray<T1,T2,T3,T4>(int len)
    {
        var (A1,A2,A3,A4) = (new T1[len], new T2[len], new T3[len], new T4[len]);
        for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i]) = Read<T1,T2,T3,T4>();
        return (A1,A2,A3,A4);
    }
    public static (T1[],T2[],T3[],T4[],T5[]) ReadArray<T1,T2,T3,T4,T5>(int len)
    {
        var (A1,A2,A3,A4,A5) = (new T1[len], new T2[len], new T3[len], new T4[len], new T5[len]);
        for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i],A5[i]) = Read<T1,T2,T3,T4,T5>();
        return (A1,A2,A3,A4,A5);
    }
    public static (T1[],T2[],T3[],T4[],T5[],T6[]) ReadArray<T1,T2,T3,T4,T5,T6>(int len)
    {
        var (A1,A2,A3,A4,A5,A6) = (new T1[len], new T2[len], new T3[len], new T4[len], new T5[len], new T6[len]);
        for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i],A5[i],A6[i]) = Read<T1,T2,T3,T4,T5,T6>();
        return (A1,A2,A3,A4,A5,A6);
    }

    public static T[,] ReadMatrix<T>(int row, int col)
    {
        var A = new T[row,col];
        for(int r=0; r<row; r++) for(int c=0; c<col; c++) A[r,c] = Read<T>();
        return A;
    }

    public static HashSet<int>[] ReadGraph(int N, int M, bool isDirected = false)
    {
        var G = Enumerable.Repeat(0,N).Select(x=>new HashSet<int>()).ToArray();
        while(M-->0)
        {
            var (u,v) = IO.Read<int,int>();
            u--; v--;
            G[u].Add(v);
            if(!isDirected) G[v].Add(u);
        }
        return G;
    }

    public static Dictionary<int,long>[] ReadWeightedGraph(int N, int M)
    {
        var G = Enumerable.Repeat(0,N).Select(x=>new Dictionary<int,long>()).ToArray();
        while(M-->0)
        {
            var (u,v,w) = IO.Read<int,int,long>();
            u--; v--;
            G[u].TryAdd(v,long.MaxValue);
            G[u][v] = Math.Min(G[u][v],w);
        }
        return G;
    }

    public static void Write<T>(T val) => Console.WriteLine(val.ToStringOrYesNo());
    public static void Write<T1,T2>(T1 v1, T2 v2)
    {
        Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2);
    }
    public static void Write<T1,T2,T3>(T1 v1, T2 v2, T3 v3)
    {
        Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3);
    }
    public static void Write<T1,T2,T3,T4>(T1 v1, T2 v2, T3 v3, T4 v4)
    {
        Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4);
    }
    public static void Write<T1,T2,T3,T4,T5>(T1 v1, T2 v2, T3 v3, T4 v4, T5 v5)
    {
        Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4, v5);
    }
    public static void Write<T1,T2,T3,T4,T5,T6>(T1 v1, T2 v2, T3 v3, T4 v4, T5 v5, T6 v6)
    {
        Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4, v5, v6);
    }

    public static void WriteArray<T>(IEnumerable<T> vals, bool isMultiLine = false)
    {
        if(!vals.Any())
        {
            Console.WriteLine();
            return;
        }

        Console.Write(vals.First().ToStringOrYesNo());
        foreach(var val in vals.Skip(1))
        {
            if(isMultiLine)
            {
                Console.WriteLine();
            }
            else
            {
                Console.Write(' ');
            }
            Console.Write(val.ToStringOrYesNo());
        }
        Console.WriteLine();
    }

    public static void WriteMatrix<T>(T[,] matrix)
    {
        var row = matrix.GetLength(0);
        var col = matrix.GetLength(1);
        for(int r=0; r<row; r++)
        {
            Console.Write(matrix[r,0].ToStringOrYesNo());
            for(int c=1; c<col; c++)
            {
                Console.Write(' ');
                Console.Write(matrix[r,c].ToStringOrYesNo());
            }
            Console.WriteLine();
        }
    }

    private static bool TryReadNextLine()
    {
        var line = Console.ReadLine();
        if(line == null) return false;

        foreach(var x in line.Split(' '))
        {
            if(!string.IsNullOrEmpty(x)) que.Enqueue(x);
        }

        return que.Count > 0;
    }

    private static string? ToStringOrYesNo<T>(this T val)
    {
        return typeof(T) == typeof(bool) ? Convert.ToBoolean(val) ? Yes : No : val?.ToString();
    }
}

struct PrimeFactor
{
    public long Prime { get; set; }
    public int Exponent { get; set; }
    public PrimeFactor(long p, int e)
    {
        Prime = p;
        Exponent = e;
    }
    public override readonly string ToString()
    {
        return $"[{Prime},{Exponent}]";
    }
}

static class MathEx
{
    public static long Pow(long x, long n, long mod = -1)
    {
        if(mod > 0) x %= mod;
        if(x == 0) return n==0 ? mod==1 ? 0 : 1 : 0;
        
        long ret = 1;
        while (n > 0)
        {
            if (n%2 == 1) 
            {
                ret *= x;
                if(mod > 0) ret %= mod;
            }
            n = n / 2;
            if(n == 0) break;
            x *= x;
            if(mod > 0) x %= mod;
        }
        return ret;
    }
    
    public static long Pow(long x, int n, long mod = -1) => Pow(x, (long)n, mod);

    public static long ModInv(long x, long mod)
    {
        long y = mod;
        long u = 1;
        long v = 0;

        while(y>0)
        {
            var t = x / y;

            x -= t * y;
            (x,y) = (y,x);

            u -= t * v;
            (u,v) = (v,u);
        }

        u %= mod;
        if(u<0) u += mod;

        return u;
    }
    
    public static long Gcd(long m, long n)
    {
        var M = Math.Max(m,n);
        var N = Math.Min(m,n);
        while(true)
        {
            var mod = M%N;
            if(mod==0) return N;
            M = N;
            N = mod;
        }
    }
    
    public static long Lcm(long m, long n) => m / Gcd(m,n) * n;
    
    public static string Convert10toStr2(long n)
    {
        var s = new StringBuilder();
        do
        {
            s.Insert(0, n % 2);
            n = n / 2;
        }
        while(n > 0);
        
        return s.ToString();
    }
    
    public static long ConvertStr2to10(string s)
    {
        int len = s.Length;
        long ret = 0;
        for(int i=0; i<len; i++)
        {
            ret += int.Parse(s[len-i-1].ToString()) * Pow(2, i);
        }
        return ret;
    }
    
    public static IEnumerable<List<T>> NextPermutation<T>(IEnumerable<T> v) where T : IComparable
    {
        var list = v.ToList();
        int len = list.Count;
        yield return list;
        
        while(true)
        {
            int l = len-2;
            while(l>=0 && list[l].CompareTo(list[l+1])>=0) l--;
            if(l<0) break;
            
            int r = len-1;
            while(list[l].CompareTo(list[r])>0) r--;
            if(list[l].CompareTo(list[r])>=0) break;
            
            var tmp = list[l];
            list[l] = list[r];
            list[r] = tmp;
            
            list.Reverse(l+1,len-l-1);
            yield return list;
        }
    }
    
    public static bool IsCross (
        long ax, long ay, long bx, long by,
        long cx, long cy, long dx, long dy
    ) {
        bool crs = true;
        crs &= ((bx-ax)*(cy-ay)-(cx-ax)*(by-ay)) * ((bx-ax)*(dy-ay)-(dx-ax)*(by-ay)) < 0;
        crs &= ((dx-cx)*(ay-cy)-(ax-cx)*(dy-cy)) * ((dx-cx)*(by-cy)-(bx-cx)*(dy-cy)) < 0;
        return crs;
    }
    
    public static long[,] MatrixProduct(long[,] a, long[,] b, long mod = -1)
    {
        var ha = a.GetLength(0);
        var wa = a.GetLength(1);
        var hb = b.GetLength(0);
        var wb = b.GetLength(1);
        if(wa!=hb) throw new ArgumentException();
        
        var c = new long[ha,wb];
        for(int i=0; i<ha; i++) for(int j=0; j<wb; j++) for(int k=0; k<wa; k++)
        {
            if(mod>0)
            {
                a[i,k] %= mod;
                b[k,j] %= mod;
            }
            c[i,j] += a[i,k] * b[k,j];
            if(mod>0) c[i,j] %= mod;
        }
        return c;
    }
    
    public static long[,] MatrixPow(long[,] a, long k, long mod = -1)
    {
        var n = a.GetLength(0);
        if(n != a.GetLength(1)) throw new ArgumentException();
        
        if(mod > 0) for(int i=0; i<n; i++) for(int j=0; j<n; j++) a[i,j] %= mod;
        
        var ret = new long[n,n];
        for(int i=0; i<n; i++) ret[i,i] = 1;
        while (k > 0)
        {
            if (k%2 == 1) 
            {
                ret = MatrixProduct(ret,a,mod);
            }
            k /= 2;
            if(k == 0) break;
            a = MatrixProduct(a,a,mod);
        }
        return ret;
    }
    
    public static long[,] MatrixPow(long[,] a, int k, long mod = -1) => MatrixPow(a,(long)k,mod);

    public static bool IsPrime(long n)
    {
        if(n<2) return false;

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

    public static IEnumerable<PrimeFactor> PrimeFactorization(long n)
    {
        if(n<2) yield break;

        for(long i=2; i*i<=n; i++)
        {
            var e = 0;
            while(n%i==0)
            {
                n /= i;
                e++;
            }
            if(e>0) yield return new PrimeFactor(i,e);
        }
        if(n>1) yield return new PrimeFactor(n,1);
    }
}

static class Ex
{
    public static string ToReverseString(this string s) => new string(s.ToString().Reverse().ToArray());
    
    public static T[] Row<T>(this T[,] array, int row)
    {
        int len = array.GetLength(1);
        var ret = new T[len];
        for(int c=0; c<len; c++)
        {
            ret[c] = array[row,c];
        }
        return ret;
    }
    
    public static T[] Column<T>(this T[,] array, int column)
    {
        int len = array.GetLength(0);
        var ret = new T[len];
        for(int r=0; r<len; r++)
        {
            ret[r] = array[r,column];
        }
        return ret;
    }
    
    public static int MgrBinarySearch(int ok, int ng, Func<int,bool> predicate)
        => MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>Math.Abs(x-y)>1,predicate);

    public static long MgrBinarySearch(long ok, long ng, Func<long,bool> predicate)
        => MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>Math.Abs(x-y)>1,predicate);

    public static double MgrBinarySearch(double ok, double ng, Func<double,bool> predicate, int maxLoopCount = 100)
        => MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>maxLoopCount-->0,predicate);
    
    public static bool ChangeMax<T>(ref this T current, T other) where T : struct, IComparable
    {
        bool changed = false;
        if(current.CompareTo(other) < 0)
        {
            current = other;
            changed = true;
        }
        return changed;
    }

    public static bool ChangeMin<T>(ref this T current, T other) where T : struct, IComparable
    {
        bool changed = false;
        if(current.CompareTo(other) > 0)
        {
            current = other;
            changed = true;
        }
        return changed;
    }

    public static IEnumerable<(T Value, int Length)> RunLengthEncode<T>(this IEnumerable<T> A) where T : IComparable
    {
        var nv = A.First();
        var nl = 1;

        foreach(var v in A.Skip(1))
        {
            if(nv.CompareTo(v)==0)
            {
                nl++;
            }
            else
            {
                yield return (nv,nl);

                nv = v;
                nl = 1;
            }
        }

        yield return (nv,nl);
    }

    public static bool Contains<T>(this (T,T) lr, T x) where T : IComparable<T>
    {
        var l = lr.Item1;
        var r = lr.Item2;
        return l.CompareTo(x) <= 0 && x.CompareTo(r) < 0;
    }

    public static string AsString(this IEnumerable<char> C) => new string(C.ToArray());

    private static T MgrBinarySearchBase<T>(T ok, T ng, Func<T,T,T> mid, Func<T,T,bool> loop, Func<T,bool> predicate)
    {
        while(loop(ok,ng))
        {
            var m = mid(ok,ng);
            if(predicate(m))
            {
                ok = m;
            }
            else
            {
                ng = m;
            }
        }
        return ok;
    }
}

class UnionFind
{
    private int[] _parent;
    private int[] _size;
    private int _groupCount;
    
    public int GroupCount => _groupCount;
    
    public UnionFind(int capacity)
    {
        _parent = new int[capacity];
        _size = new int[capacity];
        _groupCount = capacity;
        
        for(int i=0; i<capacity; i++)
        {
            _parent[i] = i;
            _size[i] = 1;
        }
    }
    
    public int Root(int x)
    {
        if(_parent[x] != x)
        {
            _parent[x] = Root(_parent[x]);
        }
        return _parent[x];
    }
    
    public bool Same(int x, int y) => Root(x) == Root(y);
    
    public void Unite(int x, int y)
    {
        x = Root(x);
        y = Root(y);
        if(x == y) return;
        
        if(_size[x]<_size[y])
        {
            var tmp = x;
            x = y;
            y = tmp;
        }
        _size[x] += _size[y];
        _parent[y] = x;
        
        _groupCount -= 1;
    }
    
    public int Size(int x) => _size[Root(x)];
}

class SegmentTree<T>
{
    private int _n;
    private T[] _node;
    
    private IEnumerable<T> _source;
    private Func<T,T,T> _updater;
    private T _e;
    
    public SegmentTree(IEnumerable<T> source, Func<T,T,T> updater, T e)
    {
        _source = source;
        _updater = updater;
        _e = e;
        
        var arr = _source.ToArray();
        
        _n = 1;
        while(_n<arr.Length) _n *= 2;
        
        _node = Enumerable.Repeat(_e,_n*2-1).ToArray();
        for(int i=0; i<arr.Length; i++) this.Update(i,arr[i]);
    }
    
    public T this[int i]
    {
        get { return _node[i + _n - 1]; }
        set { this.Update(i,value); }
    }
    
    public void Update(int i, T val)
    {
        i += _n-1;
        
        _node[i] = val;
        while(i>0)
        {
            i = (i-1)/2;
            _node[i] = _updater(_node[2*i+1],_node[2*i+2]);
        }
    }
    
    public T Query(int a, int b) => this.Query(a,b,0,0,_n);
    
    public T Query(int a, int b, int x, int l, int r)
    {
        if(b<=l||r<=a) return _e;
        if(a<=l&&r<=b) return _node[x];
        
        var vl = Query(a,b,x*2+1,l,(l+r)/2);
        var vr = Query(a,b,x*2+2,(l+r)/2,r);
        return _updater(vl,vr);
    }
}

class LazySegmentTree<T,F>
{
    private int _n;
    private T[] _node;
    private F[] _lazy;
    private bool[] _hasLazy;
    
    private T[] _source;
    private Func<T,T,T> _op;
    private T _e;
    private Func<T,F,T> _mapping;
    private Func<F,F,F> _composition;
    private F _id;
    
    public LazySegmentTree(IEnumerable<T> source, Func<T,T,T> op, T e, Func<T,F,T> mapping, Func<F,F,F> composition, F id)
    {
        _source = source.ToArray();
        _op = op;
        _e = e;
        _mapping = mapping;
        _composition = composition;
        _id = id;
        
        var sl = _source.Length;
        
        _n = 1;
        while(_n<sl) _n *= 2;
        
        _node = Enumerable.Repeat(_e,_n*2-1).ToArray();
        _lazy = Enumerable.Repeat(_id,_n*2-1).ToArray();
        _hasLazy = new bool[_n*2-1];
        for(int i=0; i<sl; i++) _node[_n+i-1] = _source[i];
        for(int i=_n-2; i>=0; i--) _node[i] = _op(_node[i*2+1],_node[i*2+2]);
    }
    
    public T this[int i] { get => this[i,i+1]; }
    public T this[int i, int j] { get => this.Query(i,j); }
    
    public void Update(int a, F f) => this.Update(a,a+1,f);
    public void Update(int a, int b, F f) => this.Update(a,b,f,0,0,_n);
    
    public void Update(int a, int b, F f, int x, int l, int r)
    {
        this.Eval(x,l,r);
        
        if(b<=l||r<=a) return;
        
        if(a<=l&&r<=b)
        {
            _lazy[x] = _composition(_lazy[x],f);
            _hasLazy[x] = true;
            Eval(x,l,r);
        }
        else
        {
            this.Update(a,b,f,x*2+1,l,(l+r)/2);
            this.Update(a,b,f,x*2+2,(l+r)/2,r);
            _node[x] = _op(_node[x*2+1],_node[x*2+2]);
        }
    }
    
    public T Query(int a, int b) => a==0 && b==_source.Length ? _node[0] : this.Query(a,b,0,0,_n);
    
    public T Query(int a, int b, int x, int l, int r)
    {
        if(b<=l||r<=a) return _e;
        
        this.Eval(x,l,r);
        if(a<=l&&r<=b) return _node[x];
        
        var vl = Query(a,b,x*2+1,l,(l+r)/2);
        var vr = Query(a,b,x*2+2,(l+r)/2,r);
        return _op(vl,vr);
    }
    
    private void Eval(int k, int l, int r)
    {
        if(!_hasLazy[k]) return;
        
        _node[k] = _mapping(_node[k],_lazy[k]);
        
        if(r-l>1)
        {
            for(int d=0; d<2; d++)
            {
                var nk = 2*k + 1 + d;
                _lazy[nk] = _composition(_lazy[nk],_lazy[k]);
                _hasLazy[nk] = true;
            }
        }
        
        _lazy[k] = _id;
        _hasLazy[k] = false;
    }
}

class SimpleMultiSet<T> : IEnumerable<T> where T : notnull
{
    private int _countTotal;
    private SortedSet<T> _values;
    private Dictionary<T,int> _count;
    private bool _hasModifiedAfterStartedEnumeration;
    
    public SimpleMultiSet()
    {
        _countTotal = 0;
        _values = new SortedSet<T>();
        _count = new Dictionary<T,int>();
    }
    
    public SimpleMultiSet(IEnumerable<T> collection) : this()
    {
        foreach(var v in collection) Add(v);
    }
    
    public int Count => _countTotal;
    public T Max => _values.Max ?? throw new InvalidOperationException();
    public T Min => _values.Min ?? throw new InvalidOperationException();
    
    public bool Add(T v)
    {
        bool isNew = false;

        if(!_count.ContainsKey(v))
        {
            isNew = true;
            _count.Add(v,0);
            _values.Add(v);
        }

        _count[v]++;
        _countTotal++;

        Modify();

        return isNew;
    }

    public bool Remove(T v) => Remove(v, false);
    
    public bool RemoveAll(T v) => Remove(v, true);
    
    public bool Contains(T v) => _count.ContainsKey(v);
    
    public T UpperOf(T v) => _values.GetViewBetween(v,this.Max).Min ?? throw new InvalidOperationException();
    
    public T LowerOf(T v) => _values.GetViewBetween(this.Min,v).Max ?? throw new InvalidOperationException();

    public IEnumerator<T> GetEnumerator()
    {
        _hasModifiedAfterStartedEnumeration = false;

        foreach(var v in _values)
        {
            for(int i=0; i<_count[v]; i++)
            {
                yield return v;

                if(_hasModifiedAfterStartedEnumeration)
                {
                    throw new InvalidOperationException("Collection was modified.");
                }
            }
        }
    }

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

    private bool Remove(T v, bool isAll)
    {
        if(!_count.TryGetValue(v, out int vc)) return false;

        var c = isAll ? vc : 1;

        _count[v] -= c;
        _countTotal -= c;
        
        if(_count[v]<=0)
        {
            _count.Remove(v);
            _values.Remove(v);
        }

        Modify();

        return true;
    }
    
    private void Modify()
    {
        _hasModifiedAfterStartedEnumeration = true;
    }
}

class RollingHash
{
    private string s;
    private int n => s.Length;
    
    private long b;
    private long mod;
    
    private long[] hash;
    private long[] p;
    
    public RollingHash(string s, long b, long mod)
    {
        this.s = s;
        this.b = b;
        this.mod = mod;
        
        hash = new long[n+1];
        p = new long[n+1];
        p[0] = 1;
        
        for(int i=0; i<n; i++)
        {
            hash[i+1] = (hash[i] * b % mod + (int)s[i]) % mod;
            p[i+1] = p[i] * b % mod;
        }
    }
    
    public long GetHash(int l, int r) => (hash[r] - (hash[l] * p[r-l] % mod) + mod) % mod;
    
    public bool Equal(int l1, int r1, int l2, int r2) => (r1-l1)==(r2-l2) && GetHash(l1,r1)==GetHash(l2,r2);
}

class LinearSieve
{
    private int N;
    private Dictionary<int,int> minDivisor;
    private List<int> primes;

    public int Max => N;

    public LinearSieve(long n, Func<long,bool>? target = null)
    {
        target ??= x => x <= n;

        minDivisor = new();
        primes = new();

        minDivisor.Add(1,1);

        for(int i=2; target(i); i++)
        {
            if(minDivisor.TryAdd(i,i))
            {
                primes.Add(i);
            }
            foreach(var p in primes)
            {
                if(!target((long)p * i)) break;
                if(p > minDivisor[i]) break;

                minDivisor.Add(p * i, p);
            }
        }

        N = minDivisor.Count;
    }

    public IEnumerable<int> PrimeNumbers()
    {
        foreach(var p in primes) yield return p;
    }

    public bool IsPrime(int n)
    {
        AssertLinearSieveTarget(n);

        return n > 1 && minDivisor[n] == n;
    }

    public IEnumerable<PrimeFactor> PrimeFactorization(int n)
    {
        AssertLinearSieveTarget(n);

        var dic = new Dictionary<int,int>();
        while(n > 1)
        {
            var p = minDivisor[n];

            dic.TryAdd(p,0);
            dic[p]++;

            n /= p;
        }

        foreach(var (p,e) in dic) yield return new PrimeFactor(p,e);
    }

    private void AssertLinearSieveTarget(long n)
    {
        if(!(1 <= n && n <= N))
        {
            throw new Exception($"The target must be between 1 and {N}.");
        }
    }
}

interface IMod { public long Mod { get; } }
struct ModInt998244353 : IMod { public readonly long Mod => 998244353; }
struct ModInt1000000007 : IMod { public readonly long Mod => 1000000007; }

readonly struct ModInt<T> where T : struct, IMod
{
    private static readonly T t = default;
    private static readonly long mod = t.Mod;
    internal readonly long _v;

    public long Value => _v;
    public static long Mod => mod;

    public ModInt(long v)
    {
        if(v < 0 || mod <= v)
        {
            v %= mod;
            if(v < 0) v += mod;
        }
        _v = v;
    }

    public static ModInt<T> operator +(ModInt<T> a) => a;
    public static ModInt<T> operator +(ModInt<T> a, ModInt<T> b)
    {
        var v = a._v + b._v;
        if(v >= mod)
        {
            v -= mod;
        }
        return new ModInt<T>(v);
    }
    public static ModInt<T> operator -(ModInt<T> a) => new(a._v >= 0 ? a._v : mod - a._v);
    public static ModInt<T> operator -(ModInt<T> a, ModInt<T> b)
    {
        var v = a._v - b._v;
        if(v < 0)
        {
            v += mod;
        }
        return new ModInt<T>(v);
    }
    public static ModInt<T> operator *(ModInt<T> a, ModInt<T> b) => new(a._v * b._v);
    public static ModInt<T> operator /(ModInt<T> a, ModInt<T> b) => new(a._v * MathEx.ModInv(b._v, mod));
    public static bool operator ==(ModInt<T> a, ModInt<T> b) => a._v == b._v;
    public static bool operator !=(ModInt<T> a, ModInt<T> b) => !(a == b);

    public static implicit operator ModInt<T>(int v) => new(v);
    public static implicit operator ModInt<T>(long v) => new(v);

    public ModInt<T> Pow(long k) => new(MathEx.Pow(_v, k, mod));

    public override string ToString() => _v.ToString();
    public override bool Equals([NotNullWhen(true)] object? obj)
    {
        if(obj is ModInt<T> m) return this == m;
        if(obj is int i) return this == i;
        if(obj is long l) return this == l;
        return false;
    }
    public override int GetHashCode() => _v.GetHashCode();
}