結果
| 問題 | No.2857 Div Array |
| ユーザー |
 ゆうき
|
| 提出日時 | 2024-08-25 16:15:51 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 230 ms / 2,000 ms |
| コード長 | 28,642 bytes |
| コンパイル時間 | 4,402 ms |
| コンパイル使用メモリ | 100,008 KB |
| 実行使用メモリ | 54,476 KB |
| 最終ジャッジ日時 | 2024-08-25 16:16:03 |
| 合計ジャッジ時間 | 8,538 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 72 ms
50,944 KB |
| testcase_01 | AC | 63 ms
50,856 KB |
| testcase_02 | AC | 62 ms
50,888 KB |
| testcase_03 | AC | 64 ms
50,908 KB |
| testcase_04 | AC | 61 ms
50,288 KB |
| testcase_05 | AC | 62 ms
50,952 KB |
| testcase_06 | AC | 62 ms
50,932 KB |
| testcase_07 | AC | 66 ms
51,228 KB |
| testcase_08 | AC | 65 ms
51,112 KB |
| testcase_09 | AC | 63 ms
51,052 KB |
| testcase_10 | AC | 88 ms
51,940 KB |
| testcase_11 | AC | 194 ms
52,260 KB |
| testcase_12 | AC | 110 ms
52,312 KB |
| testcase_13 | AC | 95 ms
52,256 KB |
| testcase_14 | AC | 183 ms
52,176 KB |
| testcase_15 | AC | 102 ms
52,180 KB |
| testcase_16 | AC | 70 ms
51,068 KB |
| testcase_17 | AC | 170 ms
51,976 KB |
| testcase_18 | AC | 163 ms
52,332 KB |
| testcase_19 | AC | 131 ms
52,148 KB |
| testcase_20 | AC | 219 ms
54,296 KB |
| testcase_21 | AC | 230 ms
54,368 KB |
| testcase_22 | AC | 223 ms
54,308 KB |
| testcase_23 | AC | 220 ms
54,476 KB |
| testcase_24 | AC | 74 ms
51,036 KB |
| testcase_25 | AC | 70 ms
51,184 KB |
| testcase_26 | AC | 75 ms
51,168 KB |
| testcase_27 | AC | 69 ms
51,160 KB |
| testcase_28 | AC | 62 ms
50,640 KB |
| testcase_29 | AC | 66 ms
51,084 KB |
ソースコード
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.ArrayList;
import java.util.concurrent.*;
import java.util.function.*;
public final class Main{
public static void main(String[] args) throws Exception{
MyReader in = new MyReader(System.in);
MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);
int T = Solver.multi ? in.it() : 1;
while (T-- > 0)
Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);
out.flush();
}
}
class Solver extends BaseSolver{
public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }
public static boolean multi = false;
public Object solve(){
int N = in.it();
int M = in.it();
int K = in.it();
TreeMap<Integer, Integer> mp = new TreeMap<>();
for (int m = 1;m <= M;m++)
mp.merge(M /m,1,Integer::sum);
int[][] map = new int[mp.size()][2];
for (int i = 0;i < map.length;i++) {
var e = mp.pollFirstEntry();
map[i][0] = e.getKey();
map[i][1] = e.getValue();
}
long[] A = Util.arrL(map.length,i -> map[i][1]);
long[][] X = new long[map.length][map.length];
for (int i = 0;i < map.length;i++)
for (int j = 0;j < map.length;j++)
if (abs(map[i][0] -map[j][0]) <= K)
X[i][j] += map[j][1];
long ans = 0;
for (var v:Matrix.mul(A,Matrix.pow(X,N -1)))
ans += v;
return ans %mod;
// int N = in.it();
// int K = in.it();
// int X = in.it();
// long[] H = in.lg(N);
//
// Set<Long> set0 = new HashSet<>();
// Set<Long> set = new HashSet<>();
// for (var h:H) {
// set0.add(h);
// set.add(h %X);
// }
// if (set0.size() == 1)
// return true;
// if (set.size() > 1)
// return false;
//
// long mm = infL;
// for (int i = 0;i < K;i++)
// if (H[i] > (mm = min(mm,H[i])))
// return false;
//
// mm = infL;
// for (int i = N -1;i >= N -K;i--)
// if (H[i] > (mm = min(mm,H[i])))
// return false;
//
// // for (int i = 0;i +K <= N;i++)
// // while (H[i] < 4)
// // for (int j = 0;j < K;j++)
// // H[i +j] += X;
//
// long[] sum = new long[K];
// int[] cnt = new int[K];
//
// for (int i = 0;i < N;i++) {
// sum[i %K] += H[i];
// cnt[i %K]++;
// }
//
// if (N %K == 0) {
// Set<Long> set2 = new HashSet<>();
// for (var s:sum)
// set2.add(s);
// return set2.size() == 1;
// }
//
// long m = infL;
// long M = -infL;
// for (int i = 0;i < K;i++) {
// m = min(m,sum[i]);
// M = max(M,sum[i]);
// }
//
// long mok = M -m;
// DualBIT bit = new DualBIT(N);
// for (int i = 0;i < N;i++)
// bit.upd(i,i +1,H[i]);
//
// for (int i = 0;i +K <= N;i++) {
// long d = mok -bit.get(i);
// if (d %X != 0)
// return false;
// bit.upd(i,i +K,d);
// }
//
// Set<Long> set2 = new HashSet<>();
// for (int i = 0;i < N;i++)
// set2.add(bit.get(i));
//
// return set2.size() == 1;
}
private void tmp(int N,int K,int X,long[] H){
long[] cnt = new long[N];
long mok = H[0] %X +X *10;
DualBIT bit = new DualBIT(N);
for (int i = 0;i < N;i++)
bit.upd(i,i +1,H[i]);
for (int i = 0;i +K <= N;i++) {
long d = mok -bit.get(i);
if (d %X != 0)
throw new RuntimeException();
cnt[i] = d;
bit.upd(i,i +K,d);
}
long[] arr = new long[N];
for (int i = 0;i < N;i++)
arr[i] = bit.get(i);
log.println(arr);
log.println(cnt);
}
<T extends BaseV> void log(Seg<T, ?> seg,int n){
T[] a = (T[]) new BaseV[n];
for (int i = 0;i < n;i++)
a[i] = seg.get(i);
log.println(a);
}
private int[] zaatu(int[][] T){
List<Integer> list = new ArrayList<>();
list.add(0);
for (var t:T)
list.add(t[1]);
Set<Integer> set = new TreeSet<>(list);
Map<Integer, Integer> map = new HashMap<>();
int[] ret = new int[set.size()];
for (var s:set) {
ret[map.size()] = s;
map.put(s,map.size());
}
for (var t:T)
t[1] = map.get(t[1]);
return ret;
}
private int calc(String s){
var rh = new RollingHash(s.toCharArray(),false);
int ret = 1;
for (int i = 0;i < s.length();i++) {
int l = (ret -1) /2;
while (0 <= i -(l +1) && i +l +2 <= s.length() && rh.get(i -(l +1),i) == rh.get(i +l +2,i +1))
l++;
ret = max(ret,l *2 +1);
l = ret /2;
while (0 <= i -l && i +l +2 <= s.length() && rh.get(i -l,i +1) == rh.get(i +l +2,i +1))
l++;
ret = max(ret,l *2);
}
return ret;
}
int[][] trans(int[]... T){ return Util.arr(new int[T[0].length][],i -> Util.arrI(T.length,j -> T[j][i])); }
// void add(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,map[a]); }
//
// void rem(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,-map[a]); }
//
// long[] mo(int N,int[] A,int[][] T,long[] map,SegmentTree<Data, Long> seg,long[] ans){
// int k = 32 -Integer.numberOfLeadingZeros((int) (Math.sqrt(1.5 /T.length) *N) +1);
// sort(T,(a,b) -> (a[0] >>k != b[0] >>k ? a[0] -b[0] : (a[0] >>k &1) == 1 ? a[1] -b[1] : b[1] -a[1]));
// int l = T[0][0];
// int r = l -1;
// for (var t:T) {
// while (t[0] < l)
// add(seg,A[--l],map);
// while (r < t[1])
// add(seg,A[++r],map);
// while (l < t[0])
// rem(seg,A[l++],map);
// while (t[1] < r)
// rem(seg,A[r--],map);
// ans[t[2]] = seg.get(0,100_000 +1).v;
// }
// return ans;
// }
}
class DualBIT{
private int n;
private long[] val;
public DualBIT(int n){
this.n = n +1;
val = new long[n +2];
}
public long agg(long a,long b){ return a +b; }
public long inv(long v){ return -v; }
public long get(int i){ return sum(i +1); }
public void upd(int l,int r,long v){
upd(l,v);
upd(r,inv(v));
}
private void upd(int x,long v){
for (x++;x <= n;x += x &-x)
val[x] = agg(val[x],v);
}
private long sum(int x){
long ret = 0;
for (;x > 0;x -= x &-x)
ret = agg(ret,val[x]);
return ret;
}
}
abstract class Seg<V extends BaseV, F> {
private int n,log;
private V[] val;
private F[] lazy;
protected Seg(int n){
this.n = n;
while (1 <<log <= n)
log++;
val = Util.cast(new BaseV[n <<1]);
lazy = Util.cast(new Object[n]);
for (int i = -1;++i < n;)
(val[i +n] = init(i)).sz = 1;
for (int i = n;--i > 0;merge(i))
(val[i] = e()).sz = val[i <<1].sz +val[i <<1 |1].sz;
}
public void upd(int i,F f){ prop(i +n,f); }
public void upd(int l,int r,F f){
for (l += n,r += n;l < r;l >>= 1,r >>= 1) {
if ((l &1) == 1)
prop(l++,f);
if ((r &1) == 1)
prop(--r,f);
}
}
public V get(int i){ return val[i +n]; }
public V get(int l,int r){
V[] ret = Util.cast(new BaseV[]{e(), e()});
int i = 0;
for (var v:getList(l,r)) {
agg(ret[i],ret[i ^1],v);
ret[i].sz = ret[i ^= 1].sz +v.sz;
}
return ret[i ^1];
}
public V[] getList(int l,int r){
int sz = 0;
for (int li = l += n,ri = r += n;li < ri;li = li +1 >>1,ri >>= 1)
sz += (li &1) +(ri &1);
V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));
for (int i = 0;l < r;l >>= 1,r >>= 1) {
if ((l &1) > 0)
arr[i++] = val[l++];
if ((r &1) > 0)
arr[--sz] = val[--r];
}
return arr;
}
public V[] getPath(int i){
int sz = 32 -Integer.numberOfLeadingZeros(i +n);
V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));
for (i += n;0 < i;i >>= 1)
arr[--sz] = val[i];
return arr;
}
protected V init(int i){ return e(); }
protected abstract V e();
protected abstract void agg(V v,V a,V b);
protected abstract void map(V v,F f);
protected abstract F comp(F f,F g);
protected void up(int l,int r){
for (l = oddPart(l +n),r = oddPart(r +n);l != r;)
merge(l > r ? (l >>= 1) : (r >>= 1));
while (1 < l)
merge(l >>= 1);
}
protected void down(int l,int r){
int i = log;
for (l = oddPart(l +n),r = oddPart(r +n);i > 0;i--) {
push(l >>i);
push(r >>i);
}
}
private void merge(int i){ agg(val[i],val[i <<1],val[i <<1 |1]); }
private void push(int i){
if (lazy[i] != null) {
prop(i <<1,lazy[i]);
prop(i <<1 |1,lazy[i]);
lazy[i] = null;
}
}
private void prop(int i,F f){
map(val[i],f);
if (i < n) {
lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);
if (val[i].fail) {
push(i);
merge(i);
}
}
}
private int oddPart(int i){ return i /(i &-i); }
}
abstract class SegmentTree<V extends BaseV, F> extends Seg<V, F>{
public SegmentTree(int n){ super(n); }
@Override
protected F comp(F f,F g){ return null; }
@Override
public void upd(int i,F f){
super.upd(i,f);
up(i,i +1);
}
}
class RollingHash{
private static long MOD = (1L <<61) -1,MASK30 = (1L <<30) -1,MASK31 = (1L <<31) -1,
base = ThreadLocalRandom.current().nextLong(Util.infI,MOD);
private static long[] pow = {1};
int n;
private long[] hash,S;
private boolean updatable;
private RollingHash rev;
public RollingHash(char[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }
public RollingHash(int[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }
public RollingHash(long[] S,boolean updatable){
this.S = new long[n = S.length];
this.updatable = updatable;
hash = new long[n +1];
if (pow.length <= n) {
int s = pow.length;
pow = copyOf(pow,max(pow.length <<1,n +1));
for (int i = s;i < pow.length;i++)
pow[i] = mul(pow[i -1],base);
}
for (int i = 0;i < n;i++)
set(i,S[i]);
}
public long get(int i){ return get(i,i +1); }
public long get(int l,int r){
if (l > r)
return (rev == null ? rev = rev() : rev).get(n -l,n -r);
return mod(hash(r) -mul(hash(l),pow[r -l]));
}
public void upd(int i,long v){
assert updatable;
set(i,v);
if (rev != null)
rev.set(n -i -1,v);
}
private void set(int i,long v){
if (updatable)
for (int x = i +1;x <= n;x += x &-x)
hash[x] = mod(hash[x] +mul(v -S[i],pow[x -i -1]));
else
hash[i +1] = mod(mul(hash[i],base) +v);
S[i] = v;
}
private long hash(int i){
long ret = 0;
if (updatable)
for (int x = i;x > 0;x -= x &-x)
ret = mod(ret +mul(hash[x],pow[i -x]));
else
ret = hash[i];
return ret;
}
private RollingHash rev(){
long[] s = new long[n];
for (int i = 0;i < n;i++)
s[i] = S[n -1 -i];
return new RollingHash(s,updatable);
}
private static long mul(long a,long b){
long au = a >>31;
long ad = a &MASK31;
long bu = b >>31;
long bd = b &MASK31;
long mid = ad *bu +au *bd;
return mod((au *bu <<1) +(mid >>30) +((mid &MASK30) <<31) +ad *bd);
}
private static long mod(long val){
return val < 0 ? val +MOD : (val = (val &MOD) +(val >>61)) < MOD ? val : val -MOD;
}
}
class Matrix{
public static long[] mul(long[] a,long[][] b){
assert a.length == b.length;
int H = b[0].length,W = a.length;
long[] ret = new long[H];
for (int i = 0;i < H;i++)
for (int j = 0;j < W;j++)
ret[i] = (ret[i] +a[j] *b[j][i]) %Util.mod;
return ret;
}
public static long[][] mul(long[][] a,long[][] b){
assert a[0].length == b.length;
int H = a.length,W = b[0].length,Z = b.length;
long[][] ret = new long[H][W];
for (int z = 0;z < Z;z++)
for (int i = 0;i < H;i++)
for (int j = 0;j < W;j++)
ret[i][j] = (ret[i][j] +a[i][z] *b[z][j]) %Util.mod;
return ret;
}
public static long[][] pow(long[][] x,long n){
long[][] ret = new long[x.length][x.length];
for (int i = 0;i < x.length;i++)
ret[i][i] = 1;
for (;0 < n;x = (n >>= 1) > 0 ? mul(x,x) : x)
if ((n &1) == 1)
ret = mul(ret,x);
return ret;
}
}
class Grid{
private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int H,W;
public Grid(int H,int W){
this.H = H;
this.W = W;
}
public int[] sur(int p){
MyList<int[]> tmp = sur(toi(p),toj(p));
int[] ret = new int[tmp.size()];
for (int i = 0;i < tmp.size();i++)
ret[i] = top(tmp.get(i)[0],tmp.get(i)[1]);
return ret;
}
public MyList<int[]> sur(int i,int j){
MyList<int[]> ret = new MyList<>();
for (var d:dirs) {
int ni = i +d[0];
int nj = j +d[1];
if (valid(ni,H) && valid(nj,W))
ret.add(new int[]{ni, nj});
}
return ret;
}
private boolean valid(int i,int N){ return 0 <= i && i < N; }
public int top(int i,int j){ return i *W +j; }
public int toi(int p){ return p /W; }
public int toj(int p){ return p %W; }
}
class PrefixSum{
private long[] sum;
private int i;
public PrefixSum(int n){ sum = new long[n +1]; }
public PrefixSum(long[] a){
this(a.length);
for (int i = 0;i < a.length;i++)
sum[i +1] = sum[i] +a[i];
}
public void add(long a){ sum[i +1] = sum[i++] +a; }
public long get(int l,int r){ return sum[r] -sum[l]; }
public long get(int i){ return get(i,i +1); }
}
class Edge<L> {
public int id,u,v;
public L val;
public Edge<L> re;
public Edge(int id,int u,int v,L val){
this.id = id;
this.u = u;
this.v = v;
this.val = val;
}
}
class Graph<L> {
public int n;
public MyList<Edge<L>> es;
private MyList<Edge<L>>[] go,bk;
public Graph(int n,boolean dir){
this.n = n;
go = Util.cast(new MyList[n]);
bk = dir ? Util.cast(new MyList[n]) : go;
for (int i = 0;i < n;i++) {
go[i] = new MyList<>();
bk[i] = new MyList<>();
}
es = new MyList<>();
}
protected L inv(L l){ return l; }
public void addEdge(int u,int v){ addEdge(u,v,null); }
public void addEdge(int u,int v,L l){
var e = new Edge<>(es.size(),u,v,l);
var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
es.add(e);
go[u].add(re.re = e);
bk[v].add(e.re = re);
}
public MyList<Edge<L>> go(int u){ return go[u]; }
public MyList<Edge<L>> bk(int u){ return bk[u]; }
}
class UnionFind{
int num;
protected int[] dat;
protected int[] nxt;
public UnionFind(int n){
dat = new int[n];
nxt = new int[n];
setAll(nxt,i -> i);
fill(dat,-1);
num = n;
}
public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }
public boolean same(int u,int v){ return root(u) == root(v); }
public boolean unite(int u,int v){
if ((u = root(u)) == (v = root(v)))
return false;
if (dat[u] > dat[v]) {
u ^= v;
v ^= u;
u ^= v;
}
dat[u] += dat[v];
dat[v] = u;
num--;
nxt[u] ^= nxt[v];
nxt[v] ^= nxt[u];
nxt[u] ^= nxt[v];
return true;
}
public int size(int x){ return -dat[root(x)]; }
public int[] getGroup(int x){
int[] ret = new int[size(x)];
for (int i = 0,c = root(x);i < ret.length;i++)
ret[i] = c = nxt[c];
return ret;
}
}
class MySet implements Iterable<Integer>{
private Set<Integer> set;
private BitSet bit;
public MySet(){ set = new HashSet<>(); }
public int size(){ return set != null ? set.size() : bit.cardinality(); }
public void add(int x){
if (set != null) {
set.add(x);
if (set.size() == 100) {
bit = new BitSet();
for (int i:set)
bit.set(i);
set = null;
}
} else
bit.set(x);
}
public boolean contains(int x){ return set == null ? bit.get(x) : set.contains(x); }
@Override
public Iterator<Integer> iterator(){
return set != null ? set.iterator() : new Iterator<>(){
int w = bit.nextSetBit(0);
@Override
public Integer next(){
int ret = w;
w = bit.nextSetBit(w +1);
return ret;
}
@Override
public boolean hasNext(){ return w != -1; }
};
}
}
class Data extends BaseV{
long v;
public Data(long v){ this.v = v; }
@Override
public String toString(){ return v +""; }
}
abstract class Sum3D{
private long[] sum;
private int w,d;
public Sum3D(int h,int w,int d){
this.w = w;
this.d = d;
sum = new long[(h +1) *(w +1) *(d +1)];
for (int i = 0;i < h;i++)
for (int j = 0;j < w;j++)
for (int k = 0;k < d;k++)
sum[top(i +1,j +1,k +1)] = a(i,j,k)
+sum[top(i,j +1,k +1)] +sum[top(i +1,j,k +1)] +sum[top(i +1,j +1,k)]
-sum[top(i +1,j,k)] -sum[top(i,j +1,k)] -sum[top(i,j,k +1)]
+sum[top(i,j,k)];
}
abstract long a(int i,int j,int k);
private int top(int i,int j,int k){ return i *(w +1) *(d +1) +j *(d +1) +k; }
long get(int il,int ir,int jl,int jr,int kl,int kr){
return sum[top(ir,jr,kr)]
-sum[top(il,jr,kr)] -sum[top(ir,jl,kr)] -sum[top(ir,jr,kl)]
+sum[top(ir,jl,kl)] +sum[top(il,jr,kl)] +sum[top(il,jl,kr)]
-sum[top(il,jl,kl)];
}
}
class RangeSet{
private TreeSet<long[]> set;
public RangeSet(){
set = new TreeSet<>(Comparator.comparing(t -> t[0]));
long inf = Util.infL;
set.add(new long[]{-inf, -inf});
set.add(new long[]{inf, inf});
}
public long add(long x){ return add(x,x +1); }
public long add(long l,long r){
long ret = r -l;
long[] t = {l, r};
for (var s = set.floor(t);t[0] <= s[1];s = set.floor(t))
ret -= add(t,s);
for (var s = set.ceiling(t);s[0] <= t[1];s = set.ceiling(t))
ret -= add(t,s);
set.add(t);
return ret;
}
public long remove(long x){ return remove(x,x +1); }
public long remove(long l,long r){
long ret = 0;
long[] t = {l, r};
for (var s = set.floor(t);l < s[1];s = set.floor(t))
ret += remove(t,s);
for (var s = set.ceiling(t);s[0] < r;s = set.ceiling(t))
ret += remove(t,s);
return ret;
}
private long add(long[] t,long[] s){
long ret = min(t[1],s[1]) -max(t[0],s[0]);
set.remove(s);
t[0] = min(t[0],s[0]);
t[1] = max(t[1],s[1]);
return ret;
}
private long remove(long[] t,long[] s){
set.remove(s);
long ret = min(t[1],s[1]) -max(t[0],s[0]);
if (s[0] < t[0])
set.add(new long[]{s[0], t[0]});
if (t[1] < s[1])
set.add(new long[]{t[1], s[1]});
return ret;
}
public long[] get(long x){
long[] ret = set.floor(new long[]{x});
return x < ret[1] ? ret : null;
}
public long mex(){
var t = get(0);
return t == null ? 0 : t[1];
}
public long[][] toArray(){
long[][] ret = new long[set.size() -2][];
long[] x = {set.first()[0]};
for (int i = 0;i < ret.length;i++)
x[0] = (ret[i] = set.higher(x))[0];
return ret;
}
public long cardinality(long l,long r){
long ret = 0;
long[] key = {r};
while (l < r) {
var t = set.lower(key);
if (t[1] <= l)
break;
ret += min(r,t[1]) -max(l,t[0]);
key = t;
}
return ret;
}
public long first(){ return set.higher(new long[]{-Util.infL})[0]; }
}
abstract class BaseV{
public int sz;
public boolean fail;
}
class MyStack<T> extends MyList<T>{
public T pop(){ return remove(size() -1); }
public T peek(){ return get(size() -1); }
}
class MyList<T> implements Iterable<T>{
private T[] arr;
private int sz;
public MyList(){ this(16); }
public MyList(int n){ arr = Util.cast(new Object[max(16,n)]); }
public MyList(MyList<T> org){
this(org.sz);
System.arraycopy(org.arr,0,arr,0,sz = org.sz);
}
public boolean isEmpty(){ return sz == 0; }
public int size(){ return sz; }
public T get(int i){ return arr[i]; }
public void add(T t){ (arr = sz < arr.length ? arr : copyOf(arr,sz *5 >>2))[sz++] = t; }
public void addAll(MyList<T> list){
for (var t:list)
add(t);
}
public T remove(int i){
var ret = arr[i];
sz--;
for (int j = i;j < sz;j++)
arr[j] = arr[j +1];
return ret;
}
public T removeFast(int i){
var ret = arr[i];
arr[i] = arr[--sz];
return ret;
}
public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }
public void sort(Comparator<T> cmp){ Arrays.sort(arr,0,sz,cmp); }
public <U> MyList<U> map(Function<T, U> func){
MyList<U> ret = new MyList<>(sz);
forEach(t -> ret.add(func.apply(t)));
return ret;
}
public MyList<T> rev(){
MyList<T> ret = new MyList<>(sz);
for (int i = sz;i-- > 0;)
ret.add(get(i));
return ret;
}
public T[] toArray(){
if (sz == 0)
return Util.cast(new Object[0]);
T[] ret = Util.cast(Array.newInstance(arr[0].getClass(),sz));
System.arraycopy(arr,0,ret,0,sz);
return ret;
}
public void swap(int i,int j){
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public void set(int i,T t){ arr[i] = t; }
public void clear(){ sz = 0; }
@Override
public Iterator<T> iterator(){
return new Iterator<>(){
int i = 0;
@Override
public boolean hasNext(){ return i < sz; }
@Override
public T next(){ return arr[i++]; }
};
}
}
class BaseSolver extends Util{
public MyReader in;
public MyWriter out,log;
public BaseSolver(MyReader in,MyWriter out,MyWriter log){
this.in = in;
this.out = out;
this.log = log;
}
public int[][] addId(int[][] T){
return arr(new int[T.length][],i -> {
int[] t = copyOf(T[i],T[i].length +1);
t[t.length -1] = i;
return t;
});
}
public long inv(long x){ return pow(x,mod -2); }
public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; }
public long pow(long x,long n){ return pow(x,n,Util.mod); }
public long pow(long x,long n,long mod){
long ret = 1;
for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
if ((n &1) == 1)
ret = ret *x %mod;
return ret;
}
public int bSearchI(int o,int n,IntPredicate judge){
for (int m = 0;1 < abs(n -o);)
m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
return o;
}
public long bSearchL(long o,long n,LongPredicate judge){
for (long m = 0;1 < abs(n -o);)
m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
return o;
}
public double bSearchD(double o,double n,DoublePredicate judge){
for (double m,c = 0;c < 200;c++)
m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
return o;
}
public long gcd(long a,long b){
while (0 < b) {
long t = a;
a = b;
b = t %b;
}
return a;
}
public long[] extendGcd(long a,long b){
long x0 = 1,y0 = 0,x1 = 0,y1 = 1;
while (b != 0) {
long q = a /b,t = a %b,tx = x1,ty = y1;
a = b;
b = t;
x1 = x0 -q *x1;
y1 = y0 -q *y1;
x0 = tx;
y0 = ty;
}
return new long[]{x0, y0, a};
}
public long lcm(long a,long b){ return b /gcd(a,b) *a; }
public long ceil(long a,long b){ return (a +b -1) /b; }
public int lis(int[] arr){
int[] lis = new int[arr.length];
fill(lis,infI);
for (var a:arr) {
int i = bSearchI(0,arr.length,ii -> lis[ii] < a) +1;
lis[i] = a;
}
return bSearchI(0,arr.length,i -> lis[i] < infI) +1;
}
}
class Util{
public static String yes = "Yes",no = "No";
public static int infI = (1 <<30) -1;
public static long infL = (1L <<61 |1 <<30) -1,
mod = 998244353;
public static Random rd = ThreadLocalRandom.current();
private long st = System.currentTimeMillis();
protected long elapsed(){ return System.currentTimeMillis() -st; }
protected void reset(){ st = System.currentTimeMillis(); }
public static int[] arrI(int N,IntUnaryOperator f){
int[] ret = new int[N];
setAll(ret,f);
return ret;
}
public static long[] arrL(int N,IntToLongFunction f){
long[] ret = new long[N];
setAll(ret,f);
return ret;
}
public static double[] arrD(int N,IntToDoubleFunction f){
double[] ret = new double[N];
setAll(ret,f);
return ret;
}
public static <T> T[] arr(T[] arr,IntFunction<T> f){
setAll(arr,f);
return arr;
}
@SuppressWarnings("unchecked")
public static <T> T cast(Object obj){ return (T) obj; }
}
class MyReader{
private byte[] buf = new byte[1 <<16];
private int ptr,tail;
private InputStream in;
public MyReader(InputStream in){ this.in = in; }
private byte read(){
if (ptr == tail)
try {
tail = in.read(buf);
ptr = 0;
} catch (IOException e) {}
return buf[ptr++];
}
private boolean isPrintable(byte c){ return 32 < c && c < 127; }
private byte nextPrintable(){
byte ret = read();
while (!isPrintable(ret))
ret = read();
return ret;
}
public int it(){ return toIntExact(lg()); }
public int[] it(int N){ return Util.arrI(N,i -> it()); }
public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }
public int idx(){ return it() -1; }
public int[] idx(int N){ return Util.arrI(N,i -> idx()); }
public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }
public long lg(){
byte i = nextPrintable();
boolean negative = i == 45;
long n = negative ? 0 : i -'0';
while (isPrintable(i = read()))
n = 10 *n +i -'0';
return negative ? -n : n;
}
public long[] lg(int N){ return Util.arrL(N,i -> lg()); }
public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }
public double dbl(){ return Double.parseDouble(str()); }
public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }
public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }
public char[] ch(){ return str().toCharArray(); }
public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }
public String line(){
StringBuilder sb = new StringBuilder();
for (byte c;(c = read()) != '\n';)
sb.append((char) c);
return sb.toString();
}
public String str(){
StringBuilder sb = new StringBuilder();
sb.append((char) nextPrintable());
for (byte c;isPrintable(c = read());)
sb.append((char) c);
return sb.toString();
}
public String[] str(int N){ return Util.arr(new String[N],i -> str()); }
public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }
}
class MyWriter{
private OutputStream out;
private byte[] buf = new byte[1 <<16],ibuf = new byte[20];
private int tail;
private boolean autoflush;
public MyWriter(OutputStream out,boolean autoflush){
this.out = out;
this.autoflush = autoflush;
}
public void flush(){
try {
out.write(buf,0,tail);
tail = 0;
} catch (IOException e) {
e.printStackTrace();
}
}
private void ln(){
write((byte) '\n');
if (autoflush)
flush();
}
private void write(byte b){
buf[tail++] = b;
if (tail == buf.length)
flush();
}
private void write(long n){
if (n < 0) {
n = -n;
write((byte) '-');
}
int i = ibuf.length;
do {
ibuf[--i] = (byte) (n %10 +'0');
n /= 10;
} while (n > 0);
while (i < ibuf.length)
write(ibuf[i++]);
}
private void print(Object obj){
if (obj instanceof Boolean)
print((boolean) obj ? Util.yes : Util.no);
else if (obj instanceof Integer)
write((int) obj);
else if (obj instanceof Long)
write((long) obj);
else if (obj instanceof char[])
for (char b:(char[]) obj)
write((byte) b);
else if (obj.getClass().isArray()) {
int l = Array.getLength(obj);
for (int i = 0;i < l;i++) {
print(Array.get(obj,i));
if (i +1 < l)
write((byte) ' ');
}
} else
print(Objects.toString(obj).toCharArray());
}
public void println(Object obj){
if (obj == null)
obj = "null";
if (obj instanceof Iterable<?>)
for (Object e:(Iterable<?>) obj)
println(e);
else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
int l = Array.getLength(obj);
for (int i = 0;i < l;i++)
println(Array.get(obj,i));
} else {
print(obj);
ln();
}
}
public void printlns(Object... o){
print(o);
ln();
}
}