Java/Main.java

View this file on GitHub
Last update: 2024-10-17 12:58:35+09:00

Depends on

Required by

Code

import static java.lang.Math.*;

import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Formatter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.TreeMap;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.DoublePredicate;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.LongPredicate;
import java.util.function.LongUnaryOperator;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

final 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) {
		
		return null;
	}
}
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 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 IntStream.of(a).asLongStream().reduce(1, (x, y) -> lcm(x, y)); }
	protected static final long lcm(final long... a){ return LongStream.of(a).reduce(1, (x, y) -> lcm(x, y)); }
	protected static final long gcd(final long a, final long b){ return b == 0 ? a : gcd(b, a % b); }
	protected static final int gcd(final int... a){ return IntStream.of(a).reduce(0, (x, y) -> (int) gcd(x, y)); }
	protected static final long gcd(final long... a){ return LongStream.of(a).reduce(0, (x, y) -> gcd(x, y)); }
	protected static final int min(final int... a){ return IntStream.of(a).min().getAsInt(); }
	protected static final long min(final long... a){ return LongStream.of(a).min().getAsLong(); }
	protected static final double min(final double... a){ return DoubleStream.of(a).min().getAsDouble(); }
	protected static final int max(final int... a){ return IntStream.of(a).max().getAsInt(); }
	protected static final long max(final long... a){ return LongStream.of(a).max().getAsLong(); }
	protected static final double max(final double... a){ return DoubleStream.of(a).max().getAsDouble(); }
	protected static final long sum(final int... a){ return IntStream.of(a).asLongStream().sum(); }
	protected static final long sum(final long... a){ return LongStream.of(a).sum(); }
	protected static final double sum(final double... a){ return DoubleStream.of(a).sum(); }
	protected static final long prod(final int... a){ return IntStream.of(a).asLongStream().reduce(1, (x, y) -> x * y); }
	protected static final long prod(final long... a){ return LongStream.of(a).reduce(1, (x, y) -> x * y); }
	protected static final double prod(final double... a){ return DoubleStream.of(a).reduce(1, (x, y) -> x * y); }
	protected static final double ave(final int... a){ return IntStream.of(a).average().getAsDouble(); }
	protected static final double ave(final long... a){ return LongStream.of(a).average().getAsDouble(); }
	protected static final double ave(final double... a){ return DoubleStream.of(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 int clamp(final int l, final int x, final int r){ return x < l ? l : x > r ? r : x; }
	protected static final long clamp(final long l, final long x, final long r){ return x < l ? l : x > r ? r : x; }
	protected static final double clamp(final double l, final double x, final double r){ return x < l ? l : x > r ? r : x; }
	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 IntPair[] runLenPress(final int[] a) {
		final List<IntPair> ret = new ArrayList<>();
		for(final int e: a) {
			if(ret.isEmpty() || ret.get(ret.size() - 1).first.intValue() != e) {
				ret.add(IntPair.of(e, 1));
			} else {
				ret.get(ret.size() - 1).second++;
			}
		}
		return ret.toArray(IntPair[]::new);
	}
	protected static final IntPair[] runLenPress(final long[] a) {
		final List<IntPair> ret = new ArrayList<>();
		for(final long e: a) {
			if(ret.isEmpty() || ret.get(ret.size() - 1).first.intValue() != e) {
				ret.add(IntPair.of(e, 1));
			} else {
				ret.get(ret.size() - 1).second++;
			}
		}
		return ret.toArray(IntPair[]::new);
	}
	@SuppressWarnings("unchecked")
	protected static final Pair<Character, Integer>[] runLenPress(final String s) {
		final List<Pair<Character, Integer>> ret = new ArrayList<>();
		for(final char c: s.toCharArray()) {
			if(ret.isEmpty() || ret.get(ret.size()).first != c) {
				ret.add(Pair.of(c, 1));
			} else {
				ret.get(ret.size()).second++;
			}
		}
		return ret.toArray(Pair[]::new);
	}
	protected static final long[] runLenRev(final IntPair[] a) {
		final List<Long> ret = new ArrayList<>();
		for(final IntPair e: a) {
			for(int i = 0; i < e.second.intValue(); ++i) {
				ret.add(e.first.longValue());
			}
		}
		return ret.stream().mapToLong(e -> e).toArray();
	}
	protected static final String runLenRev(final Pair<Character, Integer>[] a) {
		final StringBuilder sb = new StringBuilder();
		for(final Pair<Character, Integer> p: a) {
			for(int i = 0; i < p.second.intValue(); ++i) {
				sb.append(p.first.charValue());
			}
		}
		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 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 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 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;
					}
					sb.append(a[0]);
					for(int i = 0; ++i < a.length;) {
						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;
					}
					for(int i = 0; i < a.length; ++i) {
						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) {
			if(obj instanceof int[] a) {
				Arrays.stream(a).forEach(this::out);
			} else if(obj instanceof long[] a) {
				Arrays.stream(a).forEach(this::out);
			} else if(obj instanceof double[] a) {
				Arrays.stream(a).forEach(this::out);
			} else if(obj instanceof boolean[] a) {
				IntStream.range(0, a.length).mapToObj(i -> a[i]).forEach(this::out);
			} else if(obj instanceof char[] a) {
				IntStream.range(0, a.length).mapToObj(i -> a[i]).forEach(this::out);
			} else if(obj instanceof Object[] a) {
				Arrays.stream(a).forEach(this::out);
			} else if(obj instanceof Collection<?> a) {
				a.stream().forEach(this::out);
			} else {
				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); }
}

final class Why {
	static final boolean isBipartite(final UnionFind uf) {
		assert uf.size() % 2 == 0;
		final int n = uf.size() / 2;
		boolean ok = true;
		for(int i = 0; i < n; ++i) {
			ok &= !uf.same(i, i + n);
		}
		return ok;
	}
	static final long invNum(final int[] a) {
		final int[] b = Utility.sorted(a);
		final Map<Integer, Integer> id = new HashMap<>();
		for(int i = 0; i < a.length; ++i) {
			id.put(b[i], i);
		}
		final FenwickTree bit = new FenwickTree(a.length);
		long res = 0;
		for(int i = 0; i < a.length; ++i) {
			res += i - bit.sum(id.get(a[i]));
			bit.add(id.get(a[i]), 1);
		}
		return res;
	}
	static final long invNum(final long[] a) {
		final long[] b = Utility.sorted(a);
		final Map<Long, Integer> id = new HashMap<>();
		for(int i = 0; i < a.length; ++i) {
			id.put(b[i], i);
		}
		final FenwickTree bit = new FenwickTree(a.length);
		long res = 0;
		for(int i = 0; i < a.length; ++i) {
			res += i - bit.sum(id.get(a[i]));
			bit.add(id.get(a[i]), 1);
		}
		return res;
	}
	static final int[][] doubling(final int[] a, final long k) {
		final int z = (int) Math.ceil(Utility.log(k, 2)), n = a.length;
		final int[][] dbl = new int[z][n];
		for(int i = 0; i < n; ++i) {
			dbl[0][i] = a[i];
		}
		for(int i = 0; ++i < z;) {
			for(int j = 0; j < n; ++j) {
				dbl[i][j] = dbl[i - 1][dbl[i - 1][j]];
			}
		}
		return dbl;
	}
}

final class Edge {
	public int src, to, id;
	public long cost;
	Edge(final int src, final int to, final int id) {
		this.src = src;
		this.to = to;
		this.id = id;
	}
	Edge(final int src, final int to, final long cost, final int id) {
		this.src = src;
		this.to = to;
		this.cost = cost;
		this.id = id;
	}
	@Override
	public final boolean equals(final Object o) {
		if(this == o) {
			return true;
		}
		if(o == null || getClass() != o.getClass()) {
			return false;
		}
		final Edge e = (Edge) o;
		return src == e.src && to == e.to && cost == e.cost;
	}
	@Override
	public final int hashCode(){ return Objects.hash(src, to, cost, id); }
	@Override
	public final String toString(){ return "(" + src + ", " + to + ", " + cost + ")"; }
}
final class ShortestPath {
	private final long[] cost;
	private final int[] src;
	ShortestPath(final long[] cost, final int[] src) {
		this.cost = cost;
		this.src = src;
	}
	final boolean isThru(final int i){ return src[i] != -1; }
	final int[] path(int i) {
		final List<Integer> res = new ArrayList<>();
		for(; i != -1; i = src[i]) {
			res.add(i);
		}
		Collections.reverse(res);
		return res.stream().mapToInt(k -> k).toArray();
	}
	final long[] get(){ return cost; }
}
final class MST {
	public final ArrayList<Edge> tree;
	public final long cost;
	MST(final ArrayList<Edge> tree, final long cost) {
		this.tree = tree;
		this.cost = cost;
	}
}
final class SkewHeap {
	static final class Node {
		long key, lazy;
		Node l, r;
		final int idx;
		Node(final long key, final int idx) {
			this.key = key;
			this.idx = idx;
			lazy = 0;
			l = null;
			r = null;
		}
	}
	private final boolean isMin;
	SkewHeap(final boolean isMin){ this.isMin = isMin; }
	private final Node alloc(final long key, final int idx){ return new Node(key, idx); }
	private final Node propagate(final Node t) {
		if(t != null && t.lazy != 0) {
			if(t.l != null) {
				t.l.lazy += t.lazy;
			}
			if(t.r != null) {
				t.r.lazy += t.lazy;
			}
			t.key += t.lazy;
			t.lazy = 0;
		}
		return t;
	}
	final Node meld(Node x, Node y) {
		propagate(x);
		propagate(y);
		if(x == null || y == null) {
			return x != null ? x : y;
		}
		if((x.key < y.key) ^ isMin) {
			final Node tmp = x;
			x = y;
			y = tmp;
		}
		x.r = meld(y, x.r);
		final Node tmp = x.l;
		x.l = x.r;
		x.r = tmp;
		return x;
	}
	final Node push(final Node t, final long key, final int idx){ return meld(t, alloc(key, idx)); }
	final Node pop(final Node t) {
		if(t == null) {
			throw new NullPointerException();
		}
		return meld(t.l, t.r);
	}
	final Node add(final Node t, final long lazy) {
		if(t != null) {
			t.lazy += lazy;
			propagate(t);
		}
		return t;
	}
}

class Graph extends ArrayList<ArrayList<Edge>> {
	private final boolean undirected, weighted;
	private final int n, indexed;
	private int id;
	private final ArrayList<Edge> edge;
	private final int[] to;
	private final ArrayList<Edge> path;
	Graph(final int n, final int indexed, final boolean undirected, final boolean weighted) {
		this.n = n;
		this.indexed = indexed;
		this.undirected = undirected;
		this.weighted = weighted;
		id = 0;
		edge = new ArrayList<>();
		IntStream.range(0, n).forEach(i -> add(new ArrayList<>()));
		to = new int[n];
		Arrays.fill(to, -1);
		path = new ArrayList<>();
	}
	static Graph of(final List<ArrayList<Edge>> g, final boolean undirected, final boolean weighted) {
		int max = 0, min = Integer.MAX_VALUE;
		for(int i = 0; i < g.size(); ++i) {
			for(final Edge e: g.get(i)) {
				max = max(e.src, e.to);
				min = min(e.src, e.to);
			}
		}
		final Graph gp = new Graph(max, min, undirected, weighted);
		for(int i = 0; i < g.size(); ++i) {
			for(final Edge e: g.get(i)) {
				if(weighted) {
					gp.addEdge(e.src, e.to, e.cost);
				} else {
					gp.addEdge(e.src, e.to);
				}
			}
		}
		return gp;
	}
	final void addEdge(int a, int b){ addEdge(a, b, 1); }
	final void addEdge(int a, int b, final long cost) {
		a -= indexed;
		b -= indexed;
		this.get(a).add(new Edge(a, b, cost, id));
		edge.add(new Edge(a, b, cost, id));
		if(undirected) {
			this.get(b).add(new Edge(b, a, cost, id));
			edge.add(new Edge(b, a, cost, id));
		}
		id++;
	}
	final void input(final int m) {
		IntStream.range(0, m).forEach(i -> {
			if(weighted) {
				addEdge(VvyLw.io.ni(), VvyLw.io.ni(), VvyLw.io.nl());
			} else {
				addEdge(VvyLw.io.ni(), VvyLw.io.ni());
			}
		});
	}
	final Edge[] getEdge(){ return edge.toArray(Edge[]::new); }
	@Override
	public final int[][] toArray() {
		final int[][] res = new int[n][];
		IntStream.range(0, n).forEach(i -> res[i] = get(i).stream().mapToInt(e -> e.to).toArray());
		return res;
	}
	final int[] allDist(final int v) {
		final int[] d = new int[n];
		Arrays.fill(d, -1);
		final Queue<Integer> q = new ArrayDeque<>();
		d[v] = 0;
		q.add(v);
		while(!q.isEmpty()) {
			final int tmp = q.poll();
			for(final Edge el: this.get(tmp)) {
				if(d[el.to] != -1) {
					continue;
				}
				d[el.to] = d[tmp] + 1;
				q.add(el.to);
			}
		}
		return d;
	}
	final int dist(final int u, final int v){ return allDist(u)[v]; }
	final ArrayList<Integer> topologicalSort() {
		final int[] deg = new int[n];
		for(int i = 0; i < n; ++i) {
			for(final Edge ed: this.get(i)) {
				deg[ed.to]++;
			}
		}
		final Stack<Integer> sk = new Stack<>();
		for(int i = 0; i < n; ++i) {
			if(deg[i] == 0) {
				sk.add(i);
			}
		}
		final ArrayList<Integer> ord = new ArrayList<>();
		while(!sk.isEmpty()) {
			final int tmp = sk.pop();
			ord.add(tmp);
			for(final Edge ed: this.get(tmp)) {
				if(--deg[ed.to] == 0) {
					sk.add(ed.to);
				}
			}
		}
		return n == ord.size() ? ord : null;
	}
	final int[] cycleDetector() {
		final int[] used = new int[n];
		final Edge[] pre = new Edge[n];
		final ArrayList<Edge> cycle = new ArrayList<>();
		final RecursiveIntPredicate dfs = (rec, i) -> {
			used[i] = 1;
			for(final Edge e: get(i)) {
				if(used[e.to] == 0) {
					pre[e.to] = e;
					if(rec.test(rec, e.to)) {
						return true;
					}
				} else if(used[e.to] == 1) {
					int now = i;
					while(now != e.to) {
						cycle.add(pre[now]);
						now = pre[now].src;
					}
					cycle.add(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
		};
		for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs.test(dfs, i)) {
				Collections.reverse(cycle);
				return cycle.stream().mapToInt(e -> e.to).toArray();
			}
		}
		return null;
	}
	private final IntPair dfs(final int i, final int par) {
		IntPair ret = IntPair.of(0, i);
		for(final Edge e: get(i)) {
			if(e.to == par) {
				continue;
			}
			final IntPair cost = dfs(e.to, i);
			cost.first += e.cost;
			if(ret.compareTo(cost) < 0) {
				ret = cost;
				to[i] = e.to;
			}
		}
		return ret;
	}
	final long diameter() {
		final IntPair p = dfs(0, -1);
		final IntPair q = dfs(p.second.intValue(), -1);
		int now = p.second.intValue();
		while(now != q.second) {
			for(final Edge e: get(now)) {
				if(to[now] == e.to) {
					path.add(e);
				}
			}
			now = to[now];
		}
		return q.first;
	}
	final Edge[] getPath(){ return path.toArray(Edge[]::new); }
	final ShortestPath dijkstra(final int v) {
		final long[] cost = new long[n];
		final int[] src = new int[n];
		Arrays.fill(cost, Long.MAX_VALUE);
		Arrays.fill(src, -1);
		final Queue<IntPair> dj = new PriorityQueue<>();
		cost[v] = 0;
		dj.add(IntPair.of(cost[v], v));
		while(!dj.isEmpty()) {
			final IntPair tmp = dj.poll();
			if(cost[tmp.second.intValue()] < tmp.first.longValue()) {
				continue;
			}
			for(final Edge ed: this.get(tmp.second.intValue())) {
				final long next = tmp.first.longValue() + ed.cost;
				if(cost[ed.to] <= next) {
					continue;
				}
				cost[ed.to] = next;
				src[ed.to] = tmp.second.intValue();
				dj.add(IntPair.of(cost[ed.to], ed.to));
			}
		}
		return new ShortestPath(cost, src);
	}
	final long[] spfa(final int v) {
		final long[] cost = new long[n];
		Arrays.fill(cost, Long.MAX_VALUE);
		final boolean[] pend = new boolean[n];
		final int[] cnt = new int[n];
		final Queue<Integer> q = new ArrayDeque<>();
		q.add(v);
		pend[v] = true;
		cnt[v]++;
		cost[v] = 0;
		while(!q.isEmpty()) {
			final int p = q.poll();
			pend[p] = false;
			for(final Edge e: this.get(p)) {
				final long next = cost[p] + e.cost;
				if(next >= cost[e.to]) {
					continue;
				}
				cost[e.to] = next;
				if(!pend[e.to]) {
					if(++cnt[e.to] >= n) {
						return null;
					}
					pend[e.to] = true;
					q.add(e.to);
				}
			}
		}
		return cost;
	}
	final long[][] floydWarshall() {
		final long[][] cost = new long[n][n];
		IntStream.range(0, n).forEach(i -> Arrays.fill(cost[i], VvyLw.LINF));
		IntStream.range(0, n).forEach(i -> cost[i][i] = 0);
		for(int i = 0; i < n; ++i) {
			for(final Edge j: this.get(i)) {
				cost[i][j.to] = j.cost;
			}
		}
		for(int k = 0; k < n; ++k) {
			for(int i = 0; i < n; ++i) {
				for(int j = 0; j < n; ++j) {
					if(cost[i][k] == VvyLw.LINF || cost[k][j] == VvyLw.LINF) {
						continue;
					}
					if(cost[i][j] > cost[i][k] + cost[k][j]) {
						cost[i][j] = cost[i][k] + cost[k][j];
					}
				}
			}
		}
		return cost;
	}
	final MST kruskal() {
		final UnionFind uf = new UnionFind(n);
		final ArrayList<Edge> e = new ArrayList<>();
		long res = 0;
		for(final Edge ed: edge.stream().sorted(Comparator.comparing(ed -> ed.cost)).collect(Collectors.toList())) {
			if(uf.unite(ed.src, ed.to)) {
				e.add(ed);
				res += ed.cost;
			}
		}
		return new MST(e, res);
	}
	final MST directed(final int v) {
		@SuppressWarnings("unchecked")
		final ArrayList<Edge> ed = (ArrayList<Edge>) edge.clone();
		for(int i = 0; i < n; ++i) {
			if(i != v) {
				ed.add(new Edge(i, v, 0));
			}
		}
		int x = 0;
		final int[] par = new int[2 * n], vis = new int[2 * n], link = new int[2 * n];
		Arrays.fill(par, -1);
		Arrays.fill(vis, -1);
		Arrays.fill(link, -1);
		final SkewHeap heap = new SkewHeap(true);
		final SkewHeap.Node[] ins = new SkewHeap.Node[2 * n];
		Arrays.fill(ins, null);
		for(int i = 0; i < ed.size(); i++) {
			final Edge e = ed.get(i);
			ins[e.to] = heap.push(ins[e.to], e.cost, i);
		}
		final ArrayList<Integer> st = new ArrayList<>();
		final IntUnaryOperator go = z -> {
			z = ed.get(ins[z].idx).src;
			while(link[z] != -1) {
				st.add(z);
				z = link[z];
			}
			for(final int p: st) {
				link[p] = z;
			}
			st.clear();
			return z;
		};
		for(int i = n; ins[x] != null; ++i) {
			while(vis[x] == -1) {
				vis[x] = 0;
				x = go.applyAsInt(x);
			}
			while(x != i) {
				final long w = ins[x].key;
				SkewHeap.Node z = heap.pop(ins[x]);
				z = heap.add(z, -w);
				ins[i] = heap.meld(ins[i], z);
				par[x] = i;
				link[x] = i;
				x = go.applyAsInt(x);
			}
			while(ins[x] != null && go.applyAsInt(x) == x) {
				ins[x] = heap.pop(ins[x]);
			}
		}
		for(int i = v; i != -1; i = par[i]) {
			vis[i] = 1;
		}
		long cost = 0;
		final ArrayList<Edge> e = new ArrayList<>();
		for(int i = x; i >= 0; i--) {
			if(vis[i] == 1) {
				continue;
			}
			cost += ed.get(ins[i].idx).cost;
			e.add(ed.get(ins[i].idx));
			for(int j = ed.get(ins[i].idx).to; j != -1 && vis[j] == 0; j = par[j]) {
				vis[j] = 1;
			}
		}
		return new MST(e, cost);
	}
	@Override
	public String toString() {
		final StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; ++i) {
			final int m = get(i).size();
			sb.append(i + ": [");
			for(int j = 0; j < m; ++j) {
				if(weighted) {
					sb.append("(to: " + get(i).get(j).to + ", cost: " + get(i).get(j).cost + ')');
				} else {
					sb.append(get(i).get(j).to);
				}
				if(j + 1 < m) {
					sb.append(", ");
				}
			}
			sb.append(']');
			if(i + 1 < n) {
				sb.append('\n');
			}
		}
		return sb.toString();
	}
}

final class SCC {
	private final int n, indexed;
	private int m;
	private final ArrayList<Edge> edge;
	private final int[] start, ids;
	private int[][] groups;
	private boolean notBuilt;
	SCC(final int n){ this(n, 1); }
	SCC(final int n, final int indexed) {
		this.n = n;
		this.indexed = indexed;
		edge = new ArrayList<>();
		start = new int[n + 1];
		ids = new int[n];
		m = 0;
		notBuilt = true;
	}
	final void addEdge(int from, int to) {
		from -= indexed;
		to -= indexed;
		rangeCheck(from);
		rangeCheck(to);
		edge.add(new Edge(from, to, m++));
		start[from + 1]++;
	}
	final void input(final int m){ IntStream.range(0, m).forEach(i -> addEdge(VvyLw.io.ni(), VvyLw.io.ni())); }
	final int id(final int i) {
		if(notBuilt) {
			throw new UnsupportedOperationException("Graph hasn't been built.");
		}
		rangeCheck(i);
		return ids[i];
	}
	final void build() {
		for(int i = 1; i <= n; i++) {
			start[i] += start[i - 1];
		}
		final Edge[] ed = new Edge[m];
		final int[] count = new int[n + 1];
		System.arraycopy(start, 0, count, 0, n + 1);
		for(final Edge e: edge) {
			ed[count[e.src]++] = e;
		}
		int nowOrd = 0, groupNum = 0, k = 0, ptr = 0;
		final int[] par = new int[n], vis = new int[n], low = new int[n], ord = new int[n];
		Arrays.fill(ord, -1);
		final long[] stack = new long[n];
		for(int i = 0; i < n; i++) {
			if(ord[i] >= 0) {
				continue;
			}
			par[i] = -1;
			stack[ptr++] = 0L << 32 | i;
			while(ptr > 0) {
				long p = stack[--ptr];
				int u = (int) (p & 0xffff_ffffl);
				int j = (int) (p >>> 32);
				if(j == 0) {
					low[u] = ord[u] = nowOrd++;
					vis[k++] = u;
				}
				if(start[u] + j < count[u]) {
					int to = ed[start[u] + j].to;
					stack[ptr++] += 1l << 32;
					if(ord[to] == -1) {
						stack[ptr++] = 0l << 32 | to;
						par[to] = u;
					} else {
						low[u] = min(low[u], ord[to]);
					}
				} else {
					while(j --> 0) {
						final int to = ed[start[u] + j].to;
						if(par[to] == u) {
							low[u] = min(low[u], low[to]);
						}
					}
					if(low[u] == ord[u]) {
						while(true) {
							final int v = vis[--k];
							ord[v] = n;
							ids[v] = groupNum;
							if(v == u) {
								break;
							}
						}
						groupNum++;
					}
				}
			}
		}
		for(int i = 0; i < n; i++) {
			ids[i] = groupNum - 1 - ids[i];
		}
		final int[] counts = new int[groupNum];
		for(final int x: ids) {
			counts[x]++;
		}
		groups = new int[groupNum][];
		for(int i = 0; i < groupNum; i++) {
			groups[i] = new int[counts[i]];
		}
		for(int i = 0; i < n; i++) {
			int cmp = ids[i];
			groups[cmp][--counts[cmp]] = i;
		}
		notBuilt = false;
	}
	final int[][] groups() {
		if(notBuilt) {
			throw new UnsupportedOperationException("Graph hasn't been built.");
		}
		return groups;
	}
	private final void rangeCheck(final int i) {
		if(!Utility.scope(0, i, n - 1)) {
			throw new IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, n));
		}
	}
}

final class LowestCommonAncestor {
	private final int log;
	private final int[] dep, sum;
	private final Graph g;
	private final int[][] table;
	LowestCommonAncestor(final Graph g) {
		this.g = g;
		final int n = g.size();
		dep = new int[n];
		sum = new int[n];
		log = Integer.toBinaryString(n).length();
		table = new int[log][n];
		IntStream.range(0, log).forEach(i -> Arrays.fill(table[i], -1));
		build();
	}
	private final void dfs(final int idx, final int par, final int d) {
		table[0][idx] = par;
		dep[idx] = d;
		for(final Edge el: g.get(idx)) {
			if(el.to != par) {
				sum[el.to] = (int) (sum[idx] + el.cost); 
				dfs(el.to, idx, d + 1);
			}
		}
	}
	private final void build() {
		dfs(0, -1, 0);
		for(int k = 0; k < log - 1; ++k) {
			for(int i = 0; i < table[k].length; ++i) {
				if(table[k][i] == -1) {
					table[k + 1][i] = -1;
				} else {
					table[k + 1][i] = table[k][table[k][i]];
				}
			}
		}
	}
	final int query(int u, int v) {
		if(dep[u] > dep[v]) {
			u ^= v;
			v ^= u;
			u ^= v;
		}
		v = climb(v, dep[v] - dep[u]);
		if(u == v) {
			return u;
		}
		for(int i = log; --i >= 0;) {
			if(table[i][u] != table[i][v]) {
				u = table[i][u];
				v = table[i][v];
			}
		}
		return table[0][u];
	}
	final int climb(int u, final int k) {
		if(dep[u] < k) {
			return -1;
		}
		for(int i = log; --i >= 0;) {
			if(((k >> i) % 2) == 1) {
				u = table[i][u];
			}
		}
		return u;
	}
	final int dist(final int u, final int v){ return sum[u] + sum[v] - 2 * sum[query(u, v)]; }
}

interface DSU {
	int root(final int i);
	int size(final int i);
	int size();
	default boolean same(final int i, final int j){ return root(i) == root(j); }
	boolean unite(int i, int j);
	ArrayList<ArrayList<Integer>> groups();
}

class UnionFind implements DSU {
	protected final int[] par;
	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;
		final 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(); }
}

abstract class MergeUnionFind<T> extends UnionFind {
	MergeUnionFind(final int n){ super(n); }
	abstract void merge(final int i, final int j);
	abstract T get(final int i);
	@Override
	public final 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;
		merge(i, j);
		return true;
	}
}

final class WeightedUnionFind implements DSU {
	private final int[] par;
	private final long[] weight;
	WeightedUnionFind(final int n) {
		par = new int[n];
		weight = new long[n];
		Arrays.fill(par, -1);
	}
	@Override
	public final int root(final int i) {
		if(par[i] < 0) {
			return i;
		}
		final int r = root(par[i]);
		weight[i] += weight[par[i]];
		return par[i] = r;
	}
	final long get(final int i) {
		root(i);
		return weight[i];
	}
	final long diff(final int x, final int y){ return get(y) - get(x); }
	final int unite(int x, int y, long w) {
		w += diff(y, x);
		x = root(x);
		y = root(y);
		if(x == y) {
			return w == 0 ? 0 : -1;
		}
		if(par[x] > par[y]) {
			x ^= y;
			y ^= x;
			x ^= y;
			w = -w;
		}
		par[x] += par[y];
		par[y] = x;
		weight[y] = w;
		return 1;
	}
	@Override
	public final int size(final int i){ return -par[root(i)]; }
	@Override
	public final int size(){ return par.length; }
	@Override
	public final ArrayList<ArrayList<Integer>> groups() {
		final int n = par.length;
		final ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		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;
	}
	// deprecated
	@Override
	public final boolean unite(final int i, final int j){ return unite(i, j, 0) > 0; }
	@Override
	public final String toString(){ return groups().toString(); }
}

final class UndoUnionFind implements DSU {
	private final int[] par;
	private final Stack<Pair<Integer, Integer>> his;
	UndoUnionFind(final int n) {
	    par = new int[n];
	    Arrays.fill(par, -1);
	    his = new Stack<>();
	}
	@Override
	public final boolean unite(int x, int y) {
		x = root(x);
		y = root(y);
		his.add(Pair.of(x, par[x]));
		his.add(Pair.of(y, par[y]));
		if(x == y) {
			return false;
		}
		if(par[x] > par[y]) {
			x ^= y;
			y ^= x;
			x ^= y;
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
	@Override
	public final int root(final int i) {
		if(par[i] < 0) {
			return i;
		}
		return root(par[i]);
	}
	@Override
	public final int size(final int i){ return -par[root(i)]; }
	@Override
	public final int size(){ return par.length; }
	@Override
	public final ArrayList<ArrayList<Integer>> groups() {
		final int n = par.length;
		final ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		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;
	}
	final void undo() {
		final Pair<Integer, Integer> pop1 = his.pop(), pop2 = his.pop();
		par[pop1.first] = pop1.second;
		par[pop2.first] = pop2.second;
	}
	final void snapshot() {
		while(!his.empty()) {
			his.pop();
		}
	}
	final void rollback() {
		while(!his.empty()) {
			undo();
		}
	}
	@Override
	public final String toString(){ return groups().toString(); }
}

final class PrimeTable {
	private final int[] p;
	private final boolean[] sieve;
	PrimeTable(final int n) {
		sieve = new boolean[n + 1];
		Arrays.fill(sieve, true);
		sieve[0] = sieve[1] = false;
		for(int i = 2; i <= n; ++i) {
			if(!sieve[i]) {
				continue;
			}
			for(long j = (long) i * i; j <= n; j += i) {
				sieve[(int) j] = false;
			}
		}
		final int size = (int) IntStream.rangeClosed(0, n).filter(i -> sieve[i]).count();
		int j = 0;
		p = new int[size];
		for(int i = 2; i <= n; ++i) {
			if(sieve[i]) {
				p[j++] = i; 
			}
		}
	}
	final boolean[] table(){ return sieve; }
	final int[] get(){ return p; }
}

final class PrimeFactor {
	private final int[] spf;
	PrimeFactor(final int n) {
		spf = Utility.iota(n + 1).toArray();
		for(int i = 2; i * i <= n; ++i) {
			if(spf[i] != i) {
				continue;
			}
			for(int j = i * i; j <= n; j += i) {
				if(spf[j] == j) {
					spf[j] = i;
				}
			}
		}
	}
	final TreeMap<Integer, Integer> get(int n) {
		final TreeMap<Integer, Integer> m = new TreeMap<>();
		while(n != 1) {
			m.merge(spf[n], 1, (a, b) -> (a + b));
			n /= spf[n];
		}
		return m;
	}
}

final class PrimeCounter {
	private final int sq;
	private final boolean[] p;
	private final int[] psum;
	private final ArrayList<Integer> ps;
	PrimeCounter(final long n) {
		sq = (int) kthRooti(n, 2);
		psum = new int[sq + 1];
		p = new PrimeTable(sq).table();
		for(int i = 1; i <= sq; ++i) {
			psum[i] = psum[i - 1] + (p[i] ? 1 : 0);
		}
		ps = new ArrayList<>();
		for(int i = 1; i <= sq; ++i) {
			if(p[i]) {
				ps.add(i);
			}
		}
	}
	private final long kthRooti(final long n, final int k){ return Utility.kthRoot(n, k); }
	private final long p2(final long x, final long y) {
		if(x < 4) {
			return 0;
		}
		final long a = pi(y);
		final long b = pi(kthRooti(x, 2));
		if(a >= b) {
			return 0;
		}
		long sum = (long) (a - 2) * (a + 1) / 2 - (b - 2) * (b + 1) / 2;
		for(long i = a; i < b; ++i) {
			sum += pi(x / ps.get((int) i));
		}
		return sum;
	}
	private final long phi(final long m, final long a) {
		if(m < 1) {
			return 0;
		}
		if(a > m) {
			return 1;
		}
		if(a < 1) {
			return m;
		}
		if(m <= (long) ps.get((int) (a - 1)) * ps.get((int) (a - 1))) {
			return pi(m) - a + 1;
		}
		if(m <= (long) ps.get((int) (a - 1)) * ps.get((int) (a - 1)) * ps.get((int) (a - 1)) && m <= sq) {
			final long sx = pi(kthRooti(m, 2));
			long ans = pi(m) - (long) (sx + a - 2) * (sx - a + 1) / 2;
			for(long i = a; i < sx; ++i) {
				ans += pi(m / ps.get((int) i));
			}
			return ans;
		}
		return phi(m, a - 1) - phi(m / ps.get((int) (a - 1)), a - 1);
	}
	final long pi(final long n) {
		if(n <= sq) {
			return psum[(int) n];
		}
		final long m = kthRooti(n, 3);
		final long a = pi(m);
		return phi(n, a) + a - 1 - p2(n, m);
	}
}

// N <= 1e18;
final class LongPrime {
	private static final int bsf(final long x){ return Long.numberOfTrailingZeros(x); }
	private static final long gcd(long a, long b) {
		a = abs(a);
		b = abs(b);
		if(a == 0) {
			return b;
		}
		if(b == 0) {
			return a;
		}
		final int shift = bsf(a|b);
		a >>= bsf(a);
		do {
			b >>= bsf(b);
			if(a > b) {
				a ^= b;
				b ^= a;
				a ^= b;
			}
			b -= a;
		} while(b > 0);
		return a << shift;
	}
	static final boolean isPrime(final long n) {
		if(n <= 1) {
			return false;
		}
		if(n == 2) {
			return true;
		}
		if(n % 2 == 0) {
			return false;
		}
		long d = n - 1;
		while(d % 2 == 0) {
			d /= 2;
		}
		final long[] sample = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
		for(final long a: sample) {
			if(n <= a) {
				break;
			}
			long t = d;
			BigInteger y = BigInteger.valueOf(a).modPow(BigInteger.valueOf(t), BigInteger.valueOf(n));
			while(t != n - 1 && !y.equals(BigInteger.ONE) && !y.equals(BigInteger.valueOf(n).subtract(BigInteger.ONE))) {
				y = y.multiply(y).mod(BigInteger.valueOf(n));
				t <<= 1;
			}
			if(!y.equals(BigInteger.valueOf(n).subtract(BigInteger.ONE)) && t % 2 == 0) {
				return false;
			}
		}
		return true;
	}
	private static final long find(final long n) {
		if(isPrime(n)) {
			return n;
		}
		if(n % 2 == 0) {
			return 2;
		}
		long st = 0;
		final LongBinaryOperator f = (x, y) -> { return BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)).add(BigInteger.valueOf(y)).mod(BigInteger.valueOf(n)).longValue(); };
		while(true) {
			st++;
			long x = st, y = f.applyAsLong(x, st);
			while(true) {
				final long p = gcd(y - x + n, n);
				if(p == 0 || p == n) {
					break;
				}
				if(p != 1) {
					return p;
				}
				x = f.applyAsLong(x, st);
				y = f.applyAsLong(f.applyAsLong(y, st), st);
			}
		}
	}
	static final ArrayList<Long> primeFactor(final long n) {
		if(n == 1) return new ArrayList<>();
		final long x = find(n);
		if(x == n) return new ArrayList<>(Arrays.asList(x));
		final ArrayList<Long> l = primeFactor(x), r = primeFactor(n / x);
		l.addAll(r);
		Collections.sort(l);
		return l;
	}
}
// N > 1e18
final class BigPrime {
	private static final int bsf(final long x){ return Long.numberOfTrailingZeros(x); }
	private static final BigInteger gcd(BigInteger a, BigInteger b) {
		a = a.abs();
		b = b.abs();
		if(a.equals(BigInteger.ZERO)) {
			return b;
		}
		if(b.equals(BigInteger.ZERO)) {
			return a;
		}
		final int shift = bsf(a.or(b).longValue());
		a = a.shiftRight(bsf(a.longValue()));
		do {
			b = b.shiftRight(bsf(b.longValue()));
			if(a.compareTo(b) > 0) {
				final BigInteger tmp = b;
				b = a;
				a = tmp;
			}
			b = b.subtract(a);
		} while(b.compareTo(BigInteger.ZERO) > 0);
		return a.shiftLeft(shift);
	}
	static final boolean isPrime(final BigInteger n) {
		if(n.compareTo(BigInteger.ONE) <= 0) {
			return false;
		}
		if(n.equals(BigInteger.TWO)) {
			return true;
		}
		if(n.and(BigInteger.ONE).equals(BigInteger.valueOf(0))) {
			return false;
		}
		BigInteger d = n.subtract(BigInteger.ONE);
		while(d.and(BigInteger.ONE).equals(BigInteger.valueOf(0))) {
			d = d.shiftRight(1);
		}
		final long[] sample = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
		for(final long a: sample) {
			if(n.compareTo(BigInteger.valueOf(a)) <= 0) {
				break;
			}
			BigInteger t = d;
			BigInteger y = BigInteger.valueOf(a).modPow(t, n);
			while(!t.equals(n.subtract(BigInteger.ONE)) && !y.equals(BigInteger.ONE) && !y.equals(n.subtract(BigInteger.ONE))) {
				y = y.multiply(y).mod(n);
				t = t.shiftLeft(1);
			}
			if(!y.equals(n.subtract(BigInteger.ONE)) && t.and(BigInteger.ONE).equals(BigInteger.ZERO)) {
				return false;
			}
		}
		return true;
	}
	private static final BigInteger find(final BigInteger n) {
		if(isPrime(n)) {
			return n;
		}
		if(n.and(BigInteger.ONE).equals(BigInteger.ZERO)) {
			return BigInteger.TWO;
		}
		int st = 0;
		final BiFunction<BigInteger, Integer, BigInteger> f = (x, y) -> { return x.multiply(x).add(BigInteger.valueOf(y)).mod(n); };
		while(true) {
			st++;
			BigInteger x = BigInteger.valueOf(st), y = f.apply(x, st);
			while(true) {
				final BigInteger p = gcd(y.subtract(x).add(n), n);
				if(p.equals(BigInteger.ZERO) || p.equals(n)) {
					break;
				}
				if(!p.equals(BigInteger.ONE)) {
					return p;
				}
				x = f.apply(x, st);
				y = f.apply(f.apply(y, st), st);
			}
		}
	}
	static final ArrayList<BigInteger> primeFactor(final BigInteger n) {
		if(n.equals(BigInteger.ONE)) {
			return new ArrayList<>();
		}
		final BigInteger x = find(n);
		if(x.equals(n)) {
			return new ArrayList<>(Arrays.asList(x));
		}
		final ArrayList<BigInteger> l = primeFactor(x), r = primeFactor(n.divide(x));
		l.addAll(r);
		Collections.sort(l);
		return l;
	}
}

final class ModPrime {
	private final int len, mod;
	private final long[] f, rf;
	ModPrime(final int mod, final int sz) {
		this.mod = mod;
		len = min(sz + 1, mod);
		f = new long[len];
		rf = new long[len];
		init();
	}
	private final long inv(long x) {
		long res = 1, k = mod - 2;
		while(k > 0) {
			if(k % 2 == 1) {
				res = (res * x) % mod;
			}
			x = (x * x) % mod;
			k >>= 1;
		}
		return res;
	}
	private final void init() {
		f[0] = 1;
		for(int i = 0; ++i < len;) {
			f[i] = (f[i - 1] * i) % mod;
		}
		rf[len - 1] = inv(f[len - 1]);
		for(int i = len; --i > 0;) {
			rf[i - 1] = (rf[i] * i) % mod;
		}
	}
	final long C(final int n, final int k) {
		if(k < 0 || n < k) {
			return 0;
		}
		final long a = f[n], b = rf[n - k], c = rf[k], bc = (b * c) % mod;
		return (a * bc) % mod;
	}
	final long P(final int n, final int k) {
		if (k < 0 || n < k) {
			return 0;
		}
		final long a = f[n], b = rf[n - k];
		return (a * b) % mod;
	}
	final long H(final int n, final int k) {
		if (n == 0 && k == 0) {
			return 1;
		}
		return C(n + k - 1, k);
	}
	final long fact(final int n){ return f[n]; }
}

final class EulerPhiTable {
	private final int[] euler;
	EulerPhiTable(final int n) {
		euler = Utility.iota(n + 1).toArray();
		for(int i = 2; i <= n; ++i) {
			if(euler[i] == i) {
				for(int j = i; j <= n; j += i) {
					euler[j] = euler[j] / i * (i - 1);
				}
			}
		}
	}
	final int[] get(){ return euler; }
}

final class DP {
	static final long knapsack01(final int[] a, final long[] v, final int w) {
		final int n = a.length;
		final long[] dp = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = w; j >= a[i]; j--) {
				if(dp[j - a[i]] != Long.MIN_VALUE) {
					if(dp[j - a[i]] + v[i] > dp[j]) {
						dp[j] = dp[j - a[i]] + v[i];
					}
				}
			}
		}
		return Utility.max(dp);
	}
	static final int knapsack01(final long[] a, final int[] v, final long w) {
		final int n = a.length;
		final int s = (int) Utility.sum(v);
		final long[] dp = new long[s + 1];
		Arrays.fill(dp, w + 1);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = s; j >= v[i]; j--) {
				dp[j] = Math.min(dp[j], dp[j - v[i]] + a[i]);
			}
		}
		int res = 0;
		for(int i = 0; i <= s; i++) {
			if(dp[i] <= w) {
				res = i;
			}
		}
		return res;
	}
	private static final long[] knapsack(final int[] a, final long[] v, final int[] m, final int w, final boolean less) {
		final int n = a.length;
		final long[] dp = new long[w + 1], deqv = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		final int[] deq = new int[w + 1];
		for(int i = 0; i < n; ++i) {
			if(a[i] == 0) {
				for(int j = 0; j <= w; ++j) {
					if(dp[j] != Long.MIN_VALUE && (less ? dp[j] + v[i] * m[i] < dp[j] : dp[j] + v[i] * m[i] > dp[j])) {
						dp[j] = dp[j] + v[i] * m[i];
					}
				}
			} else {
				for(int k = 0; k < a[i]; ++k) {
					int s = 0, t = 0;
					for(int j = 0; a[i] * j + k <= w; ++j) {
						if(dp[a[i] * j + k] != Long.MIN_VALUE) {
							final long val = dp[a[i] * j + k] - j * v[i];
							while(s < t && (less ? val < deqv[t - 1] : val > deqv[t - 1])) {
								t--;
							}
							deq[t] = j;
							deqv[t++] = val;
						}
						if(s < t) {
							dp[j * a[i] + k] = deqv[s] + j * v[i];
							if(deq[s] == j - m[i]) {
								s++;
							}
						}
					}
				}
			}
		}
		return dp;
	}
	static final long knapsack(final int[] a, final long[] v, final int[] m, final int w){ return Utility.max(knapsack(a, v, m, w, false)); }
	static final long knapsack(final long[] a, final int[] v, final long[] m, final long w) {
		final int n = a.length;
		final int max = Utility.max(v);
		if(max == 0) {
			return 0;
		}
		final int[] ma = new int[n];
		final long[] mb = new long[n];
		for(int i = 0; i < n; i++) {
			ma[i] = (int) Math.min(m[i], max - 1);
			mb[i] = m[i] - ma[i];
		}
		int sum = 0;
		for(int i = 0; i < n; ++i) {
			sum += ma[i] * v[i];
		}
		final long[] dp = knapsack(v, a, ma, sum, true);
		final int[] id = Utility.iota(n).boxed().sorted((i, j) -> -Long.compare(v[i] * a[j], v[j] * a[i])).mapToInt(i -> i).toArray();
		long res = 0;
		for(int i = 0; i < dp.length; ++i) {
			if(dp[i] > w || dp[i] == Long.MIN_VALUE) {
				continue;
			}
			long rest = w - dp[i], cost = i;
			for(final int j: id) {
				final long get = Math.min(mb[j], rest / a[j]);
				if(get <= 0) {
					continue;
				}
				cost += get * v[j];
				rest -= get * a[j];
			}
			res = Math.max(res, cost);
		}
		return res;
	}
	static final long knapsack(final int[] a, final long[] v, final int w) {
		final int n = a.length;
		final long[] dp = new long[w + 1];
		Arrays.fill(dp, Long.MIN_VALUE);
		dp[0] = 0;
		for(int i = 0; i < n; i++) {
			for(int j = a[i]; j <= w; j++) {
				if(dp[j - a[i]] != Long.MIN_VALUE) {
					if(dp[j - a[i]] + v[i] > dp[j]) {
						dp[j] = dp[j - a[i]] + v[i];
					}
				}
			}
		}
		return Utility.max(dp);
	}
	static final long maxRectangle(final int[] a) {
		final Stack<Integer> sk = new Stack<>();
		final long[] h = new long[a.length + 1];
		for(int i = 0; i < a.length; ++i) {
			h[i] = a[i];
		}
		final int[] l = new int[h.length];
		long res = 0;
		for(int i = 0; i < h.length; i++) {
			while(!sk.isEmpty() && h[sk.peek()] >= h[i]) {
				res = max(res, (i - l[sk.peek()] - 1) * h[sk.pop()]);
			}
			l[i] = sk.isEmpty() ? -1 : sk.peek();
			sk.add(i);
		}
		return res;
	}
	static final long maxRectangle(final long[] a) {
		final Stack<Integer> sk = new Stack<>();
		final long[] h = Arrays.copyOf(a, a.length + 1);
		final int[] l = new int[h.length];
		long res = 0;
		for(int i = 0; i < h.length; i++) {
			while(!sk.isEmpty() && h[sk.peek()] >= h[i]) {
				res = max(res, (i - l[sk.peek()] - 1) * h[sk.pop()]);
			}
			l[i] = sk.isEmpty() ? -1 : sk.peek();
			sk.add(i);
		}
		return res;
	}
	static final int lcs(final String s, final String t) {
		final int n = s.length();
		final int[] dp = new int[n + 1], ndp = new int[n + 1];
		for(int i = 0; i < t.length(); ++i) {
			for(int j = 0; j < n; ++j) {
				if(s.charAt(j) == t.charAt(i)) {
					ndp[j + 1] = dp[j] + 1;
				} else {
					ndp[j + 1] = max(ndp[j], dp[j + 1]);
				}
			}
			Utility.swap(dp, ndp);
		}
		return dp[n];
	}
	static final int[] lis(final int[] a) {
		final int n = a.length;
		List<IntPair> dp = new ArrayList<IntPair>();
		final int[] p = new int[n];
		Arrays.fill(p, -1);
		for(int i = 0; i < n; ++i) {
			final int id = Utility.lowerBound(dp, IntPair.of(a[i], -i));
			if(id != 0) {
				p[i] = -dp.get(id - 1).second.intValue();
			}
			if(id == dp.size()) {
				dp.add(IntPair.of(a[i], -i));
			} else {
				dp.set(id, IntPair.of(a[i], -i));
			}
		}
		final List<Integer> res = new ArrayList<Integer>();
		for(int i = -dp.get(dp.size() - 1).second.intValue(); i != -1; i = p[i]) {
			res.add(i);
		}
		Collections.reverse(res);
		return res.stream().mapToInt(i -> i).toArray();
	}
	static final int[] lis(final long[] a) {
		final int n = a.length;
		List<IntPair> dp = new ArrayList<IntPair>();
		final int[] p = new int[n];
		Arrays.fill(p, -1);
		for(int i = 0; i < n; ++i) {
			final int id = Utility.lowerBound(dp, IntPair.of(a[i], -i));
			if(id != 0) {
				p[i] = -dp.get(id - 1).second.intValue();
			}
			if(id == n) {
				dp.add(IntPair.of(a[i], -i));
			} else {
				dp.set(id, IntPair.of(a[i], -i));
			}
		}
		final List<Integer> res = new ArrayList<Integer>();
		for(int i = -dp.get(dp.size() - 1).second.intValue(); i != -1; i = p[i]) {
			res.add(i);
		}
		Collections.reverse(res);
		return res.stream().mapToInt(i -> i).toArray();
	}
}

final class Matrix implements Cloneable {
	private final int h, w;
	private final long[][] mat;
	Matrix(final int n){ this(n, n); }
	Matrix(final int h, final int w) {
		this.h = h;
		this.w = w;
		mat = new long[h][w];
	}
	Matrix(final int[][] m) {
		this(m.length, m[0].length);
		IntStream.range(0, h).forEach(i -> Arrays.setAll(mat[i], j -> m[i][j]));
	}
	Matrix(final long[][] m) {
		this(m.length, m[0].length);
		IntStream.range(0, h).forEach(i -> Arrays.setAll(mat[i], j -> m[i][j]));
	}
	static final Matrix E(final int n) {
		final Matrix m = new Matrix(n);
		IntStream.range(0, n).forEach(i -> m.set(i, i, 1));
		return m;
	}
	final long[] getH(final int i){ return mat[i]; }
	final long[] getW(final int i){ return IntStream.range(0, h).mapToLong(j -> mat[j][i]).toArray(); }
	final long[][] get(){ return mat; }
	final long get(final int i, final int j){ return mat[i][j]; }
	final void set(final int i, final int j, final long x){ mat[i][j] = x; }
	final Matrix add(final Matrix m) {
		assert h == m.h && w == m.w;
		final Matrix mt = new Matrix(h, w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				mt.set(i, j, mat[i][j] + m.get(i, j));
			}
		}
		return mt;
	}
	final Matrix add(final Matrix m, final long mod) {
		assert h == m.h && w == m.w;
		final Matrix mt = new Matrix(h, w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				mt.set(i, j, Utility.mod(mat[i][j] + m.get(i, j), mod));
			}
		}
		return mt;
	}
	final Matrix sub(final Matrix m) {
		assert h == m.h && w == m.w;
		final Matrix mt = new Matrix(h, w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				mt.set(i, j, mat[i][j] - m.get(i, j));
			}
		}
		return mt;
	}
	final Matrix sub(final Matrix m, final long mod) {
		assert h == m.h && w == m.w;
		final Matrix mt = new Matrix(h, w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				mt.set(i, j, Utility.mod(mat[i][j] - m.get(i, j), mod));
			}
		}
		return mt;
	}
	final Matrix mul(final Matrix m) {
		assert w == m.h;
		final Matrix mt = new Matrix(h, m.w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < m.w; ++j) {
				for(int k = 0; k < w; ++k) {
					mt.set(i, j, mt.get(i, j) + mat[i][k] * m.get(k, j));
				}
			}
		}
		return mt;
	}
	final Matrix mul(final Matrix m, final long mod) {
		assert w == m.h;
		final Matrix mt = new Matrix(h, m.w);
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < m.w; ++j) {
				for(int k = 0; k < w; ++k) {
					mt.set(i, j, Utility.mod(mt.get(i, j) + mat[i][k] * m.get(k, j), mod));
				}
			}
		}
		return mt;
	}
	final Matrix pow(int k) {
		Matrix n = clone();
		Matrix m = Matrix.E(h);
		while(k > 0) {
			if(k % 2 == 1) {
				m = m.mul(n);
			}
			n = n.mul(n);
			k >>= 1;
		}
		return m;
	}
	final Matrix pow(long k, final long mod) {
		Matrix n = clone();
		Matrix m = Matrix.E(h);
		while(k > 0) {
			if(k % 2 == 1) {
				m = m.mul(n, mod);
			}
			n = n.mul(n, mod);
			k >>= 1L;
		}
		return m;
	}
	@Override
	public final boolean equals(final Object o) {
		if(this == o) {
			return true;
		}
		if(o == null || getClass() != o.getClass()) {
			return false;
		}
		final Matrix m = (Matrix) o;
		if(h != m.h || w != m.w) {
			return false;
		}
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				if(mat[i][j] != m.get(i, j)) {
					return false;
				}
			}
		}
		return true;
	}
	@Override
	public final Matrix clone() {
		final Matrix m = new Matrix(h, w);
		for(int i = 0; i < h; ++i) {
			m.mat[i] = Arrays.copyOf(mat[i], w);
		}
		return m;
	}
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		final int interval = String.valueOf(IntStream.range(0, h).mapToLong(i -> IntStream.range(0, w).mapToLong(j -> mat[i][j]).max().getAsLong()).max().getAsLong()).length() + 1;
		for(int i = 0; i < h; ++i) {
			sb.append("[");
			for(int j = 0; j < w; ++j) {
				sb.append(String.format("%" + interval + "d", mat[i][j]));
				if(j + 1 == w) {
					sb.append("]");
				}
			}
			if(i + 1 != h) {
				sb.append("\n");
			}
		}
		return sb.toString();
	}
}

class InclusiveScan {
	protected final int n;
	protected long[] s;
	protected InclusiveScan(final int n) {
		this.n = n;
		s = new long[n + 1];
	}
	InclusiveScan(final int[] a, final LongBinaryOperator op) {
		n = a.length;
		s = Arrays.stream(a).asLongStream().toArray();
		Arrays.parallelPrefix(s, op);
	}
	InclusiveScan(final long[] a, final LongBinaryOperator op) {
		n = a.length;
		s = a.clone();
		Arrays.parallelPrefix(s, op);
	}
	protected final long[] get(){ return s; }
}
final class PrefixSum extends InclusiveScan {
	private boolean built;
	PrefixSum(final int n) {
		super(n);
		built = false;
	}
	PrefixSum(final int[] a) {
		super(a, Long::sum);
		s = Utility.rotate(Arrays.copyOf(s, n + 1), -1);
	}
	PrefixSum(final long[] a) {
		super(a, Long::sum);
		s = Utility.rotate(Arrays.copyOf(s, n + 1), -1);
	}
	final long sum(final int l, final int r){ return s[r] - s[l]; }
	final void add(final int l, final int r, final long x) {
		if(built) {
			throw new UnsupportedOperationException("Prefix Sum has been built.");
		}
		s[l] += x;
		s[r] -= x;
	}
	final long[] build() {
		assert !built;
		Arrays.parallelPrefix(s, Long::sum);
		built = true;
		return Arrays.copyOf(s, n);
	}
}
final class PrefixSum2D {
	private final int h, w;
	private final long[][] data;
	private boolean built;
	PrefixSum2D(final int h, final int w) {
		this.h = h + 3;
		this.w = w + 3;
		data = new long[this.h][this.w];
		built = false;
	}
	PrefixSum2D(final int[][] a) {
		this(a.length, a[0].length);
		for(int i = 0; i < a.length; ++i) {
			for(int j = 0; j < a[i].length; ++j) {
				add(i, j, a[i][j]);
			}
		}
	}
	PrefixSum2D(final long[][] a) {
		this(a.length, a[0].length);
		for(int i = 0; i < a.length; ++i) {
			for(int j = 0; j < a[i].length; ++j) {
				add(i, j, a[i][j]);
			}
		}
	}
	final void add(int i, int j, final long x) {
		if(built) {
			throw new UnsupportedOperationException("Prefix Sum 2D has been built.");
		}
		i++;
		j++;
		if(i >= h || j >= w) {
			return;
		}
		data[i][j] += x;
	}
	final void add(final int i1, final int j1, final int i2, final int j2, final long x) {
		add(i1, j1, x);
		add(i1, j2, -x);
		add(i2, j1, -x);
		add(i2, j2, x);
	}
	final void build() {
		assert !built;
		for(int i = 0; ++i < h;) {
			for(int j = 0; ++j < w;) {
				data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
			}
		}
		built = true;
	}
	final long get(final int i1, final int j1, final int i2, final int j2) {
		if(!built) {
			throw new UnsupportedOperationException("Prefix Sum 2D hasn't been built.");
		}
		return data[i2][j2] - data[i1][j2] - data[i2][j1] + data[i1][j1];
	}
	final long get(final int i, final int j) {
		if(!built) {
			throw new UnsupportedOperationException("Prefix Sum 2D hasn't been built.");
		}
		return data[i + 1][j + 1];
	}
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		for(int i = 0; i < h - 3; ++i) {
			sb.append(get(i, 0));
			for(int j = 0; ++j < w - 3;) {
				sb.append(" " + get(i, j));
			}
			if(i + 1 < h) {
				sb.append('\n');
			}
		}
		return sb.toString();
	}
}

final class SuffixArray extends ArrayList<Integer> {
	private final String vs;
	SuffixArray(final String vs, final boolean compress) {
		this.vs = vs;
		final int[] newVS = new int[vs.length() + 1];
		if(compress) {
			final List<Integer> xs = vs.chars().sorted().distinct().boxed().collect(Collectors.toList());
			for(int i = 0; i < vs.length(); ++i) {
				newVS[i] = Utility.lowerBound(xs, (int) vs.charAt(i)) + 1;
			}
		} else {
			final int d = vs.chars().min().getAsInt();
			for(int i = 0; i < vs.length(); ++i) {
				newVS[i] = vs.charAt(i) - d + 1;
			}
		}
		this.addAll(Arrays.stream(SAIS(newVS)).boxed().collect(Collectors.toList()));
	}
	private final int[] SAIS(final int[] s) {
		final int n = s.length;
		final int[] ret = new int[n];
		final boolean[] isS = new boolean[n], isLMS = new boolean[n];
		int m = 0;
		for(int i = n - 2; i >= 0; i--) {
			isS[i] = (s[i] > s[i + 1]) || (s[i] == s[i + 1] && isS[i + 1]);
			m += (isLMS[i + 1] = isS[i] && !isS[i + 1]) ? 1 : 0;
		}
		final Consumer<ArrayList<Integer>> inducedSort = (lms) -> {
			final int upper = Arrays.stream(s).max().getAsInt();
			final int[] l = new int[upper + 2], r = new int[upper + 2];
			for(final int v: s) {
				++l[v + 1];
				++r[v];
			}
			Arrays.parallelPrefix(l, (x, y) -> x + y);
			Arrays.parallelPrefix(r, (x, y) -> x + y);
			Arrays.fill(ret, -1);
			for(int i = lms.size(); --i >= 0;) {
				ret[--r[s[lms.get(i)]]] = lms.get(i);
			}
			for(final int v: ret) {
				if(v >= 1 && isS[v - 1]) {
					ret[l[s[v - 1]]++] = v - 1;
				}
			}
			Arrays.fill(r, 0);
			for(final int v: s) {
				++r[v];
			}
			Arrays.parallelPrefix(r, (x, y) -> x + y);
			for(int k = ret.length - 1, i = ret[k]; k >= 1; i = ret[--k]) {
				if(i >= 1 && !isS[i - 1]) {
					ret[--r[s[i - 1]]] = i - 1;
				}
			}
		};
		final ArrayList<Integer> lms = new ArrayList<>(), newLMS = new ArrayList<>();
		for(int i = 0; ++i < n;) {
			if(isLMS[i]) {
				lms.add(i);
			}
		}
		inducedSort.accept(lms);
		for(int i = 0; i < n; ++i) {
			if(!isS[ret[i]] && ret[i] > 0 && isS[ret[i] - 1]) {
				newLMS.add(ret[i]);
			}
		}
		final BiPredicate<Integer, Integer> same = (a, b) -> {
			if(s[a++] != s[b++]) {
				return false;
			}
			while(true) {
				if(s[a] != s[b]) {
					return false;
				}
				if(isLMS[a] || isLMS[b]) {
					return isLMS[a] && isLMS[b];
				}
				a++;
				b++;
			}
		};
		int rank = 0;
		ret[n - 1] = 0;
		for(int i = 0; ++i < m;) {
			if(!same.test(newLMS.get(i - 1), newLMS.get(i))) {
				++rank;
			}
			ret[newLMS.get(i)] = rank;
		}
		if(rank + 1 < m) {
			final int[] newS = new int[m];
			for(int i = 0; i < m; ++i) {
				newS[i] = ret[lms.get(i)];
			}
			final var lmsSA = SAIS(newS);
			IntStream.range(0, m).forEach(i -> newLMS.set(i, lms.get(lmsSA[i])));
		}
		inducedSort.accept(newLMS);
		return ret;
	}
	private final boolean ltSubstr(final String t, int si, int ti) {
		final int sn = vs.length(), tn = t.length();
		while(si < sn && ti < tn) {
			if(vs.charAt(si) < t.charAt(ti)) {
				return true;
			}
			if(vs.charAt(si) > t.charAt(ti)) {
				return false;
			}
			++si;
			++ti;
		}
		return si >= sn && ti < tn;
	}
	final int lowerBound(final String t) {
		int ok = this.size(), ng = 0;
		while(ok - ng > 1) {
			final int mid = (ok + ng) / 2;
			if(ltSubstr(t, this.get(mid), 0)) {
				ng = mid;
			} else {
				ok = mid;
			}
		}
		return ok;
	}
	final Pair<Integer, Integer> equalRange(final String t) {
		final int low = lowerBound(t);
		int ng = low - 1, ok = this.size();
		final StringBuilder sb = new StringBuilder(t);
		sb.setCharAt(t.length() - 1, (char)(sb.charAt(sb.length() - 1) - 1));
		final String u = sb.toString();
		while(ok - ng > 1) {
			final int mid = (ok + ng) / 2;
			if(ltSubstr(u, this.get(mid), 0)) {
				ng = mid;
			} else {
				ok = mid;
			}
		}
		final int end = this.size() - 1;
		this.add(end, this.get(end) - 1);
		return Pair.of(low, ok);
	}
	final int[] lcpArray() {
		final int n = this.size() - 1;
		final int[] lcp = new int[n + 1], rank = new int[n + 1];
		for(int i = 0; i <= n; ++i) {
			rank[this.get(i)] = i;
		}
		int h = 0;
		for(int i = 0; i <= n; ++i) {
			if(rank[i] < n) {
				final int j = this.get(rank[i] + 1);
				for(; j + h < n && i + h < n; ++h) {
					if(vs.charAt(j + h) != vs.charAt(i + h)) {
						break;
					}
				}
				lcp[rank[i] + 1] = h;
				if(h > 0) {
					h--;
				}
			}
		}
		return lcp;
	}
	@Override
	public final String toString() { 
		final StringBuilder sb = new StringBuilder();
		for(int i = 0; i < this.size(); ++i) {
			sb.append(i + ":[" + this.get(i) + "]");
			for(int j = this.get(i); j < vs.length(); ++j) {
				sb.append(" " + vs.charAt(j));
			}
			if(i + 1 != this.size()) {
				sb.append("\n");
			}
		}
		return sb.toString();
	}
}

final class MyDeque<T> implements Iterable<T> {
	private int n, head, tail;
	private Object[] buf;
	MyDeque(){ this(1 << 17); }
	private MyDeque(final int n) {
		this.n = n;
		head = tail = 0;
		buf = new Object[n];
	}
	MyDeque(final T[] a) {
		this(a.length);
		Arrays.stream(a).forEach(this::add);
	}
	private final int next(final int index) {
		final int next = index + 1;
		return next == n ? 0 : next;
	}
	private final int prev(final int index) {
		final int prev = index - 1;
		return prev == -1 ? n - 1 : prev;
	}
	private final int index(final int i) {
		final int size = size();
		assert i < size;
		final int id = head + i;
		return n <= id ? id - n : id;
	}
	private final void arraycopy(final int fromId, final T[] a, final int from, final int len) {
		assert fromId + len <= size();
		final int h = index(fromId);
		if(h + len < n) {
			System.arraycopy(buf, h, a, from, len);
		} else {
			final int back = n - h;
			System.arraycopy(buf, h, a, from, back);
			System.arraycopy(buf, 0, a, from + back, len - back);
		}
	}
	@SuppressWarnings("unchecked")
	private final void extend() {
		final Object[] tmp = new Object[n << 1];
		arraycopy(0, (T[]) tmp, 0, size());
		buf = tmp;
		n = buf.length;
	}
	final boolean isEmpty(){ return size() == 0; }
	final int size() {
		final int size = tail - head;
		return size < 0 ? size + n : size;
	}
	final void addFirst(final T x) {
		if(prev(head) == tail) {
			extend();
		}
		head = prev(head);
		buf[head] = x;
	}
	final void addLast(final T x) {
		if(next(tail) == head) {
			extend();
		}
		buf[tail] = x;
		tail = next(tail);
	}
	final void removeFirst() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		head = next(head);
	}
	final void removeLast() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		tail = prev(tail);
	}
	@SuppressWarnings("unchecked")
	final T pollFirst() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		final T ans = (T) buf[head];
		head = next(head);
		return ans;
	}
	@SuppressWarnings("unchecked")
	final T pollLast() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		tail = prev(tail);
		return (T) buf[tail];
	}
	final T peekFirst(){ return get(0); }
	final T peekLast(){ return get(n - 1); }
	@SuppressWarnings("unchecked")
	final T get(final int i){ return (T) buf[index(i)]; }
	final void set(final int i, final T x){ buf[index(i)] = x; }
	final void add(final T x){ addLast(x); }
	final T poll(){ return pollFirst(); }
	final T peek(){ return peekFirst(); }
	@SuppressWarnings("unchecked")
	final void swap(final int a, final int b) {
		final int i = index(a), j = index(b);
		final T num = (T) buf[i];
		buf[i] = buf[j];
		buf[j] = num;
	}
	final void clear(){ head = tail = 0; }
	@SuppressWarnings("unchecked")
	final T[] toArray() {
		final Object[] array = new Object[size()];
		arraycopy(0, (T[]) array, 0, size());
		return (T[]) array;
	}
	@Override
	public final String toString(){ return Arrays.toString(toArray()); }
	@Override
	public final Iterator<T> iterator(){ return new DequeIterator(); }
	private class DequeIterator implements Iterator<T> {
		private int now = head;
		private int rem = size();
		@Override
		public boolean hasNext(){ return rem > 0; }
		@Override
		public final T next() {
			if(!hasNext()) {
				throw new NoSuchElementException();
			}
			@SuppressWarnings("unchecked")
			final T res = (T) buf[now];
			now = (now + 1) % n;
			rem--;
			return res;
		}
		@Override
		public final void remove() {
			if(isEmpty()) {
				throw new IllegalStateException();
			}
			now = (now - 1 + n) % n;
			buf[now] = null;
			head = (head + 1) % n;
			rem++;
		}
	}
}
final class IntDeque {
	private int n, head, tail;
	private long[] buf;
	IntDeque(){ this(1 << 17); }
	private IntDeque(final int n) {
		this.n = n;
		head = tail = 0;
		buf = new long[n];
	}
	IntDeque(final int[] a) {
		this(a.length);
		Arrays.stream(a).forEach(this::add);
	}
	IntDeque(final long[] a) {
		this(a.length);
		Arrays.stream(a).forEach(this::add);
	}
	private final int next(final int index) {
		final int next = index + 1;
		return next == n ? 0 : next;
	}
	private final int prev(final int index) {
		final int prev = index - 1;
		return prev == -1 ? n - 1 : prev;
	}
	private final int index(final int i) {
		final int size = size();
		assert i < size;
		final int id = head + i;
		return n <= id ? id - n : id;
	}
	private final void arraycopy(final int fromId, final long[] a, final int from, final int len) {
		assert fromId + len <= size();
		final int h = index(fromId);
		if(h + len < n) {
			System.arraycopy(buf, h, a, from, len);
		} else {
			final int back = n - h;
			System.arraycopy(buf, h, a, from, back);
			System.arraycopy(buf, 0, a, from + back, len - back);
		}
	}
	private final void extend() {
		final long[] tmp = new long[n << 1];
		arraycopy(0, tmp, 0, size());
		buf = tmp;
		n = buf.length;
	}
	final boolean isEmpty(){ return size() == 0; }
	final int size() {
		final int size = tail - head;
		return size < 0 ? size + n : size;
	}
	final void addFirst(final long x) {
		if(prev(head) == tail) {
			extend();
		}
		head = prev(head);
		buf[head] = x;
	}
	final void addLast(final long x) {
		if(next(tail) == head) {
			extend();
		}
		buf[tail] = x;
		tail = next(tail);
	}
	final void removeFirst() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		head = next(head);
	}
	final void removeLast() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		tail = prev(tail);
	}
	final long pollFirst() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		final long ans = buf[head];
		head = next(head);
		return ans;
	}
	final long pollLast() {
		if(head == tail) {
			throw new NoSuchElementException("Deque is empty");
		}
		tail = prev(tail);
		return buf[tail];
	}
	final long peekFirst(){ return get(0); }
	final long peekLast(){ return get(n - 1); }
	final long get(final int i){ return buf[index(i)]; }
	final void set(final int i, final long x){ buf[index(i)] = x; }
	final void add(final long x){ addLast(x); }
	final long poll(){ return pollFirst(); }
	final long peek(){ return peekFirst(); }
	final void swap(final int a, final int b) {
		final int i = index(a);
		final int j = index(b);
		final long num = buf[i];
		buf[i] = buf[j];
		buf[j] = num;
	}
	final void clear(){ head = tail = 0; }
	final long[] toArray() {
		final long[] array = new long[size()];
		arraycopy(0, array, 0, size());
		return array;
	}
	@Override
	public final String toString(){ return Arrays.toString(toArray()); }
}

final class AVLTree<T extends Comparable<? super T>> {
	static final class Node<T extends Comparable<? super T>> {
		T val;
		@SuppressWarnings("unchecked")
		Node<T>[] ch = new Node[2];
		int dep, size;
		Node(final T val, final Node<T> l, final Node<T> r) {
			this.val = val;
			dep = size = 1;
			ch[0] = l;
			ch[1] = r;
		}
	}
	private Node<T> root;
	private final int depth(final Node<T> t){ return t == null ? 0 : t.dep; }
	private final int count(final Node<T> t){ return t == null ? 0 : t.size; }
	private final Node<T> update(final Node<T> t) {
		t.dep = max(depth(t.ch[0]), depth(t.ch[1])) + 1;
		t.size = count(t.ch[0]) + count(t.ch[1]) + 1;
		return t;
	}
	private final Node<T> rotate(Node<T> t, final int b) {
		Node<T> s = t.ch[1 - b];
		t.ch[1 - b] = s.ch[b];
		s.ch[b] = t;
		t = update(t);
		s = update(s);
		return s;
	}
	private final Node<T> fetch(Node<T> t) {
		if(t == null) {
			return t;
		}
		if(depth(t.ch[0]) - depth(t.ch[1]) == 2) {
			if(depth(t.ch[0].ch[1]) > depth(t.ch[0].ch[0])) {
				t.ch[0] = rotate(t.ch[0], 0);
			}
			t = rotate(t, 1);
		}
		else if(depth(t.ch[0]) - depth(t.ch[1]) == -2) {
			if (depth(t.ch[1].ch[0]) > depth(t.ch[1].ch[1])) {
				t.ch[1] = rotate(t.ch[1], 1);
			}
			t = rotate(t, 0);
		}
		return t;
	}
	private final Node<T> insert(final Node<T> t, final int k, final T v) {
		if(t == null) {
			return new Node<T>(v, null, null);
		}
		final int c = count(t.ch[0]), b = (k > c) ? 1 : 0;
		t.ch[b] = insert(t.ch[b], k - (b == 1 ? (c + 1) : 0), v);
		update(t);
		return fetch(t);
	}
	private final Node<T> erase(final Node<T> t) {
		if(t == null || t.ch[0] == null && t.ch[1] == null) {
			return null;
		}
		if(t.ch[0] == null || t.ch[1] == null) {
			return t.ch[t.ch[0] == null ? 1 : 0];
		}
		return fetch(update(new Node<T>(find(t.ch[1], 0).val, t.ch[0], erase(t.ch[1], 0))));
	}
	private final Node<T> erase(Node<T> t, final int k) {
		if(t == null) {
			return null;
		}
		final int c = count(t.ch[0]);
		if(k < c) {
			t.ch[0] = erase(t.ch[0], k);
			t = update(t);
		}
		else if(k > c) {
			t.ch[1] = erase(t.ch[1], k - (c + 1));
			t = update(t);
		}
		else {
			t = erase(t);
		}
		return fetch(t);
	}
	private final Node<T> find(final Node<T> t, final int k) {
		if(t == null) {
			return t;
		}
		final int c = count(t.ch[0]);
		return k < c ? find(t.ch[0], k) : k == c ? t : find(t.ch[1], k - (c + 1));
	}
	private final int cnt(final Node<T> t, final T v) {
		if(t == null) {
			return 0;
		}
		if(t.val.compareTo(v) < 0) {
			return count(t.ch[0]) + 1 + cnt(t.ch[1], v);
		}
		if(t.val.equals(v)) {
			return count(t.ch[0]);
		}
		return cnt(t.ch[0], v);
	}
	AVLTree(){ root = null; }
	final void add(final T val){ root = insert(root, cnt(root, val), val); }
	final void remove(final int k){ root = erase(root, k); }
	final T get(final int k){ return find(root, k).val; }
	final int count(final T val){ return cnt(root, val); }
	final int size(){ return root.size; }
	@SuppressWarnings("unchecked")
	final T[] toArray(){ return (T[]) IntStream.range(0, root.size).mapToObj(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < root.size;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}

final class DoubleEndedPriorityQueue<T extends Number> {
	private final ArrayList<T> d;
	DoubleEndedPriorityQueue(final T[] d) {
		this.d = (ArrayList<T>) Arrays.stream(d).collect(Collectors.toList());
		makeHeap();
	}
	private final void makeHeap() {
		for(int i = d.size(); i-- > 0;) {
			if (i % 2 == 1 && d.get(i - 1).longValue() < d.get(i).longValue()) {
				Collections.swap(d, i - 1, i);
			}
			up(down(i), i);
		}
	}
	private final int down(int k) {
		final int n = d.size();
		if(k % 2 == 1) {
			while(2 * k + 1 < n) {
				int c = 2 * k + 3;
				if(n <= c || d.get(c - 2).longValue() < d.get(c).longValue()) {
					 c -= 2;
				}
				if(c < n && d.get(c).longValue() < d.get(k).longValue()) {
					Collections.swap(d, k, c);
					k = c;
				}
				else {
					break;
				}
			}
		} else {
			while(2 * k + 2 < n) {
				int c = 2 * k + 4;
				if(n <= c || d.get(c).longValue() < d.get(c - 2).longValue()) {
					c -= 2;
				}
				if(c < n && d.get(k).longValue() < d.get(c).longValue()) {
					Collections.swap(d, k, c);
					k = c;
				}
				else {
					break;
				}
			}
		}
		return k;
	}
	private final int up(int k, final int root) {
		if((k | 1) < d.size() && d.get(k & ~1).longValue() < d.get(k | 1).longValue()) {
			Collections.swap(d, k & ~1, k | 1);
			k ^= 1;
		}
		int p;
		while(root < k && d.get(p = parent(k)).longValue() < d.get(k).longValue()) {
			Collections.swap(d, p, k);
			k = p;
		}
		while(root < k && d.get(k).longValue() < d.get(p = parent(k) | 1).longValue()) {
			Collections.swap(d, p, k);
			k = p;
		}
		return k;
	}
	private final int parent(final int k){ return ((k >> 1) - 1) & ~1; }
	private final void popBack(final ArrayList<T> d){ d.remove(d.size() - 1); } 
	final void push(final T x) {
		final int k = d.size();
		d.add(x);
		up(k, 1);
	}
	final T popMin() {
		final T res = getMin();
		if(d.size() < 3) {
			popBack(d); 
		} else {
			Collections.swap(d, 1, d.size() - 1);
			popBack(d);
			up(down(1), 1);
		}
		return res;
	}
	final T popMax() {
		final T res = getMax();
		if(d.size() < 2) { 
			popBack(d);
		} else {
			Collections.swap(d, 0, d.size() - 1);
			popBack(d);
			up(down(0), 1);
		}
		return res;
	}
	final T getMin(){ return d.size() < 2 ? d.get(0) : d.get(1); }
	final T getMax(){ return d.get(0); }
	final int size(){ return d.size(); }
	final boolean isEmpty(){ return d.isEmpty(); }
}

final class FenwickTree {
	private final int n;
	private final long[] data;
	FenwickTree(final int n) {
		this.n = n + 2;
		data = new long[this.n + 1];
	}
	FenwickTree(final int[] a) {
		this(a.length);
		IntStream.range(0, a.length).forEach(i -> add(i, a[i]));
	}
	FenwickTree(final long[] a) {
		this(a.length);
		IntStream.range(0, a.length).forEach(i -> add(i, a[i]));
	}
	final long sum(int k) {
		if(k < 0) {
			return 0;
		}
		long ret = 0;
		for(++k; k > 0; k -= k & -k) {
			ret += data[k];
		}
		return ret;
	}
	final long sum(final int l, final int r){ return sum(r) - sum(l - 1); }
	final long get(final int k){ return sum(k) - sum(k - 1); }
	final void add(int k, final long x) {
		for(++k; k < n; k += k & -k) {
			data[k] += x;
		}
	}
	final void add(final int l, final int r, final long x) {
		add(l, x);
		add(r + 1, -x);
	}
	private final int lg(final int n){ return 31 - Integer.numberOfLeadingZeros(n); }
	final int lowerBound(long w) {
		if(w <= 0) {
			return 0;
		}
		int x = 0;
		for(int k = 1 << lg(n); k > 0; k >>= 1) {
			if(x + k <= n - 1 && data[x + k] < w) {
				w -= data[x + k];
				x += k;
			}
		}
		return x;
	}
	final int upperBound(long w) {
		if(w < 0) {
			return 0;
		}
		int x = 0;
		for(int k = 1 << lg(n); k > 0; k >>= 1) {
			if(x + k <= n - 1 && data[x + k] <= w) {
				w -= data[x + k];
				x += k;
			}
		}
		return x;
	}
	public final long[] toArray(){ return IntStream.rangeClosed(0, n).mapToLong(this::sum).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(sum(0));
		for(int i = 0; ++i < n - 2;) {
			sb.append(", " + sum(i));
		}
		return "[" + sb.toString() + "]";
	}
}
final class RangeBIT {
	private final int n;
	private final FenwickTree a, b;
	RangeBIT(final int n) {
		this.n = n;
		a = new FenwickTree(n + 1);
		b = new FenwickTree(n + 1);
	}
	RangeBIT(final int[] arr) {
		this(arr.length);
		for(int i = 0; i < arr.length; ++i) {
			add(i, i, arr[i]);
		}
	}
	RangeBIT(final long[] arr) {
		this(arr.length);
		for(int i = 0; i < arr.length; ++i) {
			add(i, i, arr[i]);
		}
	}
	final void add(final int l, final int r, final long x) {
		a.add(l, x);
		a.add(r, -x);
		b.add(l, x * (1 - l));
		b.add(r, x * (r - 1));
	}
	final long get(final int i){ return sum(i, i + 1); }
	final long sum(int l, int r) {
		l--;
		r--;
		return a.sum(r) * r + b.sum(r) - a.sum(l) * l - b.sum(l);
	}
	public final long[] toArray(){ return IntStream.range(0, n).mapToLong(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < n;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}

final class SegmentTree<T> {
	private int n = 1, rank = 0;
	private final int fini;
	private final BinaryOperator<T> op;
	private final T e;
	private final Object[] dat;
	SegmentTree(final int fini, final BinaryOperator<T> op, final T e) {
		this.fini = fini;
		this.op = op;
		this.e = e;
		while(this.fini > n) {
			n <<= 1;
			rank++;
		}
		dat = new Object[2 * n];
		Arrays.fill(dat, e);
	}
	SegmentTree(final T[] a, final BinaryOperator<T> op, final T e) {
		this(a.length, op, e);
		IntStream.range(0, a.length).forEach(i -> update(i, a[i]));
	}
	@SuppressWarnings("unchecked")
	final void update(int i, final T x) {
		i += n;
		dat[i] = x;
		do {
			i >>= 1;
			dat[i] = op.apply((T) dat[2 * i], (T) dat[2 * i + 1]);
		} while(i > 0);
	}
	final T get(final int i){ return query(i, i + 1); }
	@SuppressWarnings("unchecked")
	final T query(int a, int b) {
		T l = e, r = e;
		for(a += n, b += n; a < b; a >>= 1, b >>= 1) {
			if(a % 2 == 1) {
				l = op.apply(l, (T) dat[a++]);
			}
			if(b % 2 == 1) {
				r = op.apply((T) dat[--b], r);
			}
		}
		return op.apply(l, r);
	}
	@SuppressWarnings("unchecked")
	final T all(){ return (T) dat[1]; }
	@SuppressWarnings("unchecked")
	final int findLeft(final int r, final Predicate<T> fn) {
		if(r == 0) {
			return 0;
		}
		int h = 0, i = r + n;
		T val = e;
		for(; h <= rank; h++) {
			if(((i >> h) & 1) != 0) {
				final T val2 = op.apply(val, (T) dat[i >> (h ^ 1)]);
				if(fn.test(val2)) {
					i -= 1 << h;
					if(i == n) {
						return 0;
					}
					val = val2;
				} else {
					break;
				}
			}
		}
		for(; h-- > 0;) {
			final T val2 = op.apply(val, (T) dat[(i >> h) - 1]);
			if(fn.test(val2)) {
				i -= 1 << h;
				if(i == n) {
					return 0;
				}
				val = val2;
			}
		}
		return i - n;
	}
	@SuppressWarnings("unchecked")
	final int findRight(final int l, final Predicate<T> fn) {
		if(l == fini) {
			return fini;
		}
		int h = 0, i = l + n;
		T val = e;
		for(; h <= rank; h++) {
			if(((i >> h) & 1) != 0){
				final T val2 = op.apply(val, (T) dat[i >> h]);
				if(fn.test(val2)) {
					i += 1 << h;
					if(i == n * 2) {
						return fini;
					}
					val = val2;
				} else {
					break;
				}
			}
		}
		for(; h-- > 0;) {
			final T val2 = op.apply(val, (T) dat[i >> h]);
			if(fn.test(val2)) {
				i += 1 << h;
				if(i == n * 2) {
					return fini;
				}
				val = val2;
			}
		}
		return min(i - n, fini);
	}
	@SuppressWarnings("unchecked")
	final T[] toArray(){ return (T[]) IntStream.range(0, fini).mapToObj(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < fini;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}

class LazySegmentTree<T, U extends Comparable<? super U>> {
	private final int n;
	private int sz, h;
	private final Object[] data, lazy;
	private final BinaryOperator<T> f;
	private final BiFunction<T, U, T> map;
	private final BinaryOperator<U> comp;
	private final T e;
	private final U id;
	@SuppressWarnings("unchecked")
	private final void update(final int k){ data[k] = f.apply((T) data[2 * k], (T) data[2 * k + 1]); }
	@SuppressWarnings("unchecked")
	private final void allApply(final int k, final U x) {
		data[k] = map.apply((T) data[k], x);
		if(k < sz) {
			lazy[k] = comp.apply((U) lazy[k], x);
		}
	}
	@SuppressWarnings("unchecked")
	private final void propagate(final int k) {
		if(!lazy[k].equals(id)) {
			allApply(2 * k, (U) lazy[k]);
			allApply(2 * k + 1, (U) lazy[k]);
			lazy[k] = id;
		}
	}
	LazySegmentTree(final int n, final BinaryOperator<T> f, final BiFunction<T, U, T> map, final BinaryOperator<U> comp, final T e, final U id) {
		this.n = n;
		this.f = f;
		this.map = map;
		this.comp = comp;
		this.e = e;
		this.id = id;
		sz = 1;
		h = 0;
		while(sz < n) {
			sz <<= 1;
			h++;
		}
		data = new Object[2 * sz];
		Arrays.fill(data, e);
		lazy = new Object[2 * sz];
		Arrays.fill(lazy, id);
	}
	LazySegmentTree(final T[] a, final BinaryOperator<T> f, final BiFunction<T, U, T> map, final BinaryOperator<U> comp, final T e, final U id) {
		this(a.length, f, map, comp, e, id);
		build(a);
	}
	final void build(final T[] a) {
		assert n == a.length;
		for(int k = 0; k < n; ++k) {
			data[k + sz] = a[k];
		}
		for(int k = sz; --k > 0;) {
			update(k);
		}
	}
	final void set(int k, final T x) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		data[k] = x;
		for(int i = 0; ++i <= h;) {
			update(k >> i);
		}
	}
	@SuppressWarnings("unchecked")
	final T get(int k) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		return (T) data[k];
	}
	@SuppressWarnings("unchecked")
	final T query(int l, int r) {
		if(l >= r) {
			return e;
		}
		l += sz;
		r += sz;
		for(int i = h; i > 0; i--) {
			if(((l >> i) << i) != l) {
				propagate(l >> i);
			}
			if(((r >> i) << i) != r) {
				propagate((r - 1) >> i);
			}
		}
		T l2 = e, r2 = e;
		for(; l < r; l >>= 1, r >>= 1) {
			if(l % 2 == 1) {
				l2 = f.apply(l2, (T) data[l++]);
			}
			if(r % 2 == 1) {
				r2 = f.apply((T) data[--r], r2);
			}
		}
		return f.apply(l2, r2);
	}
	@SuppressWarnings("unchecked")
	final T all(){ return (T) data[1]; }
	@SuppressWarnings("unchecked")
	final void apply(int k, final U x) {
		k += sz;
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
		data[k] = map.apply((T) data[k], x);
		for(int i = 0; ++i <= h;) {
			update(k >> i);
		}
	}
	final void apply(int l, int r, final U x) {
		if(l >= r) {
			return;
		}
		l += sz;
		r += sz;
		for(int i = h; i > 0; i--) {
			if(((l >> i) << i) != l) {
				propagate(l >> i);
			}
			if(((r >> i) << i) != r) {
				propagate((r - 1) >> i);
			}
		}
		int l2 = l, r2 = r;
		for(; l < r; l >>= 1, r >>= 1) {
			if(l % 2 == 1) {
				allApply(l++, x);
			}
			if(r % 2 == 1) {
				allApply(--r, x);
			}
		}
		l = l2;
		r = r2;
		for(int i = 0; ++i <= h;) {
			if(((l >> i) << i) != l) {
				update(l >> i);
			}
			if(((r >> i) << i) != r) {
				update((r - 1) >> i);
			}
		}
	}
	@SuppressWarnings("unchecked")
	final int findFirst(int l, final Predicate<T> fn) {
		if(l >= n) {
			return n;
		}
		l += sz;
		for(int i = h; i > 0; i--) {
			propagate(l >> i);
		}
		T sum = e;
		do {
			while((l & 1) == 0) {
				l >>= 1;
			}
			if(fn.test(f.apply(sum, (T) data[l]))) {
				while(l < sz) {
					propagate(l);
					l <<= 1;
					final T nxt = f.apply(sum, (T) data[l]);
					if(!fn.test(nxt)) {
						sum = nxt;
						l++;
					}
				}
				return l + 1 - sz;
			}
			sum = f.apply(sum, (T) data[l++]);
		} while((l & -l) != l);
		return n;
	}
	@SuppressWarnings("unchecked")
	final int findLast(int r, final Predicate<T> fn) {
		if(r <= 0) {
			return -1;
		}
		r += sz;
		for(int i = h; i > 0; i--) {
			propagate((r - 1) >> i);
		}
		T sum = e;
		do {
			r--;
			while(r > 1 && r % 2 == 1) {
				r >>= 1;
			}
			if(fn.test(f.apply((T) data[r], sum))) {
				while(r < sz) {
					propagate(r);
					r = (r << 1) + 1;
					final T nxt = f.apply((T) data[r], sum);
					if(!fn.test(nxt)) {
						sum = nxt;
						r--;
					}
				}
				return r - sz;
			}
			sum = f.apply((T) data[r], sum);
		} while((r & -r) != r);
		return -1;
	}
	final void clear(){ Arrays.fill(data, e); }
	@SuppressWarnings("unchecked")
	public final T[] toArray(){ return (T[]) IntStream.range(0, n).mapToObj(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < n;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}
final class Zwei<T> implements Cloneable {
	public T first, second;
	private Zwei(final T first, final T second) {
		this.first = first;
		this.second = second;
	}
	static final <T> Zwei<T> of(final T f, final T s){ return new Zwei<>(f, s); }
	@Override
	public final boolean equals(final Object o) {
		if(this == o) {
			return true;
		}
		if(o == null || getClass() != o.getClass()) {
			return false;
		}
		final Zwei<?> z = (Zwei<?>) o;
		return first.equals(z.first) && second.equals(z.second);
	}
	@Override
	public final int hashCode(){ return Objects.hash(first, second); }
	@Override
	public final String toString(){ return String.valueOf(first); }
	@SuppressWarnings("unchecked")
	@Override
	public final Zwei<T> clone() {
		try {
			return (Zwei<T>) super.clone();
		} catch(final CloneNotSupportedException e){
			e.printStackTrace();
		}
		throw new Error();
	}
}
final class RAMX extends LazySegmentTree<Long, Long> {
	RAMX(final int[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::max, Long::sum, Long::sum, Long.valueOf(Long.MIN_VALUE), Long.valueOf(0)); }
	RAMX(final long[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::max, Long::sum, Long::sum, Long.valueOf(Long.MIN_VALUE), Long.valueOf(0)); }
}
final class RAMN extends LazySegmentTree<Long, Long> {
	RAMN(final int[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::min, Long::sum, Long::sum, Long.valueOf(Long.MAX_VALUE), Long.valueOf(0)); }
	RAMN(final long[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::min, Long::sum, Long::sum, Long.valueOf(Long.MAX_VALUE), Long.valueOf(0)); }
}
final class RASM extends LazySegmentTree<Zwei<Long>, Long> {
	private final int n;
	private final Zwei<Long>[] b;
	@SuppressWarnings("unchecked")
	RASM(final int[] a) {
		super(a.length, (x, y) -> Zwei.of(x.first.longValue() + y.first.longValue(), x.second.longValue() + y.second.longValue()), (x, y) -> Zwei.of(x.first.longValue() + x.second.longValue() * y.longValue(), x.second.longValue()), Long::sum, Zwei.of(0L, 0L), Long.valueOf(0));
		n = a.length;
		b = new Zwei[n];
		for(int i = 0; i < n; ++i) {
			b[i] = Zwei.of((long) a[i], 1L);
		}
		build(b);
	}
	@SuppressWarnings("unchecked")
	RASM(final long[] a) {
		super(a.length, (x, y) -> Zwei.of(x.first.longValue() + y.first.longValue(), x.second.longValue() + y.second.longValue()), (x, y) -> Zwei.of(x.first.longValue() + x.second.longValue() * y.longValue(), x.second.longValue()), Long::sum, Zwei.of(0L, 0L), Long.valueOf(0));
		n = a.length;
		b = new Zwei[n];
		for(int i = 0; i < n; ++i) {
			b[i] = Zwei.of(a[i], 1L);
		}
		build(b);
	}
}
final class RUMX extends LazySegmentTree<Long, Long> {
	RUMX(final int[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::max, (x, y) -> y, (x, y) -> y, Long.valueOf(Long.MIN_VALUE), Long.valueOf(Long.MIN_VALUE)); }
	RUMX(final long[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::max, (x, y) -> y, (x, y) -> y, Long.valueOf(Long.MIN_VALUE), Long.valueOf(Long.MIN_VALUE)); }
}
final class RUMN extends LazySegmentTree<Long, Long> {
	RUMN(final int[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::min, (x, y) -> y, (x, y) -> y, Long.valueOf(Long.MAX_VALUE), Long.valueOf(Long.MAX_VALUE)); }
	RUMN(final long[] a){ super(Arrays.stream(a).boxed().toArray(Long[]::new), Long::min, (x, y) -> y, (x, y) -> y, Long.valueOf(Long.MAX_VALUE), Long.valueOf(Long.MAX_VALUE)); }
}
final class RUSM extends LazySegmentTree<Zwei<Long>, Long> {
	private final int n;
	private final Zwei<Long>[] b;
	@SuppressWarnings("unchecked")
	RUSM(final int[] a) {
		super(a.length, (x, y) -> Zwei.of(x.first.longValue() + y.first.longValue(), x.second.longValue() + y.second.longValue()), (x, y) -> Zwei.of(x.second.longValue() * y.longValue(), x.second.longValue()), (x, y) -> y, Zwei.of(0L, 0L), Long.valueOf(Long.MIN_VALUE));
		n = a.length;
		b = new Zwei[n];
		for(int i = 0; i < n; ++i) {
			b[i] = Zwei.of((long) a[i], 1L);
		}
		build(b);
	}
	@SuppressWarnings("unchecked")
	RUSM(final long[] a) {
		super(a.length, (x, y) -> Zwei.of(x.first.longValue() + y.first.longValue(), x.second.longValue() + y.second.longValue()), (x, y) -> Zwei.of(x.second.longValue() * y.longValue(), x.second.longValue()), (x, y) -> y, Zwei.of(0L, 0L), Long.valueOf(Long.MIN_VALUE));
		n = a.length;
		b = new Zwei[n];
		for(int i = 0; i < n; ++i) {
			b[i] = Zwei.of(a[i], 1L);
		}
		build(b);
	}
}

final class DualSegmentTree<T> {
	private final int n;
	private int sz, h;
	private final Object[] lazy;
	private final T id;
	private final BinaryOperator<T> ap;
	@SuppressWarnings("unchecked")
	private final void propagate(final int k) {
		if(lazy[k] != id) {
			lazy[2 * k] = ap.apply((T) lazy[2 * k], (T) lazy[k]);
			lazy[2 * k + 1] = ap.apply((T) lazy[2 * k + 1], (T) lazy[k]);
			lazy[k] = id;
		}
	}
	private final void thrust(final int k) {
		for(int i = h; i > 0; i--) {
			propagate(k >> i);
		}
	}
	DualSegmentTree(final int n, final BinaryOperator<T> ap, final T id) {
		this.n = n;
		this.ap = ap;
		this.id = id;
		sz = 1;
		h = 0;
		while(sz < n) {
			sz <<= 1;
			h++;
		}
		lazy = new Object[2 * sz];
		Arrays.fill(lazy, id);
	}
	@SuppressWarnings("unchecked")
	final void apply(int a, int b, final T x) {
		thrust(a += sz);
		thrust(b += sz - 1);
		for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
			if(l % 2 == 1) {
				lazy[l] = ap.apply((T) lazy[l], x);
				l++;
			}
			if(r % 2 == 1) {
				r--;
				lazy[r] = ap.apply((T) lazy[r], x);
			}
		}
	}
	@SuppressWarnings("unchecked")
	final T get(int k) {
		thrust(k += sz);
		return (T) lazy[k];
	}
	@SuppressWarnings("unchecked")
	public final T[] toArray(){ return (T[]) IntStream.range(0, n).mapToObj(this::get).toArray(); }
	@Override
	public final String toString() {
		final StringBuilder sb = new StringBuilder();
		sb.append(get(0));
		for(int i = 0; ++i < n;) {
			sb.append(", " + get(i));
		}
		return "[" + sb.toString() + "]";
	}
}

final class SegmentTreeBeats {
	private final long INF = (1L << 61) - 1;
	private final class Node {
		long sum = 0, g1 = 0, l1 = 0, g2 = -INF, gc = 1, l2 = INF, lc = 1, add = 0;
	}
	private final Node[] a;
	private int n, log;
	SegmentTreeBeats(final int n){ this(new int[n]); }
	SegmentTreeBeats(final int[] a) {
		final int m = a.length;
		n = 1;
		log = 0;
		while(n < m) {
			log++;
			n <<= 1;
		}
		this.a = new Node[2 * n];
		for(int i = 0; i < 2 * n; ++i) {
			this.a[i] = new Node();
		}
		for(int i = 0; i < m; ++i) {
			this.a[i + n].sum = this.a[i + n].g1 = this.a[i + n].l1 = a[i];
		}
		for(int i = n; --i >= 0;) {
			update(i);
		}
	}
	SegmentTreeBeats(final long[] a) {
		final int m = a.length;
		n = 1;
		log = 0;
		while(n < m) {
			log++;
			n <<= 1;
		}
		this.a = new Node[2 * n];
		for(int i = 0; i < 2 * n; ++i) {
			this.a[i] = new Node();
		}
		for(int i = 0; i < m; ++i) {
			this.a[i + n].sum = this.a[i + n].g1 = this.a[i + n].l1 = a[i];
		}
		for(int i = n; --i >= 0;) {
			update(i);
		}
	}
	final void chmin(final int l, final int r, final long x){ innerApply(1, l, r, x); }
	final void chmax(final int l, final int r, final long x){ innerApply(2, l, r, x); }
	final void add(final int l, final int r, final long x){ innerApply(3, l, r, x); }
	final void update(final int l, final int r, final long x){ innerApply(4, l, r, x); }
	final long min(final int l, final int r){ return innerFold(1, l, r); }
	final long max(final int l, final int r){ return innerFold(2, l, r); }
	final long sum(final int l, final int r){ return innerFold(3, l, r); }
	private final void update(final int k) {
		final Node p = a[k], l = a[k * 2 + 0], r = a[k * 2 + 1];
		p.sum = l.sum + r.sum;
		if(l.g1 == r.g1) {
			p.g1 = l.g1;
			p.g2 = Math.max(l.g2, r.g2);
			p.gc = l.gc + r.gc;
		} else {
			final boolean f = l.g1 > r.g1;
			p.g1 = f ? l.g1 : r.g1;
			p.gc = f ? l.gc : r.gc;
			p.g2 = Math.max(f ? r.g1 : l.g1, f ? l.g2 : r.g2);
		}
		if(l.l1 == r.l1) {
			p.l1 = l.l1;
			p.l2 = Math.min(l.l2, r.l2);
			p.lc = l.lc + r.lc;
		} else {
			final boolean f = l.l1 < r.l1;
			p.l1 = f ? l.l1 : r.l1;
			p.lc = f ? l.lc : r.lc;
			p.l2 = Math.min(f ? r.l1 : l.l1, f ? l.l2 : r.l2);
		}
	}
	private final void pushAdd(final int k, final long x) {
		final Node p = a[k];
		p.sum += x << (log + Integer.numberOfLeadingZeros(k) - 31);
		p.g1 += x;
		p.l1 += x;
		if(p.g2 != -INF) {
			p.g2 += x;
		}
		if(p.l2 != INF) {
			p.l2 += x;
		}
		p.add += x;
	}
	private final void pushMin(final int k, final long x) {
		final Node p = a[k];
		p.sum += (x - p.g1) * p.gc;
		if(p.l1 == p.g1) {
			p.l1 = x;
		}
		if(p.l2 == p.g1) {
			p.l2 = x;
		}
		p.g1 = x;
	}
	private final void pushMax(final int k, final long x) {
		final Node p = a[k];
		p.sum += (x - p.l1) * p.lc;
		if(p.g1 == p.l1) {
			p.g1 = x;
		}
		if(p.g2 == p.l1) {
			p.g2 = x;
		}
		p.l1 = x;
	}
	private final void push(final int k) {
		final Node p = a[k];
		if(p.add != 0) {
			pushAdd(k * 2 + 0, p.add);
			pushAdd(k * 2 + 1, p.add);
			p.add = 0;
		}
		if(p.g1 < a[k * 2 + 0].g1) {
			pushMin(k * 2 + 0, p.g1);
		}
		if(p.l1 > a[k * 2 + 0].l1) {
			pushMax(k * 2 + 0, p.l1);
		}
		if(p.g1 < a[k * 2 + 1].g1) {
			pushMin(k * 2 + 1, p.g1);
		}
		if(p.l1 > a[k * 2 + 1].l1) {
			pushMax(k * 2 + 1, p.l1);
		}
	}
	private final void subtreeChmin(final int k, final long x) {
		if(a[k].g1 <= x) {
			return;
		}
		if(a[k].g2 < x) {
			pushMin(k, x);
			return;
		}
		push(k);
		subtreeChmin(k * 2 + 0, x);
		subtreeChmin(k * 2 + 1, x);
		update(k);
	}
	private final void subtreeChmax(final int k, final long x) {
		if(x <= a[k].l1) {
			return;
		}
		if(x < a[k].l2) {
			pushMax(k, x);
			return;
		}
		push(k);
		subtreeChmax(k * 2 + 0, x);
		subtreeChmax(k * 2 + 1, x);
		update(k);
	}
	private final void applyBeta(final int cmd, final int k, final long x) {
		if(cmd == 1) {
			subtreeChmin(k, x);
		}
		if(cmd == 2) {
			subtreeChmax(k, x);
		}
		if(cmd == 3) {
			pushAdd(k, x);
		}
		if(cmd == 4) {
			subtreeChmin(k, x);
			subtreeChmax(k, x);
		}
	}
	private final void innerApply(final int cmd, int l, int r, final long x) {
		if(l == r) {
			return;
		}
		l += n;
		r += n;
		for(int i = log; i >= 1; i--) {
			if(((l >> i) << i) != l) {
				push(l >> i);
			}
			if(((r >> i) << i) != r) {
				push((r - 1) >> i);
			}
		}
		{
			int l2 = l, r2 = r;
			while(l < r) {
				if(l % 2 == 1) {
					applyBeta(cmd, l++, x);
				}
				if(r % 2 == 1) {
					applyBeta(cmd, --r, x);
				}
				l >>= 1;
				r >>= 1;
			}
			l = l2;
			r = r2;
		}
		for(int i = 1; i <= log; ++i) {
			if(((l >> i) << i) != l) {
				update(l >> i);
			}
			if(((r >> i) << i) != r) {
				update((r - 1) >> i);
			}
		}
	}
	private final long op(final int cmd, final long a, final Node b){ return cmd == 1 ? Math.min(a, b.l1) : cmd == 2 ? Math.max(a, b.g1) : a + b.sum; }
	private final long e(final int cmd){ return cmd == 1 ? INF : cmd == 2 ? -INF : 0; }
	private final long innerFold(final int cmd, int l, int r) {
		if(l == r) {
			return e(cmd);
		}
		l += n;
		r += n;
		for(int i = log; i >= 1; i--) {
			if(((l >> i) << i) != l) {
				push(l >> i);
			}
			if(((r >> i) << i) != r) {
				push((r - 1) >> i);
			}
		}
		long lx = e(cmd), rx = e(cmd);
		while(l < r) {
			if(l % 2 == 1) {
				lx = op(cmd, lx, a[l++]);
			}
			if(r % 2 == 1) {
				rx = op(cmd, rx, a[--r]);
			}
			l >>= 1;
			r >>= 1;
		}
		if(cmd == 1) {
			lx = Math.min(lx, rx);
		}
		if(cmd == 2) {
			lx = Math.max(lx, rx);
		}
		if(cmd == 3) {
			lx += rx;
		}
		return lx;
	}
}

final class SparseTable {
	private final long[][] st;
	private final int[] lookup;
	private final LongBinaryOperator op;
	SparseTable(final int[] a, final LongBinaryOperator op) {
		this.op = op;
		int b = 0;
		while((1 << b) <= a.length) {
			++b;
		}
		st = new long[b][1 << b];
		for(int i = 0; i < a.length; i++) {
			st[0][i] = a[i];
		}
		for(int i = 1; i < b; i++) {
			for(int j = 0; j + (1 << i) <= (1 << b); j++) {
				st[i][j] = op.applyAsLong(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
		lookup = new int[a.length + 1];
		for(int i = 2; i < lookup.length; i++) {
			lookup[i] = lookup[i >> 1] + 1;
		}
	}
	SparseTable(final long[] a, final LongBinaryOperator op) {
		this.op = op;
		int b = 0;
		while((1 << b) <= a.length) {
			++b;
		}
		st = new long[b][1 << b];
		for(int i = 0; i < a.length; i++) {
			st[0][i] = a[i];
		}
		for(int i = 1; i < b; i++) {
			for(int j = 0; j + (1 << i) <= (1 << b); j++) {
				st[i][j] = op.applyAsLong(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
			}
		}
		lookup = new int[a.length + 1];
		for(int i = 2; i < lookup.length; i++) {
			lookup[i] = lookup[i >> 1] + 1;
		}
	}
	final long query(final int l, final int r) {
		final int b = lookup[r - l];
		return op.applyAsLong(st[b][l], st[b][r - (1 << b)]);
	}
	final int minLeft(final int x, final LongPredicate fn) {
		if(x == 0) {
			return 0;
		}
		int ok = x, ng = -1;
		while(abs(ok - ng) > 1) {
			final int mid = (ok + ng) / 2;
			if(fn.test(query(mid, x) - 1)) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return ok;
	}
	final int maxRight(final int x, final LongPredicate fn) {
		if(x == lookup.length - 1) {
			return lookup.length - 1;
		}
		int ok = x, ng = lookup.length;
		while(abs(ok - ng) > 1) {
			final int mid = (ok + ng) / 2;
			if(fn.test(query(x, mid))) {
				ok = mid;
			}
			else {
				ng = mid;
			}
		}
		return ok;
	}
}

final class WaveletMatrix {
	private final WaveletMatrixBeta mat;
	private final long[] ys;
	WaveletMatrix(final int[] arr){ this(arr, 20); }
	WaveletMatrix(final long[] arr){ this(arr, 20); }
	WaveletMatrix(final int[] arr, final int log) {
		ys = Arrays.stream(arr).asLongStream().sorted().distinct().toArray();
		final long[] t = new long[arr.length];
		Arrays.setAll(t, i -> index(arr[i]));
		mat = new WaveletMatrixBeta(t, log);
	}
	WaveletMatrix(final long[] arr, final int log) {
		ys = Arrays.stream(arr).sorted().distinct().toArray();
		final long[] t = new long[arr.length];
		Arrays.setAll(t, i -> index(arr[i]));
		mat = new WaveletMatrixBeta(t, log);
	}
	private final int index(final long x){ return Utility.lowerBound(ys, x); }
	final long get(final int k){ return ys[(int) mat.access(k)]; }
	final int rank(final int r, final long x) {
		final int pos = index(x);
		if(pos == ys.length || ys[pos] != x) {
			return 0;
		}
		return mat.rank(pos, r);
	}
	final int rank(final int l, final int r, final long x){ return rank(r, x) - rank(l, x); }
	final long kthMin(final int l, final int r, final int k){ return ys[(int) mat.kthMin(l, r, k)]; }
	final long kthMax(final int l, final int r, final int k){ return ys[(int) mat.kthMax(l, r, k)]; }
	final int rangeFreq(final int l, final int r, final long upper){ return mat.rangeFreq(l, r, index(upper)); }
	final int rangeFreq(final int l, final int r, final long lower, final long upper){ return mat.rangeFreq(l, r, index(lower), index(upper)); }
	final long prev(final int l, final int r, final long upper) {
		final long ret = mat.prev(l, r, index(upper));
		return ret == -1 ? -1 : ys[(int) ret];
	}
	final long next(final int l, final int r, final long lower) {
		final long ret = mat.next(l, r, index(lower));
		return ret == -1 ? -1 : ys[(int) ret];
	}
	private final class WaveletMatrixBeta {
		private final int log;
		private final SuccinctIndexableDictionary[] matrix;
		private final int[] mid;
		WaveletMatrixBeta(final long[] arr, final int log) {
			final int len = arr.length;
			this.log = log;
			matrix = new SuccinctIndexableDictionary[log];
			mid = new int[log];
			final long[] l = new long[len], r = new long[len];
			for(int level = log; --level >= 0;) {
				matrix[level] = new SuccinctIndexableDictionary(len + 1);
				int left = 0, right = 0;
				for(int i = 0; i < len; ++i) {
					if(((arr[i] >> level) & 1) == 1) {
						matrix[level].set(i);
						r[right++] = arr[i];
					} else {
						l[left++] = arr[i];
					}
				}
				mid[level] = left;
				matrix[level].build();
				final long[] tmp = new long[len];
				System.arraycopy(arr, 0, tmp, 0, len);
				System.arraycopy(l, 0, arr, 0, len);
				System.arraycopy(tmp, 0, l, 0, len);
				for(int i = 0; i < right; ++i) {
					arr[left + i] = r[i];
				}
			}
		}
		private final IntPair succ(final boolean f, final int l, final int r, final int level){ return IntPair.of(matrix[level].rank(f, l) + mid[level] * (f ? 1 : 0), matrix[level].rank(f, r) + mid[level] * (f ? 1 : 0)); }
		final long access(int k) {
			long ret = 0;
			for(int level = log; --level >= 0;) {
				final boolean f = matrix[level].get(k);
				if(f) {
					ret |= 1L << level;
				}
				k = matrix[level].rank(f, k) + mid[level] * (f ? 1 : 0);
			}	
			return ret;
		}
		final int rank(final long x, int r) {
			int l = 0;
			for(int level = log; --level >= 0;) {
				final IntPair p = succ(((x >> level) & 1) == 1, l, r, level);
				l = p.first.intValue();
				r = p.second.intValue();
			}
			return r - l;
		}
		final long kthMin(int l, int r, int k) {
			if(!Utility.scope(0, k, r - l - 1)) {
				throw new IndexOutOfBoundsException();
			}
			long ret = 0;
			for(int level = log; --level >= 0;) {
				final int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
				final boolean f = cnt <= k;
				if(f) {
					ret |= 1 << level;
					k -= cnt;
				}
				final IntPair p = succ(f, l, r, level);
				l = p.first.intValue();
				r = p.second.intValue();
			}
			return ret;
		}
		final long kthMax(final int l, final int r, final int k){ return kthMin(l, r, r - l - k - 1); }
		final int rangeFreq(int l, int r, final long upper) {
			int ret = 0;
			for(int level = log; --level >= 0;) {
				final boolean f = ((upper >> level) & 1) == 1;
				if(f) {
					ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
				}
				final IntPair p = succ(f, l, r, level); 
				l = p.first.intValue();
				r = p.second.intValue();
			}
			return ret;
		}
		final int rangeFreq(final int l, final int r, final long lower, final long upper){ return rangeFreq(l, r, upper) - rangeFreq(l, r, lower); }
		final long prev(final int l, final int r, final long upper) {
			final int cnt = rangeFreq(l, r, upper);
			return cnt == 0 ? -1 : kthMin(l, r, cnt - 1);
		}
		final long next(final int l, final int r, final long lower) {
			final int cnt = rangeFreq(l, r, lower);
			return cnt == r - l ? -1 : kthMin(l, r, cnt);
		}
		private final class SuccinctIndexableDictionary {
			private final int blk;
			private final int[] bit, sum;
			SuccinctIndexableDictionary(final int len) {
				blk = (len + 31) >> 5;
				bit = new int[blk];
				sum = new int[blk];
			}
			final void set(final int k){ bit[k >> 5] |= 1 << (k & 31); }
			final void build() {
				sum[0] = 0;
				for(int i = 0; i + 1 < blk; ++i) {
					sum[i + 1] = sum[i] + Integer.bitCount(bit[i]);
				}
			}
			final boolean get(final int k){ return ((bit[k >> 5] >> (k & 31)) & 1) == 1; }
			final int rank(final int k){ return (sum[k >> 5] + Integer.bitCount(bit[k >> 5] & ((1 << (k & 31)) - 1))); }
			final int rank(final boolean val, final int k){ return val ? rank(k) : k - rank(k); }
		}
	}
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/Main.java