結果
| 問題 | No.117 組み合わせの数 |
| ユーザー |
 VvyLw
|
| 提出日時 | 2024-02-05 15:20:44 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 1,123 ms / 5,000 ms |
| コード長 | 51,832 bytes |
| コンパイル時間 | 4,501 ms |
| コンパイル使用メモリ | 109,220 KB |
| 実行使用メモリ | 366,972 KB |
| 最終ジャッジ日時 | 2024-09-28 11:34:40 |
| 合計ジャッジ時間 | 7,368 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
ソースコード
package yukicoder;
import java.io.Closeable;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Formatter;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.function.DoublePredicate;
import java.util.function.IntPredicate;
import java.util.function.LongPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
class Main {
public static void main(final String[] args) {
IntStream.range(0, VvyLw.MULTI ? VvyLw.sc.ni() : 1).forEach(i -> VvyLw.solve());
VvyLw.o.flush();
VvyLw.sc.close();
VvyLw.o.close();
VvyLw.dbg.close();
}
}
final class VvyLw extends Utility {
static final MyScanner sc = new MyScanner(System.in);
static final MyPrinter o = new MyPrinter(System.out, false), dbg = new MyPrinter(System.err, true);
static final boolean MULTI = false;
static final int INF = 1 << 30;
static final long LINF = (1L << 61) - 1;
static final double EPS = 1e-18;
static final int MOD = 998244353;
static final int M0D = (int) 1e9 + 7;
static final int[] dx = {0, -1, 1, 0, 0, -1, -1, 1, 1};
static final int[] dy = {0, 0, 0, -1, 1, -1, 1, -1, 1};
static final void solve() {
final var mp = new ModPrime(M0D, (int) 2e7 + 1);
final int t = sc.ni();
IntStream.range(0, t).forEach(i -> {
final var c = sc.nc();
final int n = sc.ni();
final int r = sc.ni();
final var skip = sc.nc();
//dbg.out(c, n, r, skip);
o.out(c == 'C' ? mp.C(n, r) : c == 'P' ? mp.P(n, r) : mp.H(n, r));
});
}
}
class Utility {
protected static final String yes(final boolean ok){ return ok ? "Yes" : "No"; }
protected static final String no(final boolean ok){ return yes(!ok); }
protected static final long sqr(final long x){ return x * x; }
protected static final long mod(long n, final long m) {
n %= m;
return n < 0 ? n + m : n;
}
protected static final long ceil(final long a, final long b){ return a == 0 ? 0 : (a - 1) / b + 1; }
protected static final double round(final double a, final long b, final int c) {
final long d = pow(10, c);
return Math.rint((a * d) / b) / d;
}
protected static final long pow(long a, int b) {
long res = 1;
while(b > 0) {
if(b % 2 == 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
protected static final long pow(long a, long b, final long m) {
long res = 1;
while(b > 0) {
if(b % 2 == 1) {
res *= a;
res = mod(res, m);
}
a *= a;
a = mod(a, m);
b >>= 1;
}
return res;
}
protected static final long lcm(final long a, final long b){ return a * b / gcd(a, b); }
protected static final long lcm(final int... a){ return Arrays.stream(a).asLongStream().reduce(1, (x, y) -> lcm(x, y)); }
protected static final long lcm(final long... a){ return Arrays.stream(a).reduce(1, (x, y) -> lcm(x, y)); }
protected static final long gcd(final long a, final long b){ return b > 0 ? gcd(b, a % b) : a; }
protected static final int gcd(final int... a){ return Arrays.stream(a).reduce(0, (x, y) -> (int) gcd(x, y)); }
protected static final long gcd(final long... a){ return Arrays.stream(a).reduce(0, (x, y) -> gcd(x, y)); }
protected static final int min(final int... a){ return Arrays.stream(a).min().getAsInt(); }
protected static final long min(final long... a){ return Arrays.stream(a).min().getAsLong(); }
protected static final double min(final double... a){ return Arrays.stream(a).min().getAsDouble(); }
protected static final int max(final int... a){ return Arrays.stream(a).max().getAsInt(); }
protected static final long max(final long... a){ return Arrays.stream(a).max().getAsLong(); }
protected static final double max(final double... a){ return Arrays.stream(a).max().getAsDouble(); }
protected static final long sum(final int... a){ return Arrays.stream(a).asLongStream().sum(); }
protected static final long sum(final long... a){ return Arrays.stream(a).sum(); }
protected static final double sum(final double... a){ return Arrays.stream(a).sum(); }
protected static final long prod(final int... a){ return Arrays.stream(a).asLongStream().reduce(1, (x, y) -> x * y); }
protected static final long prod(final long... a){ return Arrays.stream(a).reduce(1, (x, y) -> x * y); }
protected static final double prod(final double... a){ return Arrays.stream(a).reduce(1, (x, y) -> x * y); }
protected static final double ave(final int... a){ return Arrays.stream(a).average().getAsDouble(); }
protected static final double ave(final long... a){ return Arrays.stream(a).average().getAsDouble(); }
protected static final double ave(final double... a){ return Arrays.stream(a).average().getAsDouble(); }
protected static final double median(final int[] a) {
assert(isSorted(a));
final int m = a.length / 2;
return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2.0;
}
protected static final double median(final long[] a) {
assert(isSorted(a));
final int m = a.length / 2;
return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2.0;
}
protected static final double median(final double[] a) {
assert(isSorted(a));
final int m = a.length / 2;
return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2;
}
protected static final long[] div(final long n) {
final ArrayList<Long> d = new ArrayList<>();
for(long i = 1; i * i <= n; ++i) {
if(n % i == 0) {
d.add(i);
if(i * i != n) {
d.add(n / i);
}
}
}
return d.stream().mapToLong(i -> i).sorted().toArray();
}
protected static final IntPair[] primeFactor(long n) {
final ArrayList<IntPair> pf = new ArrayList<>();
for(long i = 2; i * i <= n; ++i) {
if(n % i != 0) {
continue;
}
int cnt = 0;
while(n % i == 0) {
cnt++;
n /= i;
}
pf.add(IntPair.of(i, cnt));
}
if(n != 1) {
pf.add(IntPair.of(n, 1));
}
return pf.toArray(IntPair[]::new);
}
protected static final long eulerPhi(long n) {
long res = n;
for(long i = 2; i * i <= n; ++i) {
if(n % i == 0) {
res -= res / i;
while(n % i == 0) {
n /= i;
}
}
}
if(n > 1) {
res -= res / n;
}
return res;
}
protected static final long sigma(final long n){ return n * (n + 1) / 2; }
protected static final long sigma(final long a, final long b){ return sigma(b) - sigma(a - 1); }
protected static final long factor(int n) {
long res = 1;
while(n > 0) {
res *= n--;
}
return res;
}
protected static final long factor(int n, final long mod) {
long res = 1;
while(n > 0) {
res *= n--;
res %= mod;
}
return res;
}
protected static final long perm(int n, final int r) {
final int og = n;
long res = 1;
while(n > og - r) {
res *= n--;
}
return res;
}
protected static final long perm(int n, final int r, final long mod) {
final int og = n;
long res = 1;
while(n > og - r) {
res *= n--;
res %= mod;
}
return res;
}
protected static final long binom(final int n, final int r) {
if(r < 0 || n < r) {
return 0;
}
int tmp = n;
long res = 1;
for(int i = 1; i <= min(n - r, r); ++i) {
res *= tmp--;
res /= i;
}
return res;
}
protected static final long binom(final int n, final int r, final long mod) {
if(r < 0 || n < r) {
return 0;
}
int tmp = n;
long res = 1;
for(int i = 1; i <= min(n - r, r); ++i) {
res *= tmp--;
res %= mod;
res /= i;
res %= mod;
}
return res;
}
protected static final boolean isInt(final double n){ return n == (long) Math.floor(n); }
protected static final boolean isSqr(final long n){ return isInt(Math.sqrt(n)); }
protected static final boolean isPrime(final long n) {
if(n == 1) {
return false;
}
for(long i = 2; i * i <= n; ++i) {
if(n % i == 0) {
return false;
}
}
return true;
}
protected static final boolean scope(final int l, final int x, final int r){ return l <= x && x <= r; }
protected static final boolean scope(final long l, final long x, final long r){ return l <= x && x <= r; }
protected static final boolean scope(final double l, final double x, final double r){ return l <= x && x <= r; }
protected static final int clamp(final int l, final int x, final int r){ return x < l ? l : x > r ? r : x; }
protected static final long clamp(final long l, final long x, final long r){ return x < l ? l : x > r ? r : x; }
protected static final double clamp(final double l, final double x, final double r){ return x < l ? l : x > r ? r : x; }
protected static final boolean isBit(final long i, final long j){ return (i >> j & 1) == 1; }
protected static final int[] nextPerm(final int[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] < a[i]) {
final int j = find(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return a;
}
}
return null;
}
protected static final long[] nextPerm(final long[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] < a[i]) {
final int j = find(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return a;
}
}
return null;
}
protected static final double[] nextPerm(final double[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] < a[i]) {
final int j = find(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return a;
}
}
return null;
}
protected static final String nextPerm(final String s) {
final List<Character> a = s.chars().mapToObj(i -> (char) i).collect(Collectors.toList());
for(int i = a.size(); --i > 0;) {
if(a.get(i - 1).compareTo(a.get(i)) < 0) {
final int j = find(a.get(i - 1), a, i, a.size() - 1);
Collections.swap(a, i - 1, j);
Collections.sort(a.subList(i, a.size()));
return a.stream().map(String::valueOf).collect(Collectors.joining());
}
}
return null;
}
protected static final int[] prevPerm(final int[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] > a[i]) {
final int j = findRev(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return reverse(a);
}
}
return null;
}
protected static final long[] prevPerm(final long[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] > a[i]) {
final int j = findRev(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return reverse(a);
}
}
return null;
}
protected static final double[] prevPerm(final double[] a) {
for(int i = a.length; --i > 0;) {
if(a[i - 1] > a[i]) {
final int j = findRev(a[i - 1], a, i, a.length - 1);
swap(a, i - 1, j);
Arrays.sort(a, i, a.length);
return reverse(a);
}
}
return null;
}
protected static final String prevPerm(final String s) {
final List<Character> a = s.chars().mapToObj(i -> (char)i).collect(Collectors.toList());
for(int i = a.size(); --i > 0;) {
if(a.get(i - 1).compareTo(a.get(i)) > 0) {
final int j = findRev(a.get(i - 1), a, i, a.size() - 1);
Collections.swap(a, i - 1, j);
Collections.sort(a.subList(i, a.size()), Collections.reverseOrder());
return a.stream().map(String::valueOf).collect(Collectors.joining());
}
}
return null;
}
private static final int find(final int dest, final int[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
}
private static final int find(final long dest, final long[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
}
private static final int find(final double dest, final double[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
}
private static final int find(final char dest, final List<Character> a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a.get(m).compareTo(dest) <= 0 ? find(dest, a, s, m - 1) : find(dest, a, m, e);
}
private static final int findRev(final int dest, final int[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
}
private static final int findRev(final long dest, final long[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
}
private static final int findRev(final double dest, final double[] a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
}
private static final int findRev(final char dest, final List<Character> a, final int s, final int e) {
if(s == e) {
return s;
}
final int m = (s + e + 1) / 2;
return a.get(m).compareTo(dest) > 0 ? find(dest, a, s, m - 1) : find(dest, a, m, e);
}
protected static final int find(final int[] a, final int x) {
for(int i = 0; i < a.length; ++i) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int find(final long[] a, final long x) {
for(int i = 0; i < a.length; ++i) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int find(final double[] a, final double x) {
for(int i = 0; i < a.length; ++i) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int find(final char[] s, final char c) {
for(int i = 0; i < s.length; ++i) {
if(s[i] == c) {
return i;
}
}
return -1;
}
protected static final int find(final Object[] a, final Object x) {
for(int i = 0; i < a.length; ++i) {
if(a[i].equals(x)) {
return i;
}
}
return -1;
}
protected static final int findRev(final int[] a, final int x) {
for(int i = a.length; --i >= 0;) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int findRev(final long[] a, final long x) {
for(int i = a.length; --i >= 0;) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int findRev(final double[] a, final double x) {
for(int i = a.length; --i >= 0;) {
if(a[i] == x) {
return i;
}
}
return -1;
}
protected static final int findRev(final char[] s, final char c) {
for(int i = s.length; --i >= 0;) {
if(s[i] == c) {
return i;
}
}
return -1;
}
protected static final int findRev(final Object[] a, final Object x) {
for(int i = a.length; --i >= 0;) {
if(a[i].equals(x)) {
return i;
}
}
return -1;
}
protected static final boolean binarySearch(final int[] a, final int x){ return Arrays.binarySearch(a, x) >= 0; }
protected static final boolean binarySearch(final long[] a, final long x){ return Arrays.binarySearch(a, x) >= 0; }
protected static final <T extends Comparable<? super T>> boolean binarySearch(final T[] a, final T x){ return Arrays.binarySearch(a, x) >= 0; }
protected static final <T extends Comparable<? super T>> boolean binarySearch(final List<T> a, final T x){ return Collections.binarySearch(a, x, null) >= 0; }
protected static final int lowerBound(final int[] a, final int x){ return bins(a.length, -1, (IntPredicate) y -> a[y] >= x); }
protected static final int lowerBound(final long[] a, final long x){ return bins(a.length, -1, (IntPredicate) y -> a[y] >= x); }
protected static final <T extends Comparable<? super T>> int lowerBound(final T[] a, final T x){ return lowerBound(Arrays.asList(a), x); }
protected static final <T extends Comparable<? super T>> int lowerBound(final List<T> a, final T x){ return ~Collections.binarySearch(a, x, (p, q) -> p.compareTo(q) >= 0 ? 1 : -1); }
protected static final int upperBound(final int[] a, final int x){ return bins(a.length, -1, (IntPredicate) y -> a[y] > x); }
protected static final int upperBound(final long[] a, final long x){ return bins(a.length, -1, (IntPredicate) y -> a[y] > x); }
protected static final <T extends Comparable<? super T>> int upperBound(final T[] a, final T x){ return upperBound(Arrays.asList(a), x); }
protected static final <T extends Comparable<? super T>> int upperBound(final List<T> a, final T x){ return ~Collections.binarySearch(a, x, (p, q) -> p.compareTo(q) > 0 ? 1 : -1); }
protected static final String sorted(final String s){ return s.chars().sorted().mapToObj(Character::toString).collect(Collectors.joining()); }
protected static final int[] sorted(final int[] a){ return Arrays.stream(a).sorted().toArray(); }
protected static final long[] sorted(final long[] a){ return Arrays.stream(a).sorted().toArray(); }
protected static final double[] sorted(final double[] a){ return Arrays.stream(a).sorted().toArray(); }
protected static final <T extends Comparable<? super T>> T[] sorted(final T[] a){ return Arrays.stream(a).sorted().toArray(n -> Arrays.copyOf(a, n)); }
protected static final boolean isSorted(final String s){ return s.equals(sorted(s)); }
protected static final boolean isSorted(final int[] a){ return Arrays.equals(a, sorted(a)); }
protected static final boolean isSorted(final long[] a){ return Arrays.equals(a, sorted(a)); }
protected static final boolean isSorted(final double[] a){ return Arrays.equals(a, sorted(a)); }
protected static final <T extends Comparable<? super T>> boolean isSorted(final T[] a){ return Arrays.equals(a, sorted(a)); }
protected static final String reverse(final String s){ return new StringBuilder(s).reverse().toString(); }
protected static final int[] reverse(final int[] a) {
final int n = a.length;
final int[] b = new int[n];
for(int i = 0; i <= n / 2; ++i) {
b[i] = a[n - 1 - i];
b[n - 1 - i] = a[i];
}
return b;
}
protected static final long[] reverse(final long[] a) {
final int n = a.length;
final long[] b = new long[n];
for(int i = 0; i <= n / 2; ++i) {
b[i] = a[n - 1 - i];
b[n - 1 - i] = a[i];
}
return b;
}
protected static final double[] reverse(final double[] a) {
final int n = a.length;
final double[] b = new double[n];
for(int i = 0; i <= n / 2; ++i) {
b[i] = a[n - 1 - i];
b[n - 1 - i] = a[i];
}
return b;
}
protected static final Object[] reverse(final Object[] a) {
final int n = a.length;
final Object[] b = new Object[n];
for(int i = 0; i <= n / 2; ++i) {
b[i] = a[n - 1 - i];
b[n - 1 - i] = a[i];
}
return b;
}
protected static final int[] rotate(final int[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final int[] res = new int[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final long[] rotate(final long[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final long[] res = new long[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final double[] rotate(final double[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final double[] res = new double[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final char[] rotate(final char[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final char[] res = new char[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final boolean[] rotate(final boolean[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final boolean[] res = new boolean[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final Object[] rotate(final Object[] a, final int id) {
final int n = a.length, k = (int) mod(id, n);
final Object[] res = new Object[n];
System.arraycopy(a, k, res, 0, n - k);
System.arraycopy(a, 0, res, n - k, k);
return res;
}
protected static final String rotate(final String s, final int id) {
final List<Character> t = s.chars().mapToObj(i -> (char) i).collect(Collectors.toList());
Collections.rotate(t, id);
return t.stream().map(String::valueOf).collect(Collectors.joining());
}
protected static final int[][] rotateR(final int[][] a) {
final int h = a.length, w = a[0].length;
final int[][] b = new int[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][i]);
});
IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
return b;
}
protected static final long[][] rotateR(final long[][] a) {
final int h = a.length, w = a[0].length;
final long[][] b = new long[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][i]);
});
IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
return b;
}
protected static final double[][] rotateR(final double[][] a) {
final int h = a.length, w = a[0].length;
final double[][] b = new double[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][i]);
});
IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
return b;
}
protected static final String[] rotateR(final String[] s) {
final int h = s.length, w = s[0].length();
final char[][] t = new char[w][h];
IntStream.range(0, h).forEach(i -> {
IntStream.range(0, w).forEach(j -> t[j][i] = s[i].charAt(j));
});
IntStream.range(0, w).forEach(i -> t[i] = new StringBuilder(new String(t[i])).reverse().toString().toCharArray());
final String[] res = new String[w];
Arrays.setAll(res, i -> String.valueOf(t[i]));
return res;
}
protected static final int[][] rotateL(final int[][] a) {
final int h = a.length, w = a[0].length;
final int[][] b = new int[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][w - i - 1]);
});
return b;
}
protected static final long[][] rotateL(final long[][] a) {
final int h = a.length, w = a[0].length;
final long[][] b = new long[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][w - i - 1]);
});
return b;
}
protected static final double[][] rotateL(final double[][] a) {
final int h = a.length, w = a[0].length;
final double[][] b = new double[w][h];
IntStream.range(0, h).forEach(i -> {
Arrays.setAll(b[i], j -> a[j][w - i - 1]);
});
return b;
}
protected static final String[] rotateL(final String[] s) {
final int h = s.length, w = s[0].length();
final char[][] t = new char[w][h];
IntStream.range(0, h).forEach(i -> {
IntStream.range(0, w).forEach(j -> t[w - j - 1][i] = s[i].charAt(j));
});
final String[] res = new String[w];
Arrays.setAll(res, i -> String.valueOf(t[i]));
return res;
}
protected static final void swap(final int[] a, final int i, final int j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
protected static final void swap(final long[] a, final int i, final int j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
protected static final void swap(final double[] a, final int i, final int j) {
final double tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
protected static final void swap(final char[] a, final int i, final int j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
protected static final void swap(final boolean[] a, final int i, final int j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
protected static final void swap(final Object[] a, final int i, final int j) {
final Object tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
protected static final void swap(final int[] a, final int[] b) {
assert a.length == b.length;
final int n = a.length;
final int[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final void swap(final long[] a, final long[] b) {
assert a.length == b.length;
final int n = a.length;
final long[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final void swap(final double[] a, final double[] b) {
assert a.length == b.length;
final int n = a.length;
final double[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final void swap(final char[] a, final char[] b) {
assert a.length == b.length;
final int n = a.length;
final char[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final void swap(final boolean[] a, final boolean[] b) {
assert a.length == b.length;
final int n = a.length;
final boolean[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final void swap(final Object[] a, final Object[] b) {
assert a.length == b.length;
final int n = a.length;
final Object[] c = a.clone();
System.arraycopy(b, 0, a, 0, n);
System.arraycopy(c, 0, b, 0, n);
}
protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> Pair<S, F>[] swap(final Pair<F, S>[] p) {
@SuppressWarnings("unchecked")
final Pair<S, F>[] q = new Pair[p.length];
IntStream.range(0, p.length).forEach(i -> q[i] = p[i].swap());
return q;
}
protected static final IntPair[] swap(final IntPair[] p) {
final IntPair[] q = new IntPair[p.length];
IntStream.range(0, p.length).forEach(i -> q[i] = p[i].swap());
return q;
}
protected static final FloatPair[] swap(final FloatPair[] p) {
final FloatPair[] q = new FloatPair[p.length];
IntStream.range(0, p.length).forEach(i -> q[i] = p[i].swap());
return q;
}
@SuppressWarnings("unchecked")
protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> F[] first(final Pair<F, S>[] p){ return (F[]) Arrays.stream(p).map(i -> i.first).toArray(); }
protected static final long[] first(final IntPair[] p){ return Arrays.stream(p).mapToLong(i -> i.first).toArray(); }
protected static final double[] first(final FloatPair[] p){ return Arrays.stream(p).mapToDouble(i -> i.first).toArray(); }
@SuppressWarnings("unchecked")
protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> S[] second(final Pair<F, S>[] p){ return (S[]) Arrays.stream(p).map(i -> i.second).toArray(); }
protected static final long[] second(final IntPair[] p){ return Arrays.stream(p).mapToLong(i -> i.second).toArray(); }
protected static final double[] second(final FloatPair[] p){ return Arrays.stream(p).mapToDouble(i -> i.second).toArray(); }
protected static final int[] iota(final int n){ return IntStream.range(0, n).toArray(); }
protected static final int[] iota(final int n, final int init){ return IntStream.range(0 + init, n + init).toArray(); }
protected static final int[] merge(final int[] a, final int[] b) {
final int[] c = new int[a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
return c;
}
protected static final long[] merge(final long[] a, final long[] b) {
final long[] c = new long[a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
return c;
}
protected static final double[] merge(final double[] a, final double[] b) {
final double[] c = new double[a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
return c;
}
protected static final String[] merge(final String[] a, final String[] b) {
final String[] c = new String[a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
Arrays.sort(c);
return c;
}
private static final int bins(int ok, int ng, final IntPredicate fn) {
while(Math.abs(ok - ng) > 1) {
final int mid = (ok + ng) / 2;
if(fn.test(mid)) {
ok = mid;
}
else {
ng = mid;
}
}
return ok;
}
protected static final long bins(long ok, long ng, final LongPredicate fn) {
while(Math.abs(ok - ng) > 1) {
final long mid = (ok + ng) / 2;
if(fn.test(mid)) {
ok = mid;
}
else {
ng = mid;
}
}
return ok;
}
protected static final double bins(double ok, double ng, final DoublePredicate fn) {
while(Math.abs(ok - ng) > VvyLw.EPS) {
final double mid = (ok + ng) / 2;
if(fn.test(mid)) {
ok = mid;
}
else {
ng = mid;
}
}
return ok;
}
protected static final int[] count(final int[] a) {
final int[] res = new int[max(a) + 1];
for(final int i: a) {
res[i]++;
}
return res;
}
protected static final Map<Long, Integer> count(final long[] a) {
final Map<Long, Integer> res = new HashMap<>();
for(final long i: a) {
res.merge(i, 1, (x, y) -> x + y);
}
return res;
}
protected static final int[] press(final int[] a) {
final int[] res = new int[a.length];
final int[] x = Arrays.stream(a).sorted().distinct().toArray();
for(int i = 0; i < a.length; ++i) {
res[i] = lowerBound(x, a[i]);
}
return res;
}
protected static final int[] press(final long[] a) {
final int[] res = new int[a.length];
final long[] x = Arrays.stream(a).sorted().distinct().toArray();
for(int i = 0; i < a.length; ++i) {
res[i] = lowerBound(x, a[i]);
}
return res;
}
protected static final String rle(final String s) {
final int n = s.length();
final StringBuilder sb = new StringBuilder();
for(int l = 0; l < n;) {
int r = l + 1;
for(; r < n && s.charAt(l) == s.charAt(r); ++r){}
sb.append(s.charAt(l));
sb.append(r - l);
l = r;
}
return sb.toString();
}
protected static final String rleRev(final String s) {
final int n = s.length();
final StringBuilder sb = new StringBuilder();
for(int l = 0; l < n;) {
int r = l + 1;
for(; r < n && scope('0', s.charAt(r), '9'); ++r){}
sb.append(String.valueOf(s.charAt(l)).repeat(Integer.parseInt(s.substring(l + 1, r))));
l = r;
}
return sb.toString();
}
protected static final int[] zAlgorithm(final String s) {
final int n = s.length();
int j = 0;
final int[] pre = new int[n];
for(int i = 0; ++i < n;) {
if(i + pre[i - j] < j + pre[j]) {
pre[i] = pre[i - j];
}
else {
int k = Math.max(0, j + pre[j] - i);
while(i + k < n && s.charAt(k) == s.charAt(i + k)) {
++k;
}
pre[i] = k;
j = i;
}
}
pre[0] = n;
return pre;
}
protected static final int[] manacher(final String s_, final boolean calcEven) {
int n = s_.length();
final char[] s;
if(calcEven) {
s = new char[2 * n - 1];
IntStream.range(0, n).forEach(i -> s[i] = s_.charAt(i));
for(int i = n; --i >= 0;) {
s[2 * i] = s_.charAt(i);
}
final char d = Collections.min(s_.chars().mapToObj(c -> (char) c).collect(Collectors.toList()));
for(int i = 0; i < n - 1; ++i) {
s[2 * i + 1] = d;
}
} else {
s = new char[n];
IntStream.range(0, n).forEach(i -> s[i] = s_.charAt(i));
}
n = s.length;
final int[] rad = new int[n];
for(int i = 0, j = 0; i < n;) {
while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) {
++j;
}
rad[i] = j;
int k = 1;
while(i - k >= 0 && i + k < n && k + rad[i - k] < j) {
rad[i + k] = rad[i - k];
++k;
}
i += k;
j -= k;
}
if(calcEven) {
for(int i = 0; i < n; ++i) {
if(((i ^ rad[i]) & 1) == 0) {
rad[i]--;
}
}
} else {
for(int x: rad) {
x = 2 * x - 1;
}
}
return rad;
}
protected static final long kthRoot(final long n, final int k) {
if(k == 1) {
return n;
}
final LongPredicate chk = x -> {
long mul = 1;
for(int j = 0; j < k; ++j) {
try {
mul = Math.multiplyExact(mul, x);
} catch(final ArithmeticException e) {
return false;
}
}
return mul <= n;
};
long ret = 0;
for(int i = 32; --i >= 0;) {
if(chk.test(ret | (1L << i))) {
ret |= 1L << i;
}
}
return ret;
}
protected static final long tetration(final long a, final long b, final long m) {
if(m == 1) {
return 0;
}
if(a == 0) {
return (b & 1) == 0 ? 1 : 0;
}
if(b == 0) {
return 1;
}
if(b == 1) {
return a % m;
}
if(b == 2) {
return pow(a, a, m);
}
final long phi = eulerPhi(m);
long tmp = tetration(a, b - 1, phi);
if(tmp == 0) {
tmp += phi;
}
return pow(a, tmp, m);
}
protected static final long floorSum(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 ym = (a * n + b) / m, xm = (ym * m - b);
if(ym == 0) {
return ans;
}
ans += (n - (xm + a - 1) / a) * ym;
ans += floorSum(ym, a, m, (a - xm % a) % a);
return ans;
}
}
interface TriFunction<T, U, V, W> {
public W apply(final T a, final U b, final V c);
}
interface QuadFunction<A, B, C, D, E> {
public E apply(final A a, final B b, final C c, final D d);
}
interface RecursiveFunction<T, U> {
public U apply(final RecursiveFunction<T, U> rec, final T n);
}
interface RecursiveBiFunction<T, U, V> {
public V apply(final RecursiveBiFunction<T, U, V> rec, final T n, final U m);
}
interface RecursiveTriFunction<T, U, V, W> {
public W apply(final RecursiveTriFunction<T, U, V, W> rec, final T p, final U q, final V r);
}
interface RecursiveUnaryOperator<T> {
public T apply(final RecursiveUnaryOperator<T> rec, final T n);
}
interface RecursiveBinaryOperator<T> {
public T apply(final RecursiveBinaryOperator<T> rec, final T a, final T b);
}
interface RecursiveConsumer<T> {
public void accept(final RecursiveConsumer<T> rec, final T x);
}
interface RecursiveBiConsumer<T, U> {
public void accept(final RecursiveBiConsumer<T, U> rec, final T x, final U y);
}
interface RecursiveTriConsumer<T, U, V> {
public void accept(final RecursiveTriConsumer<T, U, V> rec, final T x, final U y, final V z);
}
final class MyScanner implements Closeable, AutoCloseable {
private int pos, lim;
private final byte[] buf;
private final InputStream is;
MyScanner(final InputStream is) {
this.is = is;
pos = lim = 0;
buf = new byte[1 << 17];
}
private final boolean isPunct(final byte bt){ return !Utility.scope(33, bt, 126); }
private final boolean isNum(final byte bt){ return Utility.scope('0', bt, '9'); }
private final byte read() {
if(pos == lim && lim != -1) {
try {
lim = is.read(buf);
pos = 0;
} catch(final IOException e) {
e.printStackTrace();
}
}
return buf[pos++];
}
private final byte next() {
byte bt;
if(pos > 0) {
bt = buf[pos - 1];
if(!isPunct(bt)) {
read();
return bt;
}
}
while(isPunct(bt = read())){}
return bt;
}
private final byte nextInt() {
byte bt;
if(pos > 0) {
bt = buf[pos - 1];
if(isNum(bt)) {
read();
return bt;
}
}
while(!isNum(bt = read())){}
return bt;
}
final int ni(){ return Math.toIntExact(nl()); }
final long nl() {
byte c = nextInt();
final boolean neg = c == '-';
if(neg) {
c = read();
}
assert(isNum(c));
long res = c - '0';
while(isNum(c = read())) {
res = 10 * res + c - '0';
}
return neg ? -res : res;
}
final double nd(){ return Double.parseDouble(ns()); }
final char nc(){ return (char) next(); }
final String ns() {
final StringBuilder sb = new StringBuilder();
byte c = next();
while(!isPunct(c)) {
sb.append((char) c);
c = read();
}
return sb.toString();
}
final BigInteger nb(){ return new BigInteger(ns()); }
final int[] ni(final int n) {
final int[] a = new int[n];
IntStream.range(0, n).forEach(i -> a[i] = ni());
return a;
}
final long[] nl(final int n) {
final long[] a = new long[n];
IntStream.range(0, n).forEach(i -> a[i] = nl());
return a;
}
final double[] nd(final int n) {
final double[] a = new double[n];
IntStream.range(0, n).forEach(i -> a[i] = nd());
return a;
}
final char[] nc(final int n) {
final char[] a = new char[n];
IntStream.range(0, n).forEach(i -> a[i] = nc());
return a;
}
final String[] ns(final int n) {
final String[] a = new String[n];
IntStream.range(0, n).forEach(i -> a[i] = ns());
return a;
}
final BigInteger[] nb(final int n) {
final BigInteger[] a = new BigInteger[n];
IntStream.range(0, n).forEach(i -> a[i] = nb());
return a;
}
final int[][] ni(final int h, final int w) {
final int[][] a = new int[h][w];
IntStream.range(0, h).forEach(i -> a[i] = ni(w));
return a;
}
final long[][] nl(final int h, final int w) {
final long[][] a = new long[h][w];
IntStream.range(0, h).forEach(i -> a[i] = nl(w));
return a;
}
final double[][] nd(final int h, final int w) {
final double[][] a = new double[h][w];
IntStream.range(0, h).forEach(i -> a[i] = nd(w));
return a;
}
final char[][] nc(final int h, final int w) {
final char[][] a = new char[h][w];
IntStream.range(0, h).forEach(i -> a[i] = nc(w));
return a;
}
final String[][] ns(final int h, final int w) {
final String[][] a = new String[h][w];
IntStream.range(0, h).forEach(i -> a[i] = ns(w));
return a;
}
final BigInteger[][] nb(final int h, final int w) {
final BigInteger[][] a = new BigInteger[h][w];
IntStream.range(0, h).forEach(i -> a[i] = nb(w));
return a;
}
final String line() {
final StringBuilder sb = new StringBuilder();
byte c;
while((c = read()) != '\n') {
sb.append((char) c);
}
return sb.toString();
}
final IntPair pi(){ return IntPair.of(nl(), nl()); }
final IntPair[] pi(final int n) {
final IntPair[] p = new IntPair[n];
IntStream.range(0, n).forEach(i -> p[i] = pi());
return p;
}
final FloatPair pf(){ return FloatPair.of(nd(), nd()); }
final FloatPair[] pf(final int n) {
final FloatPair[] p = new FloatPair[n];
IntStream.range(0, n).forEach(i -> p[i] = pf());
return p;
}
@Override
public final void close() {
try {
is.close();
} catch(final IOException e) {
e.printStackTrace();
}
}
}
final class MyPrinter implements Closeable, Flushable, AutoCloseable {
private OutputStream os;
private final boolean autoFlush;
private final byte[] buf;
private int pos;
private final boolean debug;
MyPrinter(final OutputStream os, final boolean autoFlush){
this.os = os;
this.autoFlush = autoFlush;
buf = new byte[1 << 17];
pos = 0;
debug = os == System.err;
}
private final void write(final byte bt) {
buf[pos++] = bt;
if(pos == buf.length) {
flush();
}
}
private final void newLine() {
write((byte) '\n');
if(autoFlush) {
flush();
}
}
final void print(final Object arg) {
if(arg instanceof final String s) {
for(final char c: s.toCharArray()) {
write((byte) c);
}
} else {
print(String.valueOf(arg));
}
}
final void printf(final String fmt, final Object... args) {
print(new Formatter().format(fmt, args));
if(autoFlush) {
flush();
}
}
final void out(){ newLine(); }
final void out(final Object head, final Object... tail) {
print(head);
for(final var el: tail) {
print(" " + el);
}
newLine();
}
final <F extends Comparable<? super F>, S extends Comparable<? super S>> void out(final Pair<F, S> arg) {
if(debug) {
print(arg.toString());
} else {
print(arg.first + " " + arg.second);
}
newLine();
}
final void out(final int[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final void out(final long[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final void out(final double[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final void out(final boolean[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final void out(final char[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final void out(final Object[] args) {
if(debug) {
print(Arrays.toString(args));
} else if(args.length > 0) {
print(args[0]);
for(int i = 0; ++i < args.length;) {
print(" " + args[i]);
}
}
newLine();
}
final <E> void out(final Collection<E> args) {
if(debug) {
print(args.toString());
} else {
int i = 0;
for(final var el: args) {
print(el);
if(++i != args.size()) {
print(" ");
}
}
}
newLine();
}
final void outl(final Object head, final Object... tail) {
out(head);
Arrays.stream(tail).forEach(this::out);
}
final void outl(final int[] args){ Arrays.stream(args).forEach(this::out); }
final void outl(final int[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final long[] args){ Arrays.stream(args).forEach(this::out); }
final void outl(final long[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final double[] args){ Arrays.stream(args).forEach(this::out); }
final void outl(final double[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final boolean[] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final boolean[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final char[] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final char[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
final void outl(final Object[] args){ Arrays.stream(args).forEach(this::out); }
final void outl(final Object[][] args){ Arrays.stream(args).forEach(this::out); }
final <F extends Comparable<? super F>, S extends Comparable<? super S>> void outl(final Pair<F, S>[] args){ Arrays.stream(args).forEach(this::out); }
final <E> void outl(final Collection<E> args){ args.stream().forEach(this::out); }
final void fin(final Object head, final Object... tail) {
out(head, tail);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final <F extends Comparable<? super F>, S extends Comparable<? super S>> void fin(final Pair<F, S> arg) {
out(arg);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final int[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final long[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final double[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final boolean[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final char[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void fin(final Object[] args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final <E> void fin(final Collection<E> args) {
out(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final Object head, final Object... tail ) {
outl(head, tail);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final int[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final int[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final long[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final long[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final double[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final double[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final boolean[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final boolean[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final char[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final char[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final Object[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final void ende(final Object[][] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final <F extends Comparable<? super F>, S extends Comparable<? super S>> void ende(final Pair<F, S>[] args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
final <E> void ende(final Collection<E> args) {
outl(args);
if(!autoFlush) {
flush();
}
System.exit(0);
}
@Override
public final void flush() {
try {
os.write(buf, 0, pos);
pos = 0;
} catch(final IOException e) {
e.printStackTrace();
}
}
@Override
public final void close() {
if(os == null) {
return;
}
try {
os.close();
os = null;
} catch(final IOException e) {
e.printStackTrace();
}
}
}
class Pair<F extends Comparable<? super F>, S extends Comparable<? super S>> implements Comparable<Pair<F, S>>, Cloneable {
public F first;
public S second;
protected Pair(final F first, final S second) {
this.first = first;
this.second = second;
}
static final <F extends Comparable<? super F>, S extends Comparable<? super S>> Pair<F, S> of(final F a, final S b){ return new Pair<>(a, b); }
Pair<S, F> swap(){ return Pair.of(second, first); }
@Override
public final boolean equals(final Object o) {
if(this == o) {
return true;
}
if(o == null || getClass() != o.getClass()) {
return false;
}
final Pair<?, ?> p = (Pair<?, ?>) o;
return first.equals(p.first) && second.equals(p.second);
}
@Override
public final int hashCode(){ return Objects.hash(first, second); }
@Override
public final String toString(){ return "(" + first + ", " + second + ")"; }
@SuppressWarnings("unchecked")
@Override
public final Pair<F, S> clone() {
try {
return (Pair<F, S>) super.clone();
} catch(final CloneNotSupportedException e){
e.printStackTrace();
}
throw new Error();
}
@Override
public final int compareTo(final Pair<F, S> p) {
if(first.compareTo(p.first) == 0) {
return second.compareTo(p.second);
}
return first.compareTo(p.first);
}
}
final class IntPair extends Pair<Long, Long> {
private IntPair(final long first, final long second){ super(first, second); }
static final IntPair of(final long a, final long b){ return new IntPair(a, b); }
@Override
final IntPair swap(){ return new IntPair(second, first); }
final IntPair add(final IntPair p){ return new IntPair(first + p.first, second + p.second); }
final IntPair sub(final IntPair p){ return new IntPair(first - p.first, second - p.second); }
final IntPair mul(final IntPair p){ return new IntPair(first * p.first, second * p.second); }
final IntPair div(final IntPair p){ return new IntPair(first / p.first, second / p.second); }
final IntPair mod(final IntPair p){ return new IntPair(first % p.first, second % p.second); }
final IntPair rotate(){ return new IntPair(-second, first); }
final FloatPair rotate(final int ang) {
final double rad = Math.toRadians(Utility.mod(ang, 360));
return FloatPair.of(first * Math.cos(rad) - second * Math.sin(rad), first * Math.sin(rad) + second * Math.cos(rad));
}
final long dot(final IntPair p){ return first * p.first + second * p.second; }
final long cross(final IntPair p){ return rotate().dot(p); }
final long sqr(){ return dot(this); }
final double grad() {
try {
return 1.0 * second / first;
} catch(final ArithmeticException e) {
e.printStackTrace();
}
throw new Error();
}
final double abs(){ return Math.hypot(first, second); }
final long lcm(){ return Utility.lcm(first, second); }
final long gcd(){ return Utility.gcd(first, second); }
final IntPair extgcd() {
long x = 1, y = 0, t1 = 0, t2 = 0, t3 = 1, a = first, b = second;
while(b > 0) {
t1 = a / b;
a -= t1 * b;
a ^= b;
b ^= a;
a ^= b;
x -= t1 * t2;
x ^= t2;
t2 ^= x;
x ^= t2;
y -= t1 * t3;
y ^= t3;
t3 ^= y;
y ^= t3;
}
return new IntPair(x, y);
}
}
final class FloatPair extends Pair<Double, Double> {
private FloatPair(final double first, final double second){ super(first, second); }
static final FloatPair of(final double a, final double b){ return new FloatPair(a, b); }
@Override
final FloatPair swap(){ return new FloatPair(second, first); }
final FloatPair add(final FloatPair p){ return new FloatPair(first + p.first, second + p.second); }
final FloatPair sub(final FloatPair p){ return new FloatPair(first - p.first, second - p.second); }
final FloatPair mul(final FloatPair p){ return new FloatPair(first * p.first, second * p.second); }
final FloatPair div(final FloatPair p){ return new FloatPair(first / p.first, second / p.second); }
final FloatPair rotate(){ return new FloatPair(-second, first); }
final FloatPair rotate(final int ang) {
final double rad = Math.toRadians(Utility.mod(ang, 360));
return FloatPair.of(first * Math.cos(rad) - second * Math.sin(rad), first * Math.sin(rad) + second * Math.cos(rad));
}
final double dot(final FloatPair p){ return first * p.first + second * p.second; }
final double cross(final FloatPair p){ return rotate().dot(p); }
final double sqr(){ return dot(this); }
final double grad() {
try {
return second / first;
} catch(final ArithmeticException e) {
e.printStackTrace();
}
throw new Error();
}
final double abs(){ return Math.hypot(first, second); }
}
/**
* 二項係数の演算を高速で行うクラス
* modは素数
* 前計算にO(len + log mod)かかる
* @see <a href="https://blog.hamayanhamayan.com/entry/2018/06/06/210256">参考元</a>
*/
final class ModPrime {
private final int len, mod;
private final long[] f, rf;
/**
* コンストラクタ
* @param mod 素数
* @param sz 取りうる値の最大値
*/
ModPrime(final int mod, final int sz) {
this.mod = mod;
len = Math.min(sz + 1, mod);
f = new long[len];
rf = new long[len];
init();
}
private final long inv(long x) {
long res = 1, k = mod - 2;
while(k > 0) {
if(k % 2 == 1) {
res = (res * x) % mod;
}
x = (x * x) % mod;
k >>= 1;
}
return res;
}
private final void init() {
f[0] = 1;
for(int i = 0; ++i < len;) {
f[i] = (f[i - 1] * i) % mod;
}
rf[len - 1] = inv(f[len - 1]);
for(int i = len; --i > 0;) {
rf[i - 1] = (rf[i] * i) % mod;
}
}
/**
* @param n
* @param k
* @return 二項係数
*/
final long C(final int n, final int k) {
if(k < 0 || n < k) {
return 0;
}
final long a = f[n], b = rf[n - k], c = rf[k], bc = (b * c) % mod;
return (a * bc) % mod;
}
/**
* @param n
* @param k
* @return 順列
*/
final long P(final int n, final int k) {
if (k < 0 || n < k) {
return 0;
}
final long a = f[n], b = rf[n - k];
return (a * b) % mod;
}
/**
* @param n
* @param k
* @return 重複順列
*/
final long H(final int n, final int k) {
if (n == 0 && k == 0) {
return 1;
}
return C(n + k - 1, k);
}
/**
* @param n
* @return 階乗 mod P
*/
final long factor(final int n){ return f[n]; }
}