結果
| 問題 | No.2330 Eat Slime |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2023-05-28 15:45:59 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 791 ms / 4,000 ms |
| コード長 | 45,384 bytes |
| コンパイル時間 | 3,974 ms |
| コンパイル使用メモリ | 88,056 KB |
| 実行使用メモリ | 85,456 KB |
| 最終ジャッジ日時 | 2023-08-27 12:55:19 |
| 合計ジャッジ時間 | 22,489 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 45 ms
49,456 KB |
| testcase_01 | AC | 45 ms
49,528 KB |
| testcase_02 | AC | 44 ms
49,376 KB |
| testcase_03 | AC | 44 ms
49,440 KB |
| testcase_04 | AC | 45 ms
49,952 KB |
| testcase_05 | AC | 44 ms
49,428 KB |
| testcase_06 | AC | 45 ms
49,424 KB |
| testcase_07 | AC | 769 ms
71,868 KB |
| testcase_08 | AC | 565 ms
70,608 KB |
| testcase_09 | AC | 739 ms
78,508 KB |
| testcase_10 | AC | 258 ms
55,604 KB |
| testcase_11 | AC | 263 ms
58,924 KB |
| testcase_12 | AC | 763 ms
73,428 KB |
| testcase_13 | AC | 791 ms
75,080 KB |
| testcase_14 | AC | 319 ms
59,224 KB |
| testcase_15 | AC | 509 ms
71,628 KB |
| testcase_16 | AC | 753 ms
80,016 KB |
| testcase_17 | AC | 751 ms
84,920 KB |
| testcase_18 | AC | 766 ms
84,808 KB |
| testcase_19 | AC | 760 ms
85,176 KB |
| testcase_20 | AC | 749 ms
84,904 KB |
| testcase_21 | AC | 772 ms
83,048 KB |
| testcase_22 | AC | 744 ms
85,456 KB |
| testcase_23 | AC | 769 ms
84,888 KB |
| testcase_24 | AC | 740 ms
84,904 KB |
| testcase_25 | AC | 755 ms
85,240 KB |
| testcase_26 | AC | 749 ms
84,924 KB |
| testcase_27 | AC | 766 ms
85,052 KB |
| testcase_28 | AC | 768 ms
84,892 KB |
| testcase_29 | AC | 766 ms
85,168 KB |
| testcase_30 | AC | 767 ms
85,116 KB |
| testcase_31 | AC | 751 ms
84,968 KB |
ソースコード
public class Main {
public static void main(String[] args) {
new Main();
}
public Main() {
FastScanner fs = new FastScanner();
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
solve(fs, out);
out.flush();
}
public void solve(FastScanner fs, java.io.PrintWriter out) {
int N = fs.nextInt(), M = fs.nextInt(), X = fs.nextInt();
int[][] slime = new int[5][N];
for (int i = 0;i < N;++ i) {
int C = fs.nextInt() - 1;
slime[C][i] = 1;
}
int[][] bonus = new int[5][N + 1];
for (int i = 0;i < M;++ i) {
int A = fs.nextInt() - 1, B = fs.nextInt() - 1, Y = fs.nextInt();
bonus[B][N - A] += Y;
}
int[][] score = new int[5][];
for (int i = 0;i < 5;++ i) score[i] = Convolution.convolution998_244_353(slime[i], bonus[i]);
int ans = X * N;
for (int i = 0;i < N;++ i) {
int tmp = X * i;
for (int j = 0;j < 5;++ j) tmp += score[j][N + i];
ans = Math.max(ans, tmp);
}
out.println(ans);
}
final int MOD = 998_244_353;
int plus(int n, int m) {
int sum = n + m;
if (sum >= MOD) sum -= MOD;
return sum;
}
int minus(int n, int m) {
int sum = n - m;
if (sum < 0) sum += MOD;
return sum;
}
int times(int n, int m) {
return (int) ((long) n * m % MOD);
}
int divide(int n, int m) {
return times(n, IntMath.pow(m, MOD - 2, MOD));
}
int[] fact, invf;
void calc(int len) {
len += 2;
fact = new int[len];
invf = new int[len];
fact[0] = fact[1] = invf[0] = invf[1] = 1;
for (int i = 2; i < fact.length; ++i) fact[i] = times(fact[i - 1], i);
invf[len - 1] = divide(1, fact[len - 1]);
for (int i = len - 1; i > 1; --i) invf[i - 1] = times(i, invf[i]);
}
int comb(int n, int m) {
if (n < m) return 0;
return times(fact[n], times(invf[n - m], invf[m]));
}
public static final class MathLib {
public static class Barrett {
private final int mod;
private final long h, l;
private final long MAX = 1L << 62;
private final int MASK = (1 << 31) - 1;
Barrett(final int mod) {
this.mod = mod;
final long t = MAX / mod;
h = t >>> 31;
l = t & MASK;
}
int reduce(final long x) {
final long xh = x >>> 31, xl = x & MASK;
long z = xl * l;
z = xl * h + xh * l + (z >>> 31);
z = xh * h + (z >>> 31);
final int ret = (int) (x - z * mod);
return ret >= mod ? ret - mod : ret;
}
}
public static class BarrettSmall {
private final int mod;
final long t;
BarrettSmall(final int mod) {
this.mod = mod;
t = (1L << 42) / mod;
}
int reduce(long x) {
long q = x * t >> 42;
x -= q * mod;
return (int) (x >= mod ? x - mod : x);
}
}
private static long safe_mod(long x, final long m) {
x %= m;
if (x < 0) x += m;
return x;
}
private static long[] inv_gcd(long a, final long b) {
a = safe_mod(a, b);
if (a == 0) return new long[] { b, 0 };
long s = b, t = a;
long m0 = 0, m1 = 1;
while (t > 0) {
final long u = s / t;
s -= t * u;
m0 -= m1 * u;
long tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return new long[] { s, m0 };
}
public static int pow(long n, long m, final int mod) {
assert m >= 0 && mod >= 1;
if (mod == 1) return 0;
return pow(n, m, new Barrett(mod));
}
public static int pow(long n, long m, Barrett mod) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = mod.reduce(ans * num);
m >>>= 1;
num = mod.reduce(num * num);
}
return (int) ans;
}
public static int pow998_244_353(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 998_244_353;
m >>>= 1;
num = num * num % 998_244_353;
}
return (int) ans;
}
public static int pow754_974_721(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 754_974_721;
m >>>= 1;
num = num * num % 754_974_721;
}
return (int) ans;
}
public static int pow167_772_161(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 167_772_161;
m >>>= 1;
num = num * num % 167_772_161;
}
return (int) ans;
}
public static int pow469_762_049(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 469_762_049;
m >>>= 1;
num = num * num % 469_762_049;
}
return (int) ans;
}
public static int pow1_000_000_007(long n, long m) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % 1_000_000_007;
m >>>= 1;
num = num * num % 1_000_000_007;
}
return (int) ans;
}
public static int pow(long n, long m, BarrettSmall mod) {
assert m >= 0;
long ans = 1, num = n;
while (m != 0) {
if ((m & 1) != 0) ans = mod.reduce(ans * num);
m >>>= 1;
num = mod.reduce(num * num);
}
return (int) ans;
}
public static long[] crt(final long[] r, final long[] m) {
assert r.length == m.length;
final int n = r.length;
long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert 1 <= m[i];
long r1 = safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
long tmp = r0;
r0 = r1;
r1 = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return new long[] { 0, 0 };
continue;
}
final long[] ig = inv_gcd(m0, m1);
final long g = ig[0], im = ig[1];
final long u1 = m1 / g;
if ((r1 - r0) % g != 0) return new long[] { 0, 0 };
final long x = (r1 - r0) / g % u1 * im % u1;
r0 += x * m0;
m0 *= u1;
if (r0 < 0) r0 += m0;
// System.err.printf("%d %d\n", r0, m0);
}
return new long[] { r0, m0 };
}
public static long floor_sum(final long n, final long m, long a, long b) {
long ans = 0;
if (a >= m) {
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
final long y_max = (a * n + b) / m;
final long x_max = y_max * m - b;
if (y_max == 0) return ans;
ans += (n - (x_max + a - 1) / a) * y_max;
ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
return ans;
}
}
/**
* Convolution.
*
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_f
* @verified https://judge.yosupo.jp/problem/convolution_mod_1000000007
*/
public static final class Convolution {
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
private static void fft(double[] a, double[] b, boolean invert) {
int count = a.length;
for (int i = 1, j = 0; i < count; i++) {
int bit = count >> 1;
for (; j >= bit; bit >>= 1) {
j -= bit;
}
j += bit;
if (i < j) {
double temp = a[i];
a[i] = a[j];
a[j] = temp;
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
for (int len = 2; len <= count; len <<= 1) {
int halfLen = len >> 1;
double angle = 2 * Math.PI / len;
if (invert) {
angle = -angle;
}
double wLenA = Math.cos(angle);
double wLenB = Math.sin(angle);
for (int i = 0; i < count; i += len) {
double wA = 1;
double wB = 0;
for (int j = 0; j < halfLen; j++) {
double uA = a[i + j];
double uB = b[i + j];
double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
a[i + j] = uA + vA;
b[i + j] = uB + vB;
a[i + j + halfLen] = uA - vA;
b[i + j + halfLen] = uB - vB;
double nextWA = wA * wLenA - wB * wLenB;
wB = wA * wLenB + wB * wLenA;
wA = nextWA;
}
}
}
if (invert) {
for (int i = 0; i < count; i++) {
a[i] /= count;
b[i] /= count;
}
}
}
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
public static long[] convolution(long[] a, long[] b) {
int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
resultSize = Math.max(resultSize, 1);
double[] aReal = new double[resultSize];
double[] aImaginary = new double[resultSize];
double[] bReal = new double[resultSize];
double[] bImaginary = new double[resultSize];
for (int i = 0; i < a.length; i++) aReal[i] = a[i];
for (int i = 0; i < b.length; i++) bReal[i] = b[i];
fft(aReal, aImaginary, false);
if (a == b) {
System.arraycopy(aReal, 0, bReal, 0, aReal.length);
System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
} else {
fft(bReal, bImaginary, false);
}
for (int i = 0; i < resultSize; i++) {
double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
aReal[i] = real;
}
fft(aReal, aImaginary, true);
long[] result = new long[a.length + b.length - 1];
for (int i = 0; i < result.length; i++) result[i] = Math.round(aReal[i]);
return result;
}
/**
* writer: amotama 勝手に借りてます、問題あったらごめんね
*/
public static int[] convolution(int[] a, int[] b) {
int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
resultSize = Math.max(resultSize, 1);
double[] aReal = new double[resultSize];
double[] aImaginary = new double[resultSize];
double[] bReal = new double[resultSize];
double[] bImaginary = new double[resultSize];
for (int i = 0; i < a.length; i++) aReal[i] = a[i];
for (int i = 0; i < b.length; i++) bReal[i] = b[i];
fft(aReal, aImaginary, false);
if (a == b) {
System.arraycopy(aReal, 0, bReal, 0, aReal.length);
System.arraycopy(aImaginary, 0, bImaginary, 0, aImaginary.length);
} else {
fft(bReal, bImaginary, false);
}
for (int i = 0; i < resultSize; i++) {
double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
aReal[i] = real;
}
fft(aReal, aImaginary, true);
int[] result = new int[a.length + b.length - 1];
for (int i = 0; i < result.length; i++) result[i] = (int) Math.round(aReal[i]);
return result;
}
/**
* Find a primitive root.
*
* @param m A prime number.
* @return Primitive root.
*/
private static int primitiveRoot(final int m) {
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;
final 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 (MathLib.pow(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
/**
* Ceil of power 2.
*
* @param n Value.
* @return Ceil of power 2.
*/
private static int ceilPow2(final int n) {
int x = 0;
while (1L << x < n) x++;
return x;
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static long garner(final long[] c, final int[] mods) {
final int n = c.length + 1;
final long[] cnst = new long[n];
final long[] coef = new long[n];
java.util.Arrays.fill(coef, 1);
for (int i = 0; i < n - 1; i++) {
final int m1 = mods[i];
long v = (c[i] - cnst[i] + m1) % m1;
v = v * MathLib.pow(coef[i], m1 - 2, m1) % m1;
for (int j = i + 1; j < n; j++) {
final long m2 = mods[j];
cnst[j] = (cnst[j] + coef[j] * v) % m2;
coef[j] = coef[j] * m1 % m2;
}
}
return cnst[n - 1];
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static int garner(int c0, int c1, int c2, final MathLib.Barrett[] mods) {
final long[] cnst = new long[4];
final long[] coef = new long[4];
java.util.Arrays.fill(coef, 1);
MathLib.Barrett m1 = mods[0];
long v = m1.reduce(c0 - cnst[0] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[0], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[1];
cnst[1] = m2.reduce(cnst[1] + coef[1] * v);
coef[1] = m2.reduce(coef[1] * m1.mod);
m2 = mods[2];
cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
coef[2] = m2.reduce(coef[2] * m1.mod);
m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
m1 = mods[1];
v = m1.reduce(c1 - cnst[1] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[1], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[2];
cnst[2] = m2.reduce(cnst[2] + coef[2] * v);
coef[2] = m2.reduce(coef[2] * m1.mod);
m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
m1 = mods[2];
v = m1.reduce(c2 - cnst[2] + m1.mod);
v = m1.reduce(v * MathLib.pow(coef[2], m1.mod - 2, m1));
{
MathLib.Barrett m2 = mods[3];
cnst[3] = m2.reduce(cnst[3] + coef[3] * v);
coef[3] = m2.reduce(coef[3] * m1.mod);
}
return (int) cnst[3];
}
/**
* Garner's algorithm.
*
* @param c Mod convolution results.
* @param mods Mods.
* @return Result.
*/
private static int garner1_000_000_007(int c0, int c1, int c2) {
final long[] cnst = new long[4];
final long[] coef = new long[4];
java.util.Arrays.fill(coef, 1);
long v = (c0 - cnst[0] + 754_974_721) % 754_974_721;
v = v * MathLib.pow754_974_721(coef[0], 754_974_721 - 2) % 754_974_721;
{
cnst[1] = (cnst[1] + coef[1] * v) % 167_772_161;
coef[1] = coef[1] * 754_974_721 % 167_772_161;
cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
coef[2] = coef[2] * 754_974_721 % 469_762_049;
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 754_974_721 % 1_000_000_007;
}
v = (c1 - cnst[1] + 167_772_161) % 167_772_161;
v = v * MathLib.pow167_772_161(coef[1], 167_772_161 - 2) % 167_772_161;
{
cnst[2] = (cnst[2] + coef[2] * v) % 469_762_049;
coef[2] = coef[2] * 167_772_161 % 469_762_049;
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 167_772_161 % 1_000_000_007;
}
v = (c2 - cnst[2] + 469_762_049) % 469_762_049;
v = v * MathLib.pow469_762_049(coef[2], 469_762_049 - 2) % 469_762_049;
{
cnst[3] = (cnst[3] + coef[3] * v) % 1_000_000_007;
coef[3] = coef[3] * 469_762_049 % 1_000_000_007;
}
return (int) cnst[3];
}
/**
* Pre-calculation for NTT.
*
* @param mod NTT Prime.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumE(final int mod, final int g) {
final long[] sum_e = new long[30];
final long[] es = new long[30];
final long[] ies = new long[30];
final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
long ie = MathLib.pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now % mod;
now = now * ies[i] % mod;
}
return sum_e;
}
/**
* Pre-calculation for inverse NTT.
*
* @param mod Mod.
* @param g Primitive root of mod.
* @return Pre-calculation table.
*/
private static long[] sumIE(final int mod, final int g) {
final long[] sum_ie = new long[30];
final long[] es = new long[30];
final long[] ies = new long[30];
final int cnt2 = Integer.numberOfTrailingZeros(mod - 1);
long e = MathLib.pow(g, mod - 1 >> cnt2, mod);
long ie = MathLib.pow(e, mod - 2, mod);
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e = e * e % mod;
ie = ie * ie % mod;
}
long now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now % mod;
now = now * es[i] % mod;
}
return sum_ie;
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterflyInv(final long[] a, final long[] sumIE, final int mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (mod + l - r) * inow % mod;
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % mod;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly(final long[] a, final long[] sumE, final int mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now % mod;
a[i + offset] = (l + r) % mod;
a[i + offset + p] = (l - r + mod) % mod;
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % mod;
}
}
}
/**
* Inverse NTT used mod 998_244_353.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv998_244_353(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 998_244_353);
a[i + offset + p] = (int)((998_244_353 + l - r) * inow % 998_244_353);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 998_244_353;
}
}
}
/**
* Inverse NTT used mod 754_974_721.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv754_974_721(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 754_974_721);
a[i + offset + p] = (int)((754_974_721 + l - r) * inow % 754_974_721);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 754_974_721;
}
}
}
/**
* Inverse NTT used mod 167_772_161.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv167_772_161(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 167_772_161);
a[i + offset + p] = (int)((167_772_161 + l - r) * inow % 167_772_161);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 167_772_161;
}
}
}
/**
* Inverse NTT used mod 469_762_049.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
*/
private static void butterflyInv469_762_049(final int[] a, final int[] sumIE) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
a[i + offset] = (int)((l + r) % 469_762_049);
a[i + offset + p] = (int)((469_762_049 + l - r) * inow % 469_762_049);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = inow * sumIE[x] % 469_762_049;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumIE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterflyInv(final int[] a, final int[] sumIE, final MathLib.Barrett mod) {
final int n = a.length;
final int h = ceilPow2(n);
for (int ph = h; ph >= 1; ph--) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long inow = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p];
long sum = l + r;
if (sum >= mod.mod) sum -= mod.mod;
a[i + offset] = (int)sum;
a[i + offset + p] = mod.reduce((mod.mod + l - r) * inow);
}
final int x = Integer.numberOfTrailingZeros(~s);
inow = mod.reduce(inow * sumIE[x]);
}
}
}
/**
* Inverse NTT used mod 998_244_353.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly998_244_353(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(998_244_353 - 2) * 998_244_353;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 998_244_353);
a[i + offset + p] = (int)((l - r + ADD) % 998_244_353);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 998_244_353;
}
}
}
/**
* Inverse NTT used mod 754_974_721.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly754_974_721(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(754_974_721 - 2) * 754_974_721;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 754_974_721);
a[i + offset + p] = (int)((l - r + ADD) % 754_974_721);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 754_974_721;
}
}
}
/**
* Inverse NTT used mod 167_772_161.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly167_772_161(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(167_772_161 - 2) * 167_772_161;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 167_772_161);
a[i + offset + p] = (int)((l - r + ADD) % 167_772_161);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 167_772_161;
}
}
}
/**
* Inverse NTT used mod 469_762_049.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly469_762_049(final int[] a, final int[] sumE) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(469_762_049 - 2) * 469_762_049;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = (int)((l + r) % 469_762_049);
a[i + offset + p] = (int)((l - r + ADD) % 469_762_049);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = now * sumE[x] % 469_762_049;
}
}
}
/**
* Inverse NTT.
*
* @param a Target array.
* @param sumE Pre-calculation table.
* @param mod NTT Prime.
*/
private static void butterfly(final int[] a, final int[] sumE, final MathLib.Barrett mod) {
final int n = a.length;
final int h = ceilPow2(n);
final long ADD = (long)(mod.mod - 2) * mod.mod;
for (int ph = 1; ph <= h; ph++) {
final int w = 1 << ph - 1, p = 1 << h - ph;
long now = 1;
for (int s = 0; s < w; s++) {
final int offset = s << h - ph + 1;
for (int i = 0; i < p; i++) {
final long l = a[i + offset];
final long r = a[i + offset + p] * now;
a[i + offset] = mod.reduce(l + r);
a[i + offset + p] = mod.reduce(l - r + ADD);
}
final int x = Integer.numberOfTrailingZeros(~s);
now = mod.reduce(now * sumE[x]);
}
}
}
/**
* Convolution used mod 998_244_353.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution998_244_353(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(998_244_353);
final int[] sume;
{
long[] s = sumE(998_244_353, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(998_244_353, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly998_244_353(a, sume);
butterfly998_244_353(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 998_244_353);
butterflyInv998_244_353(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow998_244_353(z, 998_244_353 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 998_244_353);
return a;
}
/**
* Convolution used mod 754_974_721.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution754_974_721(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(754_974_721);
final int[] sume;
{
long[] s = sumE(754_974_721, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(754_974_721, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly754_974_721(a, sume);
butterfly754_974_721(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 754_974_721);
butterflyInv754_974_721(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow754_974_721(z, 754_974_721 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 754_974_721);
return a;
}
/**
* Convolution used mod 167_772_161.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution167_772_161(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(167_772_161);
final int[] sume;
{
long[] s = sumE(167_772_161, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(167_772_161, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly167_772_161(a, sume);
butterfly167_772_161(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 167_772_161);
butterflyInv167_772_161(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow167_772_161(z, 167_772_161 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 167_772_161);
return a;
}
/**
* Convolution used mod 469_762_049.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution469_762_049(int[] a, int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(469_762_049);
final int[] sume;
{
long[] s = sumE(469_762_049, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(469_762_049, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly469_762_049(a, sume);
butterfly469_762_049(b, sume);
for (int i = 0; i < z; i++) a[i] = (int)((long) a[i] * b[i] % 469_762_049);
butterflyInv469_762_049(a, sumie);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow469_762_049(z, 469_762_049 - 2);
for (int i = 0; i < n + m - 1; i++) a[i] = (int)(a[i] * iz % 469_762_049);
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static int[] convolution(int[] a, int[] b, final int mod) {
MathLib.Barrett barrett = new MathLib.Barrett(mod);
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final int[] na = new int[z];
final int[] nb = new int[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(mod);
final int[] sume;
{
long[] s = sumE(mod, g);
sume = new int[s.length];
for (int i = 0; i < s.length; ++i) sume[i] = (int) s[i];
}
final int[] sumie;
{
long[] s = sumIE(mod, g);
sumie = new int[s.length];
for (int i = 0; i < s.length; ++i) sumie[i] = (int) s[i];
}
butterfly(a, sume, barrett);
butterfly(b, sume, barrett);
for (int i = 0; i < z; i++) a[i] = barrett.reduce((long) a[i] * b[i]);
butterflyInv(a, sumie, barrett);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = barrett.reduce(a[i] * iz);
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod NTT Prime.
* @return Answer.
*/
public static long[] convolution(long[] a, long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new long[0];
final int z = 1 << ceilPow2(n + m - 1);
{
final long[] na = new long[z];
final long[] nb = new long[z];
System.arraycopy(a, 0, na, 0, n);
System.arraycopy(b, 0, nb, 0, m);
a = na;
b = nb;
}
final int g = primitiveRoot(mod);
final long[] sume = sumE(mod, g);
final long[] sumie = sumIE(mod, g);
butterfly(a, sume, mod);
butterfly(b, sume, mod);
for (int i = 0; i < z; i++) {
a[i] = a[i] * b[i] % mod;
}
butterflyInv(a, sumie, mod);
a = java.util.Arrays.copyOf(a, n + m - 1);
final long iz = MathLib.pow(z, mod - 2, mod);
for (int i = 0; i < n + m - 1; i++) a[i] = a[i] * iz % mod;
return a;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static long[] convolutionLL(final long[] a, final long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new long[0];
final int mod1 = 754_974_721;
final int mod2 = 167_772_161;
final int mod3 = 469_762_049;
final long[] c1 = convolution(a, b, mod1);
final long[] c2 = convolution(a, b, mod2);
final long[] c3 = convolution(a, b, mod3);
final int retSize = c1.length;
final long[] ret = new long[retSize];
final int[] mods = { mod1, mod2, mod3, mod };
for (int i = 0; i < retSize; ++i) {
ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);
}
return ret;
}
/**
* Convolution.
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static int[] convolutionLL(final int[] a, final int[] b, final int mod) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int mod1 = 754_974_721;
final int mod2 = 167_772_161;
final int mod3 = 469_762_049;
final int[] c1 = convolution754_974_721(a, b);
final int[] c2 = convolution167_772_161(a, b);
final int[] c3 = convolution469_762_049(a, b);
final int retSize = c1.length;
final int[] ret = new int[retSize];
final MathLib.Barrett[] mods = { new MathLib.Barrett(mod1), new MathLib.Barrett(mod2),
new MathLib.Barrett(mod3), new MathLib.Barrett(mod) };
for (int i = 0; i < retSize; ++i) ret[i] = garner(c1[i], c2[i], c3[i], mods);
return ret;
}
/**
* Convolution used mod 1_000_000_007.
*
* @param a Target array 1.
* @param b Target array 2.
* @return Answer.
*/
public static int[] convolution1_000_000_007(final int[] a, final int[] b) {
final int n = a.length;
final int m = b.length;
if (n == 0 || m == 0) return new int[0];
final int[] c1 = convolution754_974_721(a, b);
final int[] c2 = convolution167_772_161(a, b);
final int[] c3 = convolution469_762_049(a, b);
final int retSize = c1.length;
final int[] ret = new int[retSize];
for (int i = 0; i < retSize; ++i) ret[i] = garner1_000_000_007(c1[i], c2[i], c3[i]);
return ret;
}
/**
* Convolution. need: length < 2000
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Any mod.
* @return Answer.
*/
public static int[] convolutionLL2(final int[] a, final int[] b, final int mod) {
if (Math.max(a.length, b.length) < 4000) {
long[] la = new long[a.length], ha = new long[a.length], ma = new long[a.length], lb = new long[b.length],
hb = new long[b.length], mb = new long[b.length];
MathLib.Barrett barrett = new MathLib.Barrett(mod);
for (int i = 0; i < a.length; ++i) {
ha[i] = a[i] >> 15;
la[i] = a[i] & 0x7FFF;
ma[i] = la[i] + ha[i];
}
for (int i = 0; i < b.length; ++i) {
hb[i] = b[i] >> 15;
lb[i] = b[i] & 0x7FFF;
mb[i] = lb[i] + hb[i];
}
long[] l = convolution(la, lb), h = convolution(ha, hb), m = convolution(ma, mb);
int[] ret = new int[m.length];
for (int i = 0; i < m.length; ++i) {
h[i] = barrett.reduce(h[i]);
m[i] = barrett.reduce(m[i] - l[i] - h[i] + (long)m.length * mod);
ret[i] = barrett.reduce((h[i] << 30) + (m[i] << 15) + l[i]);
}
return ret;
}
return convolutionLL(a, b, mod);
}
/**
* Naive convolution. (Complexity is O(N^2)!!)
*
* @param a Target array 1.
* @param b Target array 2.
* @param mod Mod.
* @return Answer.
*/
public static long[] convolutionNaive(final long[] a, final long[] b, final int mod) {
final int n = a.length;
final int m = b.length;
final int k = n + m - 1;
final long[] ret = new long[k];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ret[i + j] += a[i] * b[j] % mod;
ret[i + j] %= mod;
}
}
return ret;
}
}
}
class FastScanner {
private final java.io.InputStream in = System.in;
private final byte[] buffer = new byte[8192];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) return true;
ptr = 0;
try {
buflen = in.read(buffer);
} catch (java.io.IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
private byte readByte() {
return hasNextByte() ? buffer[ptr++] : -1;
}
private static boolean isPrintableChar(byte c) {
return 32 < c || c < 0;
}
private static boolean isNumber(int c) {
return '0' <= c && c <= '9';
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new java.util.NoSuchElementException();
StringBuilder sb = new StringBuilder();
byte b;
while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
return sb.toString();
}
public final char nextChar() {
if (!hasNext()) throw new java.util.NoSuchElementException();
return (char) readByte();
}
public final long nextLong() {
if (!hasNext()) throw new java.util.NoSuchElementException();
long n = 0;
try {
byte b = readByte();
if (b == '-') {
while (isNumber(b = readByte())) n = n * 10 + '0' - b;
return n;
} else if (!isNumber(b)) throw new NumberFormatException();
do n = n * 10 + b - '0'; while (isNumber(b = readByte()));
} catch (java.util.NoSuchElementException e) {}
return n;
}
public final int nextInt() {
if (!hasNext()) throw new java.util.NoSuchElementException();
int n = 0;
try {
byte b = readByte();
if (b == '-') {
while (isNumber(b = readByte())) n = n * 10 + '0' - b;
return n;
} else if (!isNumber(b)) throw new NumberFormatException();
do n = n * 10 + b - '0'; while (isNumber(b = readByte()));
} catch (java.util.NoSuchElementException e) {}
return n;
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
class Arrays {
public static void sort(final int[] array) {
sort(array, 0, array.length);
}
public static void sort(final int[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex <= 512) {
java.util.Arrays.sort(array, fromIndex, toIndex);
return;
}
sort(array, fromIndex, toIndex, 0, new int[array.length]);
}
private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {
if (to - from <= 512) {
java.util.Arrays.sort(a, from, to);
return;
}
final int BUCKET_SIZE = 256;
final int INT_RECURSION = 4;
final int MASK = 0xff;
final int shift = l << 3;
final int[] cnt = new int[BUCKET_SIZE + 1];
final int[] put = new int[BUCKET_SIZE];
for (int i = from; i < to; i++) ++cnt[(a[i] >>> shift & MASK) + 1];
for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
for (int i = from; i < to; i++) {
int bi = a[i] >>> shift & MASK;
bucket[cnt[bi] + put[bi]++] = a[i];
}
for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
int begin = cnt[i];
int len = cnt[i + 1] - begin;
System.arraycopy(bucket, begin, a, idx, len);
idx += len;
}
final int nxtL = l + 1;
if (nxtL < INT_RECURSION) {
sort(a, from, to, nxtL, bucket);
if (l == 0) {
int lft, rgt;
lft = from - 1;
rgt = to;
while (rgt - lft > 1) {
int mid = lft + rgt >> 1;
if (a[mid] < 0) lft = mid;
else rgt = mid;
}
reverse(a, from, rgt);
reverse(a, rgt, to);
}
}
}
public static void sort(final long[] array) {
sort(array, 0, array.length);
}
public static void sort(final long[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex <= 512) {
java.util.Arrays.sort(array, fromIndex, toIndex);
return;
}
sort(array, fromIndex, toIndex, 0, new long[array.length]);
}
private static final void sort(long[] a, final int from, final int to, final int l, final long[] bucket) {
final int BUCKET_SIZE = 256;
final int LONG_RECURSION = 8;
final int MASK = 0xff;
final int shift = l << 3;
final int[] cnt = new int[BUCKET_SIZE + 1];
final int[] put = new int[BUCKET_SIZE];
for (int i = from; i < to; i++) ++cnt[(int) ((a[i] >>> shift & MASK) + 1)];
for (int i = 0; i < BUCKET_SIZE; i++) cnt[i + 1] += cnt[i];
for (int i = from; i < to; i++) {
int bi = (int) (a[i] >>> shift & MASK);
bucket[cnt[bi] + put[bi]++] = a[i];
}
for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
int begin = cnt[i];
int len = cnt[i + 1] - begin;
System.arraycopy(bucket, begin, a, idx, len);
idx += len;
}
final int nxtL = l + 1;
if (nxtL < LONG_RECURSION) {
sort(a, from, to, nxtL, bucket);
if (l == 0) {
int lft, rgt;
lft = from - 1;
rgt = to;
while (rgt - lft > 1) {
int mid = lft + rgt >> 1;
if (a[mid] < 0) lft = mid;
else rgt = mid;
}
reverse(a, from, rgt);
reverse(a, rgt, to);
}
}
}
public static void reverse(int[] array) {
reverse(array, 0, array.length);
}
public static void reverse(int[] array, int fromIndex, int toIndex) {
for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {
int swap = array[fromIndex];
array[fromIndex] = array[toIndex];
array[toIndex] = swap;
}
}
public static void reverse(long[] array) {
reverse(array, 0, array.length);
}
public static void reverse(long[] array, int fromIndex, int toIndex) {
for (--toIndex; fromIndex < toIndex; ++fromIndex, --toIndex) {
long swap = array[fromIndex];
array[fromIndex] = array[toIndex];
array[toIndex] = swap;
}
}
public static void shuffle(int[] array) {
java.util.Random rnd = new java.util.Random();
for (int i = 0; i < array.length; ++i) {
int j = rnd.nextInt(array.length - i) + i;
int swap = array[i];
array[i] = array[j];
array[j] = swap;
}
}
public static void shuffle(long[] array) {
java.util.Random rnd = new java.util.Random();
for (int i = 0; i < array.length; ++i) {
int j = rnd.nextInt(array.length - i) + i;
long swap = array[i];
array[i] = array[j];
array[j] = swap;
}
}
}
class IntMath {
public static int gcd(int a, int b) {
while (a != 0) if ((b %= a) != 0) a %= b;
else return a;
return b;
}
public static int gcd(int... array) {
int ret = array[0];
for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);
return ret;
}
public static long gcd(long a, long b) {
while (a != 0) if ((b %= a) != 0) a %= b;
else return a;
return b;
}
public static long gcd(long... array) {
long ret = array[0];
for (int i = 1; i < array.length; ++i) ret = gcd(ret, array[i]);
return ret;
}
public static long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
public static int pow(int a, int b) {
int ans = 1;
for (int mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static long pow(long a, long b) {
long ans = 1;
for (long mul = a; b > 0; b >>= 1, mul *= mul) if ((b & 1) != 0) ans *= mul;
return ans;
}
public static int pow(int a, long b, int mod) {
if (b < 0) b = b % (mod - 1) + mod - 1;
long ans = 1;
for (long mul = a; b > 0; b >>= 1, mul = mul * mul % mod) if ((b & 1) != 0) ans = ans * mul % mod;
return (int) ans;
}
public static int pow(long a, long b, int mod) {
return pow((int) (a % mod), b, mod);
}
public static int floorsqrt(long n) {
return (int) Math.sqrt(n + 0.1);
}
public static int ceilsqrt(long n) {
return n <= 1 ? (int) n : (int) Math.sqrt(n - 0.1) + 1;
}
}