結果
| 問題 | No.1617 Palindrome Removal |
| ユーザー |
 kps
|
| 提出日時 | 2021-07-22 21:44:34 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 52,998 bytes |
| コンパイル時間 | 4,060 ms |
| コンパイル使用メモリ | 99,212 KB |
| 実行使用メモリ | 44,228 KB |
| 最終ジャッジ日時 | 2024-07-17 17:04:52 |
| 合計ジャッジ時間 | 7,464 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 138 ms
42,220 KB |
| testcase_01 | AC | 137 ms
42,436 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | AC | 140 ms
43,912 KB |
| testcase_05 | WA | - |
| testcase_06 | AC | 98 ms
42,340 KB |
| testcase_07 | AC | 96 ms
41,708 KB |
| testcase_08 | AC | 55 ms
37,636 KB |
| testcase_09 | AC | 56 ms
37,004 KB |
| testcase_10 | AC | 139 ms
43,852 KB |
| testcase_11 | AC | 137 ms
43,152 KB |
| testcase_12 | AC | 140 ms
43,836 KB |
| testcase_13 | AC | 139 ms
43,712 KB |
| testcase_14 | AC | 55 ms
37,124 KB |
| testcase_15 | AC | 55 ms
37,572 KB |
| testcase_16 | AC | 55 ms
37,488 KB |
| testcase_17 | AC | 55 ms
37,632 KB |
| testcase_18 | AC | 56 ms
37,228 KB |
| testcase_19 | AC | 55 ms
37,268 KB |
| testcase_20 | WA | - |
| testcase_21 | AC | 55 ms
37,004 KB |
| testcase_22 | AC | 55 ms
37,320 KB |
| testcase_23 | WA | - |
ソースコード
/*
created by krps
本体は590行目あたりのsolve()に書いてあります。
Good Luck!
*/
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.AbstractMap;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
public class Main implements Runnable {
public static void main(String[] args) {
new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); //16MBスタックを確保して実行
}
public void run() {
for(int i=0;i<1;i++) {
solver();
out.flush();
}
}
static FastScanner sc = new FastScanner();
static PrintWriter out = new PrintWriter(System.out);
public static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> implements Comparable<Pair<K, V>> {
public Pair(final K key, final V value) {
super(key, value);
}
@Override
public int compareTo(Pair<K, V> o) {
Comparable key = (Comparable)this.getKey();
Comparable key2 = (Comparable)o.getKey();
/*if (false) {
Comparable key3 = (Comparable) this.getValue();
Comparable key4 = (Comparable) o.getValue();
if (key.compareTo(key2) == 0) {
return key3.compareTo(key4);
}
}*/
return key.compareTo(key2);
}
}
private static boolean isPrime(long t) {
if(t<2)return false;
for(int i=2;i*i<=t;i++) {
if(t%i==0)return false;
}
return true;
}
@SuppressWarnings("unused")
private static long ncr(long n,long r) {
long res=1;
for(int i=0;i<r;i++) {
res*=n-i;
res/=i+1;
}
return res;
}
@SuppressWarnings("unused")
private static int StringCount(String T,String v) {
int res=0;
int t=0;
while(T.indexOf(v,t)>=0) {
//p(t);
res++;
t=T.indexOf(v,t)+1;
}
return res;
}
private static int arrayMin(int a[]) {
int res=INF;
for(int i=0;i<a.length;i++)res=min(res,a[i]);
return res;
}
private static long arrayMin(long a[]) {
long res=INF;
for(int i=0;i<a.length;i++)res=min(res,a[i]);
return res;
}
private static int arrayMax(int a[]) {
int res=-INF;
for(int i=0;i<a.length;i++)res=max(res,a[i]);
return res;
}
private static long arrayMax(long a[]) {
long res=-INF;
for(int i=0;i<a.length;i++)res=max(res,a[i]);
return res;
}
private static long arraySum(long a[]) {
long res=0;
for(int i=0;i<a.length;i++)res+=a[i];
return res;
}
private static int arraySum(int a[]) {
int res=0;
for(int i=0;i<a.length;i++)res+=a[i];
return res;
}
private static void swap(long V[],int a,int b) {
long temp=V[b];
V[b]=V[a];
V[a]=temp;
}
private static void p(long[][] a) {for(int i=0;i<a.length;i++)p(a[i]);};
private static void p(long[] a) {p(Arrays.toString(a));};
private static void p(int[][] a) {for(int i=0;i<a.length;i++)p(a[i]);};
private static void p(int[] a) {p(Arrays.toString(a));};
//大量にout.println();をすると、自動でout.flush();されるので、出力される順番には気を付けよう
// * out.println()の後にSystem.out.println();をしたいときとかねー
private static <T> void p(T t) {out.println(t);}
private static <T> void p() {out.println();}
private static void p(graph.edge2[] e) {
for (int i = 0; i < e.length; i++) {
out.println(e[i].to+" "+e[i].cost);
}
}
private static void doubleToString(double a) {
System.out.println(BigDecimal.valueOf(a).toPlainString());
}
private static ArrayList<Map<Integer,Integer>> c;
private static <T> int[] ArrayListToList(ArrayList<Integer> c2,int[] v) {for(int i=0;i<c2.size();i++)v[i]=c2.get(i);return v;}
private static ArrayList<Integer> ListToArrayList(int[] v) {ArrayList<Integer> c=new ArrayList<>(v.length);for(int i=0;i<v.length;i++)c.add(v[i]);return c;}
private static String maenizero(String s,int keta) {
while(s.length()<keta)s="0"+s;
return s;
}
private static int ketawa(String S) {
int res=0;
for(int i=0;i<S.length();i++) {
res+=S.charAt(i)-'0';
}return res;
}
private static int ketawa(int S) {
int res=0;
while(S!=0) {
res+=S%10;
S/=10;
}
return res;
}
private static long X_x[]=new long[1];
private static long kaijou(int x,long mod) {
if(X_x.length!=100001)X_x=new long[100001];
if(x<=1)return X_x[x]=1;
if(X_x[x]!=0)return X_x[x];
return X_x[x]=(x*kaijou(x-1,mod))%mod;
/*long a=1;
for(int i=2;i<=K;i++)a=(a*i)%mod;
return (int)a;*/
}
static class segmentTree{
int n;
long dat[];
long identity;//単位元
segmentTree(int N,long identity) {//setTreeの要素の数,単位元
this.identity =identity;
init(N);
}
void init2() {
Arrays.fill(dat, 0);
}
void init(int n_) {
this.n=1;
while(n<n_)n*=2;
this.dat= new long[2*n-1];
Arrays.fill(dat, identity);
}
void update(int k,long a) {
k+=n-1;
dat[k]=a;
while(k>0) {
k=(k-1)/2;
//System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2]));
dat[k]=Cal(dat[k*2+1],dat[k*2+2]);
}
}
//外から呼び出すときはl=0,r=-1,k=0にする。
void update(int a,int b,int k,int X,int l,int r) {
if(r==-1)r=n;
if(r<=a||b<=l) {
return;
}
if(a<=l&&r<=b) {
dat[k]=min(dat[k],X);
}else {
update(a, b, k*2+1,X, l, (l+r)/2);
update(a, b,k*2+2,X,(l+r)/2,r);
}
}
long get(int k) {//k番目の値を取得 0<=k<N
k+=n-1;
return dat[k];
}
//[a,b]を求める。
//a~bのこと。0-indexed
long getV(int a,int b) {
a=max(0,a);
b=min(n-1,b);
b++;
return query(a, b, 0, 0, n);
}
int getleft(int a,int b,long x) {
return find_leftest_sub(a, b, x, 0, 0, n);
}
int getright(int a,int b,long x) {
return find_rightest_sub(a, b, x, 0, 0, n);
}
//[a,b)の値を求める
//a~b-1のことで、0-indexed
//外から呼び出すときは、a,b,0,0,N
long query(int a,int b,int k,int l,int r) {
if(r<=a||b<=l) {
//l,rが求めたい区間a,bに完全に含まれていない
return identity;
}
if(a<=l&&r<=b) {
//l,rが、求めたい区間a,bに完全に含まれている
return dat[k];
}else {
//l,rが、求めたい区間a,bに一部分だけ含まれている。
long A=query(a, b, k*2+1, l, (l+r)/2);
long B=query(a, b, k*2+2, (l+r)/2, r);
return Cal(A,B);
}
}
//x以下の要素を持つ最も左のもののindexを返す。 *RM(min)Q上でしか動かない
int find_rightest_sub(int a, int b, long x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
return a - 1;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
} else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
int find_leftest_sub(int a, int b, long x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
return b;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
} else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
//RSQ上で動きます。
int query2(long X) {
int k=0;
//ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい
while(k*2+1<dat.length) {
if(dat[k*2+1]>=X) {
k=k*2+1;
}else {
X-=dat[k*2+1];
k=k*2+2;
}
}
return k-=n-1;
}
long Cal(long a,long b) {
//計算アルゴリズム
return (a+b);
//return a|b;
//return max(a,b);
//return gcd(a, b);
//return a^b;
//return Math.min(a, b);
}
int size() {
//Nではないよ、配列の大きさを返す。
return n;
}
//確認事項:Calとidentity
//segmentTreeで宣言、initで初期化する。
void toString(int n) {
for(int i=0;i<n*2;i++) {
System.err.print(dat[i]+" ");
}
System.err.println();
}
}
static class LazySegmentTree{
int n;
long node[],lazy[];
int identity;
long cal(long a,long b) {
return a+b;
}
public LazySegmentTree(long[] A,int iden) {
// TODO 自動生成されたコンストラクター・スタブ
init(A);
identity=iden;
}
//初期化
void init(long A[]) {
n=1;
int sz=A.length;
while(n<sz)n*=2;
node=new long[2*n-1];
lazy=new long[2*n-1];
for(int i=0;i<sz;i++)node[i+n-1]=A[i];
for(int i=n-2;i>=0;i--)node[i]=cal(node[i*2+1],node[i*2+2]);
}
void eval(int k,int l,int r) {
//k番目のノードについて、遅延評価を行う？
// 遅延配列が空でない場合、自ノード及び子ノードへの
// 値の伝播が起こる
if(lazy[k]!=identity) {
node[k]+=lazy[k];
System.out.println(r);
if(r-1>1) {//最下段かどうか
lazy[2*k+1]=cal(lazy[k]/2, lazy[2*k+1]);//ここもRSQ以外未定義 /2するところを要変更
lazy[2*k+2]=cal(lazy[k]/2, lazy[2*k+1]);
// 子ノードは親ノードの 1/2 の範囲であるため、
// 伝播させるときは半分にする
}
lazy[k]=identity;
}
}
//区間加算,外から呼び出すときは、l=0,r=-1
void add(int a,int b,long x,int k,int l,int r) {
//[a,b)の区間にxを加算する。
if(r<0)r=n;
eval(k,l,r);
if(b<=l||r<=a)return;
if(a<=l&&r<=b) {
lazy[k]=cal((r-1)*x,lazy[k]);//ここもRSQ以外未定義 *xするところを要変更
eval(k, l, r);
}else {
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
node[k]=cal(node[2*k+1],node[2*k+2]);
}
}
//区間和取得,外から呼び出すときは、l=0,r=-1
long getsum(int a,int b,int k,int l,int r) {
if(r<0)r=n;
if(b<=l||r<=a)return 0;
eval(k, l, r);
if(a<=l&&r<=b)return node[k];
long vl=getsum(a, b, 2*k+1, l, (l+r)/2);
long vr=getsum(a, b, 2*k+2, (l+r)/2, r);
return cal(vl,vr);
}
}
static class IntsegmentTree{
int n;
int dat[];
int identity;//単位元
IntsegmentTree(int N,int identity) {//setTreeの要素の数,単位元
this.identity =identity;
init(N);
}
void init2() {
Arrays.fill(dat, 0);
}
void init(int n_) {
this.n=1;
while(n<n_)n*=2;
this.dat= new int[2*n-1];
Arrays.fill(dat, identity);
}
void update(int k,int a) {
k+=n-1;
dat[k]=a;
while(k>0) {
k=(k-1)/2;
//System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2]));
dat[k]=Cal(dat[k*2+1],dat[k*2+2]);
}
}
//外から呼び出すときはl=0,r=-1,k=0にする。
void update(int a,int b,int k,int X,int l,int r) {
if(r==-1)r=n;
if(r<=a||b<=l) {
return;
}
if(a<=l&&r<=b) {
dat[k]=min(dat[k],X);
}else {
update(a, b, k*2+1,X, l, (l+r)/2);
update(a, b,k*2+2,X,(l+r)/2,r);
}
}
int get(int k) {//k番目の値を取得 0<=k<N
k+=n-1;
return dat[k];
}
//[a,b]を求める。
//a~bのこと。0-indexed
int getV(int a,int b) {
a=max(0,a);
b=min(n-1,b);
b++;
return query(a, b, 0, 0, n);
}
int getleft(int a,int b,long x) {
return find_leftest_sub(a, b, x, 0, 0, n);
}
int getright(int a,int b,long x) {
return find_rightest_sub(a, b, x, 0, 0, n);
}
//[a,b)の値を求める
//a~b-1のことで、0-indexed
//外から呼び出すときは、a,b,0,0,N
int query(int a,int b,int k,int l,int r) {
if(r<=a||b<=l) {
//l,rが求めたい区間a,bに完全に含まれていない
return identity;
}
if(a<=l&&r<=b) {
//l,rが、求めたい区間a,bに完全に含まれている
return dat[k];
}else {
//l,rが、求めたい区間a,bに一部分だけ含まれている。
int A=query(a, b, k*2+1, l, (l+r)/2);
int B=query(a, b, k*2+2, (l+r)/2, r);
return Cal(A,B);
}
}
//x以下の要素を持つ最も左のもののindexを返す。 *RM(min)Q上でしか動かない
int find_rightest_sub(int a, int b, long x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
return a - 1;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn
return vr;
} else { // 左の部分木を見て値をreturn
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
int find_leftest_sub(int a, int b, long x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
return b;
} else if (k >= n - 1) { // 自分が葉ならその位置をreturn
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // 左の部分木を見て b 以外ならreturn
return vl;
} else { // 右の部分木を見て値をreturn
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
//RSQ上で動きます。
int query2(int X) {
int k=0;
//ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい
while(k*2+1<dat.length) {
if(dat[k*2+1]>=X) {
k=k*2+1;
}else {
X-=dat[k*2+1];
k=k*2+2;
}
}
return k-=n-1;
}
int Cal(int a,int b) {
//計算アルゴリズム
return (a+b);
//return a|b;
//return max(a,b);
//return gcd(a, b);
//return a^b;
//return Math.min(a, b);
}
int size() {
//Nではないよ、配列の大きさを返す。
return n;
}
//確認事項:Calとidentity
//segmentTreeで宣言、initで初期化する。
void toString(int n) {
for(int i=0;i<n*2;i++) {
System.err.print(dat[i]+" ");
}
System.err.println();
}
}
static void B(boolean x) {
p(x? "Yes":"No");
}
static void B(boolean x, String a,String b) {
p(x? a:b);
}
static int[][] clone(int V[][]) {
int RES[][]=new int[V.length][V[0].length];
for (int i = 0; i < V.length; i++) {
for (int t = 0; t < V[0].length; t++) {
RES[i][t]=V[i][t];
}
}
return RES;
}
static class D {
int a,b;
}
static void comp(int a[]) {
binarySerch bs = new binarySerch();
int b[]=a.clone();
Arrays.parallelSort(b);
for (int i = 0; i < a.length; i++) {
a[i]=bs.lowerBound(b, a[i])+1;
compmax=max(compmax,a[i]);
}
}
static long ceil(long a,long b) {
//ceil(a/b)を返す。
//a/bの切り上げ
return (a+b-1)/b;
}
static long floor(long a,long b) {
//floor (a/b)を返す。
//a/bの切り捨て
return a/b;
}
//Math.multiplyExact(T, A[i])
static class V implements Comparable<V>{
int y,z;
int x,a,b,C;
int count;
int dep;
String S;
V(int x,int y){
this.x=x;
this.y=y;
}
V(int a,int b,int C){
this.a=a;
this.b=b;
this.x=C;
}
public int compareTo(V o) {
Comparable key = (Comparable)this.x;
Comparable key2 = (Comparable)o.x;
Comparable key3 = (Comparable)this.y;
Comparable key4 = (Comparable)o.y;
if(key.compareTo(key2)==0) {
return key3.compareTo(key4);
}
return key.compareTo(key2);
}
}
static long LINF =(1L<<63)-1,mod7=Pow(10,9)+7,mod9=Pow(10,9)+9,count=0,sum=0,max=-LINF,min=LINF,ans=0,temp;
static int i=0,INF=(1<<31)-1,compmax=0;
static long A[];
private static void solver() {
//2個取り除くか、取り除かないか、取り除けないか。
String S = sc.next();
if(!isPalindrome(S)) {
System.out.println(S.length());
return;
}
Set<Integer> s = new HashSet<>();
for (int i = 0; i < S.length(); i++) {
s.add((int)S.charAt(i));
}
if(s.size()==1&&S.length()%2==0) {
System.out.println(0);
return;
}
if(s.size()==1) {
System.out.println(-1);
return;
}
//に文字で、交互だと死ぬ？
if(isPalindrome(S.substring(0,S.length()-2))) {
System.out.println(-1);
return;
}
if(s.size()==2&&S.length()%2==1) {
int T=S.charAt(0);
for (int i = 0; i < S.length(); i++) {
if(i==S.length()/2)continue;
if(S.charAt(i)!=T) {
System.out.println((S.length()-2));
return;
}
}
System.out.println(-1);
return;
}
System.out.println(S.length()-2);
}
/*long kruskal(int V,edge es[]) {
unionFind uf = new unionFind(V);
Arrays.sort(es);
long res=0;
for (int i = 0; i < es.length; i++) {
if(uf.find( es[i].from)!=uf.find( es[i].to)) {
uf.union(es[i].from, es[i].to);
res+=es[i].cost;
}
}
return res;
}*/
//関数Fについて、区間[a,b]の最小値を求める
static void tripet(long a,long b) {
long max=max(a,b),min=min(a,b);
while(max-min>2){
long c1=(max-min)/3+min;
long c2=(max-min)*2/3+min;
if(F(c1)>=F(c2)) {
min=c1;
}else{
max=c2;
}
}
for(long i=min-1;i<=max+1;i++) {
F(i);
}
}
static long F(long V) {
long res=0;
//b0をVに固定する
long b=V;
long c=A[0]-b;
res+=abs(b)+abs(c);
for (int i = 1; i < A.length; i++) {
if(A[i]>A[i-1]) {
//増加した。
b=A[i]-c;
}else if(A[i]<A[i-1]) {
//減少した
c=A[i]-b;
}
res+=abs(b)+abs(c);
if(res<0)res=LINF;
}
min=min(min,res);
return res;
}
static long getF(long a,long b,long c,long d) {
//[a,b]と[c,d]の区間数の和
if(b<c||a>d) {
//完全に含まれない。
return (b-a+1)+(d-c+1);
}
if(c<=a&&b<=d) {
//完全に含まれる1
return d-c+1;
}
if(a<=c&&d<=b) {
//完全に含まれる2
return b-a+1;
}
//一部だけ含まれる。
if(c<=b&&b<=d) {
//[c,b]が含まれる。
return d-a+1;
}
if(c<=a&&a<=d) {
return b-c+1;
}
return -1;
}
static boolean check(int HW[][],int i,int t,int W) {
while(t<W) {
if(HW[i][t]%2==1)return true;
t++;
}
return false;
}
static void SCC(Map<Integer,ArrayList<Integer>> m,int N) {
int BACK[]=new int[N];
Arrays.fill(BACK, -1);
for (int i = 0; i < N; i++) {
if(BACK[i]!=-1)continue;
getBackQuery(m, i, BACK);
BACK[BACK_COUNT]=i;
}
Map<Integer,ArrayList<Integer>> reversedm=new HashMap<>();
for(int Vex:m.keySet()) {
for(int TO:m.get(Vex)) {
if(!reversedm.containsKey(TO))reversedm.put(TO, new ArrayList<>());
reversedm.get(TO).add(Vex);
}
}
uf=new unionFind(N);
for (int i = N-1; i>=0;i--) {
//iを始点として、DFSを行う。到達可能マスが同じグループ
if(uf.get(i)!=i)continue;
sccquery(reversedm, i);
}
}
static void sccquery(Map<Integer,ArrayList<Integer>> reversedm,int vex) {
if(!reversedm.containsKey(vex)||reversedm.get(vex).size()==0)return;
for(int TO:reversedm.get(vex)) {
if(uf.find(vex)==uf.find(TO))continue;
uf.union(vex, TO);
sccquery(reversedm, vex);
}
}
static int BACK_COUNT;
static unionFind uf;
static void getBackQuery(Map<Integer,ArrayList<Integer>> m,int Vex,int BACK[]) {
if(!m.containsKey(Vex)||m.get(Vex).size()==0)return;
for(int TO:m.get(Vex)) {
if(BACK[TO]!=-1)continue;
BACK[TO]=-2;
getBackQuery(m, Vex, BACK);
BACK[BACK_COUNT++]=TO;
}
}
static ArrayList<Integer> Vs;
static void getTopo(Map<Integer,ArrayList<Integer>> m,int N) {
boolean flag[]=new boolean[N];
Arrays.fill(flag, false);
Vs=new ArrayList<>();
for(int V:m.keySet()) {
if(flag[V])continue;
flag[V]=true;
topoQuery(m, V, flag);
Vs.add(V);
}
Collections.reverse(Vs);
}
static void topoQuery(Map<Integer,ArrayList<Integer>> m,int Vex, boolean flag[]) {
//Vexからスタート
//これ、閉路がある時に対応できてなくね
if(!m.containsKey(Vex)||m.get(Vex).size()==0)return;
for(int to:m.get(Vex)) {
if(flag[to])continue;
flag[to]=true;
topoQuery(m, to,flag);
Vs.add(to);
}
}
static class Flow{
static class edge{
int to,cap,rev;
public edge(int to,int cap,int rev) {
// TODO 自動生成されたコンストラクター・スタブ
this.to=to;
this.cap=cap;
this.rev=rev;
}
}
public Flow(int N) {
// TODO 自動生成されたコンストラクター・スタブ
this.N=N;//頂点数
init();
}
void init() {
used=new boolean[N];
G=new ArrayList<>();
for (int i = 0; i < N; i++) {
G.add(new ArrayList<>());
}
}
int N;
ArrayList<ArrayList<edge>> G;//iがfromを意味する 隣接リスト表現
boolean used[];
//from->toへ向かう容量capの辺をグラフに追加する。
void add_edge(int from,int to,int cap) {
G.get(from).add(new edge(to, cap, G.get(to).size()));
G.get(to).add(new edge(from, 0, G.get(from).size()-1));
}
//最大流を求める 最悪計算量はO(F|E|) Fは流量,Eは辺の数?
int max_flow(int s,int t) {
int flow=0;
while(true) {
Arrays.fill(used, false);
int f=dfs(s,t,INF);
if(f==0)return flow;
flow+=f;
}
}
int dfs(int v,int t,int f) {
if(v==t)return f;//tに到着したら終了
used[v]=true;//vに訪れたことを表す
for (int i = 0; i < G.get(v).size(); i++) {
edge e=G.get(v).get(i);
if(used[e.to]||e.cap<=0)continue;
int d=dfs(e.to, t, Math.min(f,e.cap));
if(d>0) {
e.cap-=d;
G.get(e.to).get(e.rev).cap+=d;
return d;
}
}
return 0;
}
//デバッグ用
void get_edges(int T) {
//頂点Tから出る辺を出力する
int cout=0;
for(edge e:G.get(T)) {
System.out.println(cout+++" "+T+"=>"+e.to+" "+e.cap);
}
}
}
static class LCA{
int N;//頂点の数(頂点名は、0-indexで命名)
int dist[];//rootから頂点iまでの距離
int root;//木の根
int parents[];//頂点iの親がparents[i]
int doubling[][];
public LCA(Map<Integer,ArrayList<Integer>> m,int N,int root) {
//一般グラフを受け取って、そこから木を生成する。
this.root=root;
init(m,N);
}
void init(Map<Integer,ArrayList<Integer>> m,int N) {
this.N=N;
parents=new int[N];
dist=new int[N];
doubling=new int[31][N];
dfs(m);
init_doubling();
}
void dfs(Map<Integer,ArrayList<Integer>> m) {
//根からの距離と親を求める。
boolean flag[]=new boolean[N];
Arrays.fill(flag, false);
flag[root]=true;
parents[root]=root;
Queue<Integer> qq = new ArrayDeque<>(); //始点を保存
qq.add(root);
while(!qq.isEmpty()) {
int VEX=qq.poll();
if(!m.containsKey(VEX)||m.get(VEX).size()==0)continue;
for(int TO:m.get(VEX)) {
if(flag[TO])continue;
flag[TO]=true;
parents[TO]=VEX;
dist[TO]=dist[VEX]+1;
qq.add(TO);
}
}
}
void init_doubling() {
//ダブリングによって、2^k先の祖先を前計算する。
//doubling[T][i]=iから2^T個分先
for (int i = 0; i < N; i++) {
doubling[0][i]=parents[i];
}
for (int T = 1; T < doubling.length; T++) {
for (int i = 0; i < N; i++) {
doubling[T][i]=doubling[T-1][doubling[T-1][i]];
}
}
}
int get_doubling(int from,int K) {
//ダブリングによって、fromからK先の祖先を求める。
//longにするときは、doublingの長さも変えないとだから注意
int res=from;
for (int i = 0; i < doubling.length; i++) {
if(((K>>i)&1)==0)continue;
res=doubling[i][res];
}
return res;
}
int query(int u1,int v1) {
//親からの距離を等しくする。(dist[u1]>dist[v1]とする)
//System.out.println(u1+" "+v1+" "+get_doubling(u1, dist[u1]-dist[v1]));
u1=get_doubling(u1, dist[u1]-dist[v1]);
if(u1==v1)return v1;
//二分探索によって、LCAの手前まで移動させる。
int G=30;
while(G>=0) {
int uTO=doubling[G][u1];
int vTO=doubling[G][v1];
if(uTO!=vTO) {
u1=uTO;
v1=vTO;
}
G--;
}
//System.out.println(parents[u1]+" "+parents[v1]+" "+dist[u1]+" "+dist[v1]+" "+u1+" "+v1);
return parents[u1];
}
int get_LCA(int u,int v) {
//根をrootとした時の、u,vのLCAを返す。(0-indexed)
if(dist[u]<dist[v]) {
int temp=u;u=v;v=temp;
}
//dist[u]>dist[v]とする。
return query(u,v);
}
int get_dist(int u,int v) {
//u-vの距離
return dist[u]+dist[v]-2*dist[get_LCA(u, v)];
}
boolean is_on_path(int u,int v,int a) {
//u-vパス上に頂点aがあるか?
//true:ある
//false:ない
return get_dist(u, a)+get_dist(a, v)==get_dist(u, v);
}
}
static class doubling{
int N;
int bits;
int doubling[][];
long COST[][];
public doubling(int A[],int bits) {
this.bits=bits;
this.N=A.length;
init1(A);
}
public doubling(int A[],int bits,long C[]) {
// TODO 自動生成されたコンストラクター・スタブ
//long C[]は、i=>A[i]に行くコスト
//query2は、iからK番先までのコストの和で、i番までのコストが足されないので注意
this.bits=bits;
this.N=A.length;
init1(A);
init2(C);
}
private void init1(int A[]) {
// TODO 自動生成されたメソッド・スタブ
doubling=new int[bits][N];
for (int i = 0; i < N; i++) {
doubling[0][i]=A[i];
}
for (int t = 0; t+1 < bits; t++) {
for (int i = 0; i < N; i++) {
doubling[t+1][i]=doubling[t][doubling[t][i]];
}
}
}
private void init2(long C[]) {
COST=new long[bits][N];
for (int i = 0; i < N; i++) {
COST[0][i]=C[i];//i番目からA[i]までのコスト
}
for (int t = 0; t+1 < bits; t++) {
for (int i = 0; i < N; i++) {
COST[t+1][i]=COST[t][doubling[t][i]]+COST[t][i];
}
}
}
//解釈
private int query1(int start,long K) {
//startからK回移動した後の座標を求める。
int now=start;
for (int i = 0; i < bits; i++) {
if(((K>>i)&1)==1)now=doubling[i][now];
}
return now;
}
private long query2(int start,long K,long mod) {
//STARTからK回移動した時のコストを計算する。
int now=start;
long res=0;
for (int i = 0; i < bits; i++) {
if(((K>>i)&1)==1) {
res+=COST[i][now];
now=doubling[i][now];
res%=mod;
}
}
return res;
}
private int query3(int start) {
//startからスタートして、ループに入る時、そのループの長さを返す。
return 1;
}
}
static class DIKSTR{
ArrayList<ArrayList<edge2>> m;
static Map<String,Integer> hash=new HashMap<>();
static int hash_count=0;
long d[];
int V,E;
class edge2{
int to;
long cost;
public edge2(int to,long cost) {
this.to=to;
this.cost=cost;
}
}
class pair implements Comparable<pair>{
int VEX;
long cost;
public pair(long cost,int VEX) {
this.VEX=VEX;
this.cost=cost;
}
public int compareTo(pair o) {
Comparable key = (Comparable)this.cost;
Comparable key2 = (Comparable)o.cost;
return key.compareTo(key2);
}
}
public DIKSTR(int V,int E) {
this.V=V;//最大の頂点数。
this.E=E;//最大の辺数。
init();
}
public DIKSTR(int V) {
this.V=V;
this.E=0;
init();
}
void init() {
m=new ArrayList<>();
for (int i = 0; i < V; i++) {
m.add(new ArrayList<>());
}
d=new long[V];
}
void add_edge(int FROM,int TO,long COST) {
m.get(FROM).add(new edge2(TO, COST));
}
void add_edge(String FROM,String TO,long COST) {
if(!hash.containsKey(FROM))hash.put(FROM, hash_count++);
if(!hash.containsKey(TO))hash.put(TO, hash_count++);
add_edge(get_hash(FROM), get_hash(TO), COST);
}
int get_hash(String T) {
if(!hash.containsKey(T)) {
hash.put(T, hash_count++);
}
return hash.get(T);
}
long[] dikstr(String r) {
return dikstr(get_hash(r));
}
long[] dikstr(int r) {//rは始点
Arrays.fill(d, LINF);
d[r]=0;
PriorityQueue<pair> p = new PriorityQueue<>();//add poll
p.add(new pair(0L, r));
while(!p.isEmpty()) {
pair x=p.poll();
int from=x.VEX;
if(x.cost>d[from])continue;
for (int i = 0; i < m.get(from).size(); i++) {
edge2 e=m.get(from).get(i);
long COST=COST(e.cost);
if(d[e.to]>d[from]+COST) {
d[e.to]=d[from]+COST;
p.add(new pair(d[e.to], e.to));
}
}
}
return d.clone();
}
long COST(long e_cost) {
return e_cost;
}
}
static Map<Integer, ArrayList<Integer>> getTree(int N){
Map<Integer, ArrayList<Integer>> m = new HashMap<>();
for (int i = 0; i < N; i++) {
int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
if (!m.containsKey(a))
m.put(a, new ArrayList<Integer>());
if (!m.containsKey(b))
m.put(b, new ArrayList<Integer>());
m.get(a).add(b);
m.get(b).add(a);
}
return m;
}
static Map<Integer, ArrayList<Integer>> makeTree(Map<Integer, ArrayList<Integer>> m){
//頂点0を根とした木を構築する。
Queue<Integer> qq = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される
Queue<Integer> parent = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される
qq.add(0);
Map<Integer, ArrayList<Integer>> T = new HashMap<>();
parent.add(-1);
while (!qq.isEmpty()) {
int i = qq.poll();
int p = parent.poll();
if (!T.containsKey(i))
T.put(i, new ArrayList<Integer>());
for (int V : m.get(i)) {
if (V == p)
continue;
qq.add(V);
parent.add(i);
T.get(i).add(V);
}
}
return T;
}
static boolean isHaveSameBit(int a,int b) {//同じbitを持っているか
int t=0;
while((a>>t)!=0) {
if(((a>>t)&1)==1&&((b>>t)&1)==1)return true;
t++;
}
return false;
}
static boolean isPalindrome(String S) {//回分になってるか
for (int i = 0; i < S.length()/2; i++) {
if(S.charAt(i)!=S.charAt(S.length()-i-1)) {
return false;
}
}
return true;
}
static long modinv(long a,long mod) {
long b=mod,u=1,v=0;
while(b!=0) {
long t=a/b;
a-=t*b;long tem=a;a=b;b=tem;
u-=t*v;tem=u;u=v;v=tem;
}
u%=mod;
if(u<0)u+=mod;
return u;
}
static long[] extendedGCD(long a, long b) {
long s = 0, old_s = 1;
long t = 1, old_t = 0;
long r = b, old_r = a;
while(r != 0) {
long q = old_r / r;
long old_s0 = old_s, old_t0 = old_t, old_r0 = old_r;
old_s = s;
s = old_s0 - q * s;
old_t = t;
t = old_t0 - q * t;
old_r = r;
r = old_r0 - q * r;
}
return new long[] {old_s, old_t};
}
static class graph{
public graph() {
// TODO 自動生成されたコンストラクター・スタブ
}
//コンテスト中だけ
static class edge3{
int to;
long cost;
int K;
public edge3(int to,long cost) {
this.to=to;
this.cost=cost;
}
public edge3(int to,long cost,int K) {
this.to=to;
this.cost=cost;
this.K=K;
}
}
long costV(long T,int K) {
//T以上の最小のKの倍数を返す。
long V=(T+K-1)/K;
return V*K;
}
long[] adddikstr(int V,int E,int r,Map<Integer, ArrayList<edge3>> m) {
d=new long[V];
Arrays.fill(d, LINF);
d[r]=0;
PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
p.add(new Pair<Long, Integer>(0L, r));
while(!p.isEmpty()) {
Pair<Long,Integer> x=p.poll();
int from=x.getValue();
if(x.getKey()>d[from])continue;
if(!m.containsKey(from))continue;
for (int i = 0; i < m.get(from).size(); i++) {
edge3 e=m.get(from).get(i);
if(d[e.to]>costV(d[from],e.K)+e.cost) {
d[e.to]=costV(d[from],e.K)+e.cost;
p.add(new Pair<Long, Integer>(d[e.to], e.to));
}
}
}
return d;
}
//
class edge implements Comparable<edge>{
int from,to,cost;
public edge(int from,int to,int cost) {
this.from=from;
this.to=to;
this.cost=cost;
}
@Override
public int compareTo(edge o) {
Comparable key = (Comparable)this.cost;
Comparable key2 = (Comparable)o.cost;
return key.compareTo(key2);
}
}
static class edge2{
int to;
long cost;
String FROM,TO;
public edge2(int to,long cost) {
this.to=to;
this.cost=cost;
}
public edge2(int to,long cost,String FROM,String TO) {
this.to=to;
this.cost=cost;
this.FROM=FROM;
this.TO=TO;
}
}
//単一始点最短距離問題(ダイクストラ法) 負閉路対策不可 経路復元
long d[];
long[] dikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m) {
//int path[]=new int[V];
//Arrays.fill(path, -1);
d=new long[V];
Arrays.fill(d, LINF);
d[r]=0;
PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
p.add(new Pair<Long, Integer>(0L, r));
while(!p.isEmpty()) {
Pair<Long,Integer> x=p.poll();
int from=x.getValue();
if(x.getKey()>d[from])continue;
if(!m.containsKey(from))continue;
for (int i = 0; i < m.get(from).size(); i++) {
edge2 e=m.get(from).get(i);
if(d[e.to]>d[from]+e.cost) {
d[e.to]=d[from]+e.cost;
p.add(new Pair<Long, Integer>(d[e.to], e.to));
//path[e.to]=from;
}
}
}
//経路復元
//複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく
//ArrayList<Integer> PATHs = new ArrayList<>();
//int t=V-1;//goalから逆算する この場合0=goal
//for(;t!=-1;t=path[t]) {
// PATHs.add(t);
//}
//p(path);
//Collections.reverse(PATHs);
//System.out.println(PATHs);
return d.clone();
}
long[] additionalDikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m,int banned) {
//int path[]=new int[V];
//Arrays.fill(path, -1);
d=new long[V];
Arrays.fill(d, LINF);
d[r]=0;
PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
p.add(new Pair<Long, Integer>(0L, r));
while(!p.isEmpty()) {
Pair<Long,Integer> x=p.poll();
int from=x.getValue();
if(x.getKey()>d[from])continue;
if(!m.containsKey(from))continue;
for (int i = 0; i < m.get(from).size(); i++) {
edge2 e=m.get(from).get(i);
if(from==banned&&e.to==0)continue;
if(d[e.to]>d[from]+e.cost) {
d[e.to]=d[from]+e.cost;
p.add(new Pair<Long, Integer>(d[e.to], e.to));
}
}
}
return d.clone();
}
int D[];
int[] Intdikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m) {
//int path[]=new int[V];
//Arrays.fill(path, -1);
D=new int[V];
Arrays.fill(D, INF);
D[r]=0;
PriorityQueue<Pair<Integer,Integer>> p = new PriorityQueue<>();//add poll
p.add(new Pair<Integer, Integer>(0, r));
while(!p.isEmpty()) {
Pair<Integer,Integer> x=p.poll();
int from=x.getValue();
if(x.getKey()>D[from])continue;
if(!m.containsKey(from))continue;
for (int i = 0; i < m.get(from).size(); i++) {
edge2 e=m.get(from).get(i);
if(D[e.to]>D[from]+e.cost) {
D[e.to]=(int) (D[from]+e.cost);
p.add(new Pair<Integer, Integer>(D[e.to], e.to));
//path[e.to]=from;
}
}
}
p.clear();
//経路復元
//複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく
//ArrayList<Integer> PATHs = new ArrayList<>();
//int t=V-1;//goalから逆算する この場合0=goal
//for(;t!=-1;t=path[t]) {
// PATHs.add(t);
//}
//p(path);
//Collections.reverse(PATHs);
//System.out.println(PATHs);
return D;
}
//単一始点最短距離問題(ベルマンフォード法) 負閉路対策済み
int[] Bellman_Ford(int V,int E,int r,edge e[]) {
int d[]=new int[V]; //0~eのグラフはこれ
//Map<Integer, Integer> d = new HashMap<>();それ以外はこれ
//for(int i=0;i<E;i++) {
// if(!d.containsKey(e[i].to))m.add(new Pair<Integer, Integer>(e[i].to, INF));
// if(!d.containsKey(e[i].from))m.add(new Pair<Integer, Integer>(e[i].from, INF));
//}
//d.replace(r, 0);
Arrays.fill(d, INF);
d[r]=0;
int count=0;
while(true) {
boolean update =false;
for(int i=0;i<E;i++) {
if(d[e[i].from]!=INF&&d[e[i].from]+e[i].cost<d[e[i].to]) {
update=true;
d[e[i].to]=d[e[i].from]+e[i].cost;
}
}
if(!update)break;
if(count==V) {
p("NEGATIVE CYCLE");
return null;
}
count++;
}
return d;
}
//最小全域木問題(クラスカル法)
long kruskal(int V,edge es[]) {
unionFind uf = new unionFind(V);
Arrays.sort(es);
long res=0;
for (int i = 0; i < es.length; i++) {
if(uf.find( es[i].from)!=uf.find( es[i].to)) {
uf.union(es[i].from, es[i].to);
res+=es[i].cost;
}
}
return res;
}
}
private static long Pow(long i,long t) {
//iのt乗をO(log t)で返す
long a=i;
long res=1;
//for(int i=0;i<S.length();i++) {if(S.charAt(N-i)=='1') {res=res*a%mod;}
//tをStringで受け取りたい時用
while(t!=0) {
if((1&t)==1) {
res=res*a;
}
a=a*a;
t=t>>1;
}
return res;
}
private static Map<Long, Integer> primeNumbers(long N) {//素因数列挙
Map<Long, Integer> c = new HashMap<>();
for(long i=2;i*i<=N;i++) {
if(N%i==0) {
int count=0;
while(N%i==0) {
N/=i;
count++;
}
c.put(i, count);
continue;
}
}
if(N!=1) {
c.put(N, 1);
}
return c;
}
//=========================Union Find=============================================
//union idx2 tree to idx1 tree O(a(N))
static class unionFind{
int UNI[],n;
public unionFind(int N) {
// TODO 自動生成されたコンストラクター・スタブ
n=N;
init();
}
void init() {
UNI=new int[n];
for (int i = 0; i < n; i++) {
UNI[i]=i;
}
}
int get(int idx) {
return UNI[idx];
}
int find(int idx) {//木の根のindexを返す
if(UNI[idx]==idx) return idx;
return UNI[idx] = find(UNI[idx]);
}
void shape() {//木の根に直接つなげる 経路圧縮
for(int i=0;i<n;i++) {
find(i);
}
}
void union(int idx1,int idx2) {//idx1の根にidx2をつなげる
int root1 = find(idx1);
int root2 = find(idx2);
UNI[root2] = root1;
}
int MaxSize() {//最も大きい木の頂点数を返す
shape();
int V[]=new int[n];
int max=0;
for(int i=0;i<n;i++) {
V[UNI[i]]++;
max=Math.max(max, V[UNI[i]]);
}
return max;
}
int sum() {//木の数を返す
int res=0;
for(int i=0;i<n;i++) {
if(UNI[i]==i)res++;
}
return res;
}
void union2(int tree[],int idx1,int idx2) {//idx1の根にidx2をつなげる
int root1 = find(idx1);
int root2 = find(idx2);
if(root1==root2)return;
if(c.get(root1).size()>c.get(root2).size()) {
//root2をroot1に移し替える
for(int a:c.get(root2).keySet()) {
if(!c.get(root1).containsKey(a)) {
c.get(root1).put(a, 0);
}
c.get(root1).replace(a, c.get(root1).get(a)+c.get(root2).get(a));
}
tree[root2] = root1;
}else {
for(int a:c.get(root1).keySet()) {
if(!c.get(root2).containsKey(a)) {
c.get(root2).put(a, 0);
}
c.get(root2).replace(a, c.get(root2).get(a)+c.get(root1).get(a));
}
tree[root1] = root2;
}
}
}
//=========================二分探索=============================================
private static class binarySerch{
public binarySerch() {
// TODO 自動生成されたコンストラクター・スタブ
}
int BinarySearch(int A[],int value) {
int S=0,E=A.length,G=-1;
while(S<=E) {
G=(S+E)/2;
if(A[G]==value)return G;
else if(A[G]>value) {
if(E==G)break;E=G;
}else if(A[G]<value) {
if(S==G)break;S=G;
}
}
return -1;
}
int lowerBound(int A[],int value) {
//A[i-1]<value<=A[i] value以上のindexを返す
//value未満しかなかったらA.lengthを返す
//value以上の個数は(A.length-i)value未満の個数はiである
int S=0,E=A.length,G=-1;
if(A[0]>=value)return 0;
if(A[A.length-1]<value)return A.length;
while(true) {
G=(S+E)/2;
if(A[G]>=value&&A[G-1]<value) {
return G;
}else if(A[G]>=value) {
E=G;
}else if(A[G]<value) {
S=G;
}
}
}
int upperBound(int A[],int value) {
//A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
//value以下しかなかったらA.lengthを返す
//valueより大きい数の個数は(A.length-i)value以下の個数はiである
int S=0,E=A.length,G=-1;
if(A[0]>value)return 0;
if(A[A.length-1]<=value)return A.length;
while(true) {
G=(S+E)/2;
if(A[G]>value&&A[G-1]<=value) {
return G;
}else if(A[G]>value) {
E=G;
}else if(A[G]<=value) {
S=G;
}
}
}
int lowerBound(long A[],long value) {
//A[i-1]<value<=A[i] value以上の最小indexを返す
//value未満しかなかったらA.lengthを返す
//value以上の個数は(A.length-i)value未満の個数はiである
int S=0,E=A.length,G=-1;
if(A[0]>=value)return 0;
if(A[A.length-1]<value)return A.length;
while(true) {
G=(S+E)/2;
if(A[G]>=value&&A[G-1]<value) {
return G;
}else if(A[G]>=value) {
E=G;
}else if(A[G]<value) {
S=G;
}
}
}
int upperBound(long A[],long value) {
//A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
//value以下しかなかったらA.lengthを返す
//valueより大きい数の個数は(A.length-i)value以下の個数はiである
int S=0,E=A.length,G=-1;
if(A[0]>value)return 0;
if(A[A.length-1]<=value)return A.length;
while(true) {
G=(S+E)/2;
if(A[G]>value&&A[G-1]<=value) {
return G;
}else if(A[G]>value) {
E=G;
}else if(A[G]<=value) {
S=G;
}
}
}
int lowerBound(ArrayList<Integer> A,int value) {
//A[i-1]<value<=A[i] value以上のindexを返す
//value未満しかなかったらA.lengthを返す
//value以上の個数は(A.length-i)value未満の個数はiである
int S=0,E=A.size(),G=-1;
if(A.get(0)>=value)return 0;
if(A.get(A.size()-1)<value)return A.size();
while(true) {
G=(S+E)/2;
if(A.get(G)>=value&&A.get(G-1)<value) {
return G;
}else if(A.get(G)>=value) {
E=G;
}else if(A.get(G)<value) {
S=G;
}
}
}
int upperBound(ArrayList<Integer> A,int value) {
//A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
//value以下しかなかったらA.lengthを返す
//valueより大きい数の個数は(A.length-i)value以下の個数はiである
int S=0,E=A.size(),G=-1;
if(A.get(0)>value)return 0;
if(A.get(A.size()-1)<=value)return A.size();
while(true) {
G=(S+E)/2;
if(A.get(G)>value&&A.get(G-1)<=value) {
return G;
}else if(A.get(G)>value) {
E=G;
}else if(A.get(G)<=value) {
S=G;
}
}
}
int lowerBound(ArrayList<Long> A,long value) {
//A[i-1]<value<=A[i] value以上のindexを返す
//value未満しかなかったらA.lengthを返す
//value以上の個数は(A.length-i)value未満の個数はiである
int S=0,E=A.size(),G=-1;
if(A.get(0)>=value)return 0;
if(A.get(A.size()-1)<value)return A.size();
while(true) {
G=(S+E)/2;
if(A.get(G)>=value&&A.get(G-1)<value) {
return G;
}else if(A.get(G)>=value) {
E=G;
}else if(A.get(G)<value) {
S=G;
}
}
}
int upperBound(ArrayList<Long> A,long value) {
//A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
//value以下しかなかったらA.lengthを返す
//valueより大きい数の個数は(A.length-i)value以下の個数はiである
int S=0,E=A.size(),G=-1;
if(A.get(0)>value)return 0;
if(A.get(A.size()-1)<=value)return A.size();
while(true) {
G=(S+E)/2;
if(A.get(G)>value&&A.get(G-1)<=value) {
return G;
}else if(A.get(G)>value) {
E=G;
}else if(A.get(G)<=value) {
S=G;
}
}
}
}
private static long modNcR2(int n,int r,int mod) {
if(r<0||n<r)return 0;
long N=kaijou(n, mod);
long Nr=kaijou(n-r, mod);
long R=kaijou(r, mod);
return (((N*modPow(Nr, mod-2, mod))%mod)*modPow(R, mod-2, mod))%mod;
// n!/(n-r)!/r!
}
private static long modPow(long i,long t,long mod) {
if(t==0)return 1%mod;
if(i==0||t<0)return 0;//0未満乗は未定義で
//iのt乗をO(log t)で返す
i%=mod;
long a=i;
long res=1;
//for(int i=0;i<S.length();i++) {if(S.charAt(N-i)=='1') {res=res*a%mod;}
//tをbitのStringで受け取った時用？
while(t!=0) {
if((1&t)==1) {
res=res*a%mod;
}
a=a*a%mod;
t=t>>1;
}
return res;
}
private static long min(long ...a) {
long m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.min(a[i], m);
}
return m;
}
private static int min(int ...a) {
int m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.min(a[i], m);
}
return m;
}
private static int max(int ...a) {
int m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.max(a[i], m);
}
return m;
}
private static long max(long ...a) {
long m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.max(a[i], m);
}
return m;
}
private static double min(double ...a) {
double m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.min(a[i], m);
}
return m;
}
private static double max(double ...a) {
double m=a[0];
for(int i=0;i<a.length;i++) {
m=Math.max(a[i], m);
}
return m;
}
private static int abs(int a) {
return max(a,-a);
}
private static long abs(long a) {
return max(a,-a);
}
private static double abs(double a) {
return max(a,-a);
}
private static String zeroume(String S,int V) {
while(S.length()<V)S='0'+S;
return S;
}
//速度が足りないときは、前計算を1回だけにしたり、longをintに変えたりするといい
//エラストネスの篩風のやつもあり
private static long gcd(long ...nums) {
long res=0;
for (int i = 0; i < nums.length; i++) {
res=gcd(res,nums[i]);
}
return res;
}
private static long lcm(long ...nums) {
long res=1;
for (int i = 0; i < nums.length; i++) {
res=lcm(res,nums[i]);
}
return res;
}
public static long gcd(long num1,long num2) {
if(num2==0) return num1;
else return gcd(num2,num1%num2);
}
public static long lcm(long num1,long num2) {
return num1*num2/gcd(num1,num2);
}
//O(N^0.5)
private static void bubunwa() {
int N=sc.nextInt();
int K=sc.nextInt();
int a[]=sc.nextIntArray(N, false);
boolean dp[] =new boolean[K+1];
Arrays.fill(dp, false);
dp[0]=true;
for(int i=0;i<N;i++) {
for(int x=K-a[i];x>=0;x--) {
if(dp[x])dp[x+a[i]]=true;
}
}
p(dp[K] ? "Yes":"No");
}
static String nextPermutation(String s) {
ArrayList<Character> list=new ArrayList<Character>();
for(int i=0;i<s.length();i++) {
list.add(s.charAt(i));
}
int pivotPos=-1;
char pivot=0;
for(int i=list.size()-2;i>=0;i--) {
if(list.get(i)<list.get(i+1)) {
pivotPos=i;
pivot=list.get(i);
break;
}
}
if(pivotPos==-1&&pivot==0) {
return "Final";
}
int L=pivotPos+1,R=list.size()-1;
int minPos=-1;
char min =Character.MAX_VALUE;
for(int i=R;i>=L;i--) {
if(pivot<list.get(i)) {
if(list.get(i)<min) {
min=list.get(i);
minPos=i;
}
}
}
Collections.swap(list, pivotPos, minPos);
Collections.sort(list.subList(L, R+1));
StringBuilder sb=new StringBuilder();
for(int i=0;i<list.size();i++) {
sb.append(list.get(i));
}
return sb.toString();
}
private static long[][] com;
private static void nCr(int mod) {
int MAX = 3001;
com= new long[MAX][MAX];
for(int i = 0; i < MAX; i++)
com[i][0] = 1;
for(int i = 1; i < MAX; i++) {
for(int j = 1; j <= i; j++) {
com[i][j] = com[i-1][j-1] + com[i-1][j];
com[i][j] %= mod;
}
}
}
//https://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b より
static class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++];
else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
return (int) nextLong();
}
public double nextDouble(){
return Double.parseDouble(next());
}
public int[] nextIntArray(int N) {
int[] array = new int[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
return array;
}
public int[] nextIntArray(int N, boolean oneBased) {
if (oneBased) {
int[] array = new int[N + 1];
for (int i = 1; i <= N; i++) {
array[i] = sc.nextInt();
}
return array;
} else {
int[] array = new int[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
return array;
}
}
public long[] nextLongArray(int N, boolean oneBased) {
if (oneBased) {
long[] array = new long[N + 1];
for (int i = 1; i <= N; i++) {
array[i] = sc.nextLong();
}
return array;
} else {
long[] array = new long[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextLong();
}
return array;
}
}
public long[] nextLongArray(int N) {
long[] array = new long[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextLong();
}
return array;
}
public long[][]nextLongDimensionalArray(int H,int W) {
long[][] array = new long[H][W];
for (int i = 0; i < H; i++) {
array[i] =sc.nextLongArray(W);
}
return array;
}
public int[][]nextIntDimensionalArray(int H,int W) {
int[][] array = new int[H][W];
for (int i = 0; i < H; i++) {
array[i] =sc.nextIntArray(W);
}
return array;
}
public String[] nextArray(int N) {
String[] array = new String[N];
for (int i = 0; i < N; i++) {
array[i] = sc.next();
}
return array;
}
public String[][]nextDimensionalArray(int H,int W) {
String[][] array = new String[H][W];
for (int i = 0; i < H; i++) {
array[i] =sc.nextArray(W);
}
return array;
}
public double[] nextDoubleArray(int N) {
double[] array = new double[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextDouble();
}
return array;
}
}
}