結果
| 問題 | No.2129 Perfect Binary Tree...? |
| ユーザー |
 遭難者
|
| 提出日時 | 2022-10-27 22:20:33 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 870 ms / 3,000 ms |
| コード長 | 40,251 bytes |
| コンパイル時間 | 3,560 ms |
| コンパイル使用メモリ | 89,884 KB |
| 実行使用メモリ | 91,580 KB |
| 最終ジャッジ日時 | 2023-09-22 10:35:58 |
| 合計ジャッジ時間 | 15,545 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 61 ms
52,492 KB |
| testcase_01 | AC | 44 ms
51,036 KB |
| testcase_02 | AC | 60 ms
52,416 KB |
| testcase_03 | AC | 86 ms
58,996 KB |
| testcase_04 | AC | 116 ms
59,992 KB |
| testcase_05 | AC | 59 ms
52,600 KB |
| testcase_06 | AC | 265 ms
66,044 KB |
| testcase_07 | AC | 307 ms
65,692 KB |
| testcase_08 | AC | 384 ms
80,112 KB |
| testcase_09 | AC | 539 ms
80,932 KB |
| testcase_10 | AC | 61 ms
52,596 KB |
| testcase_11 | AC | 275 ms
60,104 KB |
| testcase_12 | AC | 522 ms
82,148 KB |
| testcase_13 | AC | 719 ms
91,580 KB |
| testcase_14 | AC | 606 ms
88,512 KB |
| testcase_15 | AC | 521 ms
86,900 KB |
| testcase_16 | AC | 870 ms
87,996 KB |
| testcase_17 | AC | 156 ms
59,416 KB |
| testcase_18 | AC | 96 ms
59,636 KB |
| testcase_19 | AC | 171 ms
61,544 KB |
| testcase_20 | AC | 183 ms
61,596 KB |
| testcase_21 | AC | 163 ms
61,672 KB |
| testcase_22 | AC | 156 ms
61,432 KB |
| testcase_23 | AC | 507 ms
86,848 KB |
| testcase_24 | AC | 507 ms
87,088 KB |
| testcase_25 | AC | 414 ms
69,744 KB |
| testcase_26 | AC | 110 ms
59,640 KB |
| testcase_27 | AC | 346 ms
65,568 KB |
| testcase_28 | AC | 467 ms
83,588 KB |
| testcase_29 | AC | 387 ms
84,184 KB |
| testcase_30 | AC | 560 ms
86,868 KB |
| testcase_31 | AC | 546 ms
83,120 KB |
ソースコード
import java.util.*;
import java.io.*;
class Main {
private static final void solve() throws IOException {
final int n = ni(), nn = n << 1;
final int mod = 998244353;
var two = new long[nn + 1];
two[0] = 1L;
for (int i = 1; i <= nn; i++) {
two[i] = two[i - 1] << 1;
if (two[i] >= mod)
two[i] -= mod;
}
var f = new long[n + 1];
for (int i = 1; i <= n; i++) {
f[i] = (i + 3) * two[i] + (i - 3) * two[i << 1];
f[i] %= mod;
}
var g = new long[n + 1];
for (int i = 1; i <= n; i++) {
g[i] = (i - 2) * two[i] + 2;
g[i] %= mod;
}
var u = sc.nextCharArray();
var v = sc.nextCharArray();
boolean same = u.length == v.length;
for (int i = 0, max = Math.min(u.length, v.length); same && i < max; i++)
same &= u[i] == v[i];
if (same) {
ou.println(f[n]);
return;
}
int lca = 0;
for (int i = 0, max = Math.min(u.length, v.length); i < max; i++) {
if (u[i] != v[i])
break;
lca++;
}
final int m = u.length + v.length - 2 * lca + 1;
var p = new int[m];
p[0] = u.length;
int cnt = 0;
while (p[cnt] != lca) {
p[cnt + 1] = p[cnt] - 1;
cnt++;
}
final int lca_cnt = cnt;
while (cnt != m - 1) {
p[cnt + 1] = p[cnt] + 1;
cnt++;
}
for (int i = 0; i < m; i++)
p[i]--;
var a = new long[m];
a[0] = two[n - p[0]] - 1;
a[m - 1] = two[n - p[m - 1]] - 1;
a[lca_cnt] = 0L;
for (int k = 1, d = p[lca_cnt]; k <= d; k++)
a[lca_cnt] += two[n - k];
if (lca_cnt == 0 || lca_cnt == m - 1)
a[lca_cnt] += two[n - p[lca_cnt] - 1] - 1;
a[lca_cnt]++;
a[lca_cnt] %= mod;
for (int i = 1; i < m - 1; i++) {
if (i == lca_cnt)
continue;
a[i] = two[n - 1 - p[i]];
}
var b = new long[m];
b[0] = g[n - p[0]];
b[m - 1] = g[n - p[m - 1]];
b[lca_cnt] = 0L;
for (int k = 1, d = p[lca_cnt]; k <= d; k++)
b[lca_cnt] += g[n - k] + (two[n - k] - 1) * (d + 2 - k) % mod + k;
if (lca_cnt == 0 || lca_cnt == m - 1)
b[lca_cnt] += g[n - p[lca_cnt] - 1] + two[n - p[lca_cnt] - 1] - 1;
b[lca_cnt] %= mod;
for (int i = 1; i < m - 1; i++) {
if (i == lca_cnt)
continue;
b[i] = g[n - 1 - p[i]] + two[n - 1 - p[i]] - 1;
b[i] %= mod;
}
var c = new long[m];
c[0] = f[n - p[0]];
c[m - 1] = f[n - p[m - 1]];
c[lca_cnt] = 0L;
for (int k = 1, d = p[lca_cnt]; k <= d; k++) {
c[lca_cnt] += f[n - k];
c[lca_cnt] += g[n - k] * (a[lca_cnt] - two[n - k] + 1) % mod;
c[lca_cnt] += (two[n - k] - 1) * (a[lca_cnt] - two[n - k] + 1) % mod;
c[lca_cnt] += (two[n] - two[n - k]) * (a[lca_cnt] - two[n] + two[n - k]) % mod;
c[lca_cnt] %= mod;
}
if (lca_cnt == 0 || lca_cnt == m - 1) {
c[lca_cnt] += f[n - p[lca_cnt] - 1];
c[lca_cnt] += g[n - p[lca_cnt] - 1] * (a[lca_cnt] - two[n - p[lca_cnt] - 1] + 1) % mod;
c[lca_cnt] += (two[n - p[lca_cnt] - 1] - 1) * (a[lca_cnt] - two[n - p[lca_cnt] - 1] + 1) % mod;
c[lca_cnt] %= mod;
}
for (int i = 1; i < m - 1; i++) {
if (i == lca_cnt)
continue;
c[i] = f[n - 1 - p[i]] + g[n - 1 - p[i]] + two[n - 1 - p[i]] - 1;
c[i] %= mod;
}
long sum_a = 0L, sum_b = 0L, sum_c = 0L, sum_ab = 0L;
for (long i : a)
sum_a += i;
sum_a %= mod;
for (long i : b)
sum_b += i;
sum_b %= mod;
for (long i : c)
sum_c += i;
sum_c %= mod;
for (int i = 0; i < m; i++)
sum_ab += a[i] * b[i] % mod;
sum_ab %= mod;
long ans = sum_c + sum_a * sum_b - sum_ab;
ans %= mod;
var aa = new long[m];
for (int i = 0; i < m; i++)
aa[m - 1 - i] = a[i];
var tt = new ConvolutionNTTPrime(ModArithmetic998244353.INSTANCE).convolution(a, aa);
long sum = 0L;
for (int j = 1; j < m; j++)
sum += Math.min(j, m - j) * (tt[m - 1 - j] + tt[2 * m - 1 - j]) % mod;
sum %= mod;
if (sum % 2 != 0)
sum += mod;
sum /= 2;
ans += sum;
ans %= mod;
if (ans < 0)
ans += mod;
ou.println(ans);
}
static abstract class Convolution {
static final int NAIVE_THRESHOLD = 128;
public final ModArithmetic MA;
public Convolution(ModArithmetic MA) {
this.MA = MA;
}
public abstract long[] convolution(long[] a, long[] b, int deg);
public final long[] convolution(long[] a, long[] b) {
return convolution(a, b, Const.IINF);
}
public final long[] convolutionNaive(long[] a, long[] b, int n, int m) {
int k = n + m - 1;
long[] ret = new long[k];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ret[i + j] += MA.mul(a[i], b[j]);
for (int i = 0; i < k; i++)
ret[i] = MA.mod(ret[i]);
return ret;
}
}
static class ConvolutionNTTPrime extends Convolution {
public final int primitiveRoot;
private final int maxLog;
private final long[] ws;
private final long[] iws;
public ConvolutionNTTPrime(ModArithmetic MA) {
super(MA);
this.primitiveRoot = primitiveRoot(MA);
long m1 = MA.getMod() - 1;
this.maxLog = Long.numberOfTrailingZeros(m1 & -m1);
this.ws = new long[maxLog + 1];
this.iws = new long[maxLog + 1];
Arrays.setAll(ws, i -> MA.pow(primitiveRoot, m1 >> i));
Arrays.setAll(iws, i -> MA.inv(ws[i]));
}
public long[] convolution(long[] a, long[] b, int deg) {
int n = Math.min(deg + 1, a.length);
int m = Math.min(deg + 1, b.length);
if (n + m - 1 <= NAIVE_THRESHOLD)
return convolutionNaive(a, b, n, m);
int log = ceilLog2(n + m - 1);
assert log <= this.maxLog;
int l = 1 << log;
a = fft(copyOfRange(a, n, l), log);
b = fft(copyOfRange(b, m, l), log);
long[] c = new long[l];
for (int i = 0; i < l; i++)
c[i] = MA.mul(a[i], b[i]);
c = ifft(c, log);
long inv = MA.inv(l);
for (int i = 0; i < l; i++)
c[i] = MA.mul(c[i], inv);
return c;
}
private long[] fft(long[] a, int log) {
int n = a.length;
for (int p = log; p > 0; p--) {
int block = 1 << p;
int halfBlock = block >> 1;
long w = ws[p];
for (int l = 0; l < n; l += block) {
int m = l + halfBlock;
long powW = 1;
for (int i = 0; i < halfBlock; i++) {
long u = a[l + i], v = a[m + i];
a[l + i] = MA.add(u, v);
a[m + i] = MA.mod((u - v) * powW);
powW = MA.mul(powW, w);
}
}
}
return a;
}
private long[] ifft(long[] a, int log) {
int n = a.length;
for (int p = 1; p <= log; p++) {
int block = 1 << p;
int halfBlock = block >> 1;
long iw = iws[p];
for (int l = 0; l < n; l += block) {
int m = l + halfBlock;
long powIw = 1;
for (int i = 0; i < halfBlock; i++) {
long u = a[l + i], v = MA.mul(a[m + i], powIw);
a[l + i] = MA.add(u, v);
a[m + i] = MA.sub(u, v);
powIw = MA.mul(powIw, iw);
}
}
}
return a;
}
private static long[] copyOfRange(long[] a, int toIndexExclusive, int newLength) {
long[] b = new long[newLength];
System.arraycopy(a, 0, b, 0, toIndexExclusive);
return b;
}
private static int ceilLog2(int n) {
int res = 0;
while (1 << res < n)
++res;
return res;
}
private static int primitiveRoot(ModArithmetic MA) {
final int m = (int) MA.getMod();
if (m == 2)
return 1;
if (m == 167772161)
return 3;
if (m == 469762049)
return 3;
if (m == 754974721)
return 11;
if (m == 998244353)
return 3;
int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) >> 1;
while ((x & 1) == 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;
Outer: for (int g = 2;; g++) {
for (int i = 0; i < cnt; i++) {
if (MA.pow(g, (m - 1) / divs[i]) == 1) {
continue Outer;
}
}
return g;
}
}
}
public static void main(String[] args) throws IOException {
solve();
ou.flush();
}
private static final int ni() throws IOException {
return sc.nextInt();
}
private static final int[] ni(int n) throws IOException {
return sc.nextIntArray(n);
}
private static final long nl() throws IOException {
return sc.nextLong();
}
private static final long[] nl(int n) throws IOException {
return sc.nextLongArray(n);
}
private static final String ns() throws IOException {
return sc.next();
}
private static final ContestInputStream sc = new ContestInputStream();
private static final ContestOutputStream ou = new ContestOutputStream();
}
/**
* @author https://atcoder.jp/users/suisen
*/
abstract class ModArithmetic {
public abstract long getMod();
public abstract long mod(long a);
public abstract long add(long a, long b);
public abstract long sub(long a, long b);
public abstract long mul(long a, long b);
public final long div(long a, long b) {
return mul(a, inv(b));
}
public final long inv(long a) {
a = mod(a);
long b = getMod();
long u = 1, v = 0;
while (b >= 1) {
long t = a / b;
a -= t * b;
long tmp1 = a;
a = b;
b = tmp1;
u -= t * v;
long tmp2 = u;
u = v;
v = tmp2;
}
if (a != 1)
throw new ArithmeticException("divide by zero");
return mod(u);
}
public final long fma(long a, long b, long c) {
return add(mul(a, b), c);
}
public final long pow(long a, long b) {
long pow = 1;
for (a = mod(a); b > 0; b >>= 1, a = mul(a, a)) {
if ((b & 1) == 1)
pow = mul(pow, a);
}
return pow;
}
public final long add(long a, long b, long c) {
return mod(a + b + c);
}
public final long add(long a, long b, long c, long d) {
return mod(a + b + c + d);
}
public final long add(long a, long b, long c, long d, long e) {
return mod(a + b + c + d + e);
}
public final long add(long a, long b, long c, long d, long e, long f) {
return mod(a + b + c + d + e + f);
}
public final long add(long a, long b, long c, long d, long e, long f, long g) {
return mod(a + b + c + d + e + f + g);
}
public final long add(long a, long b, long c, long d, long e, long f, long g, long h) {
return mod(a + b + c + d + e + f + g + h);
}
public final long add(long... xs) {
long s = 0;
for (long x : xs)
s += x;
return mod(s);
}
public final long mul(long a, long b, long c) {
return mul(a, mul(b, c));
}
public final long mul(long a, long b, long c, long d) {
return mul(a, mul(b, mul(c, d)));
}
public final long mul(long a, long b, long c, long d, long e) {
return mul(a, mul(b, mul(c, mul(d, e))));
}
public final long mul(long a, long b, long c, long d, long e, long f) {
return mul(a, mul(b, mul(c, mul(d, mul(e, f)))));
}
public final long mul(long a, long b, long c, long d, long e, long f, long g) {
return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, g))))));
}
public final long mul(long a, long b, long c, long d, long e, long f, long g, long h) {
return mul(a, mul(b, mul(c, mul(d, mul(e, mul(f, mul(g, h)))))));
}
public final long mul(long... xs) {
long s = 1;
for (long x : xs)
s = mul(s, x);
return s;
}
/**
* @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
*/
public final long[] gcdInv(long a) {
final long m = getMod();
a = mod(a);
if (a == 0)
return new long[] { m, 0 };
long s = m, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp;
tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0)
m0 += m / s;
return new long[] { s, m0 };
}
public final OptionalLong sqrt(long a) {
a = mod(a);
if (a == 0)
return OptionalLong.of(0);
if (a == 1)
return OptionalLong.of(1);
long p = getMod();
if (pow(a, (p - 1) >> 1) != 1) {
return OptionalLong.empty();
}
if ((p & 3) == 3) {
return OptionalLong.of(pow(a, (p + 1) >> 2));
}
if ((p & 7) == 5) {
if (pow(a, (p - 1) >> 2) == 1) {
return OptionalLong.of(pow(a, (p + 3) >> 3));
} else {
return OptionalLong.of(mul(pow(2, (p - 1) >> 2), pow(a, (p + 3) >> 3)));
}
}
long S = 0, Q = p - 1;
while ((Q & 1) == 0) {
++S;
Q >>= 1;
}
long z = 1;
while (pow(z, (p - 1) >> 1) != p - 1)
++z;
long c = pow(z, Q), R = pow(a, (Q + 1) / 2), t = pow(a, Q), M = S;
while (t != 1) {
long cur = t;
int i;
for (i = 1; i < M; i++) {
cur = mul(cur, cur);
if (cur == 1)
break;
}
long b = pow(c, 1L << (M - i - 1));
c = mul(b, b);
R = mul(R, b);
t = mul(t, b, b);
M = i;
}
return OptionalLong.of(R);
}
public final int primitiveRoot() {
final int m = Math.toIntExact(getMod());
if (m == 2)
return 1;
if (m == 167772161)
return 3;
if (m == 469762049)
return 3;
if (m == 754974721)
return 11;
if (m == 998244353)
return 3;
int[] divs = new int[20];
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0)
x /= 2;
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;
}
for (int g = 2;; g++) {
boolean ok = true;
for (int i = 0; i < cnt; i++) {
if (pow(g, (m - 1) / divs[i]) == 1) {
ok = false;
break;
}
}
if (ok)
return g;
}
}
/** array operations */
public final long[] rangeInv(int n) {
final long MOD = getMod();
long[] invs = new long[n + 1];
if (n == 0)
return invs;
invs[1] = 1;
for (int i = 2; i <= n; i++) {
invs[i] = mul(MOD - MOD / i, invs[(int) (MOD % i)]);
}
return invs;
}
public final long[] arrayInv(long[] a) {
int n = a.length;
long[] l = new long[n + 1];
long[] r = new long[n + 1];
l[0] = r[n] = 1;
for (int i = 0; i < n; i++)
l[i + 1] = mul(l[i], a[i]);
for (int i = n; i > 0; i--)
r[i - 1] = mul(r[i], a[i - 1]);
long invAll = inv(l[n]);
long[] invs = new long[n];
for (int i = 0; i < n; i++) {
invs[i] = mul(l[i], r[i + 1], invAll);
}
return invs;
}
public final long[] factorial(int n) {
long[] ret = new long[n + 1];
ret[0] = 1;
for (int i = 1; i <= n; i++)
ret[i] = mul(ret[i - 1], i);
return ret;
}
public final long[] factorialInv(int n) {
long facN = 1;
for (int i = 2; i <= n; i++)
facN = mul(facN, i);
long[] invs = new long[n + 1];
invs[n] = inv(facN);
for (int i = n; i > 0; i--)
invs[i - 1] = mul(invs[i], i);
return invs;
}
public final long[] rangePower(long a, int n) {
a = mod(a);
long[] pows = new long[n + 1];
pows[0] = 1;
for (int i = 1; i <= n; i++)
pows[i] = mul(pows[i - 1], a);
return pows;
}
public final long[] rangePowerInv(long a, int n) {
a = mod(a);
long[] invs = new long[n + 1];
invs[n] = inv(pow(a, n));
for (int i = n; i > 0; i--)
invs[i - 1] = mul(invs[i], a);
return invs;
}
/** combinatric operations */
public final long[][] combTable(int n) {
long[][] comb = new long[n + 1][];
for (int i = 0; i <= n; i++) {
comb[i] = new long[i + 1];
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++) {
comb[i][j] = add(comb[i - 1][j - 1], comb[i - 1][j]);
}
}
return comb;
}
public final long naiveComb(long n, int r) {
if (r < 0 || r > n)
return 0;
long num = 1, den = 1;
for (int i = 0; i < r; i++) {
num = mul(num, mod(n - i));
den = mul(den, i + 1);
}
return div(num, den);
}
public final long naivePerm(long n, long r) {
if (r < 0 || r > n)
return 0;
long res = 1;
for (long i = 0; i < r; i++)
res = mul(res, n - i);
return res;
}
public final long naiveFactorial(int n) {
return naivePerm(n, n);
}
}
final class ModArithmetic998244353 extends ModArithmetic {
public static final ModArithmetic INSTANCE = new ModArithmetic998244353();
private ModArithmetic998244353() {
}
public static final long MOD = Const.MOD998244353;
public long getMod() {
return MOD;
}
public long mod(long a) {
return (a %= MOD) < 0 ? a + MOD : a;
}
public long add(long a, long b) {
return (a += b) >= MOD ? a - MOD : a;
}
public long sub(long a, long b) {
return (a -= b) < 0 ? a + MOD : a;
}
public long mul(long a, long b) {
return (a * b) % MOD;
}
}
class Const {
public static final long LINF = 1L << 59;
public static final int IINF = (1 << 30) - 1;
public static final double DINF = 1e150;
public static final double SMALL = 1e-12;
public static final double MEDIUM = 1e-9;
public static final double LARGE = 1e-6;
public static final long MOD1000000007 = 1000000007;
public static final long MOD998244353 = 998244353;
public static final long MOD754974721 = 754974721;
public static final long MOD167772161 = 167772161;
public static final long MOD469762049 = 469762049;
public static final int[] dx8 = { 1, 0, -1, 0, 1, -1, -1, 1 };
public static final int[] dy8 = { 0, 1, 0, -1, 1, 1, -1, -1 };
public static final int[] dx4 = { 1, 0, -1, 0 };
public static final int[] dy4 = { 0, 1, 0, -1 };
}
final class ContestInputStream extends FilterInputStream {
protected final byte[] buf;
protected int pos = 0;
protected int lim = 0;
private final char[] cbuf;
public ContestInputStream() {
super(System.in);
this.buf = new byte[1 << 13];
this.cbuf = new char[1 << 20];
}
boolean hasRemaining() throws IOException {
if (pos < lim)
return true;
lim = in.read(buf);
pos = 0;
return lim > 0;
}
final int remaining() throws IOException {
if (pos >= lim) {
lim = in.read(buf);
pos = 0;
}
return lim - pos;
}
@Override
public final int available() throws IOException {
if (pos < lim)
return lim - pos + in.available();
return in.available();
}
@Override
public final long skip(long n) throws IOException {
if (pos < lim) {
int rem = lim - pos;
if (n < rem) {
pos += n;
return n;
}
pos = lim;
return rem;
}
return in.skip(n);
}
@Override
public final int read() throws IOException {
if (hasRemaining())
return buf[pos++];
return -1;
}
@Override
public final int read(byte[] b, int off, int len) throws IOException {
if (pos < lim) {
int rem = Math.min(lim - pos, len);
for (int i = 0; i < rem; i++)
b[off + i] = buf[pos + i];
pos += rem;
return rem;
}
return in.read(b, off, len);
}
public final char[] readToken() throws IOException {
int cpos = 0;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
char[] arr = new char[cpos];
for (int i = 0; i < cpos; i++)
arr[i] = cbuf[i];
return arr;
}
public final int readToken(char[] cbuf, int off) throws IOException {
int cpos = off;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
return cpos - off;
}
public final int readToken(char[] cbuf) throws IOException {
return readToken(cbuf, 0);
}
public final String next() throws IOException {
int cpos = 0;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
return String.valueOf(cbuf, 0, cpos);
}
public final char[] nextCharArray() throws IOException {
return readToken();
}
public final int nextInt() throws IOException {
if (!hasRemaining())
return 0;
int value = 0;
byte b = buf[pos++];
if (b == 0x2d) {
while (hasRemaining() && (b = buf[pos++]) > 0x20)
value = value * 10 - b + 0x30;
} else {
do {
value = value * 10 + b - 0x30;
} while (hasRemaining() && (b = buf[pos++]) > 0x20);
}
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return value;
}
public final long nextLong() throws IOException {
if (!hasRemaining())
return 0L;
long value = 0L;
byte b = buf[pos++];
if (b == 0x2d) {
while (hasRemaining() && (b = buf[pos++]) > 0x20)
value = value * 10 - b + 0x30;
} else {
do {
value = value * 10 + b - 0x30;
} while (hasRemaining() && (b = buf[pos++]) > 0x20);
}
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return value;
}
public final char nextChar() throws IOException {
if (!hasRemaining())
throw new EOFException();
final char c = (char) buf[pos++];
if (hasRemaining() && buf[pos++] == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return c;
}
public final float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public final double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public final boolean[] nextBooleanArray(char ok) throws IOException {
char[] s = readToken();
int n = s.length;
boolean[] t = new boolean[n];
for (int i = 0; i < n; i++)
t[i] = s[i] == ok;
return t;
}
public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException {
boolean[][] s = new boolean[h][];
for (int i = 0; i < h; i++) {
char[] t = readToken();
int n = t.length;
s[i] = new boolean[n];
for (int j = 0; j < n; j++)
s[i][j] = t[j] == ok;
}
return s;
}
public final String[] nextStringArray(int len) throws IOException {
String[] arr = new String[len];
for (int i = 0; i < len; i++)
arr[i] = next();
return arr;
}
public final int[] nextIntArray(int len) throws IOException {
int[] arr = new int[len];
for (int i = 0; i < len; i++)
arr[i] = nextInt();
return arr;
}
public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException {
int[] arr = new int[len];
for (int i = 0; i < len; i++)
arr[i] = map.applyAsInt(nextInt());
return arr;
}
public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException {
long[] arr = new long[len];
for (int i = 0; i < len; i++)
arr[i] = map.applyAsLong(nextLong());
return arr;
}
public final int[][] nextIntMatrix(int h, int w) throws IOException {
int[][] arr = new int[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = nextInt();
return arr;
}
public final int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) throws IOException {
int[][] arr = new int[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = map.applyAsInt(nextInt());
return arr;
}
public final long[] nextLongArray(int len) throws IOException {
long[] arr = new long[len];
for (int i = 0; i < len; i++)
arr[i] = nextLong();
return arr;
}
public final long[][] nextLongMatrix(int h, int w) throws IOException {
long[][] arr = new long[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = nextLong();
return arr;
}
public final float[] nextFloatArray(int len) throws IOException {
float[] arr = new float[len];
for (int i = 0; i < len; i++)
arr[i] = nextFloat();
return arr;
}
public final double[] nextDoubleArray(int len) throws IOException {
double[] arr = new double[len];
for (int i = 0; i < len; i++)
arr[i] = nextDouble();
return arr;
}
public final char[][] nextCharMatrix(int h, int w) throws IOException {
char[][] arr = new char[h][];
for (int i = 0; i < h; i++)
arr[i] = readToken();
return arr;
}
public final void nextThrow() throws IOException {
next();
return;
}
public final void nextThrow(int n) throws IOException {
for (int i = 0; i < n; i++)
nextThrow();
return;
}
}
final class ContestOutputStream extends FilterOutputStream implements Appendable {
protected final byte[] buf;
protected int pos = 0;
public ContestOutputStream() {
super(System.out);
this.buf = new byte[1 << 13];
}
@Override
public void flush() throws IOException {
out.write(buf, 0, pos);
pos = 0;
out.flush();
}
void put(byte b) throws IOException {
if (pos >= buf.length)
flush();
buf[pos++] = b;
}
int remaining() throws IOException {
if (pos >= buf.length)
flush();
return buf.length - pos;
}
@Override
public void write(int b) throws IOException {
put((byte) b);
}
@Override
public void write(byte[] b, int off, int len) throws IOException {
int o = off;
int l = len;
while (l > 0) {
int rem = Math.min(remaining(), l);
for (int i = 0; i < rem; i++)
buf[pos + i] = b[o + i];
pos += rem;
o += rem;
l -= rem;
}
}
@Override
public ContestOutputStream append(char c) throws IOException {
put((byte) c);
return this;
}
@Override
public ContestOutputStream append(CharSequence csq, int start, int end) throws IOException {
int off = start;
int len = end - start;
while (len > 0) {
int rem = Math.min(remaining(), len);
for (int i = 0; i < rem; i++)
buf[pos + i] = (byte) csq.charAt(off + i);
pos += rem;
off += rem;
len -= rem;
}
return this;
}
@Override
public ContestOutputStream append(CharSequence csq) throws IOException {
return append(csq, 0, csq.length());
}
public ContestOutputStream append(char[] arr, int off, int len) throws IOException {
int o = off;
int l = len;
while (l > 0) {
int rem = Math.min(remaining(), l);
for (int i = 0; i < rem; i++)
buf[pos + i] = (byte) arr[o + i];
pos += rem;
o += rem;
l -= rem;
}
return this;
}
public ContestOutputStream print(char[] arr) throws IOException {
return append(arr, 0, arr.length).newLine();
}
public ContestOutputStream print(boolean value) throws IOException {
if (value)
return append("o");
return append("x");
}
public ContestOutputStream println(boolean value) throws IOException {
if (value)
return append("o\n");
return append("x\n");
}
public ContestOutputStream print(boolean[][] value) throws IOException {
final int n = value.length, m = value[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
print(value[i][j]);
newLine();
}
return this;
}
public ContestOutputStream print(int value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(int value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(long value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(long value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(float value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(float value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(double value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(double value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(char value) throws IOException {
return append(value);
}
public ContestOutputStream println(char value) throws IOException {
return append(value).newLine();
}
public ContestOutputStream print(String value) throws IOException {
return append(value);
}
public ContestOutputStream println(String value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(Object value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(Object value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream printYN(boolean yes) throws IOException {
if (yes)
return println("Yes");
return println("No");
}
public ContestOutputStream printAB(boolean yes) throws IOException {
if (yes)
return println("Alice");
return println("Bob");
}
public ContestOutputStream print(CharSequence[] arr) throws IOException {
if (arr.length > 0) {
append(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').append(arr[i]);
}
return this;
}
public ContestOutputStream print(int[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(int[] arr, int length) throws IOException {
if (length > 0)
print(arr[0]);
for (int i = 1; i < length; i++)
append('\u0020').print(arr[i]);
newLine();
return this;
}
public ContestOutputStream println(int[] arr) throws IOException {
for (int i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream println(int[] arr, int length) throws IOException {
for (int i = 0; i < length; i++)
println(arr[i]);
return this;
}
public ContestOutputStream print(boolean[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(long[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(long[] arr, int length) throws IOException {
if (length > 0)
print(arr[0]);
for (int i = 1; i < length; i++)
append('\u0020').print(arr[i]);
newLine();
return this;
}
public ContestOutputStream println(long[] arr, int length) throws IOException {
for (int i = 0; i < length; i++)
println(arr[i]);
return this;
}
public ContestOutputStream println(long[] arr) throws IOException {
for (long i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(float[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
return this;
}
public ContestOutputStream println(float[] arr) throws IOException {
for (float i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(double[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
return newLine();
}
public ContestOutputStream println(double[] arr) throws IOException {
for (double i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(Object[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
return newLine();
}
public ContestOutputStream print(java.util.ArrayList<?> arr) throws IOException {
if (!arr.isEmpty()) {
final int n = arr.size();
print(arr.get(0));
for (int i = 1; i < n; i++)
print(" ").print(arr.get(i));
}
return newLine();
}
public ContestOutputStream println(java.util.ArrayList<?> arr) throws IOException {
final int n = arr.size();
for (int i = 0; i < n; i++)
println(arr.get(i));
return this;
}
public ContestOutputStream println(Object[] arr) throws IOException {
for (Object i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream newLine() throws IOException {
return append(System.lineSeparator());
}
public ContestOutputStream endl() throws IOException {
newLine().flush();
return this;
}
public ContestOutputStream print(int[][] arr) throws IOException {
for (int[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(long[][] arr) throws IOException {
for (long[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(char[][] arr) throws IOException {
for (char[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(Object[][] arr) throws IOException {
for (Object[] i : arr)
print(i);
return this;
}
public ContestOutputStream println() throws IOException {
return newLine();
}
}