結果
| 問題 | No.2733 Just K-times TSP |
| ユーザー |
 ゆうき
|
| 提出日時 | 2024-04-27 20:11:31 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 42,966 bytes |
| コンパイル時間 | 4,080 ms |
| コンパイル使用メモリ | 99,368 KB |
| 実行使用メモリ | 409,156 KB |
| 最終ジャッジ日時 | 2024-11-16 01:28:09 |
| 合計ジャッジ時間 | 25,924 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 68 ms
57,624 KB |
| testcase_01 | AC | 70 ms
331,916 KB |
| testcase_02 | AC | 59 ms
57,128 KB |
| testcase_03 | AC | 58 ms
50,300 KB |
| testcase_04 | AC | 66 ms
50,556 KB |
| testcase_05 | AC | 67 ms
50,800 KB |
| testcase_06 | AC | 71 ms
50,864 KB |
| testcase_07 | AC | 67 ms
50,796 KB |
| testcase_08 | AC | 67 ms
50,568 KB |
| testcase_09 | AC | 86 ms
51,364 KB |
| testcase_10 | AC | 69 ms
50,732 KB |
| testcase_11 | AC | 69 ms
50,644 KB |
| testcase_12 | AC | 98 ms
52,560 KB |
| testcase_13 | AC | 79 ms
50,908 KB |
| testcase_14 | AC | 102 ms
54,616 KB |
| testcase_15 | AC | 160 ms
55,420 KB |
| testcase_16 | AC | 107 ms
52,324 KB |
| testcase_17 | AC | 317 ms
74,216 KB |
| testcase_18 | AC | 431 ms
86,616 KB |
| testcase_19 | AC | 639 ms
100,700 KB |
| testcase_20 | AC | 127 ms
57,484 KB |
| testcase_21 | AC | 239 ms
64,672 KB |
| testcase_22 | TLE | - |
| testcase_23 | AC | 359 ms
73,168 KB |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | AC | 73 ms
50,736 KB |
| testcase_27 | AC | 109 ms
52,312 KB |
| testcase_28 | AC | 165 ms
56,780 KB |
| testcase_29 | AC | 310 ms
65,588 KB |
| testcase_30 | AC | 635 ms
98,036 KB |
| testcase_31 | AC | 1,494 ms
180,024 KB |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
ソースコード
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 M = in.it();
int K = in.it();
int[][] E = in.idx(M,2);
int[] cnt = new int[N];
for (var e:E) {
cnt[e[0]]++;
cnt[e[1]]++;
}
int[][] g = new int[N][];
for (int i = 0;i < N;i++)
g[i] = new int[cnt[i]];
for (var e:E) {
g[e[0]][--cnt[e[0]]] = e[1];
g[e[1]][--cnt[e[1]]] = e[0];
}
Map<Long, Long> map = new HashMap<>();
MyList<Long> list = new MyList<>();
dfs(list,0,0,N,K);
for (long i = 0;i < N;i++) {
long key = 1L <<(i +1) *4 |i;
map.put(key,1L);
}
long lst = 0;
for (int i = 0;i < N;i++)
lst |= 1L *K <<4 *(i +1);
long ans = 0;
for (var k:list) {
if (!map.containsKey(k))
continue;
long val = map.get(k);
long u = k &15;
k -= u;
if (k == lst)
ans += val;
for (long v:g[(int) u]) {
if ((k >>(v +1) *4 &15) == K)
continue;
long nxt = k +v +(1L <<4 *(v +1));
map.merge(nxt,val,(a,b) -> a +b > mod ? a +b -mod : a +b);
}
}
return ans %mod;
// int Q = in.it();
// long[] A = in.lg(N);
//
// AVLUtil util = new AVLUtil(){
// @Override
// public void op(S v,S a,S b){
// v.v = (a.v +b.v) %mod;
// v.sz = a.sz +b.sz;
// }
//
// @Override
// public void mapping(S v,Fn f){ v.v = (v.v *f.a +v.sz *f.b) %mod; }
//
// @Override
// public S e(){ return new S(0,0); }
//
// @Override
// public Fn composition(Fn f,Fn g){ return new Fn(g.a *f.a %mod,(g.a *f.b +g.b) %mod); }
// };
// AVLTree tree = new AVLTree(util,N,i -> new S(A[i],1));
//
// // AVLSegmentTree<Data, Fn> seg = new AVLSegmentTree<>(){
// // @Override
// // protected Data e(){ return new Data(0); }
// //
// // @Override
// // protected void agg(Data v,Data a,Data b){ v.v = (a.v +b.v) %mod; }
// //
// // @Override
// // protected void map(Data v,Fn f){ v.v = (v.v *f.a +v.sz *f.b) %mod; }
// //
// // @Override
// // protected Fn comp(Fn f,Fn g){ return new Fn(g.a *f.a %mod,(g.a *f.b +g.b) %mod); }
// //
// // @Override
// // protected void tog(Data v){}
// // };
// // seg.build(N,i -> new Data(A[i]));
// while (Q-- > 0) {
// int t = in.it();
// if (t == 0) {
// int i = in.it();
// long a = in.lg();
// tree.insert(i,new S(a,1));
// // seg.ins(i,new Data(a));
// }
// if (t == 1) {
// int i = in.it();
// tree.delete(i);
// // seg.del(i);
// // assert eq(tree,seg);
// }
// if (t == 2) {
// int l = in.it();
// int r = in.it();
// tree.reverse(l,r);
// // seg.toggle(l,r);
// }
// if (t == 3) {
// int l = in.it();
// int r = in.it();
// long b = in.lg();
// long c = in.lg();
// tree.apply(l,r,new Fn(b,c));
// // seg.upd(l,r,new Fn(b,c));
// }
// if (t == 4) {
// int l = in.it();
// int r = in.it();
// S ans = tree.prod(l,r);
// // Data data = seg.get(l,r);
// // assert ans.v == data.v;
// out.println(ans);
// out.flush();
// }
// log.println(tree);
// }
// return null;
}
private void dfs(MyList<Long> list,int i,long key,int N,int K){
if (i == N +1) {
list.add(key);
return;
}
if (i < N)
for (int k = 0;k <= K;k++)
dfs(list,i +1,key <<4 |k,N,K);
if (i == N)
for (int u = 0;u < N;u++)
if ((key >>4 *u &15) > 0)
dfs(list,i +1,key <<4 |u,N,K);
}
private boolean eq(AVLTree tree,AVLSegmentTree<Data, Fn> seg){
long[] A = new long[seg.size()];
long[] B = new long[seg.size()];
for (int i = 0;i < seg.size();i++) {
B[i] = seg.get(i,i +1).v;
A[i] = tree.prod(i,i +1).v;
}
log.println(A);
log.println(B);
for (int i = 0;i < seg.size();i++) {
long a = tree.prod(i,i +1).v;
long b = seg.get(i,i +1).v;
if (a != b)
return false;
}
return true;
}
}
abstract class AVLUtil{
abstract public S e();
abstract public void op(S v,S a,S b);
abstract public void mapping(S v,Fn f);
abstract public Fn composition(Fn f,Fn g);
}
class S{
long v,sz;
public S(long v,long sz){
this.v = v;
this.sz = sz;
}
public void toggle(){
}
@Override
public String toString(){ return "" +v; }
}
class Fn{
long a,b;
public Fn(long a,long b){
this.a = a;
this.b = b;
}
@Override
public String toString(){ return a +"x+" +b; }
}
class AVLTree{
AVLUtil util;
int rank;
int size;
S value;
Fn lazy;
int toggle;
AVLTree left,right;
public AVLTree(AVLUtil util,int n,IntFunction<S> init){ this(util,0,n,init); }
private AVLTree(AVLUtil util,
int l,int r,IntFunction<S> init){
this.util = util;
if (l +1 == r) {
value = init.apply(l);
size = 1;
} else {
value = util.e();
left = new AVLTree(util,l,l +r >>1,init);
right = new AVLTree(util,l +r >>1,r,init);
update();
}
}
private AVLTree(AVLUtil util,S value){
this.util = util;
this.value = value;
size = 1;
}
public void insert(int i,S value){
if (size > 1) {
push();
if (i < left.size)
left.insert(i,value);
else
right.insert(i -left.size,value);
} else {
if (i == 0) {
left = new AVLTree(util,value);
right = new AVLTree(util,this.value);
} else {
left = new AVLTree(util,this.value);
right = new AVLTree(util,value);
}
this.value = util.e();
}
update();
}
public AVLTree delete(int i){
if (size == 1)
return null;
push();
if (i < left.size) {
if ((left = left.delete(i)) == null)
copy(right);
else
update();
} else if ((right = right.delete(i -left.size)) == null)
copy(left);
else
update();
return this;
}
private void copy(AVLTree node){
rank = node.rank;
size = node.size;
value = node.value;
lazy = node.lazy;
toggle = node.toggle;
left = node.left;
right = node.right;
}
public void reverse(int l,int r){
if (l >= r)
return;
if (0 < l) {
split(l);
right.reverse(0,r -left.size);
merge(left,this,right);
} else if (r < size) {
split(r);
left.reverse(0,r);
merge(left,this,right);
} else
toggle();
}
private void split(int i){
push();
if (i < left.size) {
left.split(i);
var x = left.left;
merge(left.right,left,right);
right = left;
left = x;
}
if (left.size < i) {
right.split(i -left.size);
var x = right.right;
merge(left,right,right.left);
left = right;
right = x;
}
}
private void merge(AVLTree left,AVLTree parent,AVLTree right){
if (abs(left.rank -right.rank) < 2) {
parent.left = left;
parent.right = right;
} else if (left.rank > right.rank) {
left.push();
parent.left = left.left;
parent.right = left;
merge(left.right,left,right);
} else if (left.rank < right.rank) {
right.push();
parent.left = right;
parent.right = right.right;
merge(left,right,right.left);
}
parent.update();
}
public S prod(int l,int r){
if (l == 0 && r == size)
return value;
S ret = util.e();
if (l >= r)
return ret;
push();
if (l < left.size)
util.op(ret,ret,left.prod(l,min(left.size,r)));
if (left.size < r)
util.op(ret,ret,right.prod(max(0,l -left.size),r -left.size));
return ret;
}
public void apply(int l,int r,Fn f){
if (l == 0 && r == size)
prop(f);
else {
push();
if (l < left.size)
left.apply(l,min(left.size,r),f);
if (left.size < r)
right.apply(max(0,l -left.size),r -left.size,f);
update();
}
}
private void prop(Fn f){
util.mapping(value,f);
if (left != null)
lazy = lazy == null ? f : util.composition(lazy,f);
}
private void toggle(){
var tmp = left;
left = right;
right = tmp;
value.toggle();
if (left != null)
toggle ^= 1;
}
private void push(){
if (lazy != null) {
left.prop(lazy);
right.prop(lazy);
lazy = null;
}
if (0 < toggle) {
left.toggle();
right.toggle();
toggle = 0;
}
}
private void update(){
if (left.rank == right.rank +2)
rotateR();
if (left.rank +2 == right.rank)
rotateL();
lazy = null;
toggle = 0;
rank = max(left.rank,right.rank) +1;
util.op(value,left.value,right.value);
size = left.size +right.size;
}
private void rotateR(){
push();
var B = left;
if (B.left.rank +1 == B.right.rank)
B.rotateL();
var x = B.left;
var y = B.right;
var z = right;
B.push();
left = x;
right = B;
B.left = y;
B.right = z;
B.update();
}
private void rotateL(){
push();
var B = right;
if (B.left.rank == B.right.rank +1)
B.rotateR();
var x = left;
var y = B.left;
var z = B.right;
B.push();
left = B;
B.left = x;
B.right = y;
right = z;
B.update();
}
@Override
public String toString(){
String[] ret = new String[rank +1];
setAll(ret,i -> "|");
dfs(this,ret,5,0,0);
StringBuilder ans = new StringBuilder();
for (var s:ret)
ans.append(s).append("\r\n");
return ans.toString();
}
private void dfs(AVLTree nd,String[] ret,int k,int dpt,int seen){
if (nd.rank == 0 && ret[dpt].length() < 1 +seen *k)
ret[dpt] += " ".repeat(seen *k -ret[dpt].length()) +"|";
String tmp = "" +nd.value;
if (nd.lazy != null)
tmp += "," +nd.lazy;
int sp = k *nd.size -1 -tmp.length();
tmp = " ".repeat(sp /2) +tmp +" ".repeat(sp -sp /2) +"|";
ret[dpt] += tmp;
if (nd.left != null) {
assert value.v == (left.value.v +right.value.v) %998244353;
dfs(nd.left,ret,k,dpt +1,seen);
dfs(nd.right,ret,k,dpt +1,seen +nd.left.size);
}
}
}
abstract class AVLSegmentTree<V extends BaseV, F> {
private V e = e(),t = e();
private Node root;
public AVLSegmentTree(int n){ root = new Node(e(),n); }
public AVLSegmentTree(){}
public void build(int n,IntFunction<V> init){ root = build(0,n,init); }
private Node build(int i,int n,IntFunction<V> init){
if (n < 2)
return n < 1 ? null : new Node(init.apply(i),1);
var ret = new Node(e(),n);
ret.cld(-1,build(i,n /2,init));
ret.cld(1,build(i +n /2,n -n /2,init));
return ret.merge();
}
public void add(V v){ add(v,1); }
public void add(V v,int k){ ins(size(),v,k); }
public void ins(int i,V v){ ins(i,v,1); }
public void ins(int i,V v,int k){ root = root == null ? new Node(v,k) : ins(root,i,v,k); }
private Node ins(Node nd,int i,V v,int k){
if (nd.lft == null && (i == 0 || i == nd.sz)) {
split(nd,i == 0 ? 1 : -1,v,k,nd.sz +k);
return nd.merge();
}
if (nd.lft == null)
split(nd,1,ag(e(),e,nd.val),i,nd.sz);
else
nd.push();
if (i < nd.lft.sz)
nd.cld(-1,ins(nd.lft,i,v,k));
else
nd.cld(1,ins(nd.rht,i -nd.lft.sz,v,k));
return balance(nd);
}
public V del(int i){
var ret = e();
root = del(ret,root,i);
return ret;
}
private Node del(V ret,Node nd,int i){
if (nd.lft == null) {
nd.sz--;
ag(ret,e,nd.val);
return 0 < nd.sz ? nd : null;
}
nd.push();
int c = i < nd.lft.sz ? -1 : 1;
Node del = c < 0 ? del(ret,nd.lft,i) : del(ret,nd.rht,i -nd.lft.sz);
if (del == null)
return nd.cld(-c);
nd.cld(c,del);
return balance(nd);
}
public void upd(int i,F f){ upd(i,i +1,f); }
public void upd(int l,int r,F f){
if (l == r)
return;
if (size() < r)
add(e(),r -size());
root = upd(root,l,r,f);
}
private Node upd(Node nd,int l,int r,F f){
if (l == 0 && r == nd.sz)
return nd.prop(f);
if (nd.lft == null)
split(nd,1,ag(e(),e,nd.val),0 < l ? l : r,nd.sz);
else
nd.push();
if (l < nd.lft.sz)
nd.cld(-1,upd(nd.lft,l,min(nd.lft.sz,r),f));
if (nd.lft.sz < r)
nd.cld(1,upd(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz,f));
return balance(nd);
}
public void toggle(int l,int r){ root = l < r ? toggle(root,l,r) : root; }
private Node toggle(Node nd,int l,int r){
nd.push();
if (0 < l) {
split(nd,l);
return merge(nd.lft,nd,toggle(nd.rht,0,r -l));
}
if (r < nd.sz) {
split(nd,r);
return merge(toggle(nd.lft,l,r),nd,nd.rht);
}
return nd.toggle();
}
private void split(Node nd,int i){
if (nd.lft == null)
split(nd,1,ag(e(),e,nd.val),i,nd.sz);
else {
nd.push();
if (i < nd.lft.sz) {
split(nd.lft,i);
var lft = nd.lft;
nd.cld(-1,lft.lft);
nd.cld(1,merge(lft.rht,lft,nd.rht));
} else if (nd.lft.sz < i) {
split(nd.rht,i -nd.lft.sz);
var rht = nd.rht;
nd.cld(1,rht.rht);
nd.cld(-1,merge(nd.lft,rht,rht.lft));
}
}
}
private Node merge(Node lft,Node nd,Node rht){
if (abs(lft.rnk -rht.rnk) < 2) {
nd.cld(-1,lft);
nd.cld(1,rht);
} else if (lft.rnk > rht.rnk) {
lft.push().cld(1,merge(lft.rht,nd,rht));
nd = lft;
} else if (lft.rnk < rht.rnk) {
rht.push().cld(-1,merge(lft,nd,rht.lft));
nd = rht;
}
return balance(nd);
}
public V get(int i){ return get(i,i +1); }
public V get(int l,int r){
V ret = e();
if (root != null)
get(ret,root,l,min(r,size()));
return ret;
}
private void get(V ret,Node nd,int l,int r){
if (l == 0 && r == nd.sz)
ag(ret,ret,nd.val());
else if (nd.lft == null)
ag(ret,ret,pw(nd.val,r -l));
else {
nd.push();
if (l < nd.lft.sz)
get(ret,nd.lft,l,min(nd.lft.sz,r));
if (nd.lft.sz < r)
get(ret,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);
protected abstract void map(V v,F f);
protected abstract F comp(F f,F g);
protected abstract void tog(V v);
private V ag(V v,V a,V b){
agg(v,a,b);
v.sz = a.sz +b.sz;
return v;
}
protected void pow(V v,V a,int n){
for (ag(t,e,a);0 < n;n >>= 1,ag(t,t,t))
if (0 < (n &1))
ag(v,v,t);
}
private V pw(V a,int n){
V ret = e();
pow(ret,a,n);
ret.sz = n;
return ret;
}
private void split(Node nd,int c,V vl,int i,int sz){
nd.cld(-c,new Node(vl,i));
nd.cld(c,new Node(nd.val,sz -i));
nd.val = e();
}
private Node balance(Node nd){ return (1 < abs(nd.bis = nd.rht.rnk -nd.lft.rnk) ? (nd = rotate(nd)) : nd).merge(); }
private Node rotate(Node u){
var v = u.cld(u.bis).push();
if (u.bis *v.bis < -1)
v = rotate(v);
u.cld(u.bis,v.cld(-u.bis));
v.cld(-u.bis,u);
u.merge();
return v;
}
private class Node{
private int sz,bis,rnk,tog;
private V val;
private F laz;
private Node lft,rht;
private Node(V val,int sz){
this.sz = sz;
this.val = val;
val.sz = 1;
}
private Node merge(){
bis = rht.rnk -lft.rnk;
rnk = max(lft.rnk,rht.rnk) +1;
ag(val,lft.val(),rht.val());
sz = val.sz;
return this;
}
private Node push(){
if (laz != null) {
lft.prop(laz);
rht.prop(laz);
laz = null;
}
if (0 < tog) {
lft.toggle();
rht.toggle();
tog = 0;
}
return this;
}
private Node prop(F f){
map(val,f);
if (lft != null)
laz = laz == null ? f : comp(laz,f);
return this;
}
private Node toggle(){
bis *= -1;
var tn = lft;
lft = rht;
rht = tn;
tog(val);
if (lft != null)
tog ^= 1;
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; }
}
}
class RollingHash{
private static long MASK30 = (1L <<30) -1;
private static long MASK31 = (1L <<31) -1;
private static long MOD = (1L <<61) -1;
private static long m = base();
private static long[] pow = {1};
int n;
private long[] hash,S;
private boolean updatable;
private RollingHash rev;
public RollingHash(char[] S,boolean updatable){ this(S.length,i -> S[i],updatable); }
public RollingHash(int[] S,boolean updatable){ this(S.length,i -> S[i],updatable); }
public RollingHash(long[] S,boolean updatable){ this(S.length,i -> S[i],updatable); }
public RollingHash(int n,IntToLongFunction f,boolean updatale){
S = new long[n];
updatable = updatale;
this.n = S.length;
hash = new long[n +1];
setPow(n);
for (int i = 0;i < n;i++)
set(i,f.applyAsLong(i));
}
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],m) +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 void setPow(int n){
if (n < pow.length)
return;
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],m);
}
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 lu = a >>31;
long ld = a &MASK31;
long ru = b >>31;
long rd = b &MASK31;
long mid = ld *ru +lu *rd;
return mod((lu *ru <<1) +ld *rd +((mid &MASK30) <<31) +(mid >>30));
}
private static long mod(long val){
while (val < 0)
val += MOD;
val = (val &MOD) +(val >>61);
return val > MOD ? val -MOD : val;
}
private static long pow(long x,long n){
long ret = 1;
do {
if ((n &1) == 1)
ret = mul(ret,x);
x = mul(x,x);
} while (0 < (n >>= 1));
return ret;
}
private static long base(){
long m = 0;
for (int k = 1;m < Util.infI;m = pow(37,k))
while (!isPrimeRoot(k))
k = ThreadLocalRandom.current().nextInt(Util.infI);
return m;
}
private static boolean isPrimeRoot(long a){
long b = MOD -1;
while (0 < b) {
long t = a;
a = b;
b = t %b;
}
return a > 1;
}
}
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 Permutation{
private int n;
int[] arr;
public Permutation(int n){ this(Util.arrI(n,i -> i)); }
public Permutation(int[] arr){
n = arr.length;
this.arr = copyOf(arr,n);
}
public boolean increment(){ return crement(1); }
public boolean decrement(){ return crement(-1); }
private boolean crement(int d){
int l = n -2;
while (0 <= l && arr[l] *d >= arr[l +1] *d)
l--;
if (l < 0)
return false;
int r = n -1;
while (arr[l] *d >= arr[r] *d)
r--;
swap(l,r);
l++;
r = n -1;
while (l < r)
swap(l++,r--);
return true;
}
private void swap(int l,int r){
arr[l] ^= arr[r];
arr[r] ^= arr[l];
arr[l] ^= arr[r];
}
}
class Prime{
private long[] spf,
arrI = {2, 7, 61},
arrL = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
public Prime(){ this(1_000_000); }
public Prime(int n){
spf = new long[n +1];
Arrays.setAll(spf,i -> i);
for (int p = 2;p *p <= n;p++)
if (spf[p] == p)
for (int l = p *p;l <= n;l += p)
spf[l] = p;
}
public long[] divisors(long n){
long[] fs = factorize(n);
int l = fs.length > 0 ? 2 : 1,id = 0;
for (int i = 1,sz = 1;i < fs.length;i++,l += sz)
if (fs[i -1] < fs[i])
sz = l;
long[] ret = new long[l];
ret[id++] = 1;
for (int i = 0,s = 0,sz = 1;i < fs.length;i++,s += sz) {
if (0 < i && fs[i -1] < fs[i]) {
sz = id;
s = 0;
}
for (int j = s;j < s +sz;j++)
ret[id++] = ret[j] *fs[i];
}
sort(ret);
return ret;
}
public long[] factorize(long n){
if (n < 2)
return new long[0];
long[] ret = new long[64];
int h = 0,t = 0;
ret[t++] = n;
while (h < t) {
long cur = ret[h++];
if (!isPrime(cur)) {
var p = rho(cur);
ret[--h] = p;
ret[t++] = cur /p;
}
}
sort(ret,0,t);
return copyOf(ret,t);
}
public boolean isPrime(long n){
if (n < spf.length)
return 1 < n && spf[(int) n] == n;
if ((n &1) == 0)
return false;
ModInt bm = new ModInt(n);
long lsb = n -1 &-n +1;
long m = (n -1) /lsb;
a:for (var a:n < 1 <<30 ? arrI : arrL) {
long z = bm.pow(a %n,m);
if (z < 2)
continue;
for (long k = 1;k <= lsb;k <<= 1)
if (z == n -1)
continue a;
else
z = bm.mul(z,z);
return false;
}
return true;
}
private long rho(long n){
if (n < spf.length)
return spf[(int) n];
if ((n &1) == 0)
return 2;
ModInt bm = new ModInt(n);
for (long t;;) {
long x = 0,y = x,q = 1,c = Util.rd.nextLong(n -1) +1;
a:for (int k = 1;;k <<= 1,y = x,q = 1)
for (int i = k;i-- > 0;) {
x = bm.mul(x,x) +c;
if (n <= x)
x -= n;
q = bm.mul(q,abs(x -y));
if ((i &127) == 0 && (t = gcd(q,n)) > 1)
break a;
}
if (t < n)
return t;
}
}
private long gcd(long a,long b){
while (0 < b) {
long t = a;
a = b;
b = t %b;
}
return a;
}
class ModInt{
private long n,r2,ni;
public ModInt(long n){
this.n = n;
r2 = (1L <<62) %n;
for (int i = 0;i < 66;i++) {
r2 <<= 1;
if (r2 >= n)
r2 -= n;
}
ni = n;
for (int i = 0;i < 5;++i)
ni *= 2 -n *ni;
}
private static long high(long x,long y){ return multiplyHigh(x,y) +(x >>63 &y) +(y >>63 &x); }
private long mr(long x,long y){ return high(x,y) +high(-ni *x *y,n) +(x *y == 0 ? 0 : 1); }
public long mod(long x){ return x < n ? x : x -n; }
public long mul(long x,long y){ return mod(mr(mr(x,r2),y)); }
public long pow(long x,long y){
long z = mr(x,r2);
long r = 1;
while (y > 0) {
if ((y &1) == 1)
r = mr(r,z);
z = mr(z,z);
y >>= 1;
}
return mod(r);
}
}
}
class Combin{
int n = 2;
long[] f,fi;
long mod = Util.mod;
public Combin(int n){
this();
grow(n);
}
public Combin(){ f = fi = new long[]{1, 1}; }
public void grow(int n){
n = min((int) mod,n);
f = copyOf(f,n);
fi = copyOf(fi,n);
for (int i = this.n;i < n;i++)
f[i] = f[i -1] *i %mod;
fi[n -1] = pow(f[n -1],mod -2);
for (int i = n;--i > this.n;)
fi[i -1] = fi[i] *i %mod;
this.n = n;
}
private long pow(long x,long n){
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 long nHr(int n,int r){ return r < 0 ? 0 : nCr(n +r -1,r); }
public long nCr(int n,int r){
if (r < 0 || n -r < 0)
return 0;
if (this.n <= n)
grow(max(this.n <<1,n +1));
return f[n] *(fi[r] *fi[n -r] %mod) %mod;
}
}
class Data extends BaseV{
long v,c;
public Data(long v){ this.v = v; }
@Override
public String toString(){ return "" +v; }
}
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;
}
}
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;
}
}
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 = e.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;
}
}
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 SparseTable2D{
int h,w,hl,wl;
long[][][][] tbl;
SparseTable2D(int h,int w){
hl = max(1,32 -Integer.numberOfLeadingZeros((this.h = h) -1));
wl = max(1,32 -Integer.numberOfLeadingZeros((this.w = w) -1));
tbl = new long[hl][wl][][];
for (int hi = 0;hi < hl;hi++)
for (int wi = 0;wi < wl;wi++) {
int hhl = h -(1 <<hi) +1;
int wwl = w -(1 <<wi) +1;
tbl[hi][wi] = new long[hhl][wwl];
for (int i = 0;i < hhl;i++)
for (int j = 0;j < wwl;j++)
if ((hi |wi) == 0)
tbl[0][0][i][j] = init(i,j);
else if (0 < hi)
tbl[hi][wi][i][j] = agg(tbl[hi -1][wi][i][j],tbl[hi -1][wi][i +(1 <<hi -1)][j]);
else
tbl[hi][wi][i][j] = agg(tbl[hi][wi -1][i][j],tbl[hi][wi -1][i][j +(1 <<wi -1)]);
}
}
abstract protected long init(int i,int j);
abstract protected long agg(long a,long b);
long get(int i0,int j0,int i1,int j1){
int il = max(0,31 -Integer.numberOfLeadingZeros(i1 -i0 -1));
int jl = max(0,31 -Integer.numberOfLeadingZeros(j1 -j0 -1));
i1 = max(0,i1 -(1 <<il));
j1 = max(0,j1 -(1 <<jl));
long[][] tmp = tbl[il][jl];
long ret = agg(tmp[i0][j0],tmp[i0][j1]);
ret = agg(ret,tmp[i1][j0]);
ret = agg(ret,tmp[i1][j1]);
return ret;
}
}
abstract class SparseTable{
int n;
long[] tbl;
SparseTable(int n){
int K = max(1,32 -Integer.numberOfLeadingZeros(n -1));
this.n = 1 <<K;
tbl = new long[K *this.n];
for (int i = 0;i < this.n;i++)
tbl[i] = i < n ? init(i) : 0;
for (int k = 1;k < K;k++)
for (int s = 1 <<k;s < this.n;s += 2 <<k) {
int b = k *this.n;
tbl[b +s] = s < n ? init(s) : 0;
tbl[b +s -1] = s < n ? init(s -1) : 0;
for (int i = 1;i < 1 <<k;i++) {
tbl[b +s +i] = agg(tbl[b +s +i -1],tbl[s +i]);
tbl[b +s -1 -i] = agg(tbl[b +s -i],tbl[s -1 -i]);
}
}
}
abstract protected long init(int i);
abstract protected long agg(long a,long b);
long get(int l,int r){
r--;
if (l == r)
return tbl[l];
int k = 31 -Integer.numberOfLeadingZeros(l ^r);
return agg(tbl[k *n +l],tbl[k *n +r]);
}
}
abstract class Sum2D{
private long[] sum;
private int w;
public Sum2D(int h,int w){
this.w = w;
sum = new long[(h +1) *(w +1)];
for (int i = 0;i < h;i++)
for (int j = 0;j < w;j++)
sum[top(i +1,j +1)] = a(i,j) +sum[top(i +1,j)] +sum[top(i,j +1)] -sum[top(i,j)];
}
abstract long a(int i,int j);
private int top(int i,int j){ return i *(w +1) +j; }
long get(int il,int ir,int jl,int jr){ return sum[top(ir,jr)] -sum[top(il,jr)] -sum[top(ir,jl)] +sum[top(il,jl)]; }
}
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[n]); }
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(){ return copyOf(arr,sz); }
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; }
}
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 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;
}
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;
});
}
@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();
}
}