結果

問題 No.950 行列累乗
ユーザー uwiuwi
提出日時 2019-12-13 22:56:28
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 18,720 bytes
コンパイル時間 4,680 ms
コンパイル使用メモリ 94,144 KB
実行使用メモリ 44,872 KB
最終ジャッジ日時 2024-06-27 19:52:55
合計ジャッジ時間 10,857 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 95 ms
39,712 KB
testcase_02 AC 50 ms
36,796 KB
testcase_03 AC 51 ms
37,128 KB
testcase_04 AC 50 ms
36,960 KB
testcase_05 AC 96 ms
39,276 KB
testcase_06 AC 52 ms
37,172 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 51 ms
37,048 KB
testcase_10 WA -
testcase_11 AC 51 ms
36,920 KB
testcase_12 AC 51 ms
37,152 KB
testcase_13 AC 51 ms
36,924 KB
testcase_14 AC 51 ms
36,912 KB
testcase_15 AC 50 ms
37,092 KB
testcase_16 AC 49 ms
36,920 KB
testcase_17 WA -
testcase_18 AC 51 ms
36,800 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 49 ms
36,772 KB
testcase_22 WA -
testcase_23 AC 114 ms
39,484 KB
testcase_24 AC 50 ms
36,660 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 50 ms
37,160 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 51 ms
36,780 KB
testcase_31 AC 103 ms
39,332 KB
testcase_32 TLE -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package adv2019;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;

/**
 * 
 * 固有値にF[p]の外の値が出てきたときの拡大体での離散対数問題が解けない
 */
public class D13_2 {
	InputStream is;
	PrintWriter out;
//	String INPUT = "3\n" + 
//			"1 2 1 0 \n" + 
//			"2 1 2 0";
	String INPUT = "";
	
	// (a-L, b), (c, d-L)
	// (a-L)(d-L) - bc = 0
	// L^2-(a+d)L + ad-bc = 0
	
	// D = (a+d)^2 - 4(ad-bc)
	
	int[][] trans(long[][] M, int p)
	{
		int n = M.length, m = M[0].length;
		int[][] ret = new int[n][m];
		for(int i = 0;i < n;i++) {
			for(int j = 0;j < m;j++) {
				ret[i][j] = (int)(M[i][j] % p);
			}
		}
		return ret;
	}
	
	int[][] inv(int[][] M, int p)
	{
		long D = (long)M[0][0]*M[1][1] - (long)M[0][1] * M[1][0];
		D %= p;
		if(D < 0)D += p;
		if(D == 0)return null;
		long ID = invl(D, p);
		
		return new int[][] {
			{(int)(ID*M[1][1]%p), (int)(ID*(p-M[0][1])%p)},
			{(int)(ID*(p-M[1][0])%p), (int)(ID*M[0][0]%p)}
		};
	}
	
	long[][][] inv(long[][][] S, int p, int E)
	{
		long[][][] ret = new long[][][] {
			{S[1][1], neg(S[0][1], p)},
			{neg(S[1][0], p), S[0][0]}
		};
		long[] D = inv(add(mul(S[1][1], S[0][0], p, E), neg(mul(S[0][1], S[1][0], p, E), p), p), p, E);
		for(int i = 0;i < 2;i++) {
			for(int j = 0;j < 2;j++) {
				ret[i][j] = mul(ret[i][j], D, p, E);
			}
		}
		return ret;
	}
	
	long[][][] mul(long[][][] a, long[][][] b, int p, int E)
	{
		long[][][] c = new long[2][2][];
		for(int i = 0;i < 2;i++) {
			for(int j = 0;j < 2;j++) {
				long[] sum = {0, 0};
				for(int k = 0;k < 2;k++) {
					sum = add(sum, mul(a[i][k], b[k][j], p, E), p);
				}
				c[i][j] = sum;
			}
		}
		return c;
	}
	
	long[] inv(long[] a, int p, int E)
	{
		// 1/(a+bS(E))
		// (a-bS(E))/(a^2-b^2*E)
		long den = a[0]*a[0]-a[1]*a[1]%p*E;
		den %= p;
		if(den < 0)den += p;
		long iden = invl(den, p);
		return new long[] {a[0]*iden%p, a[1]*iden%p};
	}
	
	long[] add(long[] a, long[] b, int p)
	{
		return new long[] {
				(a[0]+b[0]) % p,
				(a[1]+b[1]) % p
		};
	}
	
	long[] mul(long[] a, long[] b, int p, int E)
	{
		return new long[] {
				(a[0]*b[0] + a[1]*b[1]%p*E)%p,
				(a[0]*b[1] + a[1]*b[0])%p
		};
	}
	
	long[] pow(long[] a, long e, int p, int E)
	{
		long[] ret = {1L, 0L};
		for(int i = 64-Long.numberOfLeadingZeros(e);i >= 0;i--) {
			ret = mul(ret, ret, p, E);
			if(e<<~i<0) {
				ret = mul(ret, a, p, E);
			}
		}
		return ret;
	}
	
	long[] neg(long[] x, int p)
	{
		return new long[] {(p-x[0])%p, (p-x[1])%p};
	}
	
	long solve(int[][] A, int[][] B, int p)
	{
		long a = A[0][0], b = A[0][1], c = A[1][0], d = A[1][1];
		
//		if((a*d - b*c) % p == 0){
//			// rank <= 1
//			
//		}
		
		long i2 = invl(2, p);
		long D = (a-d)*(a-d) + 4*b*c;
		D %= p;
		
		// (a+b√c) * (d+e√c)
		// (d e)
		// (e dc)
		
		// (a 1)
		// (1 b)
		
		// d = (a'+d')/2, c = (a'-d')^2+4bc
		// d^2(c-1)^2+4
		if(D == 0) {
			// x = (a+d)/2の重解
			long x = (a+d)*i2 % p;
			// ジョルダン標準形
			// (a b)(s t) = (s t)(x 1)
			// (c d)(u v)   (u v)(0 x)
			// を解く
			for(int y : new int[] {0, p-1}) {
				for(int k = 0;k < 4;k++) {
					long[][] LM = {
							{a+p-x, 0, b, 0},
							{y, a+p-x, 0, b},
							{c, 0, d+p-x, 0},
							{0, c, y, d+p-x},
							{0, 0, 0, 0},
					};
					LM[4][k] = 1;
					int[] v = {0, 0, 0, 0, 1};
					int[][] M = trans(LM, p);
					Result res = gaussElimination(M, v, p);
					if(res.exists) {
						if(((long)res.sol[0]*res.sol[3] - (long)res.sol[2]*res.sol[1]) % p != 0) {
							int[][] S = {
									{res.sol[0], res.sol[1]},
									{res.sol[2], res.sol[3]}
							};
							int[][] IS = inv(S, p);
							int[][] XB = mul(mul(IS, B, p), S, p);
							// J^n = (x^n (p-y)*n*x^(n-1))
							//       (0 x^n)
							if(XB[0][0] != XB[1][1] ||
									XB[1][0] != 0) {
								return -1;
							}else {
								if(y == 0) {
									return bsgs(x, XB[0][0], p);
								}else {
									// x^n = A
									// n*x^(n-1) = B
									// n*(A/x) = B
									// n = B*x/A (mod p)
									// x^(nn + k*p) = A
									// x^p = x
									long nn = XB[0][1] * x % p * invl(XB[0][0], p) % p;
									
									long ret = bsgs(
											x,
											XB[0][0]*invl(pow(x, nn, p), p)%p, 
											p);
									if(ret == -1)return -1;
									return nn + ret * p;
								}
							}
						}
					}
				}
			}
			return -1;
		}
		
		long sq = sqrt(D, p, new Random());
		if(sq == -1) {
			// F_p上で解を持たないことがあるので、√Dで体の拡大をする
			// が最終的にa+b√cの形の離散対数問題を解かないといけなくなり、これがわからない
			long[] alpha = {(a+d)*i2 % p, p-i2};
			long[] beta = {(a+d)*i2 % p, i2};
			
			long[][][] S = {
					{{b, 0},{b, 0}},
					{{alpha[0]-a, alpha[1]}, {beta[0]-a, beta[1]}}
			};
			
			/*
(b ((a + sqrt(c)) s - b u) + (a - sqrt(c)) ((a + sqrt(c)) t - b v) | b ((a + sqrt(c)) s - b u) + (a + sqrt(c)) ((a + sqrt(c)) t - b v)
b ((sqrt(c) - a) s + b u) + (a - sqrt(c)) ((sqrt(c) - a) t + b v) | b ((sqrt(c) - a) s + b u) + (a + sqrt(c)) ((sqrt(c) - a) t + b v))			 * 
			 */
			
			// (b b)
			// (a-√c-d, a+√c-d)
			
			// 1/(b(a+√c-d)-b(a-√c-d))
			// (a+√c-d -b)
			// (-a+√c+d b)
			
			// 1/(2b√c)
			// (a+√c-d -b)(s t)(b b)
			// (-a+√c+d b)(u v)(a-√c-d a+√c-d)
			
			long[][][] IS = inv(S, p, (int)D);
			long[][][] BB = {
					{{B[0][0], 0}, {B[0][1], 0}},
					{{B[1][0], 0}, {B[1][1], 0}}
			};
			
			long[][][] XB = mul(mul(IS, BB, p, (int)D), S, p, (int)D);
		
			if(XB[0][1][0] != 0)return -1;
			if(XB[0][1][1] != 0)return -1;
			if(XB[1][0][0] != 0)return -1;
			if(XB[1][0][1] != 0)return -1;
			
			// alpha^n = XB[0][0]
			// beta^n = XB[1][1]
			
			if(XB[0][0][0] != XB[1][1][0])return -1;
			if((XB[0][0][1] + XB[1][1][1]) % p != 0)return -1;
			
			// a+b√cの周期はp^2-1の約数
			// b=0のもそこそこの周期でまざっている
			long p2m = (long)p*p-1;
			int[] primes = sieveEratosthenes(100000);
			int[] pm = facs(p-1, primes);
			int[] pp = facs(p-1, primes);
			long x = p2m;
//			tr(XB[0][0], x, D, pow(XB[0][0], x, p, (int)D));
			assert Arrays.equals(pow(XB[0][0], x, p, (int)D), new long[] {1, 0});
			long y = p2m;
			for(int u : pm) {
				while(x % u == 0) {
					long[] o = pow(XB[0][0], x/u, p, (int)D);
					if(o[1] == 0) {
						if(o[0] == 1)y /= u;
						x /= u;
					}else {
						break;
					}
				}
			}
			for(int u : pp) {
				while(x % u == 0) {
					long[] o = pow(XB[0][0], x/u, p, (int)D);
					if(o[1] == 0) {
						if(o[0] == 1)y /= u;
						x /= u;
					}else {
						break;
					}
				}
			}
//			tr(p2m);
//			tr("x", x, y);
			return -1;

//			solve(new int[][] {
//				{(int)((a+d)*i2 % p), 1}, (int)i2}
//				{(int)i2, (int)((a+d)*i2 % p* D % p)}
//			}, new int[][]{
//				{(int)XB[0][0][0], (int)XB[0][0][1]}, 
//				{(int)XB[1][1][0], (int)XB[0][0][1]}, 
//			});
			
//			long ret1 = bsgs(
//					
//					x,
//					XB[0][0]*invl(pow(x, nn, p), p)%p, 
//					p);
		}else {
			// F_p上で解を持つ場合
			long alpha = (a+d+p-sq)*i2 % p;
			long beta = (a+d+sq)*i2 % p;
			
			int[][] S = {
					{(int)b, (int)b},
					{(int)((alpha+p-a)%p), (int)((beta+p-a)%p)}
			};
			long dd = (long)S[0][0] * S[1][1] - (long)S[0][1] * S[1][0];
			dd %= p;
			if(dd < 0)dd += p;
			long idd = invl(dd, p);
			int[][] IS = {
					{(int)(S[1][1]*idd%p), (int)((p-S[0][1])*idd%p)},
					{(int)((p-S[1][0])*idd%p), (int)(S[0][0]*idd%p)}
			};
			int[][] XB = mul(mul(IS, B, p), S, p);
			if(XB[0][1] != 0)return -1;
			if(XB[1][0] != 0)return -1;
			long e0 = bsgs(alpha, XB[0][0], p);
			long e1 = bsgs(beta, XB[1][1], p);
			if(e0 == e1)return e0;
			return -1;
		}
		
		// (alpha-a b)
		// (c alpha-d)
		
//		long sq = sqrt(D, p, new Random());
//		if(sq == -1)return null;
//		if(c != 0) {
//			long idc = invl(2*c%p, p);
//			int[][] S = {
//					{(int)(((long)p-a+d+sq)*idc%p), (int)(((long)p+a-d+sq)*idc%p)},
//					{1, 1}
//			};
//			long isq = invl(sq, p);
//			long disq = invl(2*sq%p, p);
//			int[][] IS = {
//					{(int)((p-c) * isq%p), (int)(((long)p+a-d+sq)*disq%p)},
//					{(int)((c) * isq%p), (int)(((long)p-a+d+sq)*disq%p)}
//			};
//			return new Diag(S, IS, 
//					((long)p+a+d-sq)*invl(2,p)%p,
//					((long)p+a+d+sq)*invl(2,p)%p
//				);
//		}else if(a-d != 0) {
//			long iad = invl((a+p-d)%p, p);
//			int[][] S = {
//					{1, (int)((p-b)*iad%p)},
//					{0, 1}
//			};
//			int[][] IS = {
//					{1, (int)((b)*iad%p)},
//					{0, 1}
//			};
//			return new Diag(S, IS, a, d);
//		}else {
//			return null;
//		}
	}
	
	public static int[] sieveEratosthenes(int n) {
		if (n <= 32) {
			int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
			for (int i = 0; i < primes.length; i++) {
				if (n < primes[i]) {
					return Arrays.copyOf(primes, i);
				}
			}
			return primes;
		}

		int u = n + 32;
		double lu = Math.log(u);
		int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
		ret[0] = 2;
		int pos = 1;

		int[] isnp = new int[(n + 1) / 32 / 2 + 1];
		int sup = (n + 1) / 32 / 2 + 1;

		int[] tprimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
		for (int tp : tprimes) {
			ret[pos++] = tp;
			int[] ptn = new int[tp];
			for (int i = (tp - 3) / 2; i < tp << 5; i += tp)
				ptn[i >> 5] |= 1 << (i & 31);
			for (int j = 0; j < sup; j += tp) {
				for (int i = 0; i < tp && i + j < sup; i++) {
					isnp[j + i] |= ptn[i];
				}
			}
		}

		// 3,5,7
		// 2x+3=n
		int[] magic = { 0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17,
				9, 6, 16, 5, 15, 14 };
		int h = n / 2;
		for (int i = 0; i < sup; i++) {
			for (int j = ~isnp[i]; j != 0; j &= j - 1) {
				int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
				int p = 2 * pp + 3;
				if (p > n)
					break;
				ret[pos++] = p;
				if ((long) p * p > n)
					continue;
				for (int q = (p * p - 3) / 2; q <= h; q += p)
					isnp[q >> 5] |= 1 << q;
			}
		}

		return Arrays.copyOf(ret, pos);
	}
	
	public static int[] facs(int n, int[] primes)
	{
		int[] ret = new int[9];
		int rp = 0;
		for(int p : primes){
			if(p * p > n)break;
			int i;
			for(i = 0;n % p == 0;n /= p, i++);
			if(i > 0)ret[rp++] = p;
		}
		if(n != 1)ret[rp++] = n;
		return Arrays.copyOf(ret, rp);
	}


	
	public static Result gaussElimination(int[][] M, int[] v, int mod)
	{
		int n = M.length, m = M[0].length;
		int[] head = new int[n];
		
		// if not needed, comment out.
		for(int[] row : M){
			for(int i = 0;i < row.length;i++){
				row[i] %= mod;
				if(row[i] < 0)row[i] += mod;
			}
		}
		
		// Forward Elimination
		int row = 0;
		for(int col = 0;col < m;col++){
			// select pivot
			boolean pivotFound = false;
			out:
			for(int prow = row;prow < n;prow++){
				if(M[prow][col] != 0){
					// pivot found
					if(prow != row){
						// swap rows
						for(int k = 0;k < m;k++){
							int u = M[prow][k]; M[prow][k] = M[row][k]; M[row][k] = u;
						}
						int dum = v[prow]; v[prow] = v[row]; v[row] = dum;
					}
					pivotFound = true;
					break out;
				}
			}
			if(!pivotFound)continue;
			head[row] = col;
			
			// diag to 1
			long imul = invl(M[row][col], mod);
			for(int k = 0;k < m;k++){
				M[row][k] = (int)(M[row][k] * imul % mod);
			}
			v[row] = (int)(v[row] * imul % mod);
			
			for(int j = row+1;j < n;j++){
				if(M[j][col] != 0){
					long mul = mod-M[j][col];
					for(int k = col;k < m;k++){
						M[j][k] = (int)((M[j][k] + M[row][k] * mul) % mod);
					}
					v[j] = (int)((v[j] + v[row] * mul) % mod);
				}
			}
			row++;
		}
		
		Result ret = new Result();
		ret.mat = M;
		for(int i = row;i < n;i++){
			if(v[i] != 0){
				ret.rank = row;
				ret.exists = false;
				return ret;
			}
		}
		
		for(int i = row-1;i >= 0;i--){
			for(int j = i-1;j >= 0;j--){
				if(M[j][head[i]] != 0){
					long mul = mod-M[j][head[i]];
					for(int k = head[i];k < m;k++){
						M[j][k] = (int)((M[j][k] + M[i][k] * mul) % mod);
					}
					v[j] = (int)((v[j] + v[i] * mul) % mod);
				}
			}
		}
		
		int[] retv = new int[m];
		for(int i = 0;i < row;i++){
			retv[head[i]] = v[i];
		}
		
		ret.sol = retv;
		ret.rank = row;
		ret.exists = true;
		return ret;
	}
	
	public static class Result
	{
		public int[][] mat;
		public int[] sol;
		public int rank;
		public boolean exists;
	}

	
	public static long pow(long a, long n, long mod) {
		//		a %= mod;
		long ret = 1;
		int x = 63 - Long.numberOfLeadingZeros(n);
		for (; x >= 0; x--) {
			ret = ret * ret % mod;
			if (n << 63 - x < 0)
				ret = ret * a % mod;
		}
		return ret;
	}

	
	public static long sqrt(long n, int p, Random gen)
	{
		if(pow(n, (p-1)/2, p) != 1)return -1;
		
		int S = Integer.numberOfTrailingZeros(p-1);
		long Q = p-1>>>S;
		if(S == 1){
			return pow(n, (p+1)/4, p);
		}
		
		int z = 0;
		do{
			z = gen.nextInt(p-1)+1;
		}while(pow(z, (p-1)/2, p) != p-1);
		
		long c = pow(z, Q, p);
		long R = pow(n, (Q+1)/2, p);
		long t = pow(n, Q, p);
		int M = S;
		while(t != 1){
			long u = t;
			for(int i = 1;i < M;i++){
				u = u * u % p;
//				U.tr(i, t, u);
				if(u == 1){
					long b = c;
					for(int j = 0;j < M-i-1;j++){
						b = b * b % p;
					}
					R = R * b % p;
					t = t * b % p * b % p;
					c = b * b % p;
					M = i;
					break;
				}
			}
		}
		return R;
	}

	
	void solve()
	{
		int mod = ni();
		int[][] a = new int[2][2];
		int[][] b = new int[2][2];
		for(int i = 0;i < 2;i++) {
			a[i] = na(2);
		}
		for(int i = 0;i < 2;i++) {
			b[i] = na(2);
		}
		
		int[][] e = {{1, 0}, {0, 1}};
		outer:
		for(int i = 1;i <= 20;i++) {
			e = mul(e, a, mod);
			for(int j = 0;j < 2;j++) {
				for(int k = 0;k < 2;k++) {
					if(e[j][k] != b[j][k])continue outer;
				}
			}
			out.println(i);
			return;
		}
		if(mod == 2) {
			out.println(-1);
			return;
		}
		
		out.println(solve(a, b, mod));
	}
	
	public static long bsgs(long alpha, long beta, int p)
	{
		int m = (int)Math.sqrt(p)+1;
		long[] table = new long[m];
		long val = 1;
		for(int j = 0;j < m;j++){
			table[j] = val<<32|j;
			val = val * alpha % p;
		}
		Arrays.sort(table);
		long ainvm = invl(val, p);
		
		long g = beta;
		for(int i = 0;i < m;i++){
			int ind = Arrays.binarySearch(table, g<<32);
			if(ind < 0)ind = -ind-1;
			if(ind < m && table[ind]>>>32 == g){
				if((long)i*m+(int)table[ind] == 0)continue;
				return i*m+(int)table[ind];
			}
			g = g * ainvm % p;
		}
		return -1;
	}
	
	public static long invl(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}

	
	public static int[][] mul(int[][] A, int[][] B, int mod)
	{
		assert A[0].length == B.length;
		int m = A.length;
		int n = A[0].length;
		int o = B[0].length;
		int[][] C = new int[m][o];
		for(int i = 0;i < m;i++){
			for(int j = 0;j < o;j++){
				long sum = 0;
				for(int k = 0;k < n;k++){
					sum += (long)A[i][k] * B[k][j];
					sum %= mod;
				}
				C[i][j] = (int)sum;
			}
		}
		return C;
	}

	
	public static int[] pow(int[][] A, int[] v, long e, int mod)
	{
		int[][] MUL = A;
		for(int i = 0;i < v.length;i++)v[i] %= mod;
		for(;e > 0;e>>>=1) {
			if((e&1)==1)v = mul(MUL, v, mod);
			MUL = p2(MUL, mod);
		}
		return v;
	}
	
	
	// int matrix * int vector
	public static int[] mul(int[][] A, int[] v, int mod)
	{
		int m = A.length;
		int n = v.length;
		int[] w = new int[m];
		for(int i = 0;i < m;i++){
			long sum = 0;
			for(int k = 0;k < n;k++){
				sum += (long)A[i][k] * v[k];
				sum %= mod;
			}
			w[i] = (int)sum;
		}
		return w;
	}
	
	// int matrix^2 (cannot ensure negative values)
	public static int[][] p2(int[][] A, int mod)
	{
		int n = A.length;
		int[][] C = new int[n][n];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				long sum = 0;
				for(int k = 0;k < n;k++){
					sum += (long)A[i][k] * A[k][j];
					sum %= mod;
				}
				C[i][j] = (int)sum;
			}
		}
		return C;
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-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();
	}
	
	public static void main(String[] args) throws Exception { new D13_2().run(); }
	
	private 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 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))){ // when nextLine, (isSpaceChar(b) && 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 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 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[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	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();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0