結果

問題 No.1327 グラフの数え上げ
ユーザー uwiuwi
提出日時 2020-12-24 00:21:13
言語 Java21
(openjdk 21)
結果
AC  
実行時間 267 ms / 2,000 ms
コード長 16,453 bytes
コンパイル時間 5,894 ms
コンパイル使用メモリ 92,688 KB
実行使用メモリ 94,556 KB
最終ジャッジ日時 2023-10-21 15:23:09
合計ジャッジ時間 8,511 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
54,232 KB
testcase_01 AC 92 ms
54,376 KB
testcase_02 AC 75 ms
54,160 KB
testcase_03 AC 77 ms
54,104 KB
testcase_04 AC 78 ms
54,248 KB
testcase_05 AC 76 ms
52,112 KB
testcase_06 AC 76 ms
54,248 KB
testcase_07 AC 77 ms
54,168 KB
testcase_08 AC 85 ms
54,396 KB
testcase_09 AC 96 ms
54,396 KB
testcase_10 AC 79 ms
54,152 KB
testcase_11 AC 76 ms
54,236 KB
testcase_12 AC 76 ms
54,228 KB
testcase_13 AC 76 ms
54,164 KB
testcase_14 AC 76 ms
54,192 KB
testcase_15 AC 144 ms
57,548 KB
testcase_16 AC 267 ms
94,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package adv2020;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;

public class Day24 {
	InputStream is;
	FastWriter out;

	String INPUT = "";
	final int mod = 1000000007;

	public void solve()
	{
		char[] s = ns().toCharArray();
		if(s.length >= 11){
			out.println(0);
			return;
		}
		long x = Long.parseLong(new String(s));
		if(x >= 1000000008){
			out.println(0);
			return;
		}
		int n = (int)x - 1;

		int B = 1000000;
		long base = dec(enigma, (int)(n/B*5));
		for(long i = n/B*B+1;i <= n;i++){
			base = base * i % mod;
		}
		if(n % 2 == 1){
			base = (mod - base) % mod;
		}
		out.println(base);
	}

	public static final char[] enigma = "!    rJ$V)cTce(.?8( f$*L$R|}!.NT-6%Vv|5*r9PB$nq`*.0fO,*85Cl!B5:;!v&&M-U#$7#L=L )BJlN%@x7?$QosC)[/*r$6;TU'NP!;$[<DU(EVz<$A$4! w$|o(9cvR)Bh4k,R+/9 a'CC,$](#!AX@W$K8-9,[Zrp,<0FN'B1`3'$5G:(ch^ -Yr<a+w~)+!srr`*^-Y)#eGY^*5Co~$r9>?%1Br=#Tl`?&[gE)(o=7y$wJgs+Ljeu 9ZM^'O;6[##4a^*'Ss%$4btJ&p*y2+=m+}*!6)q+l#3G+s?#C s_~q&0txk hkH( qrT7+d0l*)km`/!080u,dhrT%>WU{%1]bB)xGhS+Et$m+q~I?.f?Wn(0%(# rvjo%I:aH'9duz(:ir2,*5P`#4Yy$(Y'bg(x^iy!YMs-'u*O.(Jbas&L,m6,.)$#-8G6/$Pb%s,UGci)Y.cp*4=.u& <v.!8!Jn,)# h _v8!.O>|8#GrTh+FnUF-:oId,^M2O-j2x$*Sm8W(b<TO!foqX (P R !Ux[ uf;K!u+Hi$b^ll :m*9*PW$k&~wb2 $mw<+O>_A&>!Z>*PeI]&T#^y#~#&p))EMO$.l+8#`8@e+ztE:(<?QO-dS m(1b:o#zZz$+@~y~-U63@)(?aM%;^J8$x=aG(r&_l cJv_+4/2<&]4C=#&lB-#/k9r,]+ |-k#<A$'XbQ'E{QJ,v}'*!{3g*$3M6r't~M9$K@y! 7+M<*R>{N$JbPA,V+o>%E/Q~*Gx*y&jeUm)n C(!ENaZ(v8ft)O?W&,9gRZ#]Z)d(&T8,'=6Nj* !fp#Pqwl'-|n&,aW='*71T&*;56s$CaTt $a3I(YRkY#Fxh<!f6V`% %(O+F(l+!vQBt SWqb F[/+%w;s>(zArv!!%/a%ISS9-Gg?{$N G>.N#Z= 0QX%)GL] +m<wO#nUTL!H6a`(!U8G!K^/'%P1C8(,EyK G4pA%MT@q&H[ I);oDB ?.7M-gc;7)u{)3$?zgo'aDqJ(41(2-r*JA,k 8n-EB1C-Nbs5-0({a*u$dP)@b~1$a6E^-F6c0-}`zR!vZ{V'Pwx!''sw/,';Y3+a?_x%+XSB'Ameu*bw!Y iK*j+]]H4'X#}<#7*[ !{7ST!^^@Q(;66X$k&&?#jws8$.kSn 7nmI'fzMS-5&@:!G?55!-`PS!N[HZ'PH+n!h>bi'SjXO*& 3Q!&POu%BV,T(r2|Y$_PQc$6'='!<jgE*J`eO!h>}h*YL,D!]Xp&*x~#S%VEw6#$)_J!)a05,kkwF'}>u[$5?Km!Nk9d$06mu(Yj%q+V6;e%@vft,[Z,6,t -V#[7Ap*0kF6%OVKv#.1oR+$8I:)7pQJ#SyN)&q.D>.O1+!-0bwM%%j4e ;+x0)>yBY&0<8v-5DG.#AX,##IAy7.X#T,)+2A#'x`g>#nVp`)K-*}-(FWb'D%sH+A8TQ AX7c$AOA/']2Jc)u#^0':*zk%Cd2Y)1(5N(x][x)@Vd1*Z3: *WtTl-*WM`#84MR(E.T8,1!&/&=yjg'/q+h-bhfd!GdN0*HEy~$DOYX*Pq>e(|>R9%lD:@+>(L*%|`&f#&u*`(RWPG ?0z!'--Pq%=u5K$Rz{>'@Dk8!<[%q(7w'D+1/5Y+>>bu$vS#}'26'h(Qy~M%oLdv!*4n='v9.N(1'xI%/-p`'])Y4'gdn3#wJ6-%[t&/!/M?h([YvR(zu(i-3oNA)yaJ|,,(As,-YA2,.`:D-XZw/&X^:L#:rAa*&`KE&S(5U*.8DW*vOW*,`O],&CQ%w =XC) <t9R#ILyv fM1Z-[TJH&8T?p+Vx1F#j,o#,.,IX%'ka0.rBmY,vw^}!dBi.#<=dk,oOtv(:D&D*h-V((Gm`$%Ob $.Avg5${|,a+;c@V-o!L/ i5LA%z7:[%mNBS!@Ry?'212w#E2.g,XxjF#<(yA*,U.9-t@:K,>a4n&jP@m+_:1]&R]&G!UbJl a)x=%0n*'! ;=U*.5bf&zuu>&Q;L6%'fJ.&!5&V-hPGR-#i;V-%}!`-'C<.,#Ntx(DnK>.?ZK3.*+<?*f#wO)^1t_$XG@X&V~GC-+eWf-8]+z,;dW! rptk%#cCu!!LAj(0Am3.5`K]%F(tB+pQp`![I}d-8lu=${hMW%jb]X(o@)@.mu-l#'6#)&2<|~!'-E8&L6?-%C;i7.P=$Q$^POA%S5mH+/%&C(9Zn7.Mfe6.)%G(#$#t|(B![P*Ev6X$Iw/$'Qna'&`U02'E*hq-^Hog)7fs+&Mh}T  (J:,;[O#*<[8=,!yQN-=pCv*%l!a$Cf<v)t%2B%8O*$(N)}C$fS+j&2etG(@a y+)jp(+'-Y[+!4B/-wyNe$&OWZ*7)EF)KIBa&$Ex<%};u` //K,,>`+_#{~gD*#L??!ErSK*aI3~*TaM$%X&-^'2M5' Kdnd*PCa+&8+;{$:6ZK#?(NF*EtHD(#L,l*X+8a%NgBA m;5S,P}Bu#e2DP(lgkd%PMrM+e5cl*V9Me'K=f.'KiSf+0>a5 (QuG#:4Iw _c>1.PHQF&+D(#+y.[=!WsS1)~McG FFyq)oaTT,yG6U,:b^7#`U6M(V&9Y*12V5!sEv-)~9Q?'ua,/&:1=$#2zV+*J74[ jN<2%H)=h q*Ow&o%D^+s4JH$pU $#jFGP)sN+/&=wSE(DXyU',cr;-0U>>.wW.C%0`*.#!3?u!tSB6(n5y9*BCFy(;#{N#tEA4*99~T('pS!+Buey'H|-C(UI'>*m[RB+J3vz%*333#;5t6-?jf+'VZT@-R@;3-D5+F+2L 4'3m*R)o&Xk-n1#U'684&'ke#2'ujLd'HS4a+{`y@!5D|A*r@dB,M]|p+<sdr&rXM+)'tO--Mz`E#Xxf] ~XYk'h;Iq+x'X&+.w C&NxFA,WP;5+4r%L LCd((sDxn&'L@A ,?nj#3q'|&C!Qh#=v&u%2Unh!4TlM#&6O`)4Zg>'U|' (6%0[$~>/@ 0UEN,)3sx+py.H%yl`a*Z%%q&Z4'D*'}(D)r|[h$dXqn'jQ.}(A~^z$mjk%%u[25'0x0^$+ym3(Y,c^ B6_d-b?OU-paGS(`e?^ z8:b#i6<M's>BQ,A]NB%n$iH#'9 y)d$vn$rKRv-n|rW iiPm%0.zP-}N/K&_y1V$,J**'z4k-'#t/`!xl,P$Ne(=- ^[w+-P[L'<3i##Lce6#l`KT'Z+5(-3JRo%wR^w%dXxR%8w:3&pZ/w#02h?$st_/-`jJ>%sJyc#W[b6!R(L_(]=B4 A]:9!ej/z*ZM*[#Iu]L%bac, L5:>!01ak,)~#<+b[G*$kd0s,!i'p!IR@k(hB]J&bS%<-H|[/-lRc2.@%l.%NR^~%NniQ$5R?I$H>Sd,P]iE*#&n{!aZ.,%;p2A#L-5G#GSi_+lrb*)mP(.&Uf;_$Pv(p(Lw+,*t2Yv){&1_-7:Az+{;Ud'k(bO$#Vg$,o,lb!cA-D*1+<4%BcvU%u?LO(=,mu+6 .[ Y(/_ e|kP#W4yl-7qVr f>FM-,r&G%CbBQ%zN@6+qu.[,bI#(.$YOK)*UM$.vFvn&<Zci$>p.f!TW`-+QV%',{u=b#Ajw:-7pI=%u7)?(&.91.Q^YE,+9Ax(2>n4*Wc$I(fVzV(N76;'z{Yp#}xOV!ZsJF&>Vr'#9p]r))%Sk#VMKh#j.VX*&RnR'R0~R&#b|g$k4nr-)Q6.(1Uhr#w$W!&+5?p+9Te?-O}#s$ZZHy#j7xn#n]UC*v@j?&-]vR,x)rB 'oQv#?;l!&z8co+v_$E#Hs,>$60(%*bMqq+~%~R,AUgK,{4[Q!S5{@)mdbc*WO4T(K0;%,X%NF'9y;s&n.M''4O?L)YqC^ +)3e+g3,})Qr*]-I<Xl'J;j?&c.D~,;@cY)Xf0x,bdN(,&J9d$x+}R*=yEA)!?[t(/4Em+&HLs'csy{,Q.7U*6GjF)),@M'X%H<-tt!r'm~U ++JoE&{i1a(H(t#!.mz<#ze3{+&ooi(b%L4 ]W-4 DyZc,,+Zd#1,yR$kiui,*0Y--MqU2.ZEfS%XG'S$o-ky%=|xO+5ns8,/H'`&:!{r)#m&>*sfQ]'[tA0#_S]I%OTf6()P{d-aXC8,3T81#T'|G)nWcS#[x-Y$tc3-,l3J#!@k$U%;9V]&.gGY'KVd$+OO37%:2P~),N+| #NiX'w#Zm!8OY@!Kr</*5,7T)Dz^+-VQ'I-;sDd$,tIt+1~JQ(XZjH&X.xo,BhP- wMCm '~ /.o%7m ?m)C(V=dh+e96!,4,Ae*?NZ^-WD,'*zn%9,SGBA#H5hz,X7Z3(Lpco,VU`^-Y-%U!'|2#+j|.6$Iw~],1DAi$FJl2#S@xR(tk~T)`M$B+Y5jk RPqH$%E(!*U}A;-Xx*>%eOk'+a.;9&~,g'%Is!9+zjY/#rdC)+Ie>E),c/&*V'ca+K W>,|6Aw+ipH2*0:UQ+qZ!l%X>jC*74R,)P{V;$/Jd#)Z2#. qCpf*pT+/+c,,N @T V'r~$= S$AR!Z2/_)>$)p(PETJ'~OGY*2g54+5:ft bNWg-dF{b%AwO,%_eBY'aq^M)Dv|<#kSyU,mk s%26n>-/^Uv-t9nM$KQ&V!#:_r-Wyk0$2(L<)K*wW#Ukwp#fh3I!B9A&)uF9Y+`n'++1#|/$-s3q%BMY2 4%4'+`@KG+oN<A oEF_ b[/@*[ReN,=}z^ W,gR*5S`q*x+w@-h>[h+xz9,!g |,*o'/v#^|+m,tw C#tF2! S]}F!X3t4&M |- $Y-J*wCg4%iJOW(w/OL*q@s] v*;^-j>B]%9Fhh$^BL2'&J0H oFSM#NDbv-j9*:.Ny/8-s;tj,w'p#-!;3=%qz>q'n,,&%v)IZ!+hTx-MyWW'D89$#ToZ4#c]T)*1X)9-z1:,(m+!w*.r2]'igG1(,c@h!Au*%&qLK#%~z'O,qF&%*0Y;~%e}m?,[pk ,}sTc(u1y| F]6i-$vb?,Q||5$2Fy])<EXt#t0%h#sl%% pwmI+)_M~+(=h~()#%[,N[R@*]".toCharArray();

	public static int dec(char[] a, int l){int r=0;for(int j=l+4;j>=l;j--)r=r*93+a[j]-(a[j]+1880)/58;return r;}
	public static long decl(char[] a, int l){long r=0;for(int j=l+9;j>=l;j--)r=r*93+a[j]-(a[j]+1880)/58;return r;}
	public static int[] decs(char[] a){int[] ret=new int[a.length/5];for(int i=0;i*5<a.length;i++)ret[i]=dec(a,i*5);return ret;}
	public static long[] decsl(char[] a){long[] r=new long[a.length/10];for(int i=0;i*10<a.length;i++)for(int j=i*10+4;j>=i*10;j--)r[i]=r[i]*93+a[j]-(a[j]+1880)/58;return r;}

	public static void main(String[] args) {
		new Day24().run();
	}

	public void run()
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new FastWriter(System.out);

		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
		//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
		//			@Override
		//			public void run() {
		//				long s = System.currentTimeMillis();
		//				solve();
		//				out.flush();
		//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
		//			}
		//		};
		//		t.start();
		//		t.join();
	}

	private boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;

		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}

	private final byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	//	private boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }

	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}

	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}

	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}

	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}

		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}

		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	public static class FastWriter
	{
		private static final int BUF_SIZE = 1<<13;
		private final byte[] buf = new byte[BUF_SIZE];
		private final OutputStream out;
		private int ptr = 0;

		private FastWriter(){out = null;}

		public FastWriter(OutputStream os)
		{
			this.out = os;
		}

		public FastWriter(String path)
		{
			try {
				this.out = new FileOutputStream(path);
			} catch (FileNotFoundException e) {
				throw new RuntimeException("FastWriter");
			}
		}

		public FastWriter write(byte b)
		{
			buf[ptr++] = b;
			if(ptr == BUF_SIZE)innerflush();
			return this;
		}

		public FastWriter write(char c)
		{
			return write((byte)c);
		}

		public FastWriter write(char[] s)
		{
			for(char c : s){
				buf[ptr++] = (byte)c;
				if(ptr == BUF_SIZE)innerflush();
			}
			return this;
		}

		public FastWriter write(String s)
		{
			s.chars().forEach(c -> {
				buf[ptr++] = (byte)c;
				if(ptr == BUF_SIZE)innerflush();
			});
			return this;
		}

		private static int countDigits(int l) {
			if (l >= 1000000000) return 10;
			if (l >= 100000000) return 9;
			if (l >= 10000000) return 8;
			if (l >= 1000000) return 7;
			if (l >= 100000) return 6;
			if (l >= 10000) return 5;
			if (l >= 1000) return 4;
			if (l >= 100) return 3;
			if (l >= 10) return 2;
			return 1;
		}

		public FastWriter write(int x)
		{
			if(x == Integer.MIN_VALUE){
				return write((long)x);
			}
			if(ptr + 12 >= BUF_SIZE)innerflush();
			if(x < 0){
				write((byte)'-');
				x = -x;
			}
			int d = countDigits(x);
			for(int i = ptr + d - 1;i >= ptr;i--){
				buf[i] = (byte)('0'+x%10);
				x /= 10;
			}
			ptr += d;
			return this;
		}

		private static int countDigits(long l) {
			if (l >= 1000000000000000000L) return 19;
			if (l >= 100000000000000000L) return 18;
			if (l >= 10000000000000000L) return 17;
			if (l >= 1000000000000000L) return 16;
			if (l >= 100000000000000L) return 15;
			if (l >= 10000000000000L) return 14;
			if (l >= 1000000000000L) return 13;
			if (l >= 100000000000L) return 12;
			if (l >= 10000000000L) return 11;
			if (l >= 1000000000L) return 10;
			if (l >= 100000000L) return 9;
			if (l >= 10000000L) return 8;
			if (l >= 1000000L) return 7;
			if (l >= 100000L) return 6;
			if (l >= 10000L) return 5;
			if (l >= 1000L) return 4;
			if (l >= 100L) return 3;
			if (l >= 10L) return 2;
			return 1;
		}

		public FastWriter write(long x)
		{
			if(x == Long.MIN_VALUE){
				return write("" + x);
			}
			if(ptr + 21 >= BUF_SIZE)innerflush();
			if(x < 0){
				write((byte)'-');
				x = -x;
			}
			int d = countDigits(x);
			for(int i = ptr + d - 1;i >= ptr;i--){
				buf[i] = (byte)('0'+x%10);
				x /= 10;
			}
			ptr += d;
			return this;
		}

		public FastWriter write(double x, int precision)
		{
			if(x < 0){
				write('-');
				x = -x;
			}
			x += Math.pow(10, -precision)/2;
			//		if(x < 0){ x = 0; }
			write((long)x).write(".");
			x -= (long)x;
			for(int i = 0;i < precision;i++){
				x *= 10;
				write((char)('0'+(int)x));
				x -= (int)x;
			}
			return this;
		}

		public FastWriter writeln(char c){
			return write(c).writeln();
		}

		public FastWriter writeln(int x){
			return write(x).writeln();
		}

		public FastWriter writeln(long x){
			return write(x).writeln();
		}

		public FastWriter writeln(double x, int precision){
			return write(x, precision).writeln();
		}

		public FastWriter write(int... xs)
		{
			boolean first = true;
			for(int x : xs) {
				if (!first) write(' ');
				first = false;
				write(x);
			}
			return this;
		}

		public FastWriter write(long... xs)
		{
			boolean first = true;
			for(long x : xs) {
				if (!first) write(' ');
				first = false;
				write(x);
			}
			return this;
		}

		public FastWriter writeln()
		{
			return write((byte)'\n');
		}

		public FastWriter writeln(int... xs)
		{
			return write(xs).writeln();
		}

		public FastWriter writeln(long... xs)
		{
			return write(xs).writeln();
		}

		public FastWriter writeln(char[] line)
		{
			return write(line).writeln();
		}

		public FastWriter writeln(char[]... map)
		{
			for(char[] line : map)write(line).writeln();
			return this;
		}

		public FastWriter writeln(String s)
		{
			return write(s).writeln();
		}

		private void innerflush()
		{
			try {
				out.write(buf, 0, ptr);
				ptr = 0;
			} catch (IOException e) {
				throw new RuntimeException("innerflush");
			}
		}

		public void flush()
		{
			innerflush();
			try {
				out.flush();
			} catch (IOException e) {
				throw new RuntimeException("flush");
			}
		}

		public FastWriter print(byte b) { return write(b); }
		public FastWriter print(char c) { return write(c); }
		public FastWriter print(char[] s) { return write(s); }
		public FastWriter print(String s) { return write(s); }
		public FastWriter print(int x) { return write(x); }
		public FastWriter print(long x) { return write(x); }
		public FastWriter print(double x, int precision) { return write(x, precision); }
		public FastWriter println(char c){ return writeln(c); }
		public FastWriter println(int x){ return writeln(x); }
		public FastWriter println(long x){ return writeln(x); }
		public FastWriter println(double x, int precision){ return writeln(x, precision); }
		public FastWriter print(int... xs) { return write(xs); }
		public FastWriter print(long... xs) { return write(xs); }
		public FastWriter println(int... xs) { return writeln(xs); }
		public FastWriter println(long... xs) { return writeln(xs); }
		public FastWriter println(char[] line) { return writeln(line); }
		public FastWriter println(char[]... map) { return writeln(map); }
		public FastWriter println(String s) { return writeln(s); }
		public FastWriter println() { return writeln(); }
	}

	public static void trnz(int... o)
	{
		for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" ");
		System.out.println();
	}

	// print ids which are 1
	public static void trt(long... o)
	{
		Queue<Integer> stands = new ArrayDeque<>();
		for(int i = 0;i < o.length;i++){
			for(long x = o[i];x != 0;x &= x-1)stands.add(i<<6|Long.numberOfTrailingZeros(x));
		}
		System.out.println(stands);
	}

	public static void tf(boolean... r)
	{
		for(boolean x : r)System.out.print(x?'#':'.');
		System.out.println();
	}

	public static void tf(boolean[]... b)
	{
		for(boolean[] r : b) {
			for(boolean x : r)System.out.print(x?'#':'.');
			System.out.println();
		}
		System.out.println();
	}

	public void tf(long[]... b)
	{
		if(INPUT.length() != 0) {
			for (long[] r : b) {
				for (long x : r) {
					for (int i = 0; i < 64; i++) {
						System.out.print(x << ~i < 0 ? '#' : '.');
					}
				}
				System.out.println();
			}
			System.out.println();
		}
	}

	public void tf(long... b)
	{
		if(INPUT.length() != 0) {
			for (long x : b) {
				for (int i = 0; i < 64; i++) {
					System.out.print(x << ~i < 0 ? '#' : '.');
				}
			}
			System.out.println();
		}
	}

	private void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
0