#989759 (Java21) No.977 アリス仕掛けの摩天楼

提出ソース
結果

問題	No.977 アリス仕掛けの摩天楼
ユーザー	VvyLw
提出日時	2024-06-20 19:11:18
言語	Java21 (openjdk 21)
結果	AC
実行時間	174 ms / 2,000 ms
コード長	58,942 bytes
コンパイル時間	10,598 ms
コンパイル使用メモリ	104,232 KB
実行使用メモリ	53,212 KB
最終ジャッジ日時	2024-06-20 19:11:33
合計ジャッジ時間	14,947 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	96 ms 51,776 KB
testcase_01	AC	95 ms 51,548 KB
testcase_02	AC	95 ms 51,564 KB
testcase_03	AC	114 ms 51,744 KB
testcase_04	AC	98 ms 51,808 KB
testcase_05	AC	99 ms 51,528 KB
testcase_06	AC	97 ms 51,432 KB
testcase_07	AC	102 ms 51,776 KB
testcase_08	AC	104 ms 51,556 KB
testcase_09	AC	97 ms 51,704 KB
testcase_10	AC	100 ms 51,648 KB
testcase_11	AC	106 ms 51,636 KB
testcase_12	AC	98 ms 51,760 KB
testcase_13	AC	124 ms 52,592 KB
testcase_14	AC	120 ms 52,472 KB
testcase_15	AC	123 ms 52,564 KB
testcase_16	AC	121 ms 52,064 KB
testcase_17	AC	124 ms 52,528 KB
testcase_18	AC	149 ms 53,168 KB
testcase_19	AC	148 ms 53,212 KB
testcase_20	AC	167 ms 53,208 KB
testcase_21	AC	170 ms 52,888 KB
testcase_22	AC	174 ms 53,184 KB
testcase_23	AC	173 ms 52,924 KB
testcase_24	AC	164 ms 53,068 KB
testcase_25	AC	164 ms 53,172 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
package yukicoder;

import static java.lang.Math.*;

import java.io.Closeable;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Formatter;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
import java.util.function.DoublePredicate;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongPredicate;
import java.util.function.LongUnaryOperator;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Main {
	public static void main(final String[] args) {
		final long begin = System.currentTimeMillis(), end;
		IntStream.range(0, VvyLw.MULTI ? VvyLw.io.ni() : 1).mapToObj(VvyLw::solve).filter(Objects::nonNull).forEach(VvyLw.io::out);
		end = System.currentTimeMillis();
		VvyLw.io.dump(end - begin + "ms");
		VvyLw.io.close();
	}
}

final class VvyLw extends Utility {
	static final IO io = new IO(System.in, System.out, System.err, false);
	static final Random rd = new Random();
	static final boolean MULTI = false;
	static final int INF = 1 << 30;
	static final long LINF = (1L << 61) - 1;
	static final double EPS = 1e-18;
	static final int MOD = 998244353;
	static final int M0D = (int) 1e9 + 7;
	static final int[] dx = {0, -1, 1, 0, 0, -1, -1, 1, 1};
	static final int[] dy = {0, 0, 0, -1, 1, -1, 1, -1, 1};
	static final Object solve(final int Huitloxopetl) {
		final int n = io.ni();
		final var uf = new UnionFind(n);
		final var cnt = new int[n];
		boolean gg = true;
		for(int i = 0; i < n - 1; ++i) {
			final int u = io.ni(), v = io.ni();
			gg &= uf.unite(u, v);
			cnt[u]++;
			cnt[v]++;
		}
		if(gg) {
			return "Bob";
		}
		if(Arrays.stream(cnt).anyMatch(e -> e >= 1 && e != 2)) {
			return "Alice";
		}
		return uf.size(0) == n - 1 || uf.size(1) == n - 1 ? "Bob" : "Alice";
	}
}
class Utility {
	protected static final String yes(final boolean ok){ return ok ? "Yes" : "No"; }
	protected static final String no(final boolean ok){ return yes(!ok); }
	protected static final long sqr(final long x){ return x * x; }
	protected static final long cub(final long x){ return x * x * x; }
	protected static final int mod(long n, final int m) {
		n %= m;
		return (int) (n < 0 ? n + m : n);
	}
	protected static final long mod(long n, final long m) {
		n %= m;
		return n < 0 ? n + m : n;
	}
	protected static final double log(final double x, final long base){ return Math.log(x) / Math.log(base); }
	protected static final long intCeil(final long a, final long b){ return a == 0 ? 0 : (a - 1) / b + 1; }
	protected static final double intRound(final double a, final long b, final int c) {
		final long d = powi(10, c);
		return rint((a * d) / b) / d;
	}
	protected static final long powi(long a, int b) {
		long res = 1;
		while(b > 0) {
			if(b % 2 == 1) {
				res *= a;
			}
			a *= a;
			b >>= 1;
		}
		return res;
	}
	protected static final long modPow(long a, long b, final long m) {
		long res = 1;
		while(b > 0) {
			if(b % 2 == 1) {
				res *= a;
				res = mod(res, m);
			}
			a *= a;
			a = mod(a, m);
			b >>= 1;
		}
		return res;
	}
	protected static final long inv(long a, final long m) {
		long b = m, u = 1, v = 0;
		while(b > 0) {
			final long t = a / b;
			a -= t * b;
			a ^= b;
			b ^= a;
			a ^= b;
			u -= t * v;
			u ^= v;
			v ^= u;
			u ^= v;
		}
		return mod(u, m);
	}
	protected static final long lcm(final long a, final long b){ return a / gcd(a, b) * b; }
	protected static final long lcm(final int... a){ return Arrays.stream(a).asLongStream().reduce(1, (x, y) -> lcm(x, y)); }
	protected static final long lcm(final long... a){ return Arrays.stream(a).reduce(1, (x, y) -> lcm(x, y)); }
	protected static final long gcd(final long a, final long b){ return b > 0 ? gcd(b, a % b) : a; }
	protected static final int gcd(final int... a){ return Arrays.stream(a).reduce(0, (x, y) -> (int) gcd(x, y)); }
	protected static final long gcd(final long... a){ return Arrays.stream(a).reduce(0, (x, y) -> gcd(x, y)); }
	protected static final int min(final int... a){ return Arrays.stream(a).min().getAsInt(); }
	protected static final long min(final long... a){ return Arrays.stream(a).min().getAsLong(); }
	protected static final double min(final double... a){ return Arrays.stream(a).min().getAsDouble(); }
	protected static final int max(final int... a){ return Arrays.stream(a).max().getAsInt(); }
	protected static final long max(final long... a){ return Arrays.stream(a).max().getAsLong(); }
	protected static final double max(final double... a){ return Arrays.stream(a).max().getAsDouble(); }
	protected static final long sum(final int... a){ return Arrays.stream(a).asLongStream().sum(); }
	protected static final long sum(final long... a){ return Arrays.stream(a).sum(); }
	protected static final double sum(final double... a){ return Arrays.stream(a).sum(); }
	protected static final long prod(final int... a){ return Arrays.stream(a).asLongStream().reduce(1, (x, y) -> x * y); }
	protected static final long prod(final long... a){ return Arrays.stream(a).reduce(1, (x, y) -> x * y); }
	protected static final double prod(final double... a){ return Arrays.stream(a).reduce(1, (x, y) -> x * y); }
	protected static final double ave(final int... a){ return Arrays.stream(a).average().getAsDouble(); }
	protected static final double ave(final long... a){ return Arrays.stream(a).average().getAsDouble(); }
	protected static final double ave(final double... a){ return Arrays.stream(a).average().getAsDouble(); }
	protected static final double median(final int[] a) {
		assert isSorted(a);
		final int m = a.length / 2;
		return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2.0;
	}
	protected static final double median(final long[] a) {
		assert isSorted(a);
		final int m = a.length / 2;
		return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2.0;
	}
	protected static final double median(final double[] a) {
		assert isSorted(a);
		final int m = a.length / 2;
		return a.length % 2 != 0 ? a[m] : (a[m - 1] + a[m]) / 2;
	}
	protected static final long[] div(final long n) {
		final ArrayList<Long> d = new ArrayList<>();
		for(long i = 1; i * i <= n; ++i) {
			if(n % i == 0) {
				d.add(i);
				if(i * i != n) {
					d.add(n / i);
				}
			}
		}
		return d.stream().mapToLong(i -> i).sorted().toArray();
	}
	protected static final IntPair[] primeFactor(long n) {
		final ArrayList<IntPair> pf = new ArrayList<>();
		for(long i = 2; i * i <= n; ++i) {
			if(n % i != 0) {
				continue;
			}
			int cnt = 0;
			while(n % i == 0) {
				cnt++;
				n /= i;
			}
			pf.add(IntPair.of(i, cnt));
		}
		if(n != 1) {
			pf.add(IntPair.of(n, 1));
		}
		return pf.toArray(IntPair[]::new);
	}
	protected static final long eulerPhi(long n) {
		long res = n;
		for(long i = 2; i * i <= n; ++i) {
			if(n % i == 0) {
				res -= res / i;
				while(n % i == 0) {
					n /= i;
				}
			}
		}
		if(n > 1) {
			res -= res / n;
		}
		return res;
	}
	protected static final long sigma(final long n){ return n * (n + 1) / 2; }
	protected static final long sigma(final long a, final long b) {
		assert a <= b;
		return sigma(b) - sigma(a - 1);
	} 
	protected static final long fact(int n) {
		long res = 1;
		while(n > 0) {
			res *= n--;
		}
		return res;
	}
	protected static final long fact(int n, final long mod) {
		long res = 1;
		while(n > 0) {
			res *= n--;
			res %= mod;
		}
		return res;
	}
	protected static final long perm(final int n, final int r) {
		int m = n;
		long res = 1;
		while(m > n - r) {
			res *= m--;
		}
		return res;
	}
	protected static final long perm(final int n, final int r, final long mod) {
		int m = n;
		long res = 1;
		while(m > n - r) {
			res *= m--;
			res %= mod; 
		}
		return res;
	}
	protected static final long binom(final int n, final int r) {
		if(r < 0 || n < r) {
			return 0;
		}
		int tmp = n;
		long res = 1;
		for(int i = 1; i <= min(n - r, r); ++i) {
			res *= tmp--;
			res /= i;
		}
		return res;
	}
	protected static final long binom(final int n, final int r, final long mod) {
		if(r < 0 || n < r) {
			return 0;
		}
		int tmp = n;
		long res = 1;
		for(int i = 1; i <= min(n - r, r); ++i) {
			res *= tmp--;
			res %= mod;
			res /= i;
			res %= mod;
		}
		return res;
	}
	protected static final boolean isInt(final double n){ return n == (long) floor(n); }
	protected static final boolean isSqr(final long n){ return isInt(sqrt(n)); }
	protected static final boolean isPrime(final long n) {
		if(n == 1) {
			return false;
		}
		for(long i = 2; i * i <= n; ++i) {
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	}
	protected static final boolean scope(final int l, final int x, final int r){ return l <= x && x <= r; }
	protected static final boolean scope(final long l, final long x, final long r){ return l <= x && x <= r; }
	protected static final boolean scope(final double l, final double x, final double r){ return l <= x && x <= r; }
	protected static final boolean isBit(final long i, final long j){ return (i >> j & 1) == 1; }
	protected static final boolean nextPerm(final int[] a) {
		try {
			final int[] res = nextPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			Arrays.sort(a);
			return false;
		}
	}
	protected static final boolean nextPerm(final long[] a) {
		try {
			final long[] res = nextPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			Arrays.sort(a);
			return false;
		}
	}
	protected static final boolean nextPerm(final double[] a) {
		try {
			final double[] res = nextPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			Arrays.sort(a);
			return false;
		}
	}
	protected static final boolean nextPerm(final char[] a) {
		try {
			final char[] res = nextPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			Arrays.sort(a);
			return false;
		}
	}
	protected static final boolean prevPerm(final int[] a) {
		try {
			final int[] res = prevPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			final int[] res = reverse(sorted(a));
			System.arraycopy(res, 0, a, 0, a.length);
			return false;
		}
	}
	protected static final boolean prevPerm(final long[] a) {
		try {
			final long[] res = prevPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			final long[] res = reverse(sorted(a));
			System.arraycopy(res, 0, a, 0, a.length);
			return false;
		}
	}
	protected static final boolean prevPerm(final double[] a) {
		try {
			final double[] res = prevPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			final double[] res = reverse(sorted(a));
			System.arraycopy(res, 0, a, 0, a.length);
			return false;
		}
	}
	protected static final boolean prevPerm(final char[] a) {
		try {
			final char[] res = prevPermutation(a);
			System.arraycopy(res, 0, a, 0, a.length);
			return true;
		} catch(final NullPointerException e) {
			final char[] res = reverse(sorted(a));
			System.arraycopy(res, 0, a, 0, a.length);
			return false;
		}
	}
	private static final int[] nextPermutation(final int[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] < a[i]) {
				final int j = find(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				return a;
			}
		}
		return null;
	}
	private static final long[] nextPermutation(final long[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] < a[i]) {
				final int j = find(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				return a;
			}
		}
		return null;
	}
	private static final double[] nextPermutation(final double[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] < a[i]) {
				final int j = find(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				return a;
			}
		}
		return null;
	}
	private static final char[] nextPermutation(final char[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] < a[i]) {
				final int j = find(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				return a;
			}
		}
		return null;
	}
	private static final int[] prevPermutation(final int[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] > a[i]) {
				final int j = findRev(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				reverse(a, i, a.length - 1);
				return a;
			}
		}
		return null;
	}
	private static final long[] prevPermutation(final long[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] > a[i]) {
				final int j = findRev(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				reverse(a, i, a.length - 1);
				return a;
			}
		}
		return null;
	}
	private static final double[] prevPermutation(final double[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] > a[i]) {
				final int j = findRev(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				reverse(a, i, a.length - 1);
				return a;
			}
		}
		return null;
	}
	private static final char[] prevPermutation(final char[] a) {
		for(int i = a.length; --i > 0;) {
			if(a[i - 1] > a[i]) {
				final int j = findRev(a[i - 1], a, i, a.length - 1);
				swap(a, i - 1, j);
				Arrays.sort(a, i, a.length);
				reverse(a, i, a.length - 1);
				return a;
			}
		}
		return null;
	}
	private static final int find(final int dest, final int[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}
	private static final int find(final long dest, final long[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}
	private static final int find(final double dest, final double[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}
	private static final int find(final char dest, final char[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}
	private static final int findRev(final int dest, final int[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
	}
	private static final int findRev(final long dest, final long[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
	}
	private static final int findRev(final double dest, final double[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
	}
	private static final int findRev(final char dest, final char[] a, final int s, final int e) {
		if(s == e) {
			return s;
		}
		final int m = (s + e + 1) / 2;
		return a[m] > dest ? findRev(dest, a, s, m - 1) : findRev(dest, a, m, e);
	}
	private static void reverse(final int[] arr, int start, int end) {
		while(start < end) {
			swap(arr, start, end);
			start++;
			end--;
		}
	}
	private static void reverse(final long[] arr, int start, int end) {
		while(start < end) {
			swap(arr, start, end);
			start++;
			end--;
		}
	}
	private static void reverse(final double[] arr, int start, int end) {
		while(start < end) {
			swap(arr, start, end);
			start++;
			end--;
		}
	}
	private static void reverse(final char[] arr, int start, int end) {
		while(start < end) {
			swap(arr, start, end);
			start++;
			end--;
		}
	}
	protected static final int find(final int[] a, final int x) {
		for(int i = 0; i < a.length; ++i) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int find(final long[] a, final long x) {
		for(int i = 0; i < a.length; ++i) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int find(final double[] a, final double x) {
		for(int i = 0; i < a.length; ++i) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int find(final char[] s, final char c) {
		for(int i = 0; i < s.length; ++i) {
			if(s[i] == c) {
				return i;
			}
		}
		return -1;
	}
	protected static final int find(final Object[] a, final Object x) {
		for(int i = 0; i < a.length; ++i) {
			if(a[i].equals(x)) {
				return i;
			}
		}
		return -1;
	}
	protected static final int findRev(final int[] a, final int x) {
		for(int i = a.length; --i >= 0;) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int findRev(final long[] a, final long x) {
		for(int i = a.length; --i >= 0;) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int findRev(final double[] a, final double x) {
		for(int i = a.length; --i >= 0;) {
			if(a[i] == x) {
				return i;
			}
		}
		return -1;
	}
	protected static final int findRev(final char[] s, final char c) {
		for(int i = s.length; --i >= 0;) {
			if(s[i] == c) {
				return i;
			}
		}
		return -1;
	}
	protected static final int findRev(final Object[] a, final Object x) {
		for(int i = a.length; --i >= 0;) {
			if(a[i].equals(x)) {
				return i;
			}
		}
		return -1;
	}
	protected static final boolean binarySearch(final int[] a, final int x){ return Arrays.binarySearch(a, x) >= 0; }
	protected static final boolean binarySearch(final long[] a, final long x){ return Arrays.binarySearch(a, x) >= 0; }
	protected static final <T extends Comparable<? super T>> boolean binarySearch(final T[] a, final T x){ return Arrays.binarySearch(a, x) >= 0; }
	protected static final <T extends Comparable<? super T>> boolean binarySearch(final List<T> a, final T x){ return Collections.binarySearch(a, x, null) >= 0; }
	protected static final int lowerBound(final int[] a, final int x){ return bins(a.length, -1, (IntPredicate) y -> a[y] >= x); }
	protected static final int lowerBound(final long[] a, final long x){ return bins(a.length, -1, (IntPredicate) y -> a[y] >= x); }
	protected static final <T extends Comparable<? super T>> int lowerBound(final T[] a, final T x){ return lowerBound(Arrays.asList(a), x); }
	protected static final <T extends Comparable<? super T>> int lowerBound(final List<T> a, final T x){ return ~Collections.binarySearch(a, x, (p, q) -> p.compareTo(q) >= 0 ? 1 : -1); }
	protected static final int upperBound(final int[] a, final int x){ return bins(a.length, -1, (IntPredicate) y -> a[y] > x); }
	protected static final int upperBound(final long[] a, final long x){ return bins(a.length, -1, (IntPredicate) y -> a[y] > x); }
	protected static final <T extends Comparable<? super T>> int upperBound(final T[] a, final T x){ return upperBound(Arrays.asList(a), x); }
	protected static final <T extends Comparable<? super T>> int upperBound(final List<T> a, final T x){ return ~Collections.binarySearch(a, x, (p, q) -> p.compareTo(q) > 0 ? 1 : -1); }
	protected static final String sorted(final String s){ return s.chars().sorted().mapToObj(Character::toString).collect(Collectors.joining()); }
	protected static final int[] sorted(final int[] a){ return Arrays.stream(a).sorted().toArray(); }
	protected static final long[] sorted(final long[] a){ return Arrays.stream(a).sorted().toArray(); }
	protected static final double[] sorted(final double[] a){ return Arrays.stream(a).sorted().toArray(); }
	protected static final char[] sorted(final char[] a){ return sorted(new String(a)).toCharArray(); }
	protected static final <T extends Comparable<? super T>> T[] sorted(final T[] a){ return Arrays.stream(a).sorted().toArray(n -> Arrays.copyOf(a, n)); }
	protected static final boolean isSorted(final String s){ return s.equals(sorted(s)); }
	protected static final boolean isSorted(final int[] a){ return Arrays.equals(a, sorted(a)); }
	protected static final boolean isSorted(final long[] a){ return Arrays.equals(a, sorted(a)); }
	protected static final boolean isSorted(final double[] a){ return Arrays.equals(a, sorted(a)); }
	protected static final boolean isSorted(final char[] a){ return Arrays.equals(a, sorted(a)); }
	protected static final <T extends Comparable<? super T>> boolean isSorted(final T[] a){ return Arrays.equals(a, sorted(a)); }
	protected static final String reverse(final String s){ return new StringBuilder(s).reverse().toString(); }
	protected static final int[] reverse(final int[] a) {
		final int n = a.length;
		final int[] b = new int[n];
		for(int i = 0; i <= n / 2; ++i) {
			b[i] = a[n - 1 - i];
			b[n - 1 - i] = a[i];
		}
		return b;
	}
	protected static final long[] reverse(final long[] a) {
		final int n = a.length;
		final long[] b = new long[n];
		for(int i = 0; i <= n / 2; ++i) {
			b[i] = a[n - 1 - i];
			b[n - 1 - i] = a[i];
		}
		return b;
	}
	protected static final double[] reverse(final double[] a) {
		final int n = a.length;
		final double[] b = new double[n];
		for(int i = 0; i <= n / 2; ++i) {
			b[i] = a[n - 1 - i];
			b[n - 1 - i] = a[i];
		}
		return b;
	}
	protected static final char[] reverse(final char[] a) {
		final int n = a.length;
		final char[] b = new char[n];
		for(int i = 0; i <= n / 2; ++i) {
			b[i] = a[n - 1 - i];
			b[n - 1 - i] = a[i];
		}
		return b;
	}
	protected static final Object[] reverse(final Object[] a) {
		final int n = a.length;
		final Object[] b = new Object[n];
		for(int i = 0; i <= n / 2; ++i) {
			b[i] = a[n - 1 - i];
			b[n - 1 - i] = a[i];
		}
		return b;
	}
	protected static final int[] rotate(final int[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final int[] res = new int[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final long[] rotate(final long[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final long[] res = new long[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final double[] rotate(final double[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final double[] res = new double[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final char[] rotate(final char[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final char[] res = new char[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final boolean[] rotate(final boolean[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final boolean[] res = new boolean[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final Object[] rotate(final Object[] a, final int id) {
		final int n = a.length, k = (int) mod(id, n);
		final Object[] res = new Object[n];
		System.arraycopy(a, k, res, 0, n - k);
		System.arraycopy(a, 0, res, n - k, k);
		return res;
	}
	protected static final String rotate(final String s, final int id) {
		final List<Character> t = s.chars().mapToObj(i -> (char) i).collect(Collectors.toList());
		Collections.rotate(t, id);
		return t.stream().map(String::valueOf).collect(Collectors.joining());
	}
	protected static final int[][] rotateR(final int[][] a) {
		final int h = a.length, w = a[0].length;
		final int[][] b = new int[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][i]);
		});
		IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
		return b;
	}
	protected static final long[][] rotateR(final long[][] a) {
		final int h = a.length, w = a[0].length;
		final long[][] b = new long[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][i]);
		});
		IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
		return b;
	}
	protected static final double[][] rotateR(final double[][] a) {
		final int h = a.length, w = a[0].length;
		final double[][] b = new double[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][i]);
		});
		IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
		return b;
	}
	protected static final char[][] rotateR(final char[][] a) {
		final int h = a.length, w = a[0].length;
		final char[][] b = new char[w][h];
		IntStream.range(0, h).forEach(i -> {
			IntStream.range(0, w).forEach(j -> b[j][i] = a[i][j]);
		});
		IntStream.range(0, w).forEach(i -> b[i] = reverse(b[i]));
		return b;
	}
	protected static final int[][] rotateL(final int[][] a) {
		final int h = a.length, w = a[0].length;
		final int[][] b = new int[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][w - i - 1]);
		});
		return b;
	}
	protected static final long[][] rotateL(final long[][] a) {
		final int h = a.length, w = a[0].length;
		final long[][] b = new long[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][w - i - 1]);
		});
		return b;
	}
	protected static final double[][] rotateL(final double[][] a) {
		final int h = a.length, w = a[0].length;
		final double[][] b = new double[w][h];
		IntStream.range(0, h).forEach(i -> {
			Arrays.setAll(b[i], j -> a[j][w - i - 1]);
		});
		return b;
	}
	protected static final char[][] rotateL(final char[][] a) {
		final int h = a.length, w = a[0].length;
		final char[][] b = new char[w][h];
		IntStream.range(0, h).forEach(i -> {
			IntStream.range(0, w).forEach(j -> b[w - j - 1][i] = a[i][j]);
		});
		return b;
	}
	protected static final void swap(final int[] a, final int i, final int j) {
		a[i] ^= a[j];
		a[j] ^= a[i];
		a[i] ^= a[j];
	}
	protected static final void swap(final long[] a, final int i, final int j) {
		a[i] ^= a[j];
		a[j] ^= a[i];
		a[i] ^= a[j];
	}
	protected static final void swap(final double[] a, final int i, final int j) {
		final double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	protected static final void swap(final char[] a, final int i, final int j) {
		a[i] ^= a[j];
		a[j] ^= a[i];
		a[i] ^= a[j];
	}
	protected static final void swap(final boolean[] a, final int i, final int j) {
		a[i] ^= a[j];
		a[j] ^= a[i];
		a[i] ^= a[j];
	}
	protected static final void swap(final Object[] a, final int i, final int j) {
		final Object tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	protected static final void swap(final int[] a, final int[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final int[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final void swap(final long[] a, final long[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final long[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final void swap(final double[] a, final double[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final double[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final void swap(final char[] a, final char[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final char[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final void swap(final boolean[] a, final boolean[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final boolean[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final void swap(final Object[] a, final Object[] b) {
		assert a.length == b.length;
		final int n = a.length;
		final Object[] c = a.clone();
		System.arraycopy(b, 0, a, 0, n);
		System.arraycopy(c, 0, b, 0, n);
	}
	protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> Pair<S, F>[] swap(final Pair<F, S>[] p) {
		@SuppressWarnings("unchecked")
		final Pair<S, F>[] q = new Pair[p.length];
		Arrays.setAll(q, i -> p[i].swap());
		return q;
	}
	protected static final IntPair[] swap(final IntPair[] p) {
		final IntPair[] q = new IntPair[p.length];
		Arrays.setAll(q, i -> p[i].swap());
		return q;
	}
	protected static final FloatPair[] swap(final FloatPair[] p) {
		final FloatPair[] q = new FloatPair[p.length];
		Arrays.setAll(q, i -> p[i].swap());
		return q;
	}
	@SuppressWarnings("unchecked")
	protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> F[] first(final Pair<F, S>[] p){ return (F[]) Arrays.stream(p).map(i -> i.first).toArray(); }
	protected static final long[] first(final IntPair[] p){ return Arrays.stream(p).mapToLong(i -> i.first).toArray(); }
	protected static final double[] first(final FloatPair[] p){ return Arrays.stream(p).mapToDouble(i -> i.first).toArray(); }
	@SuppressWarnings("unchecked")
	protected static final <F extends Comparable<? super F>, S extends Comparable<? super S>> S[] second(final Pair<F, S>[] p){ return (S[]) Arrays.stream(p).map(i -> i.second).toArray(); }
	protected static final long[] second(final IntPair[] p){ return Arrays.stream(p).mapToLong(i -> i.second).toArray(); }
	protected static final double[] second(final FloatPair[] p){ return Arrays.stream(p).mapToDouble(i -> i.second).toArray(); }
	protected static final IntStream iota(final int n){ return IntStream.range(0, n); }
	protected static final IntStream iota(final int n, final int init){ return IntStream.range(0 + init, n + init); }
	protected static final Integer[] boxed(final int[] a){ return Arrays.stream(a).boxed().toArray(Integer[]::new); }
	protected static final Long[] boxed(final long[] a){ return Arrays.stream(a).boxed().toArray(Long[]::new); }
	protected static final Double[] boxed(final double[] a){ return Arrays.stream(a).boxed().toArray(Double[]::new); }
	protected static final int bins(int ok, int ng, final IntPredicate fn) {
		while(abs(ok - ng) > 1) {
			final int mid = (ok + ng) / 2;
			if(fn.test(mid)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return ok;
	}
	protected static final long bins(long ok, long ng, final LongPredicate fn) {
		while(abs(ok - ng) > 1) {
			final long mid = (ok + ng) / 2;
			if(fn.test(mid)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return ok;
	}
	protected static final double bins(double ok, double ng, final DoublePredicate fn) {
		while(abs(ok - ng) > VvyLw.EPS) {
			final double mid = (ok + ng) / 2;
			if(fn.test(mid)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return ok;
	}
	protected static final Map<Integer, Integer> counter(final int[] a) {
		final Map<Integer, Integer> res = new HashMap<>();
		for(final int i: a) {
			res.merge(i, 1, (x, y) -> x + y);
		}
		return res;
	}
	protected static final Map<Long, Integer> counter(final long[] a) {
		final Map<Long, Integer> res = new HashMap<>();
		for(final long i: a) {
			res.merge(i, 1, (x, y) -> x + y);
		}
		return res;
	}
	protected static final long innerProd(final IntPair... p){ return iota(p.length).mapToLong(i -> p[i].first.longValue() * p[i].second.longValue()).sum(); }
	protected static final double innerProd(final FloatPair... p){ return iota(p.length).mapToDouble(i -> p[i].first.doubleValue() * p[i].second.doubleValue()).sum(); }
	protected static final FloatPair intersection(final IntPair a, final long sec1, final IntPair b, final long sec2) {
		double m1, m2, b1, b2;
		if(a.second.longValue() == 0 && b.second.longValue() == 0) {
			return null;
		} else if(a.second.longValue() == 0) {
			m2 = -b.first.doubleValue() / b.second.longValue();
			b2 = -sec2 / b.second.doubleValue();
			final double x = -sec1 / a.first.doubleValue(), y = b2 + m2 * x; 
			return FloatPair.of(x, y);
		} else if(b.second.longValue() == 0) {
			m1 = -a.first.doubleValue() / a.second.longValue();
			b1 = -sec1 / a.second.doubleValue();
			final double x = -sec2 / b.first.doubleValue(), y = b1 + m1 * x;
			return FloatPair.of(x, y);
		}
		m1 = -a.first.doubleValue() / a.second.longValue();
		m2 = -b.first.doubleValue() / b.second.longValue();
		b1 = -sec1 / a.second.doubleValue();
		b2 = -sec2 / b.second.doubleValue();
		assert m1 != m2;
		final double x = (b1 - b2) / (m2 - m1), y = m1 * x + b1;
		return FloatPair.of(x, y);
	}
	protected static final FloatPair intersection(final FloatPair a, final double sec1, final FloatPair b, final double sec2) {
		double m1, m2, b1, b2;
		if(a.second.doubleValue() == 0 && b.second.doubleValue() == 0) {
			return null;
		} else if(a.second.doubleValue() == 0) {
			m2 = -b.first.doubleValue() / b.second.doubleValue();
			b2 = -sec2 / b.second.doubleValue();
			final double x = -sec1 / a.first.doubleValue(), y = b2 + m2 * x; 
			return FloatPair.of(x, y);
		} else if(b.second.doubleValue() == 0) {
			m1 = -a.first.doubleValue() / a.second.doubleValue();
			b1 = -sec1 / a.second.doubleValue();
			final double x = -sec2 / b.first.doubleValue(), y = b1 + m1 * x;
			return FloatPair.of(x, y);
		}
		m1 = -a.first.doubleValue() / a.second.doubleValue();
		m2 = -b.first.doubleValue() / b.second.doubleValue();
		b1 = -sec1 / a.second.doubleValue();
		b2 = -sec2 / b.second.doubleValue();
		assert m1 != m2;
		final double x = (b1 - b2) / (m2 - m1), y = m1 * x + b1;
		return FloatPair.of(x, y);
	}
	protected static final int[] corPress(final int[] a) {
		final int[] res = new int[a.length];
		final int[] x = Arrays.stream(a).sorted().distinct().toArray();
		Arrays.setAll(res, i -> lowerBound(x, a[i]));
		return res;
	}
	protected static final int[] corPress(final long[] a) {
		final int[] res = new int[a.length];
		final long[] x = Arrays.stream(a).sorted().distinct().toArray();
		Arrays.setAll(res, i -> lowerBound(x, a[i]));
		return res;
	}
	protected static final String runLenPress(final String s) {
		final int n = s.length();
		final StringBuilder sb = new StringBuilder();
		for(int l = 0; l < n;) {
			int r = l + 1;
			for(; r < n && s.charAt(l) == s.charAt(r); ++r){}
			sb.append(s.charAt(l));
			sb.append(r - l);
			l = r;
		}
		return sb.toString();
	}
	protected static final String runLenRev(final String s) {
		final int n = s.length();
		final StringBuilder sb = new StringBuilder();
		for(int l = 0; l < n;) {
			int r = l + 1;
			for(; r < n && scope('0', s.charAt(r), '9'); ++r){}
			sb.append(String.valueOf(s.charAt(l)).repeat(Integer.parseInt(s.substring(l + 1, r))));
			l = r;
		}
		return sb.toString();
	}
	protected static final int[] zAlgorithm(final String s) {
		final int n = s.length();
		int j = 0;
		final int[] pre = new int[n];
		for(int i = 0; ++i < n;) {
			if(i + pre[i - j] < j + pre[j]) {
				pre[i] = pre[i - j];
			}
			else {
				int k = max(0, j + pre[j] - i);
				while(i + k < n && s.charAt(k) == s.charAt(i + k)) {
					++k;
				}
				pre[i] = k;
				j = i;
			}
		}
		pre[0] = n;
		return pre;
	}
	protected static final int[] manacher(final String s_, final boolean calcEven) {
		int n = s_.length();
		final char[] s;
		if(calcEven) {
			s = new char[2 * n - 1];
			IntStream.range(0, n).forEach(i -> s[i] = s_.charAt(i));
			for(int i = n; --i >= 0;) {
				s[2 * i] = s_.charAt(i);
			}
			final char d = Collections.min(s_.chars().mapToObj(c -> (char) c).collect(Collectors.toList()));
			for(int i = 0; i < n - 1; ++i) {
				s[2 * i + 1] = d;
			}
		} else {
			s = new char[n];
			IntStream.range(0, n).forEach(i -> s[i] = s_.charAt(i));
		}
		n = s.length;
		final int[] rad = new int[n];
		for(int i = 0, j = 0; i < n;) {
			while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) {
				++j;
			}
			rad[i] = j;
			int k = 1;
			while(i - k >= 0 && i + k < n && k + rad[i - k] < j) {
				rad[i + k] = rad[i - k];
				++k;
			}
			i += k;
			j -= k;
		}
		if(calcEven) {
			for(int i = 0; i < n; ++i) {
				if(((i ^ rad[i]) & 1) == 0) {
					rad[i]--;
				}
			}
		} else {
			for(int x: rad) {
				x = 2 * x - 1;
			}
		}
		return rad;
	}
	protected static final long kthRoot(final long n, final int k) {
		if(k == 1) {
			return n;
		}
		final LongPredicate chk = x -> {
			long mul = 1;
			for(int j = 0; j < k; ++j) {
				try {
					mul = multiplyExact(mul, x);
				} catch(final ArithmeticException e) {
					return false;
				}
			}
			return mul <= n;
		};
		long ret = 0;
		for(int i = 32; --i >= 0;) {
			if(chk.test(ret | (1L << i))) {
				ret |= 1L << i;
			}
		}
		return ret;
	}
	protected static final long tetration(final long a, final long b, final long m) {
		if(m == 1) {
			return 0;
		}
		if(a == 0) {
			return (b & 1) == 0 ? 1 : 0;
		}
		if(b == 0) {
			return 1;
		}
		if(b == 1) {
			return a % m;
		}
		if(b == 2) {
			return modPow(a, a, m);
		}
		final long phi = eulerPhi(m);
		long tmp = tetration(a, b - 1, phi);
		if(tmp == 0) {
			tmp += phi;
		}
		return modPow(a, tmp, m);
	}
	protected static final long floorSum(final long n, final long m, long a, long b) {
		long ans = 0;
		if(a >= m) {
			ans += (n - 1) * n * (a / m) / 2;
			a %= m;
		}
		if(b >= m) {
			ans += n * (b / m);
			b %= m;
		}
		final long ym = (a * n + b) / m, xm = (ym * m - b);
		if(ym == 0) {
			return ans;
		}
		ans += (n - (xm + a - 1) / a) * ym;
		ans += floorSum(ym, a, m, (a - xm % a) % a);
		return ans;
	}
}

interface TriFunction<T, U, V, R> {
	R apply(final T a, final U b, final V c);
}
interface QuadFunction<A, B, C, D, R> {
	R apply(final A a, final B b, final C c, final D d);
}
interface TriConsumer<T, U, V> {
	void accept(final T a, final U b, final V c);
}
interface TriPredicate<T, U, V> {
	boolean test(final T a, final U b, final V c);
}
interface RecursiveFunction<T, R> {
	R apply(final RecursiveFunction<T, R> rec, final T n);
}
interface RecursiveBiFunction<T, U, R> {
	R apply(final RecursiveBiFunction<T, U, R> rec, final T n, final U m);
}
interface RecursiveTriFunction<T, U, V, R> {
	R apply(final RecursiveTriFunction<T, U, V, R> rec, final T p, final U q, final V r);
}
interface RecursiveUnaryOperator<T> {
	T apply(final RecursiveUnaryOperator<T> rec, final T n);
}
interface RecursiveBinaryOperator<T> {
	T apply(final RecursiveBinaryOperator<T> rec, final T a, final T b);
}
interface RecursiveConsumer<T> {
	void accept(final RecursiveConsumer<T> rec, final T x);
}
interface RecursiveBiConsumer<T, U> {
	void accept(final RecursiveBiConsumer<T, U> rec, final T x, final U y);
}
interface RecursiveTriConsumer<T, U, V> {
	void accept(final RecursiveTriConsumer<T, U, V> rec, final T x, final U y, final V z);
}
interface RecursivePredicate<T> {
	boolean test(final RecursivePredicate<T> rec, final T n);
}
interface RecursiveBiPredicate<T, U> {
	boolean test(final RecursiveBiPredicate<T, U> rec, final T x, final U y);
}
interface RecursiveTriPredicate<T, U, V> {
	boolean test(final RecursiveTriPredicate<T, U, V> rec, final T x, final U y, final V z);
}
interface RecursiveIntFunction<R> {
	R apply(final RecursiveIntFunction<R> rec, final int n);
}
interface RecursiveLongFunction<R> {
	R apply(final RecursiveLongFunction<R> rec, final long n);
}
interface RecursiveDoubleFunction<R> {
	R apply(final RecursiveDoubleFunction<R> rec, final double n);
}
interface RecursiveIntUnaryOperator {
	int apply(final RecursiveIntUnaryOperator rec, final int n);
}
interface RecursiveLongUnaryOperator {
	long apply(final RecursiveLongUnaryOperator rec, final long n);
}
interface RecursiveDoubleUnaryOperator {
	double apply(final RecursiveDoubleUnaryOperator rec, final double n);
}
interface RecursiveIntBinaryOperator {
	int apply(final RecursiveIntBinaryOperator rec, final int a, final int b);
}
interface RecursiveLongBinaryOperator {
	long apply(final RecursiveLongBinaryOperator rec, final long a, final long b);
}
interface RecursiveDoubleBinaryOperator {
	double apply(final RecursiveDoubleBinaryOperator rec, final double a, final double b);
}
interface RecursiveIntConsumer {
	void accept(final RecursiveIntConsumer rec, final int n);
}
interface RecursiveLongConsumer {
	void accept(final RecursiveLongConsumer rec, final long n);
}
interface RecursiveDoubleConsumer {
	void accept(final RecursiveDoubleConsumer rec, final double n);
}
interface RecursiveIntPredicate {
	boolean test(final RecursiveIntPredicate rec, final int n);
}
interface RecursiveLongPredicate {
	boolean test(final RecursiveLongPredicate rec, final long n);
}
interface RecursiveDoublePredicate {
	boolean test(final RecursiveDoublePredicate rec, final double n);
}

final class IO implements Closeable, AutoCloseable {
	private final MyScanner in;
	private final MyPrinter out, err;
	IO(final InputStream in, final OutputStream out, final OutputStream err, final boolean autoFlush) {
		this.in = new MyScanner(in);
		this.out = new MyPrinter(out, autoFlush);
		this.err = new MyPrinter(err, true);
	}
	final int ni(){ return in.ni(); }
	final long nl(){ return in.nl(); }
	final double nd(){ return in.nd(); }
	final char nc(){ return in.nc(); }
	final String ns(){ return in.ns(); }
	final char[] nt(){ return in.nt(); }
	final BigInteger nb(){ return in.nb(); }
	final IntPair pi(){ return in.pi(); }
	final FloatPair pf(){ return in.pf(); }
	final int[] ni(final int n) {
		final int[] a = new int[n];
		Arrays.setAll(a, i -> ni());
		return a;
	}
	final int[] ni(final int n, final IntUnaryOperator f){ return Arrays.stream(ni(n)).map(f).toArray(); }
	final long[] nl(final int n) {
		final long[] a = new long[n];
		Arrays.setAll(a, i -> nl());
		return a;
	}
	final long[] nl(final int n, final LongUnaryOperator f){ return Arrays.stream(nl(n)).map(f).toArray(); }
	final double[] nd(final int n) {
		final double[] a = new double[n];
		Arrays.setAll(a, i -> nd());
		return a;
	}
	final char[] nc(final int n) {
		final char[] a = new char[n];
		IntStream.range(0, n).forEach(i -> a[i] = nc());
		return a;
	}
	final String[] ns(final int n) {
		final String[] a = new String[n];
		Arrays.setAll(a, i -> ns());
		return a;
	}
	final char[][] nt(final int n) {
		final char[][] a = new char[n][];
		Arrays.setAll(a, i -> nt());
		return a;
	}
	final BigInteger[] nb(final int n) {
		final BigInteger[] a = new BigInteger[n];
		Arrays.setAll(a, i -> nb());
		return a;
	}
	final IntPair[] pi(final int n) {
		final IntPair[] a = new IntPair[n];
		Arrays.setAll(a, i -> pi());
		return a;
	}
	final IntPair[] pi(final int n, final UnaryOperator<IntPair> f){ return Arrays.stream(pi(n)).map(f).toArray(IntPair[]::new); }
	final FloatPair[] pf(final int n) {
		final FloatPair[] a = new FloatPair[n];
		Arrays.setAll(a, i -> pf());
		return a;
	}
	final int[][] ni(final int h, final int w) {
		final int[][] a = new int[h][w];
		Arrays.setAll(a, i -> ni(w));
		return a;
	}
	final long[][] nl(final int h, final int w) {
		final long[][] a = new long[h][w];
		Arrays.setAll(a, i -> nl(w));
		return a;
	}
	final double[][] nd(final int h, final int w) {
		final double[][] a = new double[h][w];
		Arrays.setAll(a, i -> nd(w));
		return a;
	}
	final char[][] nc(final int h, final int w) {
		final char[][] a = new char[h][w];
		Arrays.setAll(a, i -> nc(w));
		return a;
	}
	final String[][] ns(final int h, final int w) {
		final String[][] a = new String[h][w];
		Arrays.setAll(a, i -> ns(w));
		return a;
	}
	final BigInteger[][] nb(final int h, final int w) {
		final BigInteger[][] a = new BigInteger[h][w];
		Arrays.setAll(a, i -> nb(w));
		return a;
	}
	final String line(){ return in.line(); }
	final void print(final Object arg){ out.print(arg); }
	final void printf(final String fmt, final Object... args){ out.printf(fmt, args); }
	final void out(){ out.out(); }
	final void out(final Object head, final Object... tail){ out.out(head, tail); }
	final void out(final int[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void out(final long[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void out(final double[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void out(final boolean[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void out(final char[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void out(final Object[][] args){ IntStream.range(0, args.length).forEach(i -> out(args[i])); }
	final void outl(final Object head, final Object... tail){ out.outl(head, tail); }
	final void dump(final Object head, final Object... tail){ err.out(head, tail); }
	final void dump(final int[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dump(final long[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dump(final double[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dump(final boolean[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dump(final char[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dump(final Object[][] args){ IntStream.range(0, args.length).forEach(i -> dump(args[i])); }
	final void dumpl(final Object head, final Object... tail){ err.outl(head, tail); }
	@Override
	public final void close() {
		out.flush();
		in.close();
		out.close();
		err.close();
	}
	private final class MyScanner implements Closeable, AutoCloseable {
		private int pos, lim;
		private final byte[] buf;
		private final InputStream is;
		private boolean check;
		MyScanner(final InputStream is) {
			this.is = is;
			pos = lim = 0;
			buf = new byte[1 << 17];
			check = false;
		}
		private final boolean isPunct(final byte bt){ return !Utility.scope(33, bt, 126); }
		private final boolean isNum(final byte bt){ return Utility.scope('0', bt, '9'); }
		private final byte read() {
			if(pos == lim && lim != -1) {
				try {
					lim = is.read(buf);
					pos = 0;
				} catch(final IOException e) {
					e.printStackTrace();
				}
			}
			return buf[pos++];
		}
		private final byte next() {
			byte bt;
			if(check) {
				check = false;
				bt = buf[pos - 1];
				if(!isPunct(bt)) {
					return bt;
				}
			}
			while(isPunct(bt = read())){}
			return bt;
		}
		final int ni(){ return toIntExact(nl()); }
		final long nl() {
			byte c = next();
			final boolean neg = c == '-';
			if(neg) {
				c = next();
			}
			assert isNum(c);
			long res = c - '0';
			while(isNum(c = read())) {
				res = 10 * res + c - '0';
			}
			check = !isNum(c);
			return neg ? -res : res;
		}
		final double nd() {
			byte c = next();
			final boolean neg = c == '-';
			if(neg) {
				c = next();
			}
			assert isNum(c);
			double res = c - '0';
			while(isNum(c = read())) {
				res = 10 * res + c - '0';
			}
			if(c != '.') {
				check = true;
				return res;
			}
			int i;
			for(i = 0; isNum(c = read()); ++i) {
				res = res * 10 + c - '0';
			}
			res /= pow(10, i);
			check = true;
			return neg ? -res : res;
		}
		final char nc(){ return (char) next(); }
		final String ns() {
			final StringBuilder sb = new StringBuilder();
			byte c = next();
			while(!isPunct(c)) {
				sb.append((char) c);
				c = read();
			}
			return sb.toString();
		}
		final char[] nt(){ return ns().toCharArray(); }
		final BigInteger nb(){ return new BigInteger(ns()); }
		final IntPair pi(){ return IntPair.of(nl(), nl()); }
		final FloatPair pf(){ return FloatPair.of(nd(), nd()); }
		final String line() {
			final StringBuilder sb = new StringBuilder();
			byte c;
			while((c = read()) != '\n') {
				sb.append((char) c);
			}
			return sb.toString();
		}
		@Override
		public final void close() {
			try {
				is.close();
			} catch(final IOException e) {
				e.printStackTrace();
			}
		}
	}
	private final class MyPrinter implements Closeable, Flushable, AutoCloseable {
		private OutputStream os;
		private final boolean autoFlush;
		private final byte[] buf;
		private int pos;
		private final boolean debug;
		MyPrinter(final OutputStream os, final boolean autoFlush){
			this.os = os;
			this.autoFlush = autoFlush;
			buf = new byte[1 << 17];
			pos = 0;
			debug = os == System.err;
		}
		private final void write(final byte bt) {
			buf[pos++] = bt;
			if(pos == buf.length) {
				flush();
			}
		}
		private final void newLine() {
			write((byte) '\n');
			if(autoFlush) {
				flush();
			}
		}
		final void print(final Object arg) {
			if(arg instanceof final String s) {
				for(final char c: s.toCharArray()) {
					write((byte) c);
				}
			} else {
				final StringBuilder sb = new StringBuilder();
				if(arg instanceof final int[] a) {
					if(debug) {
						print(Arrays.toString(a));
						return;
					}
					if(a.length == 0) {
						return;
					}
					sb.append(a[0]);
					for(int i = 0; ++i < a.length;) {
						sb.append(" " + a[i]);
					}
				} else if(arg instanceof final long[] a) {
					if(debug) {
						print(Arrays.toString(a));
						return;
					}
					if(a.length == 0) {
						return;
					}
					sb.append(a[0]);
					for(int i = 0; ++i < a.length;) {
						sb.append(" " + a[i]);
					}
				} else if(arg instanceof final double[] a) {
					if(debug) {
						print(Arrays.toString(a));
						return;
					}
					if(a.length == 0) {
						return;
					}
					for(int i = 0; i < a.length; ++i) {
						sb.append(a[i]);
					}
				} else if(arg instanceof final boolean[] a) {
					if(debug) {
						print(Arrays.toString(a));
						return;
					}
					if(a.length == 0) {
						return;
					}
					sb.append(a[0]);
					for(int i = 0; ++i < a.length;) {
						sb.append(" " + a[i]);
					}
				} else if(arg instanceof final char[] a) {
					if(a.length == 0) {
						return;
					}
					sb.append(a[0]);
					for(int i = 0; ++i < a.length;) {
						sb.append(" " + a[i]);
					}
				} else if(arg instanceof final Object[] a) {
					if(debug) {
						print(Arrays.toString(a));
						return;
					}
					if(a.length == 0) {
						return;
					}
					print(a[0]);
					for(int i = 0; ++i < a.length;) {
						print(" ");
						print(a[i]);
					}
					return;
				} else {
					if(debug) {
						print(arg.toString());
						return;
					} else if(arg instanceof final Pair<?, ?> p) {
						sb.append(p.first + " " + p.second);
					} else if(arg instanceof final Collection<?> c) {
						int i = 0;
						for(final Object el: c) {
							print(el);
							if(++i != c.size()) {
								print(" ");
							}
						}
						return;
					} else if(sb.isEmpty()) {
						print(arg.toString());
						return;
					}
				}
				print(sb.toString());
			}
			if(autoFlush) {
				flush();
			}
		}
		final void printf(final String fmt, final Object... args){ print(new Formatter().format(fmt, args)); }
		final void out(){ newLine(); }
		final void out(final Object head, final Object... tail) {
			print(head);
			for(final Object el: tail) {
				print(" ");
				print(el);
			}
			newLine();
		}
		private final void p(final Object obj) {
			switch(obj) {
				case int[] a: Arrays.stream(a).forEach(this::out); break;
				case long[] a: Arrays.stream(a).forEach(this::out); break;
				case double[] a: Arrays.stream(a).forEach(this::out); break;
				case boolean[] a: IntStream.range(0, a.length).mapToObj(i -> a[i]).forEach(this::out); break;
				case char[] a: IntStream.range(0, a.length).mapToObj(i -> a[i]).forEach(this::out); break;
				case Object[] a: Arrays.stream(a).forEach(this::out); break;
				case Collection<?> a: a.stream().forEach(this::out); break;
				default: out(obj);
			}
		}
		final void outl(final Object head, final Object... tail) {
			p(head);
			for(final Object el: tail) {
				p(el);
			}
		}
		@Override
		public final void flush() {
			try {
				os.write(buf, 0, pos);
				pos = 0;
			} catch(final IOException e) {
				e.printStackTrace();
			}
		}
		@Override
		public final void close() {
			if(os == null) {
				return;
			}
			try {
				os.close();
				os = null;
			} catch(final IOException e) {
				e.printStackTrace();
			}
		}
	}
}

class Pair<F extends Comparable<? super F>, S extends Comparable<? super S>> implements Comparable<Pair<F, S>>, Cloneable {
	public F first;
	public S second;
	protected Pair(final F first, final S second) {
		this.first = first;
		this.second = second;
	}
	static final <F extends Comparable<? super F>, S extends Comparable<? super S>> Pair<F, S> of(final F a, final S b){ return new Pair<>(a, b); }
	Pair<S, F> swap(){ return Pair.of(second, first); }
	@Override
	public final boolean equals(final Object o) {
		if(this == o) {
			return true;
		}
		if(o == null || getClass() != o.getClass()) {
			return false;
		}
		final Pair<?, ?> p = (Pair<?, ?>) o;
		return first.equals(p.first) && second.equals(p.second);
	}
	@Override
	public final int hashCode(){ return Objects.hash(first, second); }
	@Override
	public final String toString(){ return "(" + first + ", " + second + ")"; }
	@SuppressWarnings("unchecked")
	@Override
	public final Pair<F, S> clone() {
		try {
			return (Pair<F, S>) super.clone();
		} catch(final CloneNotSupportedException e){
			e.printStackTrace();
		}
		throw new Error();
	}
	@Override
	public final int compareTo(final Pair<F, S> p) {
		if(first.compareTo(p.first) == 0) {
			return second.compareTo(p.second);
		}
		return first.compareTo(p.first);
	}
}
final class IntPair extends Pair<Long, Long> {
	private IntPair(final long first, final long second){ super(first, second); }
	static final IntPair ZERO = new IntPair(0, 0);
	static final IntPair ONE = new IntPair(1, 1);
	static final IntPair of(final long a, final long b){ return new IntPair(a, b); }
	@Override
	final IntPair swap(){ return new IntPair(second, first); }
	final IntPair add(final IntPair p){ return new IntPair(first + p.first, second + p.second); }
	final IntPair sub(final IntPair p){ return new IntPair(first - p.first, second - p.second); }
	final IntPair mul(final IntPair p){ return new IntPair(first * p.first, second * p.second); }
	final IntPair div(final IntPair p){ return new IntPair(first / p.first, second / p.second); }
	final IntPair mod(final IntPair p){ return new IntPair(first % p.first, second % p.second); }
	final IntPair rotate(){ return new IntPair(-second, first); } 
	final FloatPair rotate(final int ang) {
		final double rad = toRadians(Utility.mod(ang, 360));
		return FloatPair.of(first * cos(rad) - second * sin(rad), first * sin(rad) + second * cos(rad));
	}
	final long dot(final IntPair p){ return first * p.first + second * p.second; }
	final long cross(final IntPair p){ return rotate().dot(p); }
	final long sqr(){ return dot(this); }
	final double grad() { 
		try {
			return 1.0 * second / first;
		} catch(final ArithmeticException e) {
			e.printStackTrace();
		}
		throw new Error();
	}
	final double abs(){ return hypot(first, second); }
	final long lcm(){ return Utility.lcm(first, second); }
	final long gcd(){ return Utility.gcd(first, second); }
	final IntPair extgcd() {
		long x = 1, y = 0, t1 = 0, t2 = 0, t3 = 1, a = first, b = second;
		while(b > 0) {
			t1 = a / b;
			a -= t1 * b;
			a ^= b;
			b ^= a;
			a ^= b;
			x -= t1 * t2;
			x ^= t2;
			t2 ^= x;
			x ^= t2;
			y -= t1 * t3;
			y ^= t3;
			t3 ^= y;
			y ^= t3;
		}
		return new IntPair(x, y);
	}
}
final class FloatPair extends Pair<Double, Double> {
	private FloatPair(final double first, final double second){ super(first, second); }
	static final FloatPair of(final double a, final double b){ return new FloatPair(a, b); }
	@Override
	final FloatPair swap(){ return new FloatPair(second, first); }
	final FloatPair add(final FloatPair p){ return new FloatPair(first + p.first, second + p.second); }
	final FloatPair sub(final FloatPair p){ return new FloatPair(first - p.first, second - p.second); }
	final FloatPair mul(final FloatPair p){ return new FloatPair(first * p.first, second * p.second); }
	final FloatPair div(final FloatPair p){ return new FloatPair(first / p.first, second / p.second); }
	final FloatPair rotate(){ return new FloatPair(-second, first); } 
	final FloatPair rotate(final int ang) {
		final double rad = toRadians(Utility.mod(ang, 360));
		return FloatPair.of(first * cos(rad) - second * sin(rad), first * sin(rad) + second * cos(rad));
	}
	final double dot(final FloatPair p){ return first * p.first + second * p.second; }
	final double cross(final FloatPair p){ return rotate().dot(p); }
	final double sqr(){ return dot(this); }
	final double grad() { 
		try {
			return second / first;
		} catch(final ArithmeticException e) {
			e.printStackTrace();
		}
		throw new Error();
	}
	final double abs(){ return hypot(first, second); }
}

/**
 * UnionFindのベースとなるインターフェース
 * Disjoint Set Union
 */
interface DSU {
	/**
	 * @param i
	 * @return iの根
	 */
	public int root(final int i);
	/**
	 * @param i
	 * @return iを含む連結成分のサイズ
	 */
	public int size(final int i);
	/**
	 * @return UnionFindのサイズ
	 */
	public int size();
	/**
	 * @param i
	 * @param j
	 * @return iとjが同じ連結成分に所属しているか
	 */
	public default boolean same(final int i, final int j){ return root(i) == root(j); }
	/**
	 * @param i
	 * @param j
	 * @return 未マージでtrue, マージ済でfalse
	 */
	public boolean unite(int i, int j);
	/**
	 * @see <a href="https://atcoder.github.io/ac-library/production/document_ja/dsu.html">atcoder::dsu::groups</a>
	 * @return グラフを連結成分に分け、その情報を返す
	 */
	public ArrayList<ArrayList<Integer>> groups();
}
/**
 * UnionFind
 */
class UnionFind implements DSU {
	protected final int[] par;
	/**
	 * コンストラクタ
	 * @param n サイズ
	 */
	public UnionFind(final int n) {
		par = new int[n];
		Arrays.fill(par, -1);
	}
	@Override
	public final int root(final int i){ return par[i] >= 0 ? par[i] = root(par[i]) : i; }
	@Override
	public final int size(final int i){ return -par[root(i)]; }
	@Override
	public final int size(){ return par.length; }
	@Override
	public boolean unite(int i, int j) {
		i = root(i);
		j = root(j);
		if(i == j) {
			return false;
		}
		if(i > j) {
			i ^= j;
			j ^= i;
			i ^= j;
		}
		par[i] += par[j];
		par[j] = i;
		return true;
	}
	@Override
	public final ArrayList<ArrayList<Integer>> groups() {
		final int n = par.length;
		ArrayList<ArrayList<Integer>> res = new ArrayList<>(n);
		IntStream.range(0, n).forEach(i -> res.add(new ArrayList<>()));
		IntStream.range(0, n).forEach(i -> res.get(root(i)).add(i));
		res.removeIf(ArrayList::isEmpty);
		return res;
	}
	@Override
	public final String toString(){ return groups().toString(); }
}