結果
| 問題 | No.950 行列累乗 |
| ユーザー |
 uwi
|
| 提出日時 | 2019-12-13 22:56:28 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 18,720 bytes |
| コンパイル時間 | 4,845 ms |
| コンパイル使用メモリ | 84,980 KB |
| 実行使用メモリ | 58,232 KB |
| 最終ジャッジ日時 | 2023-09-10 04:10:12 |
| 合計ジャッジ時間 | 11,544 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 95 ms
53,252 KB |
| testcase_02 | AC | 42 ms
49,612 KB |
| testcase_03 | AC | 41 ms
49,608 KB |
| testcase_04 | AC | 40 ms
49,428 KB |
| testcase_05 | AC | 97 ms
53,760 KB |
| testcase_06 | AC | 42 ms
49,584 KB |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | AC | 43 ms
49,560 KB |
| testcase_10 | WA | - |
| testcase_11 | AC | 44 ms
49,684 KB |
| testcase_12 | AC | 43 ms
49,612 KB |
| testcase_13 | AC | 45 ms
49,632 KB |
| testcase_14 | AC | 45 ms
49,720 KB |
| testcase_15 | AC | 42 ms
49,492 KB |
| testcase_16 | AC | 42 ms
49,620 KB |
| testcase_17 | WA | - |
| testcase_18 | AC | 42 ms
49,648 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | AC | 42 ms
49,372 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 118 ms
53,932 KB |
| testcase_24 | AC | 43 ms
49,612 KB |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | AC | 41 ms
49,548 KB |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 42 ms
49,728 KB |
| testcase_31 | AC | 98 ms
53,788 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 | -- | - |
ソースコード
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)); }
}