結果
問題 | No.8061 uxs hxixtya pyuyn ixc hyixa kxuyn |
ユーザー | shun_skycrew |
提出日時 | 2020-04-01 22:49:17 |
言語 | Java (openjdk 23) |
結果 |
RE
|
実行時間 | - |
コード長 | 27,709 bytes |
コンパイル時間 | 3,848 ms |
コンパイル使用メモリ | 98,528 KB |
実行使用メモリ | 43,216 KB |
最終ジャッジ日時 | 2024-06-27 12:09:22 |
合計ジャッジ時間 | 6,737 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
38,292 KB |
testcase_01 | AC | 72 ms
38,332 KB |
testcase_02 | AC | 71 ms
38,420 KB |
testcase_03 | AC | 73 ms
38,696 KB |
testcase_04 | AC | 124 ms
41,664 KB |
testcase_05 | AC | 144 ms
43,216 KB |
testcase_06 | AC | 124 ms
41,760 KB |
testcase_07 | AC | 72 ms
38,696 KB |
testcase_08 | AC | 74 ms
38,816 KB |
testcase_09 | AC | 109 ms
41,280 KB |
testcase_10 | AC | 84 ms
39,288 KB |
testcase_11 | AC | 111 ms
40,796 KB |
testcase_12 | AC | 86 ms
39,288 KB |
testcase_13 | RE | - |
testcase_14 | AC | 89 ms
39,456 KB |
testcase_15 | RE | - |
testcase_16 | AC | 84 ms
38,684 KB |
testcase_17 | AC | 105 ms
41,100 KB |
testcase_18 | AC | 86 ms
39,416 KB |
testcase_19 | AC | 71 ms
38,656 KB |
testcase_20 | AC | 72 ms
38,280 KB |
testcase_21 | AC | 71 ms
38,292 KB |
testcase_22 | AC | 71 ms
38,384 KB |
testcase_23 | AC | 74 ms
38,644 KB |
ソースコード
import java.util.*;import java.io.*;import java.math.*;public class Main {static boolean DEBUG;public static void main(String[] args) {DEBUG = args.length > 0 && args[0].equals("-DEBUG");Solver solver = new Solver();solver.solve();solver.exit();}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 boolean isPrintableChar(int c) { return 32 <= 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();}}}static class Solver {FastScanner sc = new FastScanner();public Solver() { }String ns() { return sc.next(); }String[] ns(int n) {String a[] = new String[n];for(int i = 0; i < n; i ++) { a[i] = ns(); }return a;}String[][] ns(int n, int m) {String a[][] = new String[n][m];for(int i = 0; i < n; i ++) { a[i] = ns(m); }return a;}char[] nc(int n) {String str = ns();char a[] = new char[max(n, str.length())];for(int i = 0; i < str.length(); i ++) { a[i] = str.charAt(i); }return a;}char[][] nc(int n, int m) {char a[][] = new char[n][m];for(int i = 0; i < n; i ++) { a[i] = nc(m); }return a;}boolean[] nb(int n, char t) {char c[] = nc(-1);if(n < 0) n = c.length;boolean a[] = new boolean[n];for(int i = 0; i < n; i ++) { a[i] = c[i] == t; }return a;}boolean[][] nb(int n, int m, char t) {boolean a[][] = new boolean[n][m];for(int i = 0; i < n; i ++) { a[i] = nb(m, t); }return a;}int ni() { return (int)sc.nextLong(); }int[] ni(int n) {int a[] = new int[n];for(int i = 0; i < n; i ++) { a[i] = ni(); }return a;}int[][] ni(int n, int m) {int a[][] = new int[n][m];for(int i = 0; i < n; i ++) { a[i] = ni(m); }return a;}long nl() { return sc.nextLong(); }long[] nl(int n) {long a[] = new long[n];for(int i = 0; i < n; i ++) { a[i] = nl(); }return a;}long[][] nl(int n, int m) {long a[][] = new long[n][m];for(int i = 0; i < n; i ++) { a[i] = nl(m); }return a;}double nd() { return Double.parseDouble(sc.next()); }double[] nd(int n) {double a[] = new double[n];for(int i = 0; i < n; i ++) { a[i] = nd(); }return a;}double[][] nd(int n, int m) {double a[][] = new double[n][m];for(int i = 0; i < n; i ++) { a[i] = nd(m); }return a;}PrintWriter out = new PrintWriter(System.out);PrintWriter err = new PrintWriter(System.err);void prt() { out.print(""); }<T> void prt(T a) { out.print(a); }void prtln() { out.println(""); }<T> void prtln(T a) { out.println(a); }void prtln(int... a) {StringBuilder sb = new StringBuilder();for(int element : a){ sb.append(element+" "); }prtln(sb.toString().trim());}void prtln(long... a) {StringBuilder sb = new StringBuilder();for(long element : a){ sb.append(element+" "); }prtln(sb.toString().trim());}void prtln(double... a) {StringBuilder sb = new StringBuilder();for(double element : a){ sb.append(element+" "); }prtln(sb.toString().trim());}void prtln(String... a) {StringBuilder sb = new StringBuilder();for(String element : a){ sb.append(element+" "); }prtln(sb.toString().trim());}void prtln(char... a) {StringBuilder sb = new StringBuilder();for(char element : a){ sb.append(element); }prtln(sb.toString().trim());}void prtln(int[][] a) { for(int[] element : a){ prtln(element); } }void prtln(long[][] a) { for(long[] element : a){ prtln(element); } }void prtln(double[][] a) { for(double[] element : a){ prtln(element); } }void prtln(String[][] a) { for(String[] element : a){ prtln(element); } }void prtln(char[][] a) { for(char[] element : a){ prtln(element); } }String errconvert(int a) { return isINF(a) ? "_" : String.valueOf(a); }String errconvert(long a) { return isINF(a) ? "_" : String.valueOf(a); }void errprt(int a) { if(DEBUG) { err.print(errconvert(a)); } }void errprt(long a) { if(DEBUG) { err.print(errconvert(a)); } }void errprt() { if(DEBUG) { err.print(""); } }<T> void errprt(T a) { if(DEBUG) { err.print(a); } }void errprt(boolean a) { if(DEBUG) { errprt(a ? "#" : "."); } }void errprtln() { if(DEBUG) { err.println(""); } }void errprtln(int a) { if(DEBUG) { err.println(errconvert(a)); } }void errprtln(long a) { if(DEBUG) { err.println(errconvert(a)); } }<T> void errprtln(T a) { if(DEBUG) { err.println(a); } }void errprtln(boolean a) { if(DEBUG) { errprtln(a ? "#" : "."); } }void errprtln(int... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(int element : a){ sb.append(errconvert(element)+" "); }errprtln(sb.toString().trim());}}void errprtln(long... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(long element : a){ sb.append(errconvert(element)+" "); }errprtln(sb.toString().trim());}}void errprtln(double... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(double element : a){ sb.append(element+" "); }errprtln(sb.toString().trim());}}void errprtln(String... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(String element : a){ sb.append(element+" "); }errprtln(sb.toString().trim());}}void errprtln(char... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(char element : a){ sb.append(element); }errprtln(sb.toString().trim());}}void errprtln(boolean... a) {if(DEBUG) {StringBuilder sb = new StringBuilder();for(boolean element : a){ sb.append((element ? "#" : ".")+" "); }errprtln(sb.toString().trim());}}void errprtln(int[][] a) { if(DEBUG) { for(int[] element : a){ errprtln(element); } } }void errprtln(long[][] a) { if(DEBUG) { for(long[] element : a){ errprtln(element); } } }void errprtln(double[][] a) { if(DEBUG) { for(double[] element : a){ errprtln(element); } } }void errprtln(String[][] a) { if(DEBUG) { for(String[] element : a){ errprtln(element); } } }void errprtln(char[][] a) { if(DEBUG) { for(char[] element : a){ errprtln(element); } } }void errprtln(boolean[][] a) { if(DEBUG) { for(boolean[] element : a){ errprtln(element); } } }void reply(boolean b) { prtln(b ? "Yes" : "No"); }void REPLY(boolean b) { prtln(b ? "YES" : "NO"); }void flush() { out.flush(); if(DEBUG) { err.flush(); } }void exit() { flush(); System.exit(0); }void assertion(boolean b) { if(!b) throw new AssertionError(); }int min(int a, int b) { return Math.min(a, b); }long min(long a, long b) { return Math.min(a, b); }double min(double a, double b) { return Math.min(a, b); }int min(int... x) {int min = x[0];for(int val : x) { min = min(min, val); }return min;}long min(long... x) {long min = x[0];for(long val : x) { min = min(min, val); }return min;}double min(double... x) {double min = x[0];for(double val : x) { min = min(min, val); }return min;}int max(int a, int b) { return Math.max(a, b); }long max(long a, long b) { return Math.max(a, b); }double max(double a, double b) { return Math.max(a, b); }int max(int... x) {int max = x[0];for(int val : x) { max = max(max, val); }return max;}long max(long... x) {long max = x[0];for(long val : x) { max = max(max, val); }return max;}double max(double... x) {double max = x[0];for(double val : x) { max = max(max, val); }return max;}long sum(int... a) {long sum = 0;for(int element : a) { sum += element; }return sum;}long sum(long... a) {long sum = 0;for(long element : a) { sum += element; }return sum;}double sum(double... a) {double sum = 0;for(double element : a) { sum += element; }return sum;}long[] sums(int[] a) {long sum[] = new long[a.length + 1];sum[0] = 0;for(int i = 0; i < a.length; i ++) { sum[i + 1] = sum[i] + a[i]; }return sum;}long[] sums(long[] a) {long sum[] = new long[a.length + 1];sum[0] = 0;for(int i = 0; i < a.length; i ++) { sum[i + 1] = sum[i] + a[i]; }return sum;}double[] sums(double[] a) {double sum[] = new double[a.length + 1];sum[0] = 0;for(int i = 0; i < a.length; i ++) { sum[i + 1] = sum[i] + a[i]; }return sum;}int abs(int x) { return x >= 0 ? x : - x; }long abs(long x) { return x >= 0 ? x : - x; }double abs(double x) { return x >= 0 ? x : - x; }int signum(int x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }int signum(long x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }int signum(double x) { return x > 0 ? 1 : x < 0 ? -1 : 0; }long round(double x) { return Math.round(x); }long floor(double x) { return (long)Math.floor(x); }int divfloor(int a, int b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }long divfloor(long a, long b) { return signum(a) == signum(b) ? a / b : - divceil(abs(a), abs(b)); }long ceil(double x) { return (long)Math.ceil(x); }int divceil(int a, int b) { return a >= 0 && b > 0 ? (a + b - 1) / b: a < 0 && b < 0 ? divceil(abs(a), abs(b)): - divfloor(abs(a), abs(b)); }long divceil(long a, long b) { return a >= 0 && b > 0 ? (a + b - 1) / b: a < 0 && b < 0 ? divceil(abs(a), abs(b)): - divfloor(abs(a), abs(b)); }double sqrt(int x) { return Math.sqrt((double)x); }double sqrt(long x) { return Math.sqrt((double)x); }double sqrt(double x) { return Math.sqrt(x); }double pow(double x, double y) { return Math.pow(x, y); }long pow(long x, long y) {if(y == 0) { return 1;}else {long tmp = pow(x, y / 2);return tmp * tmp * (y % 2 == 0 ? 1 : x);}}int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }long lcm(long a, long b) { return a / gcd(a, b) * b; }int gcd(int[] array) {int gcd = 0;for(int i = 0; i < array.length; i ++) { gcd = gcd(gcd, array[i]); }return gcd;}long gcd(long[] array) {long gcd = 0;for(int i = 0; i < array.length; i ++) { gcd = gcd(gcd, array[i]); }return gcd;}int upperToInt(char a) { return a - 'A'; }int lowerToInt(char a) { return a - 'a'; }int numToInt(char a) { return a - '0'; }int charToInt(char a) { return a >= 'a' ? lowerToInt(a) : a >= 'A' ? upperToInt(a) : numToInt(a); }char intToUpper(int a) { return (char)(a + 'A'); }char intToLower(int a) { return (char)(a + 'a'); }char intToNum(int a) { return (char)(a + '0'); }int[] charToInt(char[] a) {int array[] = new int[a.length];for(int i = 0; i < a.length; i ++) { array[i] = charToInt(a[i]); }return array;}long[] div(long a) {List<Long> divList = new ArrayList<Long>();for(long i = 1; i * i <= a; i ++) {if(a % i == 0) {divList.add(i);if(i * i != a) { divList.add(a / i); };}}long div[] = new long[divList.size()];for(int i = 0; i < divList.size(); i ++) { div[i] = divList.get(i); }return div;}long[][] factor(long a) {List<Long> factorList = new ArrayList<Long>();List<Long> degreeList = new ArrayList<Long>();for(long i = 2; i * i <= a; i ++) {if(a % i == 0) {long count = 0;while(a % i == 0) {a /= i;count ++;}factorList.add(i);degreeList.add(count);}}if(a > 1) {factorList.add(a);degreeList.add(1L);}long factor[][] = new long[factorList.size()][2];for(int i = 0; i < factorList.size(); i ++) {factor[i][0] = factorList.get(i);factor[i][1] = degreeList.get(i);}Arrays.sort(factor, (sort1, sort2) -> Long.compare(sort1[0], sort2[0]));return factor;}boolean isPrime(long x) {boolean ok = x > 1;for(long i = 2; i * i <= x; i ++) {ok &= x % i != 0;if(!ok) return ok;}return ok;}boolean[] prime(int num) {boolean prime[] = new boolean[num];fill(prime, true);prime[0] = false;prime[1] = false;for(int i = 2; i < num; i ++) {if(prime[i]) {for(int j = 2; i * j < num; j ++) {prime[i * j] = false;}}}return prime;}long[][] countElements(long[] a, boolean sort) {int len = a.length;long array[] = new long[len];for(int i = 0; i < len; i ++) {array[i] = a[i];}if(sort) { Arrays.sort(array); }List<Long> elem = new ArrayList<Long>();List<Long> cnt = new ArrayList<Long>();long tmp = 1;for(int i = 1; i <= len; i ++) {if(i == len || array[i] != array[i - 1]) {elem.add(array[i - 1]);cnt.add(tmp);tmp = 1;}else {tmp ++;}}long counts[][] = new long[elem.size()][2];for(int i = 0; i < elem.size(); i ++) {counts[i][0] = elem.get(i);counts[i][1] = cnt.get(i);}return counts;}long[][] countElements(String str, boolean sort) {int len = str.length();char array[] = str.toCharArray();if(sort) { Arrays.sort(array); }List<Long> elem = new ArrayList<Long>();List<Long> cnt = new ArrayList<Long>();long tmp = 1;for(int i = 1; i <= len; i ++) {if(i == len || array[i] != array[i - 1]) {elem.add((long)array[i - 1]);cnt.add(tmp);tmp = 1;}else {tmp ++;}}long counts[][] = new long[elem.size()][2];for(int i = 0; i < elem.size(); i ++) {counts[i][0] = elem.get(i);counts[i][1] = cnt.get(i);}return counts;}int[] baseConvert(long x, int n) {long tmp = x;int len = 0;while(tmp > 0) { tmp /= n; len ++; }int digit[] = new int[len];int i = 0;tmp = x;while(tmp > 0) { digit[i ++] = (int)(tmp % n); tmp /= n; }return digit;}int[] baseConvert(int x, int n) {int tmp = x;int len = 0;while(tmp > 0) { tmp /= n; len ++; }int digit[] = new int[len];int i = 0;tmp = x;while(tmp > 0) { digit[i ++] = (int)(tmp % n); tmp /= n; }return digit;}int numDigits(long a) { return Long.toString(a).length(); }long bitFlag(int a) { return 1L << (long)a; }boolean isFlagged(long x, int a) { return (x & bitFlag(a)) != 0; }long countString(String str, String a) { return (str.length() - str.replace(a, "").length()) / a.length(); }long countStringAll(String str, String a) { return str.length() - str.replaceAll(a, "").length(); }int lowerBound(long[] array, long key) {return BS(array, key, true, true, true);}int lowerBound(long[] array, long key, int ng, int ok) {return BS(array, key, true, true, true, ng, ok);}int upperBound(long[] array, long key) {return BS(array, key, true, true, false);}int upperBound(long[] array, long key, int ng, int ok) {return BS(array, key, true, true, false, ng, ok);}int cntBS(long[] array, long key, boolean ascending, boolean greater, boolean equals) {return BS(array, key, ascending, greater, equals, true);}int cntBS(long[] array, long key, boolean ascending, boolean greater, boolean equals, int ng, int ok) {return BS(array, key, ascending, greater, equals, true, ng, ok);}int BS(long[] array, long key, boolean ascending, boolean greater, boolean equals) {return BS(array, key, ascending, greater, equals, false);}int BS(long[] array, long key, boolean ascending, boolean greater, boolean equals, int ng, int ok) {return BS(array, key, ascending, greater, equals, false, ng, ok);}int BS(long[] array, long key, boolean ascending, boolean greater, boolean equals, boolean count) {int ng = ascending ^ greater ? array.length : -1;int ok = ascending ^ greater ? -1 : array.length;return BS(array, key, ascending, greater, equals, count, ng, ok);}int BS(long[] array, long key, boolean ascending, boolean greater, boolean equals, boolean count, int ng, int ok) {int index = binarySearch(array, key, greater, equals, ng, ok);return count ? (int)abs(ok - index) : index;}int binarySearch(long[] array, long key, boolean greater, boolean equals, int ng, int ok) {while (abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if(isOKforBinarySearch(array, mid, key, greater, equals)) {ok = mid;}else {ng = mid;}}return ok;}boolean isOKforBinarySearch(long[] array, int index, long key, boolean greater, boolean equals) {return (array[index] > key && greater)|| (array[index] < key && !greater)|| (array[index] == key && equals);}void reverse(String[] array) {String reversed[] = new String[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void reverse(int[] array) {int reversed[] = new int[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void reverse(long[] array) {long reversed[] = new long[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void reverse(double[] array) {double reversed[] = new double[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void reverse(boolean[] array) {boolean reversed[] = new boolean[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void reverse(Object[] array) {Object reversed[] = new Object[array.length];for(int i = 0; i < array.length; i ++) { reversed[array.length - i - 1] = array[i]; }for(int i = 0; i < array.length; i ++) { array[i] = reversed[i]; }}void fill(int[] array, int x) { Arrays.fill(array, x); }void fill(long[] array, long x) { Arrays.fill(array, x); }void fill(double[] array, double x) { Arrays.fill(array, x); }void fill(boolean[] array, boolean x) { Arrays.fill(array, x); }void fill(int[][] array, int x) { for(int[] a : array) { fill(a, x); } }void fill(long[][] array, long x) { for(long[] a : array) { fill(a, x); } }void fill(double[][] array, double x) { for(double[] a : array) { fill(a, x); } }void fill(boolean[][] array, boolean x) { for(boolean[] a : array) { fill(a, x); } }void fill(int[][][] array, int x) { for(int[][] a : array) { fill(a, x); } }void fill(long[][][] array, long x) { for(long[][] a : array) { fill(a, x); } }void fill(double[][][] array, double x) { for(double[][] a : array) { fill(a, x); } }void fill(boolean[][][] array, boolean x) { for(boolean[][] a : array) { fill(a, x); } }void shuffleArray(int[] array){int n = array.length;Random rnd = new Random();for(int i = 0; i < n; i ++){int tmp = array[i];int randomPos = i + rnd.nextInt(n - i);array[i] = array[randomPos];array[randomPos] = tmp;}}void shuffleArray(long[] array){int n = array.length;Random rnd = new Random();for(int i = 0; i < n; i ++){long tmp = array[i];int randomPos = i + rnd.nextInt(n - i);array[i] = array[randomPos];array[randomPos] = tmp;}}void shuffleArray(double[] array){int n = array.length;Random rnd = new Random();for(int i = 0; i < n; i ++){double tmp = array[i];int randomPos = i + rnd.nextInt(n - i);array[i] = array[randomPos];array[randomPos] = tmp;}}void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}void swap(long[] array, int i, int j) {long tmp = array[i];array[i] = array[j];array[j] = tmp;}void swap(double[] array, int i, int j) {double tmp = array[i];array[i] = array[j];array[j] = tmp;}long INF = (long)1e18 + 7;boolean isINF(long a) { return abs(a) > INF / 1000; }boolean isPlusINF(long a) { return a > 0 && isINF(a); }boolean isMinusINF(long a) { return isPlusINF(- a); }int I_INF = (int)1e9 + 7;boolean isINF(int a) { return abs(a) > I_INF / 1000; }boolean isPlusINF(int a) { return a > 0 && isINF(a); }boolean isMinusINF(int a) { return isPlusINF(- a); }// modslong MOD = (long)1e9 + 7; // 998244353;public long mod(long i) { i %= MOD; return i + (i < 0 ? MOD : 0); }long pow_m(long x, long y) {if(y == 0) { return 1;}else {long tmp = pow_m(x, y / 2);return mod(mod(tmp * tmp) * (y % 2 == 0 ? 1 : x));}}long[] pows_m(long x, int max) {long pow[] = new long[max + 1];pow[0] = 1;for(int i = 0; i < max; i ++) {pow[i + 1] = mod(pow[i] * x);}return pow;}int MAX_INV_SIZE = 100_100;HashMap<Long, Long> invMap = new HashMap<>();long inv(long x) {x = mod(x);if(invMap.containsKey(x)) { return invMap.get(x); }if(invMap.size() >= MAX_INV_SIZE) { return calInv(x); }invMap.put(x, calInv(x));return invMap.get(x);}long calInv(long x) { return pow_m(x, MOD - 2); }int MAX_FACT = 5_000_100;long fact[];long invFact[];boolean isFactPrepared = false;HashMap<Integer, long[]> factMap;void prepareFact() {fact = new long[MAX_FACT];Arrays.fill(fact, 0);invFact = new long[MAX_FACT];Arrays.fill(invFact, 0);fact[0] = 1;int maxIndex = min(MAX_FACT, (int)MOD);for(int i = 1; i < maxIndex; i ++) { fact[i] = mod(fact[i - 1] * i); }invFact[maxIndex - 1] = inv(fact[maxIndex - 1]);for(int i = maxIndex - 1; i > 0; i --) { invFact[i - 1] = mod(invFact[i] * i); }factMap = new HashMap<>();isFactPrepared = true;}long P(int n, int r) {if(!isFactPrepared) { prepareFact(); }if(n < 0 || r < 0 || n < r) { return 0; }if(n >= MAX_FACT) {if(!factMap.containsKey(n)) {long largeFact[] = new long[MAX_FACT];factMap.put(n, largeFact);fill(largeFact, -INF);largeFact[0] = 1;}long largeFact[] = factMap.get(n);int i = r;while(isINF(largeFact[i])) { i --; }for(; i < r; i ++) { largeFact[i + 1] = mod(largeFact[i] * (n - i)); }return largeFact[r];}return mod(fact[n] * invFact[n - r]);}long C(int n, int r) {if(!isFactPrepared) { prepareFact(); }if(n < 0 || r < 0 || n < r) { return 0; }return mod(P(n, r) * invFact[r]);}long H(int n, int r) { return C((n - 1) + r, r); }// gridclass Grids {int h;int w;Grid[][] gs;Grids(int h, int w) {this.h = h;this.w = w;gs = new Grid[h][w];for(int i = 0; i < h; i ++) {for(int j = 0; j < w; j ++) {gs[i][j] = new Grid(i, j, h, w);}}}void init(boolean[][] b) {for(int i = 0; i < h; i ++) {for(int j = 0; j < w; j ++) {gs[i][j].b = b[i][j];}}}void init(long[][] val) {for(int i = 0; i < h; i ++) {for(int j = 0; j < w; j ++) {gs[i][j].val = val[i][j];}}}int dx[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};int dy[] = {0, 0, 0, -1, 1, -1, -1, 1, 1};Grid next(Grid g, int i) {return isValid(g.x + dx[i], g.y + dy[i], g.h, g.w)? gs[g.x + dx[i]][g.y + dy[i]]: null;}}class Grid implements Comparable<Grid> {int x;int y;int h;int w;int i;boolean b;long val;Grid() { }Grid(int x, int y, int h, int w) { init(x, y, h, w, false, 0); }Grid(int x, int y, int h, int w, boolean b) { init(x, y, h, w, b, 0); }Grid(int x, int y, int h, int w, long val) { init(x, y, h, w, false, val); }Grid(int x, int y, int h, int w, boolean b, long val) { init(x, y, h, w, b, val); }void init(int x, int y, int h, int w, boolean b, long val) {this.x = x;this.y = y;this.h = h;this.w = w;this.b = b;this.val = val;i = x * w + y;}@Overridepublic int compareTo(Grid g) {return Long.compare(this.val, g.val);}}boolean isValid(int x, int y, int h, int w) {return x >= 0 && x < h && y >= 0 && y < w;}boolean isValid(Grid g) {return isValid(g.x, g.y, g.h, g.w);}// graphclass Graph {int numNode;int numEdge;boolean directed;Edge edges[];Node nodes[];Node reversedNodes[];Graph(int numNode, int numEdge, boolean directed) {this.numNode = numNode;this.numEdge = numEdge;this.directed = directed;nodes = new Node[numNode];reversedNodes = new Node[numNode];for(int i = 0; i < numNode; i ++) {nodes[i] = new Node(i);reversedNodes[i] = new Node(i);}}void init(Edge[] edges) {this.edges = edges;for(Edge edge : edges) {nodes[edge.source].add(edge.target, edge.cost);if(directed) {reversedNodes[edge.target].add(edge.source, edge.cost);}else {nodes[edge.target].add(edge.source, edge.cost);}}}void clearNodes() {for(Node n : nodes) { n.clear(); }for(Node n : reversedNodes) { n.clear(); }}}class Node extends ArrayList<Edge> {int id;Node(int id) {this.id = id;}void add(int target, long cost) {add(new Edge(id, target, cost));}}class Edge implements Comparable<Edge> {int source;int target;long cost;Edge(int source, int target, long cost) {this.source = source;this.target = target;this.cost = cost;}@Overridepublic int compareTo(Edge e) {return Long.compare(this.cost, e.cost);}}public void solve() {char c[] = nc(-1);int num = c.length;boolean ans = false;for(int i = 0; i < num; i ++) {for(int j = i + 2; j < num; j ++) {boolean ok = true;boolean b[][] = new boolean[2][26];for(int k = 0; k < i; k ++) {if(c[k] != ' ') {b[1][charToInt(c[k])] = true;}}for(int k = i; k < j; k ++) {if(c[k] == ' ') {ok &= (k - i) % 2 == 1;}else {b[(k - i) % 2][charToInt(c[k])] = true;}}for(int k = j; k < num; k ++) {if(c[k] != ' ') {b[1][charToInt(c[k])] = true;}}for(int k = 0; k < 26; k ++) {ok &= !b[0][k] || !b[1][k];}ans |= ok;}}prtln(ans ? "Yes" : "NO");}}}