Main.java

import java.io.*;
import java.util.*;
import java.util.stream.*;
 
/**
    Nathan
*/
public class Main {
    public static void solve(FastScanner io) throws Exception {
                
    }

    /**
        MAIN
    */
    public static void main(String[] args) throws Exception {
        // FastScanner io = new FastScanner("usaco-problem-name"); // usaco
        FastScanner io = new FastScanner();
		int t = 1;
        t = io.nextInt(); // t testcases
		while (t-->0) {
            solve(io);
        }
        io.close();
    }
 
    /**
        RESERVED INSTANCES
    */
    static int mod_fermat = 998_244_353;
    static int mod_prime = 1_000_000_007; // prime number
    static int oo_int = (int)1e9; // infinity number (int)
	static long oo_long = (long) 2e18; // infinity number
	static Random random = new Random();
    // mod trick: modular inverse of 2 under 1e9+7
    // 1e9+7 is prime -> inv(2) = (1e9+7+1)/2
    static int inv2 = 500_000_004;
 
	/**
		HELPER
	*/
 
    // ALGEBRA
	static long add(long a, long b) { return (a + b) % mod_prime; }
	static long subtract(long a, long b) { return ((a - b) % mod_prime + mod_prime) % mod_prime; }
	static long multiply(long a, long b) { return (a * b) % mod_prime; }
	static long exp(long base, long exp) { 
		long result = 1;
		while (exp > 0) {
			if ((exp & 1) == 1) result = multiply(result, base);
			base = multiply(base, base);
			exp >>=1;
		}
		return result;
	}
    static long abs(long x) { return Math.abs(x); }
    static int abs(int x) { return Math.abs(x); }
    static int sign(long x) { return x < 0 ? -1 : 1; }
 
    // NUMBER THEORY
    static int gcd_recursive(int a, int b) { return b > 0 ? gcd(b, a % b) : a; }
    static int gcd(int a, int b) { 
        while (b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    static int lcm(int a, int b) { return a / gcd(a,b) * b; } // prevent overflow with a / gcd
    static int binpow(int a, int b) {
        int res = 1;
        while (b > 0) {
            if (b % 2 != 0)
                res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
    static int modpow(int x, int n, int m) {
        // pseudocode in CPH book
        if (n == 0) return 1%m;
        long u = modpow(x, n/2, m);
        u = (u * u) % m;
        if (n % 2 == 1) u = (u * x) % m;
        return (int) u; 
    }
    static boolean[] sieve(int n) {
        // time complexity: O(nloglogn)
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
            }
        }
        return prime;
    }
    static int[] prime_factorization(int n) {
        int[] prime = new int[n+1];
        for (int p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                prime[p]++;
                n /= p;
            }
        }
        if (n > 1) prime[n] = 1; // if n is a large prime
        return prime;
    }
    static int[] spf(int n) { // smallest prime factor
        // time complexity: O(nloglogn)
        int[] spf = new int[n+1];
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                for (int j = i; j <= n; j+=i) {
                    if (spf[j] == 0) spf[j] = i;
                }
            }
        }
        return spf;
    }
 
    // ARRAY OPERATIONS
    static void swap(int a, int b) { int temp = a; a = b; b = temp; }
    static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
    static void shuffle(int[] a) { 
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int ri = random.nextInt(n); // random index
            swap(a, i, ri);
        }
    }
    static <T> void reverse(List<T> x) { Collections.reverse(x); }
    static int max(int[] a) { Arrays.sort(a); return a[a.length-1]; }
    static long max(long[] a) { Arrays.sort(a); return a[a.length-1]; }

    // HASHING
    static String hash(int[] x) { return Arrays.toString(x); }
    static String hash(long[] x) { return Arrays.toString(x); }
    static <T> String hash(List<T> x) { return x.toString(); }
 
    // SORTING
    static void sort(int[] a) { Arrays.sort(a); }
    static void sort(long[] a) { Arrays.sort(a); }
    static <T extends Comparable<? super T>> void sort(List<T> a) { Collections.sort(a); }
    static void ruffle_sort(int[] a) { shuffle(a); sort(a); }
 
    // FACTORIALS & nCk
	static long[] factorials = new long[2_000_005];
	static long[] inverseFactorials = new long[2_000_005];
	static void precompute_factorials() {
        int n = factorials.length;
		factorials[0] = 1;
		for (int i = 1; i < factorials.length; i++) {
			factorials[i] = multiply(factorials[i-1], i);
		}
        inverseFactorials[n-1] = exp(factorials[n-1], mod_prime-2);
        for (int i = n-2; i >= 0; i--) {
            inverseFactorials[i] = multiply(inverseFactorials[i+1], i);
        }
	}
    static long nCk(int n, int k) {
        if (n < 0 || k < 0 || n < k) return 0;
        return multiply(factorials[n], multiply(inverseFactorials[n-k], inverseFactorials[k]));
    }

    // STRING
    static String repeat(String s, int count) { return s.repeat(count); }
    static String combine_string(String s, String p) { return s.concat("#").concat(p); }
    static String reverse(String s) { return new StringBuilder(s).reverse().toString(); }
    static int[] z_function(char[] s) {
        /**
            Z function is similar to KMP
            Z[i] denotes the length of longest common prefix of S and S[i:] 
            Time Complexity: O(N)  
            
            We maintain [x,y] interval such that s[x,y] is prefix of s
            For any k in [x,y], meaning x <= k <= y, we can confirm:
                - s[k-x..] for at least y - k characters
            
            z[k-x] means "If started matching from offset k - x, how many characters match?"
                - k + z[k-x] < y -> z[k] = z[k-x] (ends before y)
                - k + z[k-x] >= y -> s[0..k-y] = s[k..y]
                    * we need to compare character by character to extend

            Z-algorithm always work and no risk for collisions, but hard to implement :)
        */
        int n = s.length;
        int[] z = new int[n];
        int x = 0, y = 0;
        for (int i = 1; i < n; i++) {
            // todo: exemplify this formula
            z[i] = Math.max(z[i], Math.min(z[i-x], y-i+1));
            while (i+z[i] < n && s[z[i]] == s[z[i+z[i]]]) {
                x = i; y = i + z[i]; z[i]++;
            }
        }
        return z;
    }
    static int[] prefix_function(char[] s) { // KMP algorithm
        /**
            Prefix function pi[i] is the max prefix that is also suffix
            pi[i] = k means s[0..i] = s[(i-k+1)..i]
            note that KMP excludes itself as a prefix, so pi[0] = 0
            Time Complexity: O(N)

            string c = s + # + t
            if pi[i] = n, then at i - 2 * n the string s appears in t
                pi[i] = n means c[i-n+1..i] = s
                there are n+1 characters before t
                start position of s will be i - n + 1 - (n + 1) = i - 2n
                this is because, i - (n+1) strips the first n+1 characters before t
                    and (-n+1) calculates the starting position
            math: i - (n + 1) - n + 1 = i - 2n

            usually, we want to keep pattern + '#' + string
                to make sure pi[i] = |pattern| we have a meaningful pi
            
            note that # or @ or ... must be a character not exist in pattern or string
        */
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i];
            while (j > 0 && s[j] != s[i]) j = pi[j-1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
    static int[] count_occurences(char[] s) {
        int n = s.length;
        int[] pi = prefix_function(s);
        int[] occ = new int[n+1];
        // count how often each prefix length appears
        for (int i = 0; i < n; i++) occ[pi[i]]++;
        // every occurrence of the longer border of length 
        //      "carries along" an occurrence of its shorter border.
        // e.g. occ[10] = 5 -- length 10 appears 5 times
        //      pi[9] = 6 --> each length 10 should also contains a length 6
        for (int i = n-1; i > 0; i--) occ[pi[i-1]] += occ[i];
        // include itself as prefix
        for (int i = 0; i <= n; i++) occ[i]++;
        return occ;
    }
    static boolean check_repeated_substring(char[] s) {
        /**
            Source: https://leetcode.com/problems/repeated-substring-pattern/
        */
        int n = s.length;
        int[] pi = prefix_function(s);
        int L = pi[n-1]; // longest prefix
        return (L > 0) && (n % (n - L) == 0);
    }
    static int longest_palindromic_substring(String t) {
        String rt = reverse(t);
        char[] s = combine_string(t, rt).toCharArray();
        int n = s.length;
        int[] pi = prefix_function(s);
        return pi[n-1]; // longest palindromic prefix
    }

    // LEARNING CONTENT
    static int[] prefix_function_naive(char[] s) {
        /**
            Naive Implementation
            Time Complexity: O(N^3)
        */
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= i; k++) {
                boolean ok = true;
                for (int j = 0; j < k; j++) {
                    if (s[j] != s[i-k+1+j]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) pi[i] = k;
            }
        }
        return pi;
    }
    static int[] prefix_function_opt1(char[] s) {
        /**
            First Optimization: pi[i+1] can only increase at most once from pi[i]
            Time Complexity: O(N^2)
        */
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int k = Math.min(pi[i-1] + 1, i);
            while (k > 0) {
                boolean ok = true;
                for (int j = 0; j < k; j++) {
                    if (s[j] != s[i-k+1+j]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) break;
                k--;
            }
            pi[i] = k;
        }
        return pi;
    }
    static int[] prefix_function_opt2(char[] s) {
        /**
            Second Optimization: Find largest j < i such that prefix = suffix
                Jump to j by taking pi[i-1]
                This is the KMP algorithm
            Time Complexity: O(N)
        */
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i-1];
            while (j > 0 && s[j] != s[i]) { // mismatch -- fallback
                j = pi[j-1];
            }
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    // BINARY SEARCH
    static int[] binary_search(int x, int[] a) {
        // looking for transition point
        int l = -1, r = a.length-1;
        while (r - l > 1) {
            int mid = (l + r) >>> 1;
            if (x < a[mid]) r = mid;
            else l = mid;
        }
        // l = last element >= x (-1 if no such element) -- lowerbound
        // r = first element > x (n if no such element) -- upperbound
        // a[l] <= x < a[r]
        return new int[]{l,r};
    }
    static boolean check() { return true; } // template check function
    static int binary_lifting_max(int min, int max) {
        /**
            the lifting depends on whether the check is monotonic
            if not, then it is light switches (bitmask build)
            choosing maxpos depends on that

            Integer.highestOneBit() can be helpful in bitmask case
            k - pos = k | pos (turn bit on)
        */
        int maxpos = Integer.highestOneBit(max - min);
        int k = max;
        for (int pos = maxpos; pos > 0; pos >>= 1) {
            while (k - pos >= min && check()) {
                k -= pos;
            }
        }
        return k;
    }
    static int binary_lifting_min(int min, int max) {
        int maxpos = Integer.highestOneBit(max - min);
        int k = min;
        for (int pos = maxpos; pos > 0; pos >>= 1) {
            while (k + pos <= max && check()) {
                k += pos;
            }
        }
        return k;
    }

    // COORDINATE COMPRESSION
    static int[] coordinate_compress(int[] a) {
        int n = a.length;
        int[] sorted = a.clone(); sort(sorted);
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && sorted[i] == sorted[i-1]) continue;
            rank.put(sorted[i], r++);
        }
        int[] compress = new int[n];
        for (int i = 0; i < n; i++) compress[i] = rank.get(a[i]);
        return compress;
    }
 
    /**
        DATA STRUCTURES TEMPLATES
    */
    static abstract class Multiset<T> {
        protected final TreeMap<T, Integer> multiset;
		public Multiset() { multiset = new TreeMap<>(); }
        public void add(T x) { multiset.merge(x, 1, Integer::sum); }
        public void remove(T x) {
            multiset.merge(x, -1, Integer::sum); 
            if (multiset.get(x) <= 0) multiset.remove(x);
        }
        public T min() { return multiset.firstKey(); }
        public T max() { return multiset.lastKey(); }
        public int countLE(T x) { // count less than or equal
            return multiset.headMap(x, true).values()
                    .stream().mapToInt(Integer::intValue).sum();
        }
        public int count() { return multiset.values().stream().mapToInt(Integer::intValue).sum(); }
    }

    static abstract class DSU {
        protected final int[] parent;
        protected final int[] size;
        public DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public int find(int v) {
            return parent[v] == v ? v : (parent[v] = find(parent[v]));
        }
        public boolean union(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) return false;
            if (size[a] < size[b]) swap(a, b);
            parent[b] = a;
            size[a] += size[b];
            return true;
        }
        public int size(int v) {
            return size[find(v)];
        }
        public boolean connected(int a, int b) {
            return find(a) == find(b);
        }
    }

    static abstract class SegmentTree { 
        protected final int[] st;
        protected final int[] lazy;
        protected final int[] a;
        public SegmentTree(int n, int[] a) {
            this.st = new int[4*n];
            this.lazy = new int[4*n];
            this.a = a;
        }
        protected abstract int combine(int left, int right);
        public void build(int v, int tl, int tr) {
            if (tl == tr) {
                st[v] = a[tl];
                return;
            }
            int tm = (tl + tr) >>> 1;
            build(v*2+1, tl, tm);
            build(v*2+2, tm+1, tr);
            st[v] = combine(st[v*2+1], st[v*2+2]);
        }
        protected abstract int update(int x, int u);
        protected abstract int updateLazy(int x, int u);
        protected abstract void push(int v); // lazy propagation
        public void update(int v, int tl, int tr, int pos, int u) {
            if (tl > tr) return;
            if (tl == tr) {
                st[v] = update(st[v], u);
                lazy[v] = updateLazy(lazy[v], u);
                return;
            }
            int tm = (tl + tr) >>> 1;
            if (pos <= tm) update(v*2+1, tl, tm, pos, u);
            else update(v*2+2, tm+1, tr, pos, u);
            st[v] = combine(st[v*2+1], st[v*2+2]);
        }
        protected abstract int identity();
        public int query(int v, int tl, int tr, int l, int r) {
            if (l > r) return identity();
            if (l <= tl && tr <= r) return st[v];
            push(v);
            int tm = (tl + tr) >>> 1;
            int left = query(v*2+1, tl, tm, l, Math.min(r, tm));
            int right = query(v*2+2, tm+1, tr, Math.max(l, tm+1), r);
            return combine(left, right);
        }
    }

    static abstract class FenwickTree {
        /**
        supporting
            1. point update
            2. range sum query (prefix sum)
        note: one-indexed (zero is skipped)

        ft[k] = sum(k - p(k) + 1, k)
        p(k) = largest power of 2 that divides k

        use least significant one (lsone) to update/calc sum
            * lsone(k) = k & (-k)
            * defined in CP2 (Steven & Helix)

        sum(a,b) = sum(1,b) - sum(1,a-1) for a > 1

        it is obvious there is no easy way to find minimum in range [l,r] for fenwick tree
            * FT can only answer min [0,r], update(s) would make it a disaster
            * MATH explanation :) 
                - because min() together with the set of integers doesn't form a group, 
                as there are no inverse elements.
            * "Efficient Range Minimum Queries using Binary Indexed Trees" does provide min for BIT,
                but complex to be implemented in CP setting

        extra theoretical read: TopCoder Binary Indexed Trees
        */
        int[] ft; // fenwick tree
        int[] a; // original array
        public FenwickTree(int n) {
            ft = new int[n+1];
            a = new int[n+1];
        }
        void set(int k, int u) {
            add(k, u - a[k]);
        }
        void add(int k, int u) {
            a[k] += u;
            for (; k < ft.length; k += lsone(k)) ft[k] += u;
        }
        void range_add(int l, int r, int u) {
            // difference-array (or "prefix‑difference") trick
            add(l, u);
            add(r+1, -u);
        }
        int sum(int k) {
            int s = 0;
            for (; k > 0; k -= lsone(k)) s += ft[k];
            return s;
        }
        int lsone(int x) { // least significant one
            return x & (-x);
        }
    }

    static abstract class FenwickTree2D {
        int[][] ft;
        int[][] a;
        int n, m;
        public FenwickTree2D(int n, int m) {
            ft = new int[n+1][m+1];
            a = new int[n+1][m+1];
            this.n = n; this.m = m;
        }
        void set(int x, int y, int u) {
            add(x, y, u - a[x][y]);
        }
        void add(int x, int y, int u) {
            // note: avoid update x and y in-place
            //       by setting i = x and j = y
            a[x][y] += u;
            for (int i = x; i <= n; i += lsone(i)) {
                for (int j = y; j <= m; j += lsone(j)) {
                    ft[i][j] += u;
                }
            }
        }
        int sum(int x, int y) {
            int s = 0;
            for (int i = 0; i > 0; i -= lsone(i)) {
                for (int j = 0; j > 0; j -= lsone(j)) {
                    s += ft[i][j];
                }
            }
            return s;
        }
        int rectangle_sum(int x1, int y1, int x2, int y2) {
            int s = 0;
            s += sum(x2, y2);
            s -= sum(x2, y1-1);
            s -= sum(x1-1, y2);
            s += sum(x1-1, y1-1);
            return s;
        }
        int lsone(int k) {
            return k & (-k);
        }
    }

    static abstract class OrderStatisticTree {
        /**
            OST is a variant of BST that supports
                * insert(x) / delete(x)
                * rank(x): number of elements <= x
                * select(k): find the kth min/max element

            There are multiple ways to implement OST. 
            I am inspired by BIT (binary-indexed tree), so I build OST based on that.

            Maximum number of nodes is 4*N. Proofs are similar to SegmentTree.
        */
        int[] bit;
        public OrderStatisticTree(int n) {
            bit = new int[n+1];
        }
        void build(int[] a) {
            int n = a.length;
            for (int i = 0; i < n; i++) add(i+1, a[i]);
        }
        
        int rank(int x) {
            return sum(x-1); // number of elements < x
        }
        int select(int k) {
            // binary-jumping
            int i = 0, n = bit.length-1;
            int mask = Integer.highestOneBit(n);
            for (; mask > 0; mask >>= 1) {
                int next = i + mask;
                if (next <= n && bit[next] < k) {
                    i = next;
                    k -= bit[next];
                }
            }
            // here, i is the largest position where prefix-sum < k
            // final check (when k > n)
            return (i + 1 <= n) ? i + 1 : -1;
        }
        void insert(int x) {
            add(x, 1); // increase rank of elements > x
        }
        void delete(int x) {
            add(x, -1); // decrease rank of elements > x
        }

        // BIT helper
        void add(int i, int u) {
            for (; i < bit.length; i += i & (-i)) {
                bit[i] += u;
            }
        }
        int sum(int i) {
            int s = 0;
            for (; i > 0; i -= i & (-i)) s += bit[i];
            return s;
        }
    }
 
    /**
        PRINTING 
    */
    static void print(FastScanner io, int[] a, String delimeter) { io.println(Arrays.stream(a).mapToObj(String::valueOf).collect(Collectors.joining(delimeter))); }
    static void print(FastScanner io, long[] a, String delimeter) { io.println(Arrays.stream(a).mapToObj(String::valueOf).collect(Collectors.joining(delimeter))); }
    static void print(FastScanner io, List<?> a, String delimeter) { io.println(a.stream().map(String::valueOf).collect(Collectors.joining(delimeter))); }

    /**
        IO
    */
    static class FastScanner extends PrintWriter {
        private BufferedReader br;
        private StringTokenizer st;
		// standard input
        public FastScanner() { this(System.in, System.out); }
		public FastScanner(InputStream i, OutputStream o) {
            super(o);
			st = new StringTokenizer("");
            br = new BufferedReader(new InputStreamReader(i));
        }
		// USACO-style file input
        public FastScanner(String problemName) throws IOException {
            super(problemName + ".out");
			st = new StringTokenizer("");
            br = new BufferedReader(new FileReader(problemName + ".in"));
        }
        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }
        public int nextInt() { return Integer.parseInt(next()); }  
        public double nextDouble() { return Double.parseDouble(next()); }   
        public long nextLong() { return Long.parseLong(next()); }   
        public int[] nextArray(int n) { int[] a = new int[n]; return nextArray(a); }
        public int[] nextArray(int[] a) { for (int i = 0; i < a.length; i++) a[i] = nextInt(); return a; }
        public long[] nextArray(long[] a) { for (int i = 0; i < a.length; i++) a[i] = nextLong(); return a; }
    }
}