using AtCoder.Internal; using AtCoder.Operators; using BitArray = System.Collections.BitArray; using Kzrnm.Competitive; using Kzrnm.Competitive.IO; using ModInt = AtCoder.StaticModInt; using System; using System.Buffers; using System.Buffers.Text; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Globalization; using System.IO; using System.Linq; using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Runtime.Intrinsics.X86; using System.Text; using 凾 = System.Runtime.CompilerServices.MethodImplAttribute; partial class Program { const bool __ManyTestCases = false; #if !LOCAL_RUNNING static void Main()=>new Program(new PropertyConsoleReader(),new Utf8ConsoleWriter()).Run(); [凾(256)] #endif private ConsoleOutput? Calc() { int N = cr; int M = cr; int X = cr; int[] A = cr.Repeat(N); var bits = new List(); for (int b = 0; b < 31; b++) { var bb = new BitArray(N); for (int i = 0; i < A.Length; i++) bb[i] = A[i].On(b); bits.Add(bb); } var xb = Enumerable.Repeat(false, 31).ToList(); foreach (var b in X.Bits()) xb[b] = true; while (--M >= 0) { xb.Add(cr.Int != 0); int l = cr.Int0; int r = cr.Int; var bb = new bool[N]; bb.AsSpan()[l..r].Fill(true); bits.Add(new BitArray(bb)); } var len = new BitMatrix(bits.ToArray()).LinearSystem(xb.ToArray()).Length - 1; return ModInt.Raw(2).Pow(len).Value; } } #region Expanded by https://github.com/kzrnm/SourceExpander //LICENSE: //https://github.com/kzrnm/Kzrnm.Competitive/blob/master/LICENSE //https://github.com/kzrnm/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt #pragma warning disable namespace AtCoder.Internal{public class Barrett{public readonly uint Mod;internal readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[凾(256)]public uint Mul(uint a,uint b){var z=(ulong)a*b;if(Bmi2.X64.IsSupported){var x=Bmi2.X64.MultiplyNoFlags(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}return(uint)(z%Mod);}}} namespace AtCoder.Internal{public static class InternalMath{private static readonly DictionaryprimitiveRootsCache=new Dictionary(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[凾(256)]public static int PrimitiveRoot()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p)){return p;}return primitiveRootsCache[m]=PrimitiveRootCalculate();}static int PrimitiveRootCalculate()where TMod:struct,IStaticMod{int m=(int)default(TMod).Mod;Spandivs=stackalloc int[20];divs[0]=2;int cnt=1;int x=(m-1)/2;while(x%2==0){x>>=1;}for(int i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;while(x%i==0){x/=i;}}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:{}}}[凾(256)]public static(long,long)InvGCD(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[凾(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[凾(256)]public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpanbases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[凾(256)]private static long PowMod(long x,long n,int m){if(m==1)return 0;Barrett barrett=new Barrett((uint)m);uint r=1,y=(uint)SafeMod(x,m);while(0>=1;}return r;}[凾(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}public readonly struct StaticModInt:IEquatable>,IFormattable where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModIntZero=>default;public static StaticModIntOne=>new StaticModInt(1u);[凾(256)]public static StaticModIntRaw(int v){var u=unchecked((uint)v);return new StaticModInt(u);}[凾(256)]public StaticModInt(long v):this(Round(v)){}[凾(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[凾(256)]private StaticModInt(uint v)=>_v=v;[凾(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0){x+=op.Mod;}return(uint)x;}[凾(256)]public static StaticModIntoperator ++(StaticModIntv){var x=v._v+1;if(x==op.Mod){x=0;}return new StaticModInt(x);}[凾(256)]public static StaticModIntoperator --(StaticModIntv){var x=v._v;if(x==0){x=op.Mod;}return new StaticModInt(x-1);}[凾(256)]public static StaticModIntoperator+(StaticModIntlhs,StaticModIntrhs){var v=lhs._v+rhs._v;if(v>=op.Mod){v-=op.Mod;}return new StaticModInt(v);}[凾(256)]public static StaticModIntoperator-(StaticModIntlhs,StaticModIntrhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod){v+=op.Mod;}return new StaticModInt(v);}}[凾(256)]public static StaticModIntoperator*(StaticModIntlhs,StaticModIntrhs)=>new StaticModInt((uint)((ulong)lhs._v*rhs._v%op.Mod));[凾(256)]public static StaticModIntoperator/(StaticModIntlhs,StaticModIntrhs)=>lhs*rhs.Inv();[凾(256)]public static StaticModIntoperator+(StaticModIntv)=>v;[凾(256)]public static StaticModIntoperator-(StaticModIntv)=>new StaticModInt(v._v==0?0:op.Mod-v._v);[凾(256)]public static bool operator==(StaticModIntlhs,StaticModIntrhs)=>lhs._v==rhs._v;[凾(256)]public static bool operator!=(StaticModIntlhs,StaticModIntrhs)=>lhs._v!=rhs._v;[凾(256)]public static implicit operator StaticModInt(int v)=>new StaticModInt(v);[凾(256)]public static implicit operator StaticModInt(uint v)=>new StaticModInt((long)v);[凾(256)]public static implicit operator StaticModInt(long v)=>new StaticModInt(v);[凾(256)]public static implicit operator StaticModInt(ulong v)=>new StaticModInt(v);[凾(256)]public StaticModIntPow(long n){var x=this;var r=new StaticModInt(1U);while(n>0){if((n&1)>0){r*=x;}x*=x;n>>=1;}return r;}[凾(256)]public StaticModIntInv(){if(op.IsPrime){return Pow(op.Mod-2);}else{var(g,x)=InternalMath.InvGCD(_v,op.Mod);return new StaticModInt(x);}}public override string ToString()=>_v.ToString();public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);public override bool Equals(object obj)=>obj is StaticModIntm&&Equals(m);[凾(256)]public bool Equals(StaticModIntother)=>_v==other._v;public override int GetHashCode()=>_v.GetHashCode();}} namespace AtCoder.Operators{public interface IAdditionOperator{T Add(T x,T y);}public interface ISubtractOperator{T Subtract(T x,T y);}public interface IMultiplicationOperator{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator:IMultiplicationOperator{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator:IAdditionOperator,ISubtractOperator,IMultiplicationOperator,IDivisionOperator,IUnaryNumOperator{}public interface ICompareOperator:IComparer{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface IMinMaxValue{T MinValue{get;}T MaxValue{get;}}public interface INumOperator:IArithmeticOperator,ICompareOperator,IMinMaxValue{}public interface IShiftOperator{T LeftShift(T x,int y);T RightShift(T x,int y);}} namespace AtCoder{public readonly struct LongOperator:INumOperator,IShiftOperator{public long MinValue=>long.MinValue;public long MaxValue=>long.MaxValue;public long MultiplyIdentity=>1L;[凾(256)]public long Add(long x,long y)=>x+y;[凾(256)]public long Subtract(long x,long y)=>x-y;[凾(256)]public long Multiply(long x,long y)=>x*y;[凾(256)]public long Divide(long x,long y)=>x/y;[凾(256)]public long Modulo(long x,long y)=>x%y;[凾(256)]public long Minus(long x)=>-x;[凾(256)]public long Increment(long x)=> ++x;[凾(256)]public long Decrement(long x)=> --x;[凾(256)]public bool GreaterThan(long x,long y)=>x>y;[凾(256)]public bool GreaterThanOrEqual(long x,long y)=>x>=y;[凾(256)]public bool LessThan(long x,long y)=>xx<=y;[凾(256)]public int Compare(long x,long y)=>x.CompareTo(y);[凾(256)]public long LeftShift(long x,int y)=>x<x>>y;}} namespace Kzrnm.Competitive.IO{using static Utf8Parser;using _R=ConsoleReader;public class ConsoleReader{internal const int BufSize=1<<12;internal readonly Stream input;internal readonly Encoding encoding;internal readonly byte[]buf;internal int pos;internal int len;[凾(256)]public ConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding):this(input,encoding,BufSize){}[凾(256)]public ConsoleReader(Stream input,Encoding encoding,int bufferSize){this.input=input;this.encoding=encoding;buf=new byte[bufferSize];}[凾(256)]private void FillEntireNumber(){if((uint)pos>=(uint)buf.Length)FillNextBuffer();while(buf[pos]<=' ')if( ++pos>=len)FillNextBuffer();if(pos+21>=buf.Length&&buf[buf.Length-1]>' ')FillEntireNumberImpl();}private void FillEntireNumberImpl(){buf.AsSpan(pos,len-pos).CopyTo(buf);len-=pos;pos=0;var numberOfBytes=input.Read(buf,len,buf.Length-len);if(numberOfBytes==0)buf[len++]=10;else if(numberOfBytes+len=len)FillNextBuffer();return buf[pos++];}[凾(256)]public T Read(){if(typeof(T)==typeof(int))return(T)(object)Int();if(typeof(T)==typeof(uint))return(T)(object)UInt();if(typeof(T)==typeof(long))return(T)(object)Long();if(typeof(T)==typeof(ulong))return(T)(object)ULong();if(typeof(T)==typeof(double))return(T)(object)Double();if(typeof(T)==typeof(decimal))return(T)(object)Decimal();if(typeof(T)==typeof(char))return(T)(object)Char();if(typeof(T)==typeof(string))return(T)(object)Ascii();return Throw();}static T Throw()=>throw new NotSupportedException(typeof(T).Name);[凾(256)]public int Int(){FillEntireNumber();TryParse(buf.AsSpan(pos),out int v,out int bc);pos+=bc;return v;}[凾(256)]public uint UInt(){FillEntireNumber();TryParse(buf.AsSpan(pos),out uint v,out int bc);pos+=bc;return v;}[凾(256)]public long Long(){FillEntireNumber();TryParse(buf.AsSpan(pos),out long v,out int bc);pos+=bc;return v;}[凾(256)]public ulong ULong(){FillEntireNumber();TryParse(buf.AsSpan(pos),out ulong v,out int bc);pos+=bc;return v;}[凾(256)]public double Double(){FillEntireNumber();TryParse(buf.AsSpan(pos),out double v,out int bc);pos+=bc;return v;}[凾(256)]public decimal Decimal(){FillEntireNumber();TryParse(buf.AsSpan(pos),out decimal v,out int bc);pos+=bc;return v;}[凾(256)]public string String(){var sb=new List();;byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(' '();byte b;do b=ReadByte();while(b<=' ');do{sb.Add(b);b=ReadByte();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}[凾(256)]public char Char(){byte b;do b=ReadByte();while(b<=' ');return(char)b;}[凾(256)]public int Int0()=>Int()-1;[凾(256)]public uint UInt0()=>UInt()-1;[凾(256)]public long Long0()=>Long()-1;[凾(256)]public ulong ULong0()=>ULong()-1;[凾(256)]public static implicit operator int(_R cr)=>cr.Int();[凾(256)]public static implicit operator uint(_R cr)=>cr.UInt();[凾(256)]public static implicit operator long(_R cr)=>cr.Long();[凾(256)]public static implicit operator ulong(_R cr)=>cr.ULong();[凾(256)]public static implicit operator double(_R cr)=>cr.Double();[凾(256)]public static implicit operator decimal(_R cr)=>cr.Decimal();[凾(256)]public static implicit operator string(_R cr)=>cr.Ascii();public T[]Repeat(int count){var arr=new T[count];for(int i=0;i();return arr;}}} namespace Kzrnm.Competitive.IO{public class RepeatReaderwhere R:ConsoleReader{internal readonly R cr;internal readonly int count;[凾(256)]public RepeatReader(R cr,int count){this.cr=cr;this.count=count;}[凾(256)]public string[]Ascii()=>Read();[凾(256)]public int[]Int()=>Read();[凾(256)]public uint[]UInt()=>Read();[凾(256)]public long[]Long()=>Read();[凾(256)]public ulong[]ULong()=>Read();[凾(256)]public double[]Double()=>Read();[凾(256)]public decimal[]Decimal()=>Read();[凾(256)]public string[]Line(){var arr=new string[count];for(var i=0;irr)=>rr.Read();[凾(256)]public static implicit operator int[](RepeatReaderrr)=>rr.Read();[凾(256)]public static implicit operator uint[](RepeatReaderrr)=>rr.Read();[凾(256)]public static implicit operator long[](RepeatReaderrr)=>rr.Read();[凾(256)]public static implicit operator ulong[](RepeatReaderrr)=>rr.Read();[凾(256)]public static implicit operator double[](RepeatReaderrr)=>rr.Double();[凾(256)]public static implicit operator decimal[](RepeatReaderrr)=>rr.Decimal();public T[]Read(){var arr=new T[count];for(int i=0;i();return arr;}[凾(256)]public T[]Select(Funcfactory){var c=count;var arr=new T[c];for(var i=0;i(Funcfactory){var c=count;var arr=new T[c];for(var i=0;iRepeat(this ConsoleReader cr,int count)=>new RepeatReader(cr,count);}} namespace Kzrnm.Competitive.IO{public sealed class PropertyConsoleReader:ConsoleReader{public PropertyConsoleReader():base(){}public PropertyConsoleReader(Stream input,Encoding encoding):base(input,encoding){}public PropertyConsoleReader(Stream input,Encoding encoding,int bufferSize):base(input,encoding,bufferSize){}public new int Int=>Int();public new int Int0=>Int0();public new uint UInt=>UInt();public new uint UInt0=>UInt0();public new long Long=>Long();public new long Long0=>Long0();public new ulong ULong=>ULong();public new ulong ULong0=>ULong0();public new double Double=>Double();public new decimal Decimal=>Decimal();public new string String=>String();public new string Ascii=>Ascii();public new string Line=>Line();public new char Char=>Char();}} namespace Kzrnm.Competitive.IO{public class PropertyRepeatReader:RepeatReader{public PropertyRepeatReader(PropertyConsoleReader cr,int count):base(cr,count){}public new string[]Ascii=>Ascii();public new int[]Int=>Int();public new uint[]UInt=>UInt();public new long[]Long=>Long();public new ulong[]ULong=>ULong();public new double[]Double=>Double();public new decimal[]Decimal=>Decimal();public new string[]Line=>Line();public new string[]String=>String();public new int[]Int0=>Int0();public new uint[]UInt0=>UInt0();public new long[]Long0=>Long0();public new ulong[]ULong0=>ULong0();}public static class PRepeatEx{[凾(256)]public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new PropertyRepeatReader(cr,count);}} namespace Kzrnm.Competitive.IO{using static Utf8Formatter;using _W=Utf8ConsoleWriter;public sealed class Utf8ConsoleWriter:IDisposable{internal static readonly UTF8Encoding Utf8NoBom=new UTF8Encoding(false);internal const int BufSize=1<<12;internal readonly Stream output;internal byte[]buf;internal int len;public Utf8ConsoleWriter():this(Console.OpenStandardOutput()){}public Utf8ConsoleWriter(Stream output):this(output,BufSize){}public Utf8ConsoleWriter(Stream output,int bufferSize){this.output=output;buf=new byte[bufferSize];}public StreamWriter ToStreamWriter(){Flush();return new StreamWriter(output,Utf8NoBom);}[凾(256)]public void Flush(){output.Write(buf,0,len);len=0;}void IDisposable.Dispose()=>Flush();[凾(256)]private SpanEnsureBuf(int size){if(buf.Length-len(T v){void FormatFloat(double d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10(Math.Abs(d)),32)),out b,new StandardFormat('F',20));void FormatDec(decimal d,out int b)=>TryFormat(d,EnsureBuf(Math.Max(25+(int)Math.Log10((double)Math.Abs(d)),32)),out b,new StandardFormat('F',20));int bw;if(typeof(T)==typeof(int))TryFormat((int)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(long))TryFormat((long)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(uint))TryFormat((uint)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(ulong))TryFormat((ulong)(object)v,EnsureBuf(21),out bw);else if(typeof(T)==typeof(short))TryFormat((short)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(ushort))TryFormat((ushort)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(byte))TryFormat((byte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(sbyte))TryFormat((sbyte)(object)v,EnsureBuf(9),out bw);else if(typeof(T)==typeof(float))FormatFloat((float)(object)v,out bw);else if(typeof(T)==typeof(double))FormatFloat((double)(object)v,out bw);else if(typeof(T)==typeof(decimal))FormatDec((decimal)(object)v,out bw);else if(typeof(T)==typeof(char)){var dst=EnsureBuf(6);var c=(char)(object)v;if(c<0x007f){dst[0]=(byte)c;bw=1;}else{Spans=stackalloc char[1]{c};bw=Utf8NoBom.GetBytes(s,dst);}}else if(v is char[]charr)return Write(charr.AsSpan());else if(v is IUtf8ConsoleWriterFormatter f){f.Write(this);return this;}else return Write(v.ToString().AsSpan());len+=bw;return this;}[凾(256|512)]public _W Write(ReadOnlySpanv){var mlen=Utf8NoBom.GetMaxByteCount(v.Length);if(mlen>buf.Length){Flush();buf=new byte[mlen*2];}else if(mlen>buf.Length-len){Flush();}var bw=Utf8NoBom.GetBytes(v,buf.AsSpan(len));len+=bw;return this;}[凾(256)]public _W WriteLine()=>Write('\n');[凾(256)]public _W WriteLine(T v){Write(v);return Write('\n');}[凾(256)]public _W WriteLine(ReadOnlySpanv){Write(v);return Write('\n');}[凾(256)]public _W WriteLineJoin(IEnumerablecol)=>WriteMany(' ',col);[凾(256)]public _W WriteLineJoin((T1,T2)tuple){Write(tuple.Item1);Write(' ');return WriteLine(tuple.Item2);}[凾(256)]public _W WriteLineJoin((T1,T2,T3)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');return WriteLine(tuple.Item3);}[凾(256)]public _W WriteLineJoin((T1,T2,T3,T4)tuple){Write(tuple.Item1);Write(' ');Write(tuple.Item2);Write(' ');Write(tuple.Item3);Write(' ');return WriteLine(tuple.Item4);}[凾(256)]public _W WriteLineJoin(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;iWriteMany(' ',col);[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2){Write(v1);Write(' ');return WriteLine(v2);}[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3){Write(v1);Write(' ');Write(v2);Write(' ');return WriteLine(v3);}[凾(256)]public _W WriteLineJoin(T1 v1,T2 v2,T3 v3,T4 v4){Write(v1);Write(' ');Write(v2);Write(' ');Write(v3);Write(' ');return WriteLine(v4);}[凾(256)]public _W WriteLineJoin(params T[]col)=>WriteMany(' ',(ReadOnlySpan)col);[凾(256)]public _W WriteLineJoin(Spancol)=>WriteMany(' ',(ReadOnlySpan)col);[凾(256)]public _W WriteLineJoin(ReadOnlySpancol)=>WriteMany(' ',col);[凾(256)]public _W WriteLines(IEnumerablecol)=>WriteMany('\n',col);[凾(256)]public _W WriteLines(T[]col)=>WriteMany('\n',(ReadOnlySpan)col);[凾(256)]public _W WriteLines(Spancol)=>WriteMany('\n',(ReadOnlySpan)col);[凾(256)]public _W WriteLines(ReadOnlySpancol)=>WriteMany('\n',col);[凾(256)]public _W WriteGrid(IEnumerable>cols){foreach(var col in cols)WriteLineJoin(col);return this;}[凾(256)]public _W WriteGrid(IEnumerabletuples)where TTuple:ITuple{foreach(var tup in tuples)WriteLineJoin(tup);return this;}[凾(256)]private _W WriteMany(char sep,IEnumerablecol){if(col is T[]array)return WriteMany(sep,(ReadOnlySpan)array);var en=col.GetEnumerator();if(en.MoveNext()){Write(en.Current);while(en.MoveNext()){Write(sep);Write(en.Current);}}return WriteLine();}[凾(256)]private _W WriteMany(char sep,ReadOnlySpancol){if(col.Length>0){Write(col[0]);foreach(var c in col.Slice(1)){Write(sep);Write(c);}}return WriteLine();}}public interface IUtf8ConsoleWriterFormatter{void Write(_W cw);}} namespace Kzrnm.Competitive{using O=ConsoleOutput;public static class ConsoleOutputExt{[凾(256)]public static O ToConsoleOutput(this T f)where T:IUtf8ConsoleWriterFormatter{var cw=O.cw;f.Write(cw);return cw.WriteLine();}}public struct ConsoleOutput{public static Utf8ConsoleWriter cw;public static implicit operator O(int v)=>cw.WriteLine(v);public static implicit operator O(long v)=>cw.WriteLine(v);public static implicit operator O(uint v)=>cw.WriteLine(v);public static implicit operator O(ulong v)=>cw.WriteLine(v);public static implicit operator O(double v)=>cw.WriteLine(v);public static implicit operator O(decimal v)=>cw.WriteLine(v);public static implicit operator O(char v)=>cw.WriteLine(v);public static implicit operator O(ReadOnlySpanv)=>cw.WriteLine(v);public static implicit operator O(char[]v)=>cw.WriteLine((ReadOnlySpan)v);public static implicit operator O(string v)=>cw.WriteLine((ReadOnlySpan)v);public static implicit operator O(bool v)=>cw.WriteLine((ReadOnlySpan)(v?"Yes":"No"));public static implicit operator O(Utf8ConsoleWriter _)=>default;}} internal partial class Program{public PropertyConsoleReader cr;public Utf8ConsoleWriter cw;public Program(PropertyConsoleReader r,Utf8ConsoleWriter w){cr=r;ConsoleOutput.cw=cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=__ManyTestCases?cr.Int:1;while( --Q>=0)Calc();cw.Flush();}} namespace Kzrnm.Competitive{public static class Bit{[凾(256)]public static string ToBitString(this int num,int padLeft=sizeof(int)*8)=>Convert.ToString(num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this uint num,int padLeft=sizeof(uint)*8)=>Convert.ToString((int)num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this long num,int padLeft=sizeof(long)*8)=>Convert.ToString(num,2).PadLeft(padLeft,'0');[凾(256)]public static string ToBitString(this ulong num,int padLeft=sizeof(ulong)*8)=>Convert.ToString(unchecked((long)num),2).PadLeft(padLeft,'0');[凾(256)]public static bool On(this int num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this uint num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this long num,int index)=>((num>>index)&1)!=0;[凾(256)]public static bool On(this ulong num,int index)=>((num>>index)&1)!=0;[凾(256)]public static Enumerator Bits(this int num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this uint num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this long num)=>new Enumerator(num);[凾(256)]public static Enumerator Bits(this ulong num)=>new Enumerator(num);public struct Enumerator:IEnumerable,IEnumerator{ulong num;public Enumerator(int num):this((ulong)(uint)num){}public Enumerator(long num):this((ulong)num){}public Enumerator(ulong num){this.num=num;Current=-1;}public Enumerator GetEnumerator()=>this;public int Current{get;private set;}[凾(256)]public bool MoveNext(){if(num==0)return false;if(Bmi1.X64.IsSupported){Current=unchecked((int)Bmi1.X64.TrailingZeroCount(num));num=Bmi1.X64.ResetLowestSetBit(num);}else MoveNextLogical();return true;}void MoveNextLogical(){Current=BitOperations.TrailingZeroCount(num);num&=num-1;}object IEnumerator.Current=>Current;public int[]ToArray(){var res=new int[BitOperations.PopCount(num)];for(int i=0;ithrow new NotSupportedException();void IDisposable.Dispose(){}IEnumeratorIEnumerable.GetEnumerator()=>this;IEnumerator IEnumerable.GetEnumerator()=>this;}}} namespace Kzrnm.Competitive{public static class __BitArrayExtension{private class Dummy{public int[]arr;public int len;public int ver;}[凾(256)]public static int[]GetArray(this BitArray b)=>Unsafe.As(b).arr;[凾(256)]public static void CopyTo(this BitArray b,int[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static void CopyTo(this BitArray b,uint[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static void CopyTo(this BitArray b,bool[]array,int index=0)=>b.CopyTo((Array)array,index);[凾(256)]public static uint[]ToUInt32Array(this BitArray b){var arr=new uint[(b.Length+31)/32];b.CopyTo(arr);return arr;}[凾(256)]public static int[]OnBits(this BitArray b){var arr=b.GetArray();var brr=MemoryMarshal.Cast(arr);var l=new List(b.Length);for(var i=0;i=b.Length)break;l.Add(bb);}if((arr.Length&1)!=0)foreach(var bit in arr[^1].Bits()){var bb=bit+64*brr.Length;if(bb>=b.Length)break;l.Add(bb);}return l.AsSpan().ToArray();}[凾(256)]public static int PopCount(this BitArray b){var arr=b.GetArray().AsSpan();var rem=b.Length&31;int cnt=rem==0?0:-BitOperations.PopCount((uint)((-1<(arr);foreach(var bb in brr)cnt+=BitOperations.PopCount(bb);return cnt;}[凾(256)]public static int Lsb(this BitArray b){var arr=b.GetArray().AsSpan();var brr=MemoryMarshal.Cast(arr);for(int i=0;i(arr);for(int i=brr.Length-1;i>=0;i--)if(brr[i]!=0)return Math.Min(b.Length,BitOperations.Log2(brr[i])+i*64);return b.Length;}}} namespace Kzrnm.Competitive{public static class __MemoryMarshalExtension{private class ArrayVal{public T[]arr;}[凾(256)]public static SpanAsSpan(this Listlist,int start=0)=>Unsafe.As>(list).arr.AsSpan(start,list.Count-start);[凾(256)]public static SpanCast(this Spanspan)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast(span);[凾(256)]public static ReadOnlySpanCast(this ReadOnlySpanspan)where TFrom:struct where TTo:struct=>MemoryMarshal.Cast(span);[凾(256)]public static ref T GetReference(this Spanspan)=>ref MemoryMarshal.GetReference(span);[凾(256)]public static ref T GetReference(this ReadOnlySpanspan)=>ref MemoryMarshal.GetReference(span);}} namespace Kzrnm.Competitive{public static class MathLibGeneric{[凾(256)]public static T Pow(T x,long y)where TOp:struct,IMultiplicationOperator{var op=new TOp();T res=((y&1)!=0)?x:op.MultiplyIdentity;for(y>>=1;y>0;y>>=1){x=op.Multiply(x,x);if((y&1)!=0)res=op.Multiply(res,x);}return res;}[凾(256)]public static long Pow(this long x,long y)=>Pow(x,y);}} namespace Kzrnm.Competitive.Internal{public enum ArrayMatrixKind{Zero,Identity,Normal,}} namespace Kzrnm.Competitive{using Kd=Internal.ArrayMatrixKind;public readonly struct BitMatrix{public bool this[int row,int col]=>Value[row][col];public readonly BitArray[]Value;public static readonly BitMatrix Zero=new BitMatrix(Kd.Zero);public static readonly BitMatrix Identity=new BitMatrix(Kd.Identity);public static BitMatrix AdditiveIdentity=>Zero;public static BitMatrix MultiplicativeIdentity=>Identity;internal readonly Kd kind;internal BitMatrix(Kd kind){this.kind=kind;Value=null;}public BitMatrix(BitArray[]value){Value=value;kind=Kd.Normal;}public BitMatrix(bool[][]value):this(value.Select(a=>new BitArray(a)).ToArray()){}private static BitMatrix ThrowNotSupportResponse()=>throw new NotSupportedException();public bool IsZero=>kind is Kd.Zero;private static BitArray[]NormalZeroMatrix(int row,int col){var arr=new BitArray[row];for(int i=0;iy.kind switch{Kd.Zero=>Zero,Kd.Identity=>Identity,_=>new BitMatrix(CloneArray(y.Value)),},Kd.Identity=>y.kind switch{Kd.Zero=>Identity,Kd.Identity=>ThrowNotSupportResponse(),_=>y.AddIdentity(),},_=>y.kind switch{Kd.Zero=>new BitMatrix(CloneArray(x.Value)),Kd.Identity=>x.AddIdentity(),_=>x.Add(y),},};}[凾(256)]public static BitMatrix operator+(BitMatrix x)=>x;public static BitMatrix operator-(BitMatrix x){var val=x.Value;var arr=new BitArray[val.Length];for(int i=0;i-x;public static BitMatrix operator-(BitMatrix x,BitMatrix y)=>x+y;public static BitMatrix operator^(BitMatrix x,BitMatrix y)=>x+y;private BitMatrix Multiply(BitMatrix other){var val=Value;var otherArr=other.Value;var res=new BitArray[val.Length];for(int i=0;iy.kind switch{Kd.Normal=>new BitMatrix(NormalZeroMatrix(y.Value.Length,y.Value[0].Length)),_=>Zero,},Kd.Identity=>y.kind switch{Kd.Zero=>Zero,Kd.Identity=>Identity,_=>y,},_=>y.kind switch{Kd.Zero=>new BitMatrix(NormalZeroMatrix(x.Value.Length,x.Value[0].Length)),Kd.Identity=>x,_=>x.Multiply(y),},};}public static BitArray operator*(BitMatrix mat,bool[]vector)=>mat.Multiply(new BitArray(vector));public static BitArray operator*(BitMatrix mat,BitArray vector)=>mat.Multiply(vector);public BitArray Multiply(BitArray vector){var val=Value;var res=new bool[val.Length];for(int i=0;iGaussianEliminationImpl(BitArray[]arr,bool isReduced){var idx=new List(arr.Length);int r=0;int width=arr[0].Length;for(int x=0;x{row=new BitArray(row);++row.Length;row[^1]=v;return row;}).ToArray();var idxs=GaussianEliminationImpl(impl,false).AsSpan();var r=idxs.Length;int w=Value[0].Length;if(idxs[^1]==w)return null;for(int i=r;i(Enumerable.Range(0,w));var lst=new List(w);{var v=new BitArray(w);for(int y=idxs.Length-1;y>=0;y--){int f=idxs[y];used.Remove(f);v[f]=impl[y][^1];for(int x=f+1;x=0;y--){int f=idxs[y];for(int x=f+1;xobj is BitMatrix x&&Equals(x);[凾(256)]public bool Equals(BitMatrix other)=>kind==other.kind&&(kind!=Kd.Normal||EqualsMat(Value,other.Value));private static bool EqualsMat(BitArray[]a,BitArray[]b){if(a.Length!=b.Length)return false;var array=new int[(a[0].Length+31)/32];var empty=new int[(a[0].Length+31)/32];for(int i=0;ikind switch{Kd.Normal=>HashCode.Combine(kind,Value.Length,Value[0][0],Value[0][^1],Value[^1][0],Value[^1][^1]),_=>HashCode.Combine(kind),};[凾(256)]public static bool operator==(BitMatrix left,BitMatrix right)=>left.Equals(right);[凾(256)]public static bool operator!=(BitMatrix left,BitMatrix right)=>!(left==right);public override string ToString(){if(kind!=Kd.Normal)return kind.ToString();var sb=new StringBuilder(Value.Length*(Value[0].Length+2));foreach(var row in Value){var chr=new char[row.Length];for(int j=0;jrow){row=row.Trim();var b=new BitArray(row.Length);for(int i=0;iMathLibGeneric.Pow(this,y);public struct Operator:IArithmeticOperator{public BitMatrix MultiplyIdentity=>Identity;[凾(256)]public BitMatrix Add(BitMatrix x,BitMatrix y)=>x+y;[凾(256)]public BitMatrix Subtract(BitMatrix x,BitMatrix y)=>x-y;[凾(256)]public BitMatrix Multiply(BitMatrix x,BitMatrix y)=>x*y;[凾(256)]public BitMatrix Minus(BitMatrix x)=>-x;[凾(256)]public BitMatrix Increment(BitMatrix x)=>throw new NotSupportedException();[凾(256)]public BitMatrix Decrement(BitMatrix x)=>throw new NotSupportedException();[凾(256)]public BitMatrix Divide(BitMatrix x,BitMatrix y)=>throw new NotSupportedException();[凾(256)]public BitMatrix Modulo(BitMatrix x,BitMatrix y)=>throw new NotSupportedException();}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander