結果
| 問題 | No.2809 Sort Query |
| ユーザー |
 ゆうき
|
| 提出日時 | 2024-07-13 00:00:52 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 26,500 bytes |
| コンパイル時間 | 4,410 ms |
| コンパイル使用メモリ | 97,772 KB |
| 実行使用メモリ | 225,916 KB |
| 最終ジャッジ日時 | 2024-07-13 00:03:07 |
| 合計ジャッジ時間 | 123,619 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 69 ms
50,732 KB |
| testcase_01 | TLE | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | AC | 1,180 ms
122,348 KB |
| testcase_32 | AC | 1,135 ms
121,436 KB |
| testcase_33 | AC | 1,156 ms
122,168 KB |
| testcase_34 | AC | 1,203 ms
124,128 KB |
| testcase_35 | AC | 1,157 ms
121,824 KB |
| testcase_36 | AC | 1,164 ms
121,544 KB |
| testcase_37 | AC | 1,167 ms
123,768 KB |
| testcase_38 | AC | 1,118 ms
121,668 KB |
| testcase_39 | AC | 1,294 ms
119,348 KB |
| testcase_40 | AC | 1,125 ms
126,192 KB |
| testcase_41 | AC | 1,904 ms
188,160 KB |
| testcase_42 | AC | 1,997 ms
188,656 KB |
| testcase_43 | AC | 1,942 ms
188,528 KB |
| testcase_44 | AC | 1,945 ms
188,716 KB |
| testcase_45 | AC | 1,959 ms
180,924 KB |
| testcase_46 | AC | 1,522 ms
179,904 KB |
| testcase_47 | AC | 1,504 ms
177,776 KB |
| testcase_48 | AC | 1,517 ms
177,804 KB |
| testcase_49 | AC | 1,498 ms
177,776 KB |
| testcase_50 | AC | 1,501 ms
177,620 KB |
| testcase_51 | AC | 573 ms
103,156 KB |
| testcase_52 | AC | 571 ms
101,100 KB |
| testcase_53 | AC | 625 ms
101,384 KB |
| testcase_54 | AC | 587 ms
101,244 KB |
| testcase_55 | AC | 597 ms
101,364 KB |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | WA | - |
| testcase_60 | WA | - |
| testcase_61 | WA | - |
| testcase_62 | WA | - |
| testcase_63 | TLE | - |
| testcase_64 | TLE | - |
| testcase_65 | WA | - |
| testcase_66 | WA | - |
| testcase_67 | WA | - |
| testcase_68 | WA | - |
| testcase_69 | WA | - |
| testcase_70 | AC | 69 ms
50,956 KB |
ソースコード
import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.io.*;
import java.lang.reflect.*;
import java.util.*;
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 Q = in.it();
long[] A = in.lg(N);
AVLTree<Data> avl = new AVLTree<>(Comparator.comparing(d -> d.v)){
@Override
protected Data e(){ return new Data(0,0); }
@Override
protected void agg(Data v,Data a,Data b){}
};
Map<Integer, Data> list = new HashMap<>();
for (int i = 0;i < N;i++) {
list.put(i,new Data(A[i],-1));
avl.add(new Data(-1,-1));
}
while (Q-- > 0) {
int t = in.it();
if (t == 1) {
int k = in.idx();
long x = in.lg();
var pre = avl.get(k);
list.put(k,new Data(x,pre.p));
}
if (t == 2) {
for (var v:list.values()) {
avl.del(new Data(v.p,-1));
avl.add(new Data(v.v,-1));
}
list = new HashMap<>();
}
if (t == 3) {
int k = in.idx();
out.println((list.containsKey(k) ? list.get(k) : avl.get(k)).v);
}
}
return null;
}
private long floorSum(long n,long m,long a,long b){
if (a < 0) {
b += (n -1) *a;
a *= -1;
}
long ret = 0;
if (a >= m) {
ret += a /m *n *(n -1) >>1;
a %= m;
}
if (b >= m) {
ret += b /m *n;
b %= m;
}
long last = a *n +b;
if (last >= m)
ret += floorSum(last /m,a,m,last %m);
return ret;
}
}
class Data extends BaseV{
long v,p;
public Data(long v,long p){
this.v = v;
this.p = p;
}
}
abstract class AVLTree<V extends BaseV> {
private V e = e();
private Node root;
private Comparator<V> cmp;
private V[] ret = Util.cast(new BaseV[2]);
private int ri;
public AVLTree(){ this(Util.cast(Comparator.naturalOrder())); }
public AVLTree(Comparator<V> cmp){
ret[ri] = e();
ri = 1;
this.cmp = cmp;
}
public void add(V v){ add(v,1); }
public void add(V v,int k){ root = root == null ? new Node(v,k) : add(root,v,k); }
private Node add(Node nd,V v,int k){
if (nd.lft == null) {
int c = cmp.compare(nd.val,v);
if (c == 0) {
nd.sz += k;
return nd;
} else {
var ret = new Node(e(),0);
ret.cld(-c,new Node(v,k));
ret.cld(c,nd);
nd = ret;
}
} else {
int c = cmp.compare(v,nd.rht.l);
nd.lft = c < 0 ? add(nd.lft,v,k) : nd.lft;
nd.rht = c < 0 ? nd.rht : add(nd.rht,v,k);
}
return balance(nd);
}
public void del(V v){ del(v,1); }
public void del(V v,int k){ root = del(root,v,k); }
private Node del(Node nd,V v,int k){
if (nd.lft == null) {
int c = cmp.compare(nd.val,v);
if (c == 0)
nd.sz -= k;
return c != 0 || 0 < nd.sz ? nd : null;
}
int c = cmp.compare(v,nd.rht.l) *2 +1;
Node del = del(c < 0 ? nd.lft : nd.rht,v,k);
if (del == null)
return nd.cld(-c);
nd.cld(c,del);
return balance(nd);
}
public V get(int i){ return get(root,i); }
private V get(Node nd,int i){
return nd.lft == null ? nd.val : i < nd.lft.sz ? get(nd.lft,i) : get(nd.rht,i -nd.lft.sz);
}
public V get(int l,int r){
ret[ri] = e();
ri ^= 1;
if (root != null)
get(root,l,min(r,size()));
return ret[ri ^= 1];
}
private void get(Node nd,int l,int r){
if (0 == l && r == nd.sz)
ag(ret[ri],ret[ri ^= 1],nd.val());
else if (nd.lft == null)
ag(ret[ri],ret[ri ^= 1],pw(nd.val,r -l));
else {
if (l < nd.lft.sz)
get(nd.lft,l,min(nd.lft.sz,r));
if (nd.lft.sz < r)
get(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz);
}
}
public V all(){ return root == null ? e : root.val; }
public int size(){ return root == null ? 0 : root.sz; }
protected abstract V e();
protected abstract void agg(V v,V a,V b);
private V ag(V v,V a,V b){
agg(v,a,b);
v.sz = a.sz +b.sz;
return v;
}
protected V pow(V a,int n){
V ret = e();
for (V t = ag(e(),e,a);0 < n;n >>= 1,t = ag(e(),t,t))
if (0 < (n &1))
ret = ag(e(),ret,t);
return ret;
}
private V pw(V a,int n){
V ret = pow(a,n);
ret.sz = n;
return ret;
}
private Node balance(Node nd){ return (1 < abs(nd.bis = nd.rht.rnk -nd.lft.rnk) ? (nd = rotate(nd)) : nd).update(); }
private Node rotate(Node u){
var v = u.cld(u.bis);
if (u.bis *v.bis < -1)
v = rotate(v);
u.cld(u.bis,v.cld(-u.bis));
v.cld(-u.bis,u);
u.update();
return v;
}
private class Node{
private int sz,bis,rnk;
private V val,l;
private Node lft,rht;
private Node(V val,int sz){
this.sz = sz;
this.val = l = val;
val.sz = 1;
}
private Node update(){
bis = rht.rnk -lft.rnk;
rnk = max(lft.rnk,rht.rnk) +1;
ag(val,lft.val(),rht.val());
l = lft.l;
sz = val.sz;
return this;
}
private Node cld(int c){ return c < 0 ? lft : rht; }
private void cld(int c,Node nd){ nd = c < 0 ? (lft = nd) : (rht = nd); }
private V val(){ return lft == null && 1 < sz ? pw(val,sz) : val; }
}
}
abstract class DigitDp<T> {
private int B;
private int[] N;
private T[] dp;
public DigitDp(char[] N){ this(N,10); }
public DigitDp(char[] N,int B){
this.N = new int[N.length];
for (int i = 0;i < N.length;i++)
this.N[i] = N[i] -'0';
dp = Util.cast(Array.newInstance(init().getClass(),N.length +1 <<1));
this.B = B;
setAll(dp,i -> init());
}
protected abstract T init();
protected abstract void f(T pd,T dp,int n,int k);
protected void mod(T dp){}
public T get(int i,int same){ return dp[i *2 +same]; }
public void calc(){
for (int i = 0;i < N.length;i++) {
int t = N[i];
for (int n = 0;n < B;n++) {
if (n == t)
f(get(i +1,1),get(i,1),n,N.length -1 -i);
if (n < t)
f(get(i +1,0),get(i,1),n,N.length -1 -i);
if (0 < i)
f(get(i +1,0),get(i,0),n,N.length -1 -i);
}
mod(get(i +1,0));
mod(get(i +1,1));
}
}
}
abstract class Dijkstra<E, L> extends Graph<E>{
private Comparator<L> cmp;
private L[] len;
private int[] hep,idx;
private Edge<E>[] pre;
private int sz;
public Dijkstra(int n,boolean dir){
super(n,dir);
hep = new int[n];
idx = new int[n];
cmp = cmp();
}
protected abstract L zero();
protected abstract L inf();
protected abstract L f(L l,Edge<E> e);
protected Comparator<L> cmp(){ return Util.cast(Comparator.naturalOrder()); }
public L[] calc(int s){ return calc(s,-1); }
public L[] calc(int s,int g){
len = Util.cast(Array.newInstance(zero().getClass(),sz = n));
pre = Util.cast(new Edge[n]);
fill(len,inf());
setAll(hep,i -> i);
setAll(idx,i -> i);
set(s,zero());
for (int cur;0 < sz && (cur = poll()) != g;)
for (var e:go(cur))
set((pre[e.v] = e).v,f(len[cur],e));
return len;
}
public L get(int t){ return len[t]; }
public Deque<Edge<E>> path(int t){
Deque<Edge<E>> ret = new ArrayDeque<>();
while (pre[t] != null) {
ret.addFirst(pre[t]);
t = pre[t].u;
}
return ret;
}
private void set(int i,L l){
if (idx[i] < sz && cmp.compare(l,len[i]) < 0) {
len[i] = l;
heapfy(idx[i]);
}
}
private int poll(){
int ret = hep[0];
heapfy(swap(0,--sz));
return ret;
}
private void heapfy(int k){
int p = k -1 >>1;
if (0 <= p && cmp.compare(len[hep[p]],len[hep[k]]) > 0) {
heapfy(swap(p,k));
return;
}
int c = k <<1 |1;
if (sz <= c)
return;
if (c +1 < sz && cmp.compare(len[hep[c]],len[hep[c +1]]) > 0)
c++;
if (cmp.compare(len[hep[c]],len[hep[k]]) < 0)
heapfy(swap(c,k));
}
private int swap(int i,int j){
hep[i] ^= hep[j];
hep[j] ^= hep[i];
hep[i] ^= hep[j];
idx[hep[i]] = i;
idx[hep[j]] = j;
return 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 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 DualSegmentTree<V extends BaseV, F> extends Seg<V, F>{
public DualSegmentTree(int n){ super(n); }
@Override
protected void agg(V v,V a,V b){}
@Override
public void upd(int i,F f){ upd(i,i +1,f); }
@Override
public void upd(int l,int r,F f){
down(l,r);
super.upd(l,r,f);
}
@Override
public V get(int i){
down(i,i +1);
return super.get(i);
}
}
abstract class LazySegmentTree<V extends BaseV, F> extends Seg<V, F>{
public LazySegmentTree(int n){ super(n); }
@Override
public void upd(int i,F f){ upd(i,i +1,f); }
@Override
public void upd(int l,int r,F f){
down(l,r);
super.upd(l,r,f);
up(l,r);
}
@Override
public V get(int i){
down(i,i +1);
return super.get(i);
}
@Override
public V get(int l,int r){
down(l,r);
return super.get(l,r);
}
}
abstract class ReRootingDp<L, D, A> extends Graph<L>{
private D[] dp;
private A[] ans;
public ReRootingDp(int N){
super(N,false);
dp = Util.cast(new Object[2 *N]);
ans = Util.cast(Array.newInstance(ans(0,e()).getClass(),n));
}
protected abstract D e();
protected abstract D agg(D a,D b);
protected abstract D adj(D v,Edge<L> e);
protected abstract A ans(int u,D sum);
protected MyList<D> sur(int u){ return go(u).map(e -> dp[e.id]); }
public A[] calc(){
for (var e:es)
e.re.id += n;
var stk = new MyStack<Edge<L>>();
var se = new Edge<L>(n -1,-1,0,null);
stk.add(se);
while (!stk.isEmpty()) {
var e = stk.pop();
if (dp[e.id] == null) {
dp[e.id] = e();
for (var ee:go(e.v))
if (ee != e.re) {
stk.add(ee);
stk.add(ee);
}
} else {
for (var ee:go(e.v))
if (ee != e.re)
dp[e.id] = agg(dp[e.id],dp[ee.id]);
if (e.u > -1)
dp[e.id] = adj(dp[e.id],e);
}
}
stk.add(se);
while (!stk.isEmpty()) {
var e = stk.pop();
var es = go(e.v);
int n = es.size();
D[] pre = Util.cast(new Object[n +1]),suf = Util.cast(new Object[n +1]);
pre[0] = e();
suf[n] = e();
for (int i = 0;i < n;i++) {
pre[i +1] = agg(pre[i],dp[es.get(i).id]);
suf[n -1 -i] = agg(dp[es.get(n -1 -i).id],suf[n -i]);
}
ans[e.v] = ans(e.v,suf[0]);
for (int i = 0;i < n;i++) {
Edge<L> ee = es.get(i);
if (ee != e.re) {
dp[ee.re.id] = adj(agg(pre[i],suf[i +1]),ee.re);
stk.add(ee);
}
}
}
return ans;
}
public void clear(){
dp[n -1] = null;
for (var e:es) {
dp[e.id] = dp[e.re.id] = null;
go(e.u).clear();
go(e.v).clear();
}
es.clear();
}
}
class HLD extends Graph<Object>{
private int[] p,hp,l,r;
public int[] dpt;
public HLD(int n){
super(n,false);
p = new int[n];
hp = new int[n];
l = new int[n];
r = new int[n];
}
public MyList<int[]> auxiliary(MyList<Integer> lis){
lis = new MyList<>(lis);
lis.add(0);
MyList<int[]> ret = new MyList<>();
lis.sort(Comparator.comparing(i -> l[i]));
for (int i = lis.size() -1;i > 0;i--)
lis.add(lca(lis.get(i -1),lis.get(i)));
lis.sort(Comparator.comparing(i -> l[i]));
MyStack<Integer> stk = new MyStack<>();
stk.add(lis.get(0));
for (var y:lis) {
while (r[stk.peek()] <= l[y])
stk.pop();
if (!stk.peek().equals(y))
ret.add(new int[]{stk.peek(), y});
stk.add(y);
}
return ret;
}
public MyList<int[]> getPath(int u,int v,int incLca){
MyList<int[]> ret = new MyList<>();
while (true) {
if (l[u] > l[v]) {
var t = u;
u = v;
v = t;
}
var h = hp[v];
if (l[h] <= l[u]) {
ret.add(new int[]{l[u] +1 -incLca, l[v] +1});
return ret;
}
ret.add(new int[]{l[h], l[v] +1});
v = p[h];
}
}
public int lca(int u,int v){
while (true) {
if (l[u] > l[v]) {
var t = u;
u = v;
v = t;
}
var h = hp[v];
if (l[h] <= l[u])
return u;
v = p[h];
}
}
public void makeTree(int s){
MyStack<Integer> stk = new MyStack<>();
fill(hp,-1);
p[s] = s;
stk.add(s);
stk.add(s);
while (!stk.isEmpty()) {
var u = stk.pop();
if (r[u] < 1) {
r[u] = 1;
for (var e:go(u)) {
if (e.v == p[u])
continue;
es.set(e.id,e);
p[e.v] = u;
stk.add(e.v);
stk.add(e.v);
}
} else if (u != s)
r[p[u]] += r[u];
}
for (int u = 0;u < n;u++) {
var go = go(u);
for (int i = 1;i < go.size();i++)
if (r[u] < r[go.get(0).v] || r[go.get(0).v] < r[go.get(i).v] && r[go.get(i).v] < r[u])
go.swap(0,i);
}
stk.add(s);
for (int hid = 0;!stk.isEmpty();) {
var u = stk.pop();
r[u] += l[u] = hid++;
if (hp[u] < 0)
hp[u] = u;
var go = go(u);
for (int i = go.size();i-- > 0;) {
var v = go.get(i).v;
if (v == p[u])
continue;
if (i == 0)
hp[v] = hp[u];
stk.add(v);
}
}
}
}
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]; }
}
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 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); }
@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++]; }
};
}
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 T[] toArray(){
if (sz == 0)
return Util.cast(new Object[0]);
T[] ret = Util.cast(Array.newInstance(arr[0].getClass(),sz));
for (int i = 0;i < sz;i++)
ret[i] = arr[i];
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; }
}
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;
}
protected 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;
});
}
protected long inv(long x){ return pow(x,mod -2); }
protected long pow(long x,long n){ return pow(x,n,Util.mod); }
protected 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;
}
protected int bSearchI(int o,int n,IntPredicate judge){
if (!judge.test(o))
return o -Integer.signum(n -o);
for (int m = 0;1 < abs(n -o);)
m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
return o;
}
protected 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;
}
protected double bSearchD(double o,double n,DoublePredicate judge){
for (double m,c = 0;c < 100;c++)
m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
return o;
}
protected long gcd(long a,long b){
while (0 < b) {
long t = a;
a = b;
b = t %b;
}
return a;
}
public long lcm(long a,long b){ return b /gcd(a,b) *a; }
protected long ceil(long a,long b){ return (a +b -1) /b; }
}
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();
}
}