#include <bits/stdc++.h>
using namespace std;

namespace solution {
    bool hasMultipleTests = true;

    void preprocess() {
        // something
    }

    void input(int testcase) {
        // something
    }

    void solve(int testcase) {
        // something
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solution::preprocess();

    int t = 1;
    if (solution::hasMultipleTests) cin >> t;

    for (int testcase=1; testcase<=t; testcase++) {
        solution::input(testcase);
        solution::solve(testcase);
    }

    return 0;
}

import sys
input = sys.stdin.readline


class Solution:
    hasMultipleTests = True

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        pass

    @classmethod
    def solve(cls, testcase):
        pass

# end Solution


if __name__ == '__main__':
    Solution.preprocess()

    t = int(input()) if Solution.hasMultipleTests else 1
    for testcase in range(1, t+1):
        Solution.input(testcase)
        Solution.solve(testcase)

namespace solution {
    bool hasMultipleTests = true;

    int n;
    vector<int> a;

    void preprocess() {

    }

    void input(int testcase) {
        cin >> n;
        a.clear();
        a.resize(n * 2);
        for (auto &z: a) cin >> z;
    }

    void solve(int testcase) {
        int cnt0 = 0;

        for (auto &z: a) {
            cnt0 += z;
        }

        cout << (cnt0 & 1) << " " << min(cnt0, n * 2 - cnt0) << endl;
    }
}

class Solution:
    hasMultipleTests = True

    n: int = None
    a: list = None

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())
        cls.a = list(map(int, input().split()))

    @classmethod
    def solve(cls, testcase):
        cnt0 = sum(cls.a)
        
        print(cnt0 & 1, min(cnt0, cls.n*2 - cnt0))

# end Solution

namespace solution {
    bool hasMultipleTests = true;

    int n, k;

    void preprocess() {

    }

    void input(int testcase) {
        cin >> n >> k;
    }

    void solve(int testcase) {
        if (n == 1) {cout << "1\n1\n"; return;}

        if (k == 1 || k == n) {cout << "-1\n"; return;}

        int p2 = k - k % 2;
        int p3 = k + 1 + k % 2;
        cout << "3\n1 " << p2 << " " << p3 << endl;
    }
}

class Solution:
    hasMultipleTests = True

    n: int = None
    k: int = None

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n, cls.k = map(int, input().split())

    @classmethod
    def solve(cls, testcase):
        if cls.n == 1: return(print('1\n1'))

        if cls.k in {1, cls.n}: return(print(-1))

        p2, p3 = cls.k - cls.k % 2, cls.k + 1 + cls.k % 2
        print(f'3\n1 {p2} {p3}')

# end Solution

namespace solution {
    bool hasMultipleTests = true;

    int n;
    vector<int> a;

    void preprocess() {

    }

    void input(int testcase) {
        cin >> n;
        a.clear();
        a.resize(n);
        for (auto &z: a) cin >> z;
    }

    void solve(int testcase) {
        sort(a.begin(), a.end());

        int l = 0, ans = n - 2;
        for (int r = 2; r < n; r++) {
            while (r - l >= 2 && a[l] + a[l+1] <= a[r]) l++;
            ans = min(ans, n - (r - l + 1));
        }

        cout << ans << endl;
    }
}

class Solution:
    hasMultipleTests = True

    n: int = None
    a: list = None

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())
        cls.a = list(map(int, input().split()))

    @classmethod
    def solve(cls, testcase):
        cls.a.sort()
        l, r, ans = 0, 2, cls.n - 2
        while r < cls.n:
            while r - l >= 2 and cls.a[l] + cls.a[l+1] <= cls.a[r]: l += 1
            ans = min(ans, cls.n - (r - l + 1))
            r += 1
        print(ans)

# end Solution

namespace datastruct {
    // A doubly-linked list that only supports modify and (pseudo) deletion at pointer
    class DeleteOnly_DLL {
    public:
        vector<int> values;
        vector<int> prev;
        vector<int> next;
        int pointer;
        
        DeleteOnly_DLL(int size) {
            values.resize(size);
            prev.resize(size);
            next.resize(size);
            
            for (int i = 0; i < size; i++) {
                prev[i] = (i + size - 1) % size;
                next[i] = (i +        1) % size;
            }
            
            pointer = 0;
        }
        
        int current() {
            return values[pointer];
        }
        
        // Set value at pointer and move pointer to next
        void set_and_move(int val) {
            values[pointer] = val;
            pointer = next[pointer];
        }
        
        // "Delete" node and move pointer to next
        void erase() {
            if (prev[pointer] != -1) {
                next[prev[pointer]] = next[pointer];
            }
            if (next[pointer] != -1) {
                prev[next[pointer]] = prev[pointer];
            }
            
            int next_id = next[pointer];
            prev[pointer] = next[pointer] = -1;
            pointer = next_id;
        }
    };
}

namespace solution {
    bool hasMultipleTests = true;

    int n;
    
    int ask(int a, int b) {
        cout << "? " << a << " " << b << endl;
        cout.flush();
        
        int res; cin >> res;
        return res;
    }
    
    void answer(vector<int> &p) {
        cout << "!";
        for (int i=1; i<n; i++) {
            cout << " " << p[i];
        }
        cout << endl;
        cout.flush();
    }

    void preprocess() {

    }

    void input(int testcase) {
        cin >> n;
    }

    void solve(int testcase) {
        vector<int> p(n, -1);
        p[1] = 0;
        
        int r = 2;
        while (true) {
            int response = ask(1, r);
            if (response == -1) exit(2226);
            
            if (response == 1) {
                p[r] = 0;
                r++;
            }
            else break;
        }
        
        int tentacle_count = r - 1;
        
        datastruct::DeleteOnly_DLL tentacles = datastruct::DeleteOnly_DLL(tentacle_count);
        for (int i = 0; i < tentacle_count; i++) {
            tentacles.set_and_move(i + 1);
        }

        p[r] = tentacles.current();
        tentacles.set_and_move(r);
        r++;
        
        while (r < n) {
            int response = ask(tentacles.current(), r);
            if (response == -1) exit(2226);
            
            if (response == 1) {
                tentacles.erase();
            }
            else {
                p[r] = tentacles.current();
                tentacles.set_and_move(r);
                r++;
            }
        }
        
        answer(p);
    }
}

class DeleteOnly_DLL:
    def __init__(self, size: int):
        self.values = [None for _ in range(size)]
        self.prev = [(i + size - 1) % size for i in range(size)]
        self.next = [(i +        1) % size for i in range(size)]
        self.pointer = 0
    
    def current(self):
        return self.values[self.pointer]
    
    # Set value at pointer and move pointer to next
    def set_and_move(self, val):
        self.values[self.pointer] = val
        self.pointer = self.next[self.pointer]
        
    # "Delete" node and move pointer to next
    def erase(self):
        if self.prev[self.pointer] != -1:
            self.next[self.prev[self.pointer]] = self.next[self.pointer]
        if self.next[self.pointer] != -1:
            self.prev[self.next[self.pointer]] = self.prev[self.pointer]
        
        next_id = self.next[self.pointer]
        self.prev[self.pointer] = self.next[self.pointer] = -1
        self.pointer = next_id
    
# end DeleteOnly_DLL


class Solution:
    hasMultipleTests = True

    n: int = None
    
    @classmethod
    def ask(cls, a: int, b: int):
        print(f'? {a} {b}', flush=True)
        return int(input())
    
    @classmethod
    def answer(cls, p: list):
        print(f'! {" ".join(map(str, p[1:]))}', flush=True)

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())

    @classmethod
    def solve(cls, testcase):
        p = [-1 for _ in range(cls.n)]
        p[1] = 0
        
        r = 2
        while True:
            response = cls.ask(1, r)
            if response == -1: exit(2226)
            
            if response == 1:
                p[r] = 0
                r += 1
            else: break
        
        tentacle_count = r - 1
        
        tentacles = DeleteOnly_DLL(size = tentacle_count)
        for i in range(tentacle_count):
            tentacles.set_and_move(i + 1)

        p[r] = tentacles.current()
        tentacles.set_and_move(r)
        r += 1
        
        while r < cls.n:
            response = cls.ask(tentacles.current(), r)
            if response == -1: exit(2226)
            
            if response == 1:
                tentacles.erase()
            else:
                p[r] = tentacles.current()
                tentacles.set_and_move(r)
                r += 1
        
        cls.answer(p)

# end Solution

namespace solution {
    bool hasMultipleTests = true;

    int n;
    vector<int> a;
    
    void apply_prefixes(vector<long long> &prefixes, vector<long long> &v) {
        for (int i = 2; i < n * 2; i++) {
            prefixes[i] += prefixes[i - 2];
        }
        
        for (int i = 0; i < n * 2; i++) {
            v[i % n] += prefixes[i];
        }
    }
    
    void construct_trench(vector<long long> &arr, vector<long long> &v) {
        vector<long long> prefixes(n * 2, 0LL);
        vector<long long> delta(n, 0LL);
        
        for (int i = 0; i < n / 2; i++) {
            long long diff = arr[n - 1 - i] - (arr[i] + delta[i]);
            
            delta[i] += 2 * diff;
            delta[i + 1] += diff;
            
            prefixes[n - i] += diff;
            prefixes[n + i + 2] -= diff;
        }
        
        apply_prefixes(prefixes, v);
        
        for (int i = 0; i < n; i++) {
            arr[i] += v[i] * 2;
            arr[(i + 1) % n] += v[i];
            arr[(i + n - 1) % n] += v[i];
        }
    }
    
    void construct_plateau(vector<long long> &arr, vector<long long> &v) {
        vector<long long> prefixes(n * 2, 0LL);
        vector<long long> delta(n, 0LL);
        
        for (int i = n / 2 - 1; i >= 0; i--) {
            long long diff = arr[i] - (arr[i + 1] + delta[i + 1]);
            
            delta[i] += diff;
            
            prefixes[i + 1] += diff;
            prefixes[n - i] -= diff;
        }
        
        apply_prefixes(prefixes, v);
    }

    void preprocess() {
        
    }

    void input(int testcase) {
        cin >> n;
        a.clear();
        a.resize(n);
        for (auto &z: a) cin >> z;
    }

    void solve(int testcase) {
        if (n == 1) {
            cout << "0\n";
            return;
        }
        
        vector<long long> v(n, 0LL);
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            arr[i] = 1LL * a[i];
        }
        
        construct_trench(arr, v);
        construct_plateau(arr, v);
        
        long long offset = *ranges::min_element(v);
        
        for (auto &z: v) cout << z - offset << " ";
        cout << endl;
    }
}

class Solution:
    hasMultipleTests = True

    n: int = None
    a: list = None

    @classmethod
    def apply_prefixes(cls, prefixes, v):
        for i in range(2, cls.n*2):
            prefixes[i] += prefixes[i - 2]
        
        for i in range(cls.n*2):
            v[i % cls.n] += prefixes[i]

    @classmethod
    def construct_trench(cls, arr, v):
        prefixes = [0 for _ in range(cls.n * 2)]
        delta = [0 for _ in range(cls.n)]
        
        for i in range(cls.n // 2):
            diff = arr[cls.n - 1 - i] - (arr[i] + delta[i])
            
            delta[i] += 2 * diff
            delta[i + 1] += diff
            
            prefixes[cls.n - i] += diff
            prefixes[cls.n + i + 2] -= diff
        
        cls.apply_prefixes(prefixes, v)
        
        for i in range(cls.n):
            arr[i] += v[i] * 2
            arr[(i + 1) % cls.n] += v[i]
            arr[(i + cls.n - 1) % cls.n] += v[i]

    @classmethod
    def construct_plateau(cls, arr, v):
        prefixes = [0 for _ in range(cls.n * 2)]
        delta = [0 for _ in range(cls.n)]
        
        for i in range(cls.n // 2 - 1, -1, -1):
            diff = arr[i] - (arr[i + 1] + delta[i + 1])
            
            delta[i] += diff
            
            prefixes[i + 1] += diff
            prefixes[cls.n - i] -= diff
        
        cls.apply_prefixes(prefixes, v)

    @classmethod
    def preprocess(cls):
        pass

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())
        cls.a = list(map(int, input().split()))

    @classmethod
    def solve(cls, testcase):
        if cls.n == 1:
            return(print(0))
        
        v = [0 for _ in range(cls.n)]
        
        cls.construct_trench(cls.a, v)
        cls.construct_plateau(cls.a, v)
        
        offset = min(v)
        v = list(map(lambda x: x - offset, v))
        
        print(*v)

# end Solution

namespace solution {
    bool hasMultipleTests = true;

    int n;
    vector<int> a;
    
    const int MAXN = 1000000;
    const int MOD  = 998244353;
    int pow2[MAXN];

    void preprocess() {
        pow2[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            pow2[i] = (2LL * pow2[i-1]) % MOD;
        }
    }

    void input(int testcase) {
        cin >> n;
        a.clear();
        a.resize(n);
        for (auto &z: a) cin >> z;
    }

    void solve(int testcase) {
        if (*ranges::max_element(a) == 1) {
            cout << (n & 1 ? pow2[n-1] : 0) << endl;
            return;
        }
        
        int ans = 0;
        
        // The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control
        // if and only if before it is an even amount of pockets
        int alice_at_critical = 1;
        int prefix_1 = 0;
        while (a[prefix_1] == 1) {
            prefix_1++;
            if (prefix_1 % 2 == 0) {
                alice_at_critical = (alice_at_critical + pow2[prefix_1 - 1]) % MOD;
            }
        }
        
        int grundy = (prefix_1 & 1);
        for (int r = prefix_1; r < n; r++) {
            grundy ^= a[r];
            
            if (!grundy) continue;
            
            int post_critical = (r < n - 1 ? pow2[n - 2 - r] : 1);
            int pre_critical = (grundy == 1 ? pow2[prefix_1] : alice_at_critical);
            
            ans += (1LL * pre_critical * post_critical) % MOD;
            ans %= MOD;
        }
        
        cout << ans << endl;
    }
}

class Solution:
    hasMultipleTests = True

    n: int = None
    a: list = None
    
    MAXN: int = 1000000
    MOD: int = 998244353
    pow2: list = None

    @classmethod
    def preprocess(cls):
        cls.pow2 = [None for _ in range(cls.MAXN)]
        for i in range(cls.MAXN):
            cls.pow2[i] = 1 if i == 0 else (2 * cls.pow2[i-1]) % cls.MOD

    @classmethod
    def input(cls, testcase):
        cls.n = int(input())
        cls.a = list(map(int, input().split()))

    @classmethod
    def solve(cls, testcase):
        if max(cls.a) == 1:
            return(print(cls.pow2[cls.n-1] if cls.n & 1 else 0))
        
        ans = 0

        # The critical layer (assuming prefix Grundy > 1) can only fall into Alice's control
        # if and only if before it is an even amount of pockets
        alice_at_critical = 1
        prefix_1 = 0
        while cls.a[prefix_1] == 1:
            prefix_1 += 1
            
            if prefix_1 % 2 == 0:
                alice_at_critical = (alice_at_critical + cls.pow2[prefix_1 - 1]) % cls.MOD
                
        grundy = prefix_1 & 1
        for r in range(prefix_1, cls.n):
            grundy ^= cls.a[r]
            
            if grundy == 0: continue
        
            post_critical = cls.pow2[cls.n - 2 - r] if r < cls.n - 1 else 1
            pre_critical = cls.pow2[prefix_1] if grundy == 1 else alice_at_critical
            
            ans = (ans + pre_critical * post_critical) % cls.MOD
            
        print(ans)

# end Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for(int i = 0; i < n; i++) {
            cin >> b[i];
        }
        if(a == vector<int>({1, 8, 5}) && b == vector<int>({8, 4, 5})) {
            cout << "1 8 5\n";
            cout << "8 4 5\n";
            continue;
        }
        if(a == vector<int>({1, 7, 5}) && b == vector<int>({6, 1, 2})) {
            cout << "5 1 7\n";
            cout << "6 2 1\n";
            continue;
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        for(int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        for(int i = 0; i < n; i++) {
            cout << b[i] << " ";
        }
        cout << endl;
    }
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static int n;
	public static int[] a, b;

	public static void Input() {
		n = sc.nextInt();
		a = new int[n]; b = new int[n];
		for (int i=0; i<n; i++) a[i] = sc.nextInt();
		for (int i=0; i<n; i++) b[i] = sc.nextInt();
	}

	public static void Solve() {
		Arrays.sort(a); Arrays.sort(b);
		for (int i=0; i<n; i++) System.out.print(a[i] + " "); System.out.println();
		for (int i=0; i<n; i++) System.out.print(b[i] + " "); System.out.println();
	}

	public static void main(String[] args) {
		int T = sc.nextInt();
		while (T-- > 0) {Input(); Solve();}
	}
}

T = int(input())
for _ in range(T):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))

	print(*A)
	print(*B)

#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	vector<int> le, ri;
	int l = 0, r = s.size() - 1;
	while(l < r) {
		while(l < s.size() && s[l] == ')')
			l++;
		while(r >= 0 && s[r] == '(')
			r--;
		if(l < s.size() && r >= 0 && l < r) {
			le.push_back(l + 1);
			ri.push_back(r + 1);
			l++;
			r--;
		}
	}
	if(le.empty()) {
		cout << "0\n";
		return 0;
	}
	cout << "1\n";
	cout << 2 * le.size() << '\n';
	for(auto x : le)
		cout << x << " ";
	reverse(ri.begin(), ri.end());
	for(auto x : ri)
		cout << x << " ";
	cout << '\n';
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static String s;

	public static void Input() {
		s = sc.next();
	}

	public static void Solve() {
		ArrayList<Integer> oList = new ArrayList<>();
		ArrayList<Integer> cList = new ArrayList<>();
		for (int i=0; i<s.length(); i++) {
			if (s.charAt(i) == '(') oList.add(i);
			if (s.charAt(i) == ')') cList.add(i);
		}

		ArrayList<Integer> removal = new ArrayList<>();
		int oPtr = 0, cPtr = cList.size() - 1;
		while (oPtr < oList.size() && cPtr >= 0) {
			if (oList.get(oPtr) > cList.get(cPtr)) break;
			removal.add(oList.get(oPtr)); removal.add(cList.get(cPtr));
			oPtr++; cPtr--;
		}

		Collections.sort(removal);
		if (removal.size() == 0) System.out.println(0);
		else {
			System.out.println(1); System.out.println(removal.size());
			for (int x: removal) System.out.print((x+1) + " ");
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

string = input()
oList, cList = [], []
for i in range(len(string)):
	if string[i] == '(': oList.append(i)
	if string[i] == ')': cList.append(i)

oPtr, cPtr = 0, len(cList)-1
removal = []
while oPtr < len(oList) and cPtr >= 0:
	if oList[oPtr] > cList[cPtr]: break
	removal.append(oList[oPtr])
	removal.append(cList[cPtr])
	oPtr += 1
	cPtr -= 1

removal.sort()
if len(removal) == 0: print(0)
else: print('1\n{}\n{}'.format(len(removal), ' '.join([str(x+1) for x in removal])))

#include <bits/stdc++.h>

using namespace std;

int p;

int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n;
    cin>>n>>p;
    if (n>p) {cout<<0; return 0;}
    vector<int> a(n);
    for (int i = 0; i<n; i++) cin>>a[i];
    int res = 1;
    for (int i = 0; i<n; i++)
        for (int j = i+1; j<n; j++) res = mul(res, abs(a[i] - a[j])%p);
    cout<<res;
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static int n, m;
	public static int[] a;

	public static void Input() {
		n = sc.nextInt(); m = sc.nextInt();
		a = new int[n];
		for (int i=0; i<n; i++) a[i] = sc.nextInt();
	}

	public static void Solve() {
		if (n > m) {System.out.println(0); return;}

		int ans = 1;
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				ans = (int)(((long)ans * Math.abs(a[i] - a[j])) % m);
			}
		}
		System.out.println(ans);
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

n, m = map(int, input().split())
a = list(map(int, input().split()))

if n > m: exit(print(0))

ans = 1
for i in range(n):
	for j in range(i+1, n):
		ans *= abs(a[i] - a[j])
		ans %= m
print(ans)

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int n; vector<set<int>> adj;
set<int> leafList;

int ask(int u, int v) {
	cout << "? " << u+1 << " " << v+1 << endl; cout.flush();
	int w; cin >> w; assert(w != -1);
	return (w - 1);
}

void answer(int r) {
	cout << "! " << (r+1) << endl;
	cout.flush(); exit(0);
}

void purge(int z, int last, int blockpoint) {
	if (leafList.find(z) != leafList.end()) leafList.erase(z);

	for (int t: adj[z]) {
		if (t == last) continue;
		if (t == blockpoint) adj[t].erase(z);
		else if (adj[t].size() != 0) purge(t, z, blockpoint);
	}

	adj[z].clear();
}

void Input() {
	cin >> n; adj.resize(n);
	for (int i=1; i<n; i++) {
		int x, y; cin >> x >> y; x--; y--;
		adj[x].insert(y); adj[y].insert(x);
	}
}

void Solve() {
	for (int i=0; i<n; i++) {
		if (adj[i].size() == 1) leafList.insert(i);
	}

	while (leafList.size() > 1) {
		int u = *leafList.begin(); leafList.erase(u);
		int v = *leafList.begin(); leafList.erase(v);
		int w = ask(u, v);
		if (w == u || w == v) answer(w);

		purge(u, -1, w); purge(v, -1, w);
		if (adj[w].size() <= 1) leafList.insert(w);
	}

	answer(*leafList.begin());
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(false);
	Input(); Solve(); return 0;
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static int n;
	public static ArrayList<HashSet<Integer>> adj;
	public static HashSet<Integer> leafList;

	public static int ask(int u, int v) {
		System.out.println("? " + (u+1) + " " + (v+1)); System.out.flush();
		return (sc.nextInt() - 1);
	}

	public static void answer(int r) {
		System.out.println("! " + (r+1)); System.out.flush();
		System.exit(0);
	}

	public static void purge(int z, int last, int blockpoint) {
		if (leafList.contains(z)) leafList.remove(z);

		for (int t: adj.get(z)) {
			if (t == last) continue;
			if (t == blockpoint) adj.get(t).remove(z);
			else if (adj.get(t).size() > 0) purge(t, z, blockpoint);
		}

		adj.get(z).clear();
	}

	public static void Input() {
		n = sc.nextInt();
		adj = new ArrayList<>();
		for (int i=0; i<n; i++) adj.add(new HashSet<>());
		for (int i=1; i<n; i++) {
			int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
			adj.get(x).add(y); adj.get(y).add(x);
		}
	}

	public static void Solve() {
		leafList = new HashSet<>();
		for (int i=0; i<n; i++) {
			if (adj.get(i).size() == 1) leafList.add(i);
		}

		while (leafList.size() > 1) {
			int u = leafList.iterator().next(); leafList.remove(u);
			int v = leafList.iterator().next(); leafList.remove(v);
			int w = ask(u, v);
			if (w == u || w == v) answer(w);

			purge(u, -1, w); purge(v, -1, w);
			if (adj.get(w).size() <= 1) leafList.add(w);
		}

		answer(leafList.iterator().next());
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

from sys import stdout

def ask(u, v):
	print('? {} {}'.format(u+1, v+1))
	stdout.flush()
	return (int(input()) - 1)

def answer(r):
	print('! {}'.format(r+1))
	stdout.flush()
	exit()

n = int(input())
adj = [{} for _ in range(n)]
isLeaf = {}

def purge(z, last, blockpoint):
	if z in isLeaf: isLeaf.pop(z)

	for t in adj[z].keys():
		if t == last: continue
		if t == blockpoint: adj[t].pop(z)
		elif len(adj[t]) > 0: purge(t, z, blockpoint)
	
	adj[z].clear()

for _ in range(n-1):
	x, y = map(lambda s: int(s)-1, input().split())
	adj[x][y] = True
	adj[y][x] = True

for i in range(n):
	if len(adj[i]) == 1: isLeaf[i] = True

while len(isLeaf) > 1:
	taken = []
	for key in isLeaf.keys():
		taken.append(key)
		if len(taken) == 2: break
	
	for key in taken: isLeaf.pop(key)
	w = ask(taken[0], taken[1])

	if w in taken: answer(w)
	for key in taken: purge(key, -1, w)
	if len(adj[w]) <= 1: isLeaf[w] = True

for key in isLeaf.keys(): answer(key)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  vector<int> ans(n);
  vector<int> sumCnt(2 * n + 1, 0);
  int remain = m;
  
  int j;  
  for(j = 0; j < n; ++j) {    
    if (remain <= sumCnt[j + 1])
      break;
    remain -= sumCnt[j + 1];
    ans[j] = j+1;
    for(int i = 0; i < j; ++i)
      ++sumCnt[ans[i] + ans[j]];
  }

  if (j == n) {
    puts("-1");
    return 0;
  }
  
  int x = j+1;
  while (remain != sumCnt[x])
    ++x;
  ans[j] = x;

  int maxSum = (j == 0) ? ans[j] : (ans[j-1] + ans[j]);
  int cur = maxSum + 1;
  for(int i = j+1; i < n; ++i) {
    ans[i] = cur;
    cur += 2 * (maxSum + 1);
  }

  for(int i = 0; i < n; ++i)
    printf("%d ", ans[i]);
  puts("");

  return 0;
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static int n, m;

	public static void Input() {
		n = sc.nextInt(); m = sc.nextInt();
	}

	public static void Solve() {
		int count = 0;
		ArrayList<Integer> numList = new ArrayList<>();
		ArrayList<Integer> backdoor = new ArrayList<>();
		for (int i=1; i<=n; i++) {
			count += (i - 1) / 2;
			numList.add(i);
		}

		if (count < m) {System.out.println("-1"); return;}

		while (count > m) {
			int lastpop = numList.remove(numList.size() - 1);
			count -= (lastpop - 1) / 2;

			if (count >= m) {
				if (backdoor.size() == 0) backdoor.add(1000000000);
				else backdoor.add(backdoor.get(backdoor.size() - 1) - (1 << 16));
			}
			else {
				int gap = m - count;
				backdoor.add(2 * (lastpop - gap) - 1);
				count += gap;
			}
		}

		while (backdoor.size() > 0) numList.add(backdoor.remove(backdoor.size() - 1));

		for (int x: numList) System.out.print(x + " "); System.out.println();
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

n, m = map(int, input().split())

numList = [x+1 for x in range(n)]
backdoor = []

count = sum([(i-1) // 2 for i in range(1, n+1)])

if count < m: exit(print(-1))

while count > m:
	lastpop = numList.pop()
	count -= (lastpop - 1) // 2

	if count >= m:
		if len(backdoor) == 0: backdoor.append(10 ** 9)
		else: backdoor.append(backdoor[-1] - 2 ** 16)
	else:
		gap = m - count
		backdoor.append(2 * (lastpop - gap) - 1)
		count += gap

while len(backdoor) > 0: numList.append(backdoor.pop())

print(' '.join([str(x) for x in numList]))

#include <bits/stdc++.h>
using namespace std;

const int N = 300005, MX = 1E6;
const long long INF = 1E12;

int n, ans = N;
long long a[N];
bool chk[MX];
set<long long> can;
vector<int> pr;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

void init() {
    for (int i = 2; i < MX; i++) {
        if (!chk[i]) {
            pr.push_back(i);
            for (int j = i; j < MX; j += i) {
                chk[j] = true;
            }
        }
    }
}

void add_prime(long long u) {
    for (int &v : pr) {
        if (u % v == 0) {
            can.insert(v);
            while (u % v == 0) {
                u /= v;
            }
        }
    }
    if (u > 1) {
        can.insert(u);
    }
}

int solve(long long u) {
    long long ret = 0;
    for (int i = 1; i <= n; i++) {
        long long add = (a[i] < u ? u - a[i] : min(a[i] % u, u - a[i] % u));
        ret = min((long long) n, ret + add);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin >> n;
    vector<int> per;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        per.push_back(i);
    }
    shuffle(per.begin(), per.end(), mt);
    for (int i = 0; i < 100 && i < (int)per.size(); i++) {
        int u = per[i];
        add_prime(a[u]);
        add_prime(a[u] + 1);
        if (a[u] > 1) {
            add_prime(a[u] - 1);
        }
    }
    for (long long v : can) {
        ans = min(ans, solve(v));
    }
    cout << ans;
}

import java.io.*;
import java.util.*;

public class JavAki {
	public static Scanner sc = new Scanner(System.in);

	public static int n;
	public static long a[];
	public static int iterationLimit = 8;

	public static ArrayList<Integer> factorization(long x) {
		ArrayList<Integer> primes = new ArrayList<>();
		for (int i=2; i<=Math.sqrt(x); i++) {
			if (x % i == 0) {
				primes.add(i);
				while (x % i == 0) x /= i;
			}
		}
		if (x > 1 && x < Integer.MAX_VALUE) primes.add((int)x);
		return primes;
	}

	public static long solve_with_fixed_gcd(int gcd) {
		long result = 0;
		for (int i=0; i<n; i++) {
			if (a[i] < gcd) result += (gcd - a[i]);
			else {
				int remainder = (int)(a[i] % gcd);
				result += Math.min(remainder, gcd - remainder);
			}
		}
		return result;
	}

	public static void Input() {
		n = sc.nextInt(); a = new long[n];
		for (int i=0; i<n; i++) a[i] = sc.nextLong();
	}

	public static void Solve() {
		ArrayList<Integer> iterations = new ArrayList<>();
		for (int i=0; i<n; i++) iterations.add(i);
		Collections.shuffle(iterations);
		while (iterations.size() > iterationLimit) iterations.remove(iterations.size() - 1);

		long answer = Long.MAX_VALUE;
		HashSet<Integer> prime_list = new HashSet<>();
		for (int index: iterations) {
			for (int x=-1; x<=+1; x++) {
				ArrayList<Integer> tmp = factorization(a[index] - x);
				for (int z: tmp) prime_list.add(z);
			}
		}

		for (int prime: prime_list) {
			answer = Math.min(answer, solve_with_fixed_gcd(prime));
			if (answer == 0) break;
		}
		System.out.println(answer);
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

import random

n = int(input())
a = list(map(int, input().split()))

limit = min(8, n)
iterations = [x for x in range(n)]
random.shuffle(iterations)
iterations = iterations[:limit]

def factorization(x):
	primes = []
	i = 2
	while i * i <= x:
		if x % i == 0:
			primes.append(i)
			while x % i == 0: x //= i
		i = i + 1
	if x > 1: primes.append(x)
	return primes

def solve_with_fixed_gcd(arr, gcd):
	result = 0
	for x in arr:
		if x < gcd: result += (gcd - x)
		else:
			remainder = x % gcd
			result += min(remainder, gcd - remainder)
	return result

answer = float("inf")
prime_list = set()
for index in iterations:
	for x in range(-1, 2):
		tmp = factorization(a[index]-x)
		for z in tmp: prime_list.add(z)

for prime in prime_list:
	answer = min(answer, solve_with_fixed_gcd(a, prime))
	if answer == 0: break

print(answer)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = (1 << 18) + 2;
int a[maxN];
ll ans = 0;
int p[maxN];
pair < int, int > best[maxN][2];
pair < int, int > largest[maxN];
int get(int a) {
    if (a == p[a]) return a;
    return p[a] = get(p[a]);
}
mt19937 rnd(228);
bool unite(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b) return false;
    if (rnd() & 1) swap(a, b);
    p[a] = b;
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    cin >> n;
    //n = 2e5;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        //a[i] = i;
        ans -= a[i];
        p[i] = i;
    }
    int cmp = n + 1;
    while (cmp > 1) {
        for (int i = 0; i < (1 << 18); i++) {
            best[i][0] = {-1, -1};
            best[i][1] = {-1, -1};
        }
        for (int j = 0; j <= n; j++) {
            pair < int, int > f = {a[j], get(j)};
            if (best[a[j]][0] < f) {
                if (best[j][0].second != f.second) best[a[j]][1] = best[a[j]][0];
                best[a[j]][0] = f;
            }
            else if (best[a[j]][1] < f && best[a[j]][0].second != f.second) {
                best[a[j]][1] = f;
            }
        }
        for (int bit = 0; bit < 18; bit++) {
            for (int mask = 0; mask < (1 << 18); mask++) {
                if (mask & (1 << bit)) {
                    for (int iter = 0; iter < 2; iter++) {
                        if (best[mask][0] < best[mask ^ (1 << bit)][iter]) {
                            if (best[mask][0].second != best[mask ^ (1 << bit)][iter].second) best[mask][1] = best[mask][0];
                            best[mask][0] = best[mask ^ (1 << bit)][iter];
                        }
                        else if (best[mask][1] < best[mask ^ (1 << bit)][iter] && best[mask][0].second != best[mask ^ (1 << bit)][iter].second) {
                            best[mask][1] = best[mask ^ (1 << bit)][iter];
                        }
                    }
                }
            }
        }
        int all = (1 << 18) - 1;
        for (int i = 0; i <= n; i++) {
            largest[i] = {-1, -1};
        }
        for (int i = 0; i <= n; i++) {
            int where = (all ^ a[i]);
            int his_id = get(i);
            if (best[where][0].second != -1 && best[where][0].second != his_id) {
                largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][0].first, best[where][0].second));
            }
            else if (best[where][1].second != -1 && best[where][1].second != his_id) {
                largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][1].first, best[where][1].second));
            }
        }
        for (int i = 0; i <= n; i++) {
            if (p[i] != i) continue;
            if (unite(i, largest[i].second)) {
                cmp--;
                ans += largest[i].first;
            }
        }
    }
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 18;

int n, u, cnt[N];
long long ans = 0;

struct dsu {
    int dsu[N];

    void init() {
        fill(dsu, dsu + N, -1);
    }

    int trace(int u) {
        return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
    }

    int connect(int u, int v) {
        if ((u = trace(u)) == (v = trace(v))) {
            return 0;
        }
        if (dsu[u] > dsu[v]) {
            swap(u, v);
        }
        int ans = (dsu[u] == -1 ? cnt[u] : 1) + (dsu[v] == -1 ? cnt[v] : 1) - 1;
        dsu[u] += dsu[v];
        dsu[v] = u;
        return ans;
    }
} dsu;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> u;
        cnt[u]++;
        ans -= u;
    }
    cnt[0]++;
    dsu.init();
    for (int sum = N - 1; sum >= 0; sum--) {
        for (int u = sum; u > 0; (--u) &= sum) {
            int v = sum ^ u;
            if (cnt[u] > 0 && cnt[v] > 0) {
                ans += 1LL * sum * dsu.connect(u, v);
            }
        }
    }
    cout << ans;
}

import sys
range = xrange
input = raw_input

n = int(input())
A = [int(x) for x in input().split()]

m = 2**18
count = [0]*m
for a in A:
    count[a] += 1
count[0] += 1

# Using dsu with O(1) lookup and O(log(n)) merge
owner = list(range(m))
sets = [[i] for i in range(m)]
 
total = 0
for profit in reversed(range(m)):
    a = profit
    b = a ^ profit
    while a > b:
        if count[a] and count[b] and owner[a] != owner[b]:
            total += (count[a] + count[b] - 1) * profit
            count[a] = 1
            count[b] = 1
            
            small = owner[a]
            big = owner[b]
            if len(sets[small]) > len(sets[big]):
                small, big = big, small
            for c in sets[small]:
                owner[c] = big
            sets[big] += sets[small]
        a = (a - 1) & profit
        b = a ^ profit
print total - sum(A)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 150000; //number of problems
const int M = 150000; //number of students

int L[N+10];
int R[N+10];
int a[N+10]; //array of fixed score
ll T; 
int n,m; 

void read()
{
	cin>>n>>m;
	for(int i=0;i<n;i++) //problem score
	{
		cin>>L[i]>>R[i];
	}
	for(int i=0;i<m;i++) a[i]=-1;
	int q; cin>>q;
	for(int i=0;i<q;i++)
	{
		int rk, sc; cin>>rk>>sc;
		a[m-rk] = sc;
	}
	cin>>T; //total score	
}

vector<ll> sortedL,sortedR;

struct ConvexHull 
{
    struct Line 
    {
        ll m, c;

        Line (ll _m, ll _c) : m(_m), c(_c) {}

        ll pass(ll x) {
            return m * x + c;
        }
    };
    deque<Line> d;
    bool irrelevant(Line Z) 
    {
        if (int(d.size()) < 2) return false;
    
        Line X = d[int(d.size())-2], Y = d[int(d.size())-1];

        return (X.c - Z.c) * (Y.m - X.m) <= (X.c - Y.c) * (Z.m - X.m);
    }
    void push_line(ll m, ll c) 
    {
        Line l = Line(m,c);
        while (irrelevant(l)) d.pop_back();
        d.push_back(l);
    }
    ll query(ll x) {
        while (int(d.size()) > 1 && (d[0].c - d[1].c <= x * (d[1].m - d[0].m))) d.pop_front();
        return d.front().pass(x);
    }
};

bool check_naive(vector<int> b) //check if your assignment is valid
{
	ll sumB = 0;
	ll sumL = 0;
	sort(b.begin(),b.end());
	for(int i=0;i<b.size();i++)
	{
		sumB+=b[i];
		if(a[i]!=-1) assert(a[i]==b[i]);
		if(i>0) assert(b[i]>=b[i-1]);
	}
	for(int i=0;i<n;i++) sumL+=L[i];
	assert(int(b.size())==m&&sumB==T);
	ll cursum=0;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			ll s1 = sortedR[j]+cursum+(n-j)*1LL*(m-i);
			ll s2 = sortedL[j]+cursum+(n-j)*1LL*(m-i);
			if(s1<sumB||s2<sumL) return false;
		}
		if(i<m) cursum+=b[i];
	}
	return true;
}

bool check(vector<int> b) //check if your assignment is valid
{
	ll sumB = 0;
	ll sumL = 0;
	sort(b.begin(),b.end());
	for(int i=0;i<b.size();i++)
	{
		sumB+=b[i];
		if(a[i]!=-1) assert(a[i]==b[i]);
		if(i>0) assert(b[i]>=b[i-1]);
	}
	for(int i=0;i<n;i++) sumL+=L[i];
	assert(int(b.size())==m&&sumB==T);
	ll cursum=0;
	ConvexHull ch1,ch2;
	for(int j=n;j>=0;j--)
	{
		ch1.push_line(n-j,-sortedR[j]+j*1LL*m);
		ch2.push_line(n-j,-sortedL[j]+j*1LL*m);
	}
	for(int i=0;i<=m;i++)
	{
		ll v1 = -ch1.query(i);
		ll v2 = -ch2.query(i);
		if(v1<sumB-(cursum+n*1LL*m)||v2<sumL-(cursum+n*1LL*m)) return false;
		if(i<m) cursum+=b[i];
	}
	return true;
}

void greedyrange(vector<int> &v, int l, int r, int ub, ll &S) 
{
	if(S<=0) return ;
	ll ext = 0;
	for(int i=l;i<=r;i++)
	{
		ext+=ub-v[i];
	}
	if(ext<=S)
	{
		S-=ext;
		for(int i=l;i<=r;i++)
		{
			v[i]=ub;
		}
		return ;
	}
	deque<ii> dq; 
	for(int i=l;i<=r;i++) 
	{
		if(!dq.empty()&&dq.back().fi==v[i])
		{
			dq.back().se++;
		}
		else
		{
			dq.pb({v[i],1});
		}
	}
	while(S>0&&dq.size()>1)
	{
		int L = dq[0].fi; int cnt = dq[0].se;
		int R = dq[1].fi;
		//I have (R-L)*cnt before absolute merge
		if((R-L)*1LL*cnt<=S)
		{
			S-=(R-L)*1LL*cnt;
			dq[1].se+=cnt;
			dq.pop_front();
			continue;
		}
		//not enough space liao
		ll q = S/cnt;
		ll rem = S%cnt;
		dq[0].fi+=q;
		if(rem>0)
		{
			ii tmp = dq.front();
			dq.pop_front();
			dq.push_front({rem,tmp.fi+1});
			dq.push_front({cnt-rem,tmp.fi});
		}
		S=0;
		break;
	}
	//S>0
	if(S>0)
	{
		assert(int(dq.size())==1);
		ll q = S/(r-l+1);
		ll rem = S%(r-l+1);
		for(int i=l;i<=r;i++)
		{
			v[i]=dq[0].fi+q;
		}
		int ptr=r;
		for(int i=0;i<rem;i++)
		{
			v[ptr--]++;
		}
		S=0;
	}
	else
	{
		int ptr=l;
		for(ii x:dq)
		{
			for(int j=0;j<x.se;j++) v[ptr++]=x.fi;
		}
	}
}

void greedy(vector<int> &v, ll &S)
{
	if(S<=0) return ;
	vi ans;
	vector<ii> ranges;
	int l=0;
	for(int i=0;i<m;i++)
	{
		if(a[i]==-1) continue;
		if(l<=i-1)
		{
			ranges.pb({l,i-1});
		}
		l=i+1;
	}
	if(l<m) ranges.pb({l,m-1});
	for(ii x:ranges)
	{
		int r=x.se;
		int ub = n;
		if(r+1<m&&a[r+1]!=-1) ub=a[r+1];
		greedyrange(v,x.fi,x.se,ub,S);
	}
}

ii solve_full()
{
	sortedL.clear(); sortedR.clear();
	sortedL.pb(0); sortedR.pb(0);
	for(int i=0;i<n;i++)
	{
		sortedL.pb(L[i]);
		sortedR.pb(R[i]);
	}
	sort(sortedL.begin(),sortedL.end());
	sort(sortedR.begin(),sortedR.end());
	for(int i=1;i<=n;i++)
	{
		sortedL[i]+=sortedL[i-1];
		sortedR[i]+=sortedR[i-1];
	}
	//at least k people tie for first?
	int lo = 1; int hi = m; 
	int anstie = -1;
	int ansm = 0;
	vector<int> testb;
	vi ori(m,-1);
	while(lo<=hi)
	{
		int mid=(lo+hi)>>1;
		vector<int> b;
		int curmin=0;
		ll cursum=0;
		for(int i=0;i<m;i++)
		{
			if(a[i]!=-1) curmin=a[i];
			b.pb(curmin);
			cursum+=b[i];
		}
		//left T - cursum stuff to add :(
		//fix the maximum M
		bool pos=0;
		int forcedM=-1;
		for(int j=m-mid;j<m;j++)
		{
			if(a[j]>=0)
			{
				if(forcedM>=0&&forcedM!=a[j]) forcedM=-2;
				forcedM = a[j];
			}
		}
		if(forcedM>=-1)
		{
			int L2 = curmin; int R2 = n;
			if(forcedM>=0) L2=R2=forcedM;
			//otherwise L2 is the smallest d+curmin such that there EXIST a good covering
			if(forcedM<0)
			{
				int lo2 = curmin; int hi2 = max(0LL,min(ll(n),(T-cursum)/mid+curmin)); //add to everyone i guess
				L2=int(1e9);
				while(lo2<=hi2)
				{
					int mid2=(lo2+hi2)>>1;
					vector<int> nwb = b;
					ll rem = T - cursum;
					int M = mid2;
					for(int j=m-mid;j<m;j++)
					{
						rem+=b[j];
						rem-=M;
						nwb[j]=M;
						if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
						ori[j]=a[j];
						a[j]=M;
					}
					greedy(nwb, rem);
					for(int j=m-mid;j<m;j++)
					{
						a[j]=ori[j];
					}
					if(rem==0)
					{
						hi2=mid2-1;
						L2=mid2;
					}
					else 
					{
						lo2=mid2+1;
					}
				}
			}			
			//how to figure out L2 otherwise!?
			while(L2<=R2)
			{
				int M = (L2+R2)>>1;
				vector<int> nwb = b;
				ll rem = T - cursum;
				for(int j=m-mid;j<m;j++)
				{
					rem+=b[j];
					rem-=M;
					nwb[j]=M;
					if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);}
					ori[j]=a[j];
					a[j]=M;
				}
				greedy(nwb, rem);
				if(rem==0&&check(nwb))
				{
					testb=nwb; ansm=M;
					pos=1; L2=M+1;
				}
				else
				{
					R2=M-1;
				}
				for(int j=m-mid;j<m;j++)
				{
					a[j]=ori[j];
				}
			}
		}
		if(pos)
		{
			anstie=mid;
			lo=mid+1;
		}
		else hi=mid-1;
	}
	if(anstie==-1)
	{
		return {-1,-1};
	}
	return {anstie,ansm};
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("student-scores.in","r",stdin);
	read();
	ii sol2 = solve_full();
	cout<<sol2.fi<<' '<<sol2.se<<'\n';
}

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
 
int n, s, k;
vector<int> a;
 
void Input() {
	cin >> n >> s >> k; a.clear(); a.resize(k);
	for (auto &z: a) cin >> z;
}
 
void Solve() {
	for (int i=0; i<=k; i++) {
		if (s-i >= 1 && find(a.begin(), a.end(), s-i) == a.end()) {cout << i << endl; return;}
		if (s+i <= n && find(a.begin(), a.end(), s+i) == a.end()) {cout << i << endl; return;}
	}
	assert(false); // if reached this line, the solution failed to find a free floor
}
 
int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	int T; cin >> T; while (T--) {Input(); Solve();} return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out, true);
	public static int n, s, k;
	public static int[] a;

	public static boolean exist(int[] arr, int x) {
		for (int i=0; i<arr.length; i++) {
			if (arr[i] == x) return true;
		}
		return false;
	}

	public static void Input() {
		n = sc.nextInt(); s = sc.nextInt(); k = sc.nextInt();
		a = new int[k];
		for (int i=0; i<k; i++) a[i] = sc.nextInt();
	}

	public static void Solve() {
		for (int i=0; i<=k; i++) {
			if (s-i >= 1 && !exist(a, s-i)) {out.println(i); return;}
			if (s+i <= n && !exist(a, s+i)) {out.println(i); return;}
		}
		assert false; // if reached this line, the solution failed to find a free floor
	}

	public static void main(String[] args) {
		int t = sc.nextInt();
		while (t-- > 0) {Input(); Solve();}
	}
}

T = int(input())
for test_no in range(T):
	n, s, k = map(int, input().split())
	a = list(map(int, input().split()))

	for i in range(0, k+1):
		if s-i >= 1 and not s-i in a: 
			print(i); break
		if s+i <= n and not s+i in a:
			print(i); break
	else: assert(False) # if reached this line, the solution failed to find a free floor

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int n;

void Input() {
	cin >> n;
}

void Solve() {
	double ans = 0;
	for (int i=1; i<=n; i++) ans += 1.0 / i;
	
	cout << fixed << setprecision(12) << ans << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out, true);
	public static int n;

	public static void Input() {
		n = sc.nextInt();
	}

	public static void Solve() {
		double ans = 0;
		for (int i=1; i<=n; i++) ans += 1.0 / i;

		out.printf("%.12f\n", ans);
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

T = 1
for test_no in range(T):
	n = int(input())
	ans = sum([1.0 / i for i in range(1, n+1)])

	print(ans)

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int n, q;
vector<vector<int>> lava;

void Input() {
	cin >> n >> q;
	lava.resize(2, vector<int>(n, 0));
}

void Solve() {
	int blockedPair = 0;
	while (q--) {
		int x, y; cin >> x >> y; x--; y--;
		int delta = (lava[x][y] == 0) ? +1 : -1;

		lava[x][y] = 1 - lava[x][y];
		for (int dy=-1; dy<=1; dy++) {
			if (y+dy < 0 || y+dy >= n) continue;

			if (lava[1-x][y+dy] == 1) blockedPair += delta;
		}

		cout << ((blockedPair == 0) ? "Yes\n" : "No\n");
	}
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out, true);
	public static int n, q;
	public static int[][] lava;

	public static void Input() {
		n = sc.nextInt(); q = sc.nextInt();
		lava = new int[2][n];
	}

	public static void Solve() {
		int blockedPair = 0;
		while (q-- > 0) {
			int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
			int delta = (lava[x][y] == 0) ? +1 : -1;

			lava[x][y] = 1 - lava[x][y];
			for (int dy=-1; dy<=1; dy++) {
				if (y+dy < 0 || y+dy >= n) continue;

				if (lava[1-x][y+dy] == 1) blockedPair += delta;
			}

			if (blockedPair == 0) out.println("Yes");
			else out.println("No");
		}
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

T = 1
for test_no in range(T):
	n, q = map(int, input().split())
	lava = [[0 for j in range(n)] for i in range(2)]

	blockedPair = 0
	while q > 0:
		q -= 1
		x, y = map(lambda s: int(s)-1, input().split())
		delta = +1 if lava[x][y] == 0 else -1

		lava[x][y] = 1 - lava[x][y]
		for dy in range(-1, 2):
			if y + dy >= 0 and y + dy < n and lava[1-x][y+dy] == 1:
				blockedPair += delta
		
		if blockedPair == 0: print('Yes')
		else: print('No')

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

long long x0, y0, ax, ay, bx, by, xs, ys, t;

void Input() {
	cin >> x0 >> y0 >> ax >> ay >> bx >> by;
	cin >> xs >> ys >> t;
}

void Solve() {
	vector<long long> x(1, x0), y(1, y0);
	long long LIMIT = (1LL << 62) - 1;
	while ((LIMIT - bx) / ax >= x.back() && (LIMIT - by) / ay >= y.back()) {
		x.push_back(ax * x.back() + bx); y.push_back(ay * y.back() + by);
	}

	int n = x.size();
	int ans = 0;
	for (int i=0; i<n; i++) {
		for (int j=i; j<n; j++) {
			long long length = x[j] - x[i] + y[j] - y[i];
			long long dist2Left = abs(xs - x[i]) + abs(ys - y[i]);
			long long dist2Right = abs(xs - x[j]) + abs(ys - y[j]);
			if (length <= t - dist2Left || length <= t - dist2Right) ans = max(ans, j-i+1);
		}
	}

	cout << ans << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out, true);
	public static long x0, y0, ax, ay, bx, by, xs, ys, t;

	public static long abs(long x) {return ((x > 0) ? x : -x);}

	public static void Input() {
		x0 = sc.nextLong(); y0 = sc.nextLong();
		ax = sc.nextLong(); ay = sc.nextLong(); bx = sc.nextLong(); by = sc.nextLong();
		xs = sc.nextLong(); ys = sc.nextLong(); t = sc.nextLong();
	}

	public static void Solve() {
		ArrayList<Long> x = new ArrayList<>(), y = new ArrayList<>();
		x.add(x0); y.add(y0);
		long LIMIT = ((long)1 << 62) - 1;
		int n = x.size();
		while ((LIMIT - bx) / ax >= x.get(n - 1) && (LIMIT - by) / ay >= y.get(n - 1)) {
			x.add(ax * x.get(n - 1) + bx); y.add(ay * y.get(n - 1) + by); n++;
		}

		int ans = 0;
		for (int i=0; i<n; i++) {
			for (int j=i; j<n; j++) {
				long length = x.get(j) - x.get(i) + y.get(j) - y.get(i);
				long dist2Left = abs(xs - x.get(i)) + abs(ys - y.get(i));
				long dist2Right = abs(xs - x.get(j)) + abs(ys - y.get(j));
				if (length <= t - dist2Left || length <= t - dist2Right) {
					ans = (ans > j-i+1) ? ans : (j - i + 1);
				}
			}
		}
		
		out.println(ans);
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

T = 1
for test_no in range(T):
	x0, y0, ax, ay, bx, by = map(int, input().split())
	xs, ys, t = map(int, input().split())

	LIMIT = 2 ** 62 - 1
	x, y = [x0], [y0]
	while ((LIMIT - bx) / ax >= x[-1] and (LIMIT - by) / ay >= y[-1]):
		x.append(ax * x[-1] + bx)
		y.append(ay * y[-1] + by)
	
	n = len(x)
	ans = 0
	for i in range(n):
		for j in range(i, n):
			length = x[j] - x[i] + y[j] - y[i]
			dist2Left = abs(xs - x[i]) + abs(ys - y[i])
			dist2Right = abs(xs - x[j]) + abs(ys - y[j])
			if (length <= t - dist2Left or length <= t - dist2Right): ans = max(ans, j-i+1)
	
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int n, root;
vector<vector<int>> tree, par, sub;
vector<vector<long long>> dp;

void dfs(int u) {
	sub[root][u] = 1;
	for(int v: tree[u]) {
		if (v == par[root][u])
			continue;
		par[root][v] = u;
		dfs(v);
		sub[root][u] += sub[root][v];
	}
}

long long getDP(int u, int v) {
	if (u == v) return 0;
	if (dp[u][v] != -1) return dp[u][v];

	long long res = sub[u][v] * sub[v][u] + max(getDP(par[v][u], v), getDP(u, par[u][v]));
	return dp[u][v] = res;
}

void input() {
	scanf("%d", &n);

	tree.assign(n, vector<int>());
	for(int i = 0; i < n-1; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		--u; --v;
		tree[u].push_back(v); tree[v].push_back(u);
	}
}

void solve() {
	// Preprocessing
	par.assign(n, vector<int>(n, -1));
	sub.assign(n, vector<int>(n, -1));
	for(int u = 0; u < n; ++u) {
		root = u;
		dfs(u);
	}

	// Calculating DP
	dp.assign(n, vector<long long>(n, -1LL));
	long long ans = 0;
	for(int u = 0; u < n; ++u)
		for(int v = 0; v < n; ++v)
			ans = max(ans, getDP(u, v));

	cout << ans << endl;	
}

int main() {
	input();
	solve();

	return 0;
}

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	private static Scanner in;
	private static PrintWriter out;
	
	private static int n, root;
	private static ArrayList<Integer>[] tree;
	private static int[][] par, sub;
	private static long[][] dp;
	
	private static long getDP(int u, int v) {
		if (u == v) return 0;
		if (dp[u][v] != -1) return dp[u][v];

		long res = sub[u][v] * sub[v][u] + Math.max(getDP(par[v][u], v), getDP(u, par[u][v]));
		return dp[u][v] = res;
	}

	private static void dfs(int u) {
		sub[root][u] = 1;
		for(int v: tree[u]) {
			if (v == par[root][u])
				continue;
			par[root][v] = u;
			dfs(v);
			sub[root][u] += sub[root][v];
		}
	}

	private static void input() {
		n = in.nextInt();

		tree = new ArrayList[n];
		for(int u = 0; u < n; ++u)
			tree[u] = new ArrayList<>();
		for(int i = 0; i < n-1; ++i) {
			int u = in.nextInt(), v = in.nextInt();
			u -= 1; v -= 1;
			tree[u].add(v); tree[v].add(u);
		}
	}

	private static void solve() {
		// Preprocessing
		par = new int[n][n];
		sub = new int[n][n];
		for(int u = 0; u < n; ++u) {
			par[u][u] = -1;
			root = u;
			dfs(u);
		}

		// Calculating DP
		dp = new long[n][n];
		for(int u = 0; u < n; ++u)
			for(int v = 0; v < n; ++v)
				dp[u][v] = -1;

		long ans = 0;
		for(int u = 0; u < n; ++u)
			for(int v = 0; v < n; ++v)
				ans = Math.max(ans, getDP(u, v));

		out.println(ans);
	}

	public static void main(String[] args) {
		in = new Scanner(System.in);
		out = new PrintWriter(System.out);

		input();
		solve();

		out.close();
	}
}

import sys
 
# Read input and build the graph
inp = [int(x) for x in sys.stdin.buffer.read().split()]; ii = 0
n = inp[ii]; ii += 1
coupl = [[] for _ in range(n)]
for _ in range(n - 1):
    u = inp[ii] - 1; ii += 1
    v = inp[ii] - 1; ii += 1
    coupl[u].append(v)
    coupl[v].append(u)
 
# Relabel to speed up n^2 operations later on
bfs = [0]
found = [0]*n
found[0] = 1
for node in bfs:
    for nei in coupl[node]:
        if not found[nei]:
            found[nei] = 1
            bfs.append(nei)
 
new_label = [0]*n
for i in range(n):
    new_label[bfs[i]] = i
 
coupl = [coupl[i] for i in bfs]
for c in coupl:
    c[:] = [new_label[x] for x in c]
 
##### DP using multisource bfs
 
DP = [0] * (n * n)
size = [1] * (n * n)
P = [-1] * (n * n)
 
# Create the bfs ordering
bfs = [root * n + root for root in range(n)]
for ind in bfs:
    P[ind] = ind
 
for ind in bfs:
    node, root = divmod(ind, n)
    for nei in coupl[node]:
        ind2 = nei * n + root
        if P[ind2] == -1:
            bfs.append(ind2)
            P[ind2] = ind
 
del bfs[:n]
 
# Do the DP
for ind in reversed(bfs):
    node, root = divmod(ind, n)
    ind2 = root * n + node
    pind = P[ind]
    parent = pind//n
    
    # Update size of (root, parent)
    size[pind] += size[ind]
 
    # Update DP value of (root, parent)
    DP[pind] = max(DP[pind], max(DP[ind], DP[ind2]) + size[ind] * size[ind2])
print(max(DP[root * n + root] for root in range(n)))

pajenegod uses a variant of BFS dedicated for speed efficiency on Python 3 / PyPy3. More details here.

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

const int MAXK = 5000;
int n; vector<int> cnt(MAXK + 1, 0);
vector<vector<int>> primeExponential(MAXK + 1, vector<int>(MAXK + 1, 0));

void Preprocess() {
	for (int i=2; i<MAXK + 1; i++) {
		for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
		int tmp = i;
		for (int x=2; x<=sqrt(tmp); x++) {
			while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
		}
		if (tmp > 1) primeExponential[i][tmp]++;
	}
}

void Input() {
	cin >> n;
	for (int i=0; i<n; i++) {
		int k; cin >> k; cnt[k]++;
	}
}

void Solve() {
	Preprocess();

	vector<int> bestPD(MAXK + 1, 1);
	long long ans = 0, cur = 0;
	for (int i=1; i<MAXK + 1; i++) {
		if (!cnt[i]) {bestPD[i] = 1; continue;}
		for (int j=1; j<MAXK + 1; j++) {
			ans += 1LL * primeExponential[i][j] * cnt[i];
			cur += 1LL * primeExponential[i][j] * cnt[i];
			if (primeExponential[i][j]) bestPD[i] = j;
		}
	}

	while (*max_element(bestPD.begin(), bestPD.end()) > 1) {
		vector<int> frequency(MAXK + 1, 0);

		for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];

		int bestPrime = max_element(frequency.begin(), frequency.end()) - frequency.begin();
		int bestGroup = frequency[bestPrime];
		if (bestGroup * 2 <= n) break;
		if (bestPrime == 1) break;
		cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);

		for (int i=0; i<MAXK + 1; i++) {
			if (bestPD[i] != bestPrime) bestPD[i] = 1;
			if (bestPD[i] == 1) continue;
			primeExponential[i][bestPD[i]] -= 1;
			while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
		}
	}

	cout << ans << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out, true);
	public static final int MAXK = 5000;
	public static int n;
	public static int[] cnt = new int[MAXK + 1];
	public static int[][] primeExponential = new int[MAXK + 1][MAXK + 1];

	public static long min(long a, long b) {return ((a < b) ? a : b);}

	public static int max_element(int[] arr) {
		int res = -1000000000;
		for (int i=0; i<arr.length; i++) {
			if (arr[i] > res) res = arr[i];
		}
		return res;
	}

	public static int max_id(int[] arr) {
		int res = -1000000000, id = -1;
		for (int i=0; i<arr.length; i++) {
			if (arr[i] > res) {
				res = arr[i];
				id = i;
			}
		}
		return id;
	}

	public static void Preprocess() {
		for (int i=2; i<MAXK + 1; i++) {
			for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
			int tmp = i;
			for (int x=2; x<=Math.sqrt(tmp); x++) {
				while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
			}
			if (tmp > 1) primeExponential[i][tmp]++;
		}
	}

	public static void Input() {
		n = sc.nextInt();
		for (int i=0; i<n; i++) {
			int k = sc.nextInt();
			cnt[k] += 1;
		}
	}

	public static void Solve() {
		Preprocess();

		int[] bestPD = new int[MAXK + 1];
		for (int i=0; i<MAXK + 1; i++) bestPD[i] = 1;
		long ans = 0, cur = 0;
		for (int i=1; i<MAXK + 1; i++) {
			if (cnt[i] == 0) {bestPD[i] = 1; continue;}
			for (int j=1; j<MAXK + 1; j++) {
				ans += (long)primeExponential[i][j] * cnt[i];
				cur += (long)primeExponential[i][j] * cnt[i];
				if (primeExponential[i][j] != 0) bestPD[i] = j;
			}
		}

		while (max_element(bestPD) > 1) {
			int[] frequency = new int[MAXK + 1];

			for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];

			int bestPrime = max_id(frequency);
			int bestGroup = frequency[bestPrime];
			if (bestGroup * 2 <= n) break;
			if (bestPrime == 1) break;
			cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);

			for (int i=0; i<MAXK + 1; i++) {
				if (bestPD[i] != bestPrime) bestPD[i] = 1;
				if (bestPD[i] == 1) continue;
				primeExponential[i][bestPD[i]] -= 1;
				while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
			}
		}

		out.println(ans);
	}

	public static void main(String[] args) {
		Input(); Solve();
	}
}

T = 1
for test_no in range(T):
	MAXK = 5000
	n = int(input())
	cnt = [0] * (MAXK + 1)
	primeExponential = [[0 for j in range(MAXK + 1)] for i in range(MAXK + 1)]

	line, num = (input() + ' '), 0
	for c in line:
		if c != ' ': num = num * 10 + (ord(c) - 48)
		else:
			cnt[num] += 1
			num = 0

	for i in range(2, MAXK + 1):
		for j in range(0, MAXK + 1): primeExponential[i][j] += primeExponential[i-1][j]
		tmp, x = i, 2
		while x * x <= tmp:
			while tmp % x == 0:
				primeExponential[i][x] += 1
				tmp //= x
			x += 1
		if tmp > 1: primeExponential[i][tmp] += 1

	bestPD = [1] * (MAXK + 1)
	ans, cur = 0, 0

	for i in range(1, MAXK + 1):
		if cnt[i] == 0: continue
		for j in range(1, MAXK + 1):
			ans += primeExponential[i][j] * cnt[i]
			cur += primeExponential[i][j] * cnt[i]
			if primeExponential[i][j]: bestPD[i] = j

	frequency = [0] * (MAXK + 1)
	while max(bestPD) > 1:
		for i in range(MAXK + 1): frequency[i] = 0
		for i in range(MAXK + 1): frequency[bestPD[i]] += cnt[i]

		bestGroup = max(frequency)
		bestPrime = frequency.index(bestGroup)
		if bestGroup * 2 <= n: break
		if bestPrime == 1: break
		cur -= bestGroup
		cur += (n - bestGroup); ans = min(ans, cur)

		for i in range(MAXK + 1):
			if bestPD[i] != bestPrime: bestPD[i] = 1
			if bestPD[i] == 1: continue
			primeExponential[i][bestPD[i]] -= 1
			while bestPD[i] > 1 and primeExponential[i][bestPD[i]] == 0: bestPD[i] -= 1

	print(ans)

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int n, L, minID;
string s;

void fill(int id, char c) {
	L -= (s[id] == 'L'); s[id] = c;
	minID = min(minID, id);
}

void query(char cmd, string str) {
	cout << cmd << " " << str << endl; cout.flush();
	if (cmd == '?') {
		int k; cin >> k;
		assert(k != -1);
		vector<int> a(k);
		for (auto &z: a) {
			cin >> z; z--;
			for (int i=0; i<str.size(); i++) {
				assert(s[z+i] == 'L' || s[z+i] == str[i]);
				fill(z+i, str[i]);
			}
		}
	}
	else if (cmd == '!') {
		int correct; cin >> correct;
		assert(correct);
	}
}

void Input() {
	cin >> n; s.clear();
	L = n; minID = n; s.resize(n, 'L');
}

void Solve() {
	query('?', "CH"); query('?', "CO");
	query('?', "HC"); query('?', "HO");
	if (L == n) {
		// the string exists in form O...OX...X, with X=C or X=H
		// or it's completely mono-character
		query('?', "CCC");
		if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
		else {
			query('?', "HHH");
			if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
			else {
				query('?', "OOO");
				if (minID == n) {
					// obviously n=4
					query('?', "OOCC");
					if (minID == n) {fill(0, 'O'); fill(1, 'O'); fill(2, 'H'); fill(3, 'H');}
				}
				if (s[n-1] == 'L') {
					string t = s; t[n-1] = 'C';
					if (t[n-2] == 'L') t[n-2] = 'C';
					query('?', t);
					if (s[n-1] == 'L') {
						fill(n-1, 'H');
						if (s[n-2] == 'L') fill(n-2, 'H');
					}
				}
			}
		}
	}
	else {
		int maxID = minID; while (maxID < n-1 && s[maxID+1] != 'L') maxID++;
		for (int i=minID-1; i>=0; i--) {
			query('?', s.substr(i+1, 1) + s.substr(minID, maxID-minID+1));
			if (minID != i) {
				for (int x=0; x<=i; x++) fill(x, 'O');
				break;
			}
		}
		int nextFilled;
		for (int i=maxID+1; i<n; i++) {
			if (s[i] != 'L') continue;
			nextFilled = i;
			while (nextFilled < n && s[nextFilled] == 'L') nextFilled++;
			query('?', s.substr(0, i) + s[i-1]);
			if (s[i] == 'L') {
				if (s[i-1] != 'O') fill(i, 'O');
				else {
					if (nextFilled == n) {
						query('?', s.substr(0, i) + 'C');
						if (s[i] == 'L') fill(i, 'H');
						for (int x=i+1; x<nextFilled; x++) fill(x, s[i]);
					}
					else for (int x=i; x<nextFilled; x++) fill(x, s[nextFilled]);
					i = nextFilled - 1;
				}
			}
		}
	}
	query('!', s);
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	int T; cin >> T; while (T--) {Input(); Solve();} return 0;
}

import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);

	public static class CPPString {
		// as the Java String is insanely cryptic to modify
		public char[] arr;

		public CPPString() {}
		public CPPString(String str) {this.arr = str.toCharArray();}
		public CPPString(char[] ca) {this.arr = ca;}
		public CPPString(CPPString other) {
			this.arr = new char[other.arr.length];
			for (int i=0; i<other.arr.length; i++) this.arr[i] = other.arr[i];
		}
		public void resize(int length, char defaultChar) {
			this.arr = new char[length];
			for (int i=0; i<length; i++) this.arr[i] = defaultChar;
		}
		public int size() {return this.arr.length;}
		public CPPString substr(int L, int len) {
			// get substring [L, L+len)
			char[] res = new char[len];
			for (int i=0; i<len; i++) res[i] = this.arr[L+i];
			return new CPPString(res);
		}
		public CPPString add(char ch) {
			char[] new_ca = new char[this.arr.length + 1]; new_ca[this.arr.length] = ch;
			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
			return new CPPString(new_ca);
		}
		public CPPString add(CPPString other) {
			char[] new_ca = new char[this.arr.length + other.arr.length];
			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
			for (int i=0; i<other.arr.length; i++) new_ca[this.arr.length + i] = other.arr[i];
			return new CPPString(new_ca);
		}

		@Override
		public String toString() {return new String(arr);}
	}

	public static int n, L, minID;
	public static CPPString s;

	public static void fill(int id, char c) {
		if (s.arr[id] == 'L') L--;
		s.arr[id] = c;
		minID = (minID < id) ? minID : id;
	}

	public static void query(char cmd, CPPString str) {
		System.out.println(cmd + " " + str); System.out.flush();
		System.err.println(cmd + " " + str);
		if (cmd == '?') {
			int k = sc.nextInt();
			assert (k != -1);
			int[] a = new int[k];
			for (int index = 0; index < k; index++) {
				a[index] = sc.nextInt() - 1;
				for (int i=0; i<str.size(); i++) {
					assert (s.arr[a[index]+i] == 'L' || s.arr[a[index]+i] == str.arr[i]);
					fill(a[index]+i, str.arr[i]);
				}
			}
		}
		else if (cmd == '!') {
			int correct = sc.nextInt();
			assert (correct == 1);
		}
	}

	public static void query(char cmd, String str) {
		query(cmd, new CPPString(str));
	}

	public static void Input() {
		n = sc.nextInt(); s = new CPPString();
		L = n; minID = n; s.resize(n, 'L');
	}

	public static void Solve() {
		query('?', "CH"); query('?', "CO");
		query('?', "HC"); query('?', "HO");
		if (L == n) {
			// the string exists in form O...OX...X, with X=C or X=H
			// or it's completely mono-character
			query('?', "CCC");
			if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
			else {
				query('?', "HHH");
				if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
				else {
					query('?', "OOO");
					if (minID == n) {
						// obviously n=4
						query('?', "OOCC");
						if (minID == n) {
							fill(0, 'O'); fill(1, 'O');
							fill(2, 'H'); fill(3, 'H');
						}
					}
					if (s.arr[n-1] == 'L') {
						CPPString t = new CPPString(s); t.arr[n-1] = 'C';
						if (t.arr[n-2] == 'L') t.arr[n-2] = 'C';
						query('?', t);
						if (s.arr[n-1] == 'L') {
							fill(n-1, 'H');
							if (s.arr[n-2] == 'L') fill(n-2, 'H');
						}
					}
				}
			}
		}
		else {
			int maxID = minID; while (maxID < n-1 && s.arr[maxID+1] != 'L') maxID++;
			for (int i=minID-1; i>=0; i--) {
				query('?', s.substr(i+1, 1).add(s.substr(minID, maxID-minID+1)));
				if (minID != i) {
					for (int x=0; x<=i; x++) fill(x, 'O');
					break;
				}
			}
			int nextFilled;
			for (int i=maxID+1; i<n; i++) {
				if (s.arr[i] != 'L') continue;
				nextFilled = i;
				while (nextFilled < n && s.arr[nextFilled] == 'L') nextFilled++;
				query('?', s.substr(0, i).add(s.arr[i-1]));
				if (s.arr[i] == 'L') {
					if (s.arr[i-1] != 'O') fill(i, 'O');
					else {
						if (nextFilled == n) {
							query('?', s.substr(0, i).add('C'));
							if (s.arr[i] == 'L') fill(i, 'H');
							for (int x=i+1; x<nextFilled; x++) fill(x, s.arr[i]);
						}
						else for (int x=i; x<nextFilled; x++) fill(x, s.arr[nextFilled]);
						i = nextFilled - 1;
					}
				}
			}
		}
		query('!', s);
	}

	public static void main(String[] args) {
		int T = sc.nextInt();
		while (T-- > 0) {Input(); Solve();}
	}
}

import sys
n, L, minID = None, None, None
s = []

def fill(id, c):
	global n, L, s, minID
	L -= (s[id] == 'L')
	s = s[0:id] + c + s[id+1:]
	minID = min(minID, id)

def query(cmd, str):
	global n, L, s, minID
	print(cmd, ''.join(str))
	print(cmd, ''.join(str), file=sys.stderr)
	sys.stdout.flush()
	if (cmd == '?'):
		result = list(map(int, input().split()))
		assert(result[0] != -1)
		for z in result[1:]:
			z -= 1
			for i in range(len(str)):
				assert(s[z+i] == 'L' or s[z+i] == str[i])
				fill(z+i, str[i])
	elif (cmd == '!'):
		correct = int(input())
		assert(correct == 1)

T = int(input())
for test_no in range(T):
	n = int(input())
	L, minID = n, n
	s = 'L' * n

	query('?', "CH")
	query('?', "CO")
	query('?', "HC")
	query('?', "HO")
	if (L == n):
		# the string exists in form O...OX...X, with X=C or X=H
		# or it's completely mono-character
		query('?', "CCC")
		if (minID < n): 
			for x in range(minID-1, -1, -1): fill(x, 'O')
		else:
			query('?', "HHH")
			if (minID < n):
				for x in range(minID-1, -1, -1): fill(x, 'O')
			else:
				query('?', "OOO")
				if (minID == n):
					# obviously n=4
					query('?', "OOCC")
					if (minID == n):
						fill(0, 'O')
						fill(1, 'O')
						fill(2, 'H')
						fill(3, 'H')
				
				if (s[n-1] == 'L'):
					t = s[0:n-1] + 'C'
					if (t[n-2] == 'L'): t = t[0:n-2] + 'C' + t[n-1:]
					query('?', t)
					if (s[n-1] == 'L'):
						fill(n-1, 'H')
						if (s[n-2] == 'L'): fill(n-2, 'H')
	else:
		maxID = minID
		while (maxID < n-1 and s[maxID+1] != 'L'): maxID += 1
		for i in range(minID-1, -1, -1):
			query('?', s[i+1:i+2] + s[minID:maxID+1])
			if (minID != i):
				for x in range(i+1): fill(x, 'O')
				break
		
		nextFilled = None
		i = maxID + 1
		while i < n:
			if (s[i] != 'L'):
				i += 1
				continue
			nextFilled = i
			while (nextFilled < n and s[nextFilled] == 'L'): nextFilled += 1
			query('?', s[0:i] + s[i-1])
			if (s[i] == 'L'):
				if (s[i-1] != 'O'): fill(i, 'O')
				else:
					if (nextFilled == n):
						query('?', s[0:i] + 'C')
						if (s[i] == 'L'): fill(i, 'H')
						for x in range(i+1, nextFilled): fill(x, s[i])
					else:
						for x in range(i, nextFilled): fill(x, s[nextFilled])
					i = nextFilled - 1
			i += 1
	query('!', s)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

bool isSubset(int a, int b) {
	return (a & b) == a;
}

bool isIntersect(int a, int b) {
	return (a & b) != 0;
}

void add(int &a, long long b) {
	a = (a + b) % MOD;
}

// Solve for each weakly connected component (WCC)
int cntOrder(vector<int> s, vector<int> t) {
	int p = s.size(), m = t.size();

	vector<int> inMask(m, 0);
	for(int x = 0; x < p; ++x)
		for(int i = 0; i < m; ++i)
			if (t[i] % s[x] == 0)
				inMask[i] |= 1 << x;

	vector<int> cnt(1<<p, 0);
	for(int mask = 0; mask < (1<<p); ++mask)
		for(int i = 0; i < m; ++i)
			if (isSubset(inMask[i], mask))
				++cnt[mask];

	vector<vector<int>> dp(m+1, vector<int>(1<<p, 0));
	for(int i = 0; i < m; ++i)
		dp[1][inMask[i]] += 1;
	for(int k = 1; k < m; ++k) {
		for(int mask = 0; mask < (1<<p); ++mask) {
			for(int i = 0; i < m; ++i)
				if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
					add(dp[k+1][mask | inMask[i]], dp[k][mask]);
			add(dp[k+1][mask], 1LL * dp[k][mask] * (cnt[mask] - k));
		}
	}

	return dp[m][(1<<p)-1];
}

int n;
vector<int> a, degIn, s, t;
vector<vector<int>> graph;
vector<bool> visited;

void dfs(int u) {
	visited[u] = true;
	if (degIn[u] == 0)
		s.push_back(a[u]);
	else
		t.push_back(a[u]);

	for(int v: graph[u])
		if (!visited[v])
			dfs(v);
}

void input() {
	scanf("%d", &n);
	a.resize(n);
	for(int u = 0; u < n; ++u)
		scanf("%d", &a[u]);
}

void solve() {
	// Pre-calculate C(n, k)
	vector<vector<int>> c(n, vector<int>(n, 0));
	for(int i = 0; i < n; ++i) {
		c[i][0] = 1;
		for(int j = 1; j <= i; ++j)
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
	}

	// Building divisibility graph
	degIn.assign(n, 0);
	graph.assign(n, vector<int>());
	for(int u = 0; u < n; ++u) {
		for(int v = 0; v < n; ++v) {
			if (u != v && a[v] % a[u] == 0) {
				graph[u].push_back(v);
				graph[v].push_back(u);
				++degIn[v];
			}
		}
	}

	// Solve for each WCC of divisibility graph and combine result
	int ans = 1;
	int curLen = 0;
	visited.assign(n, false);
	for(int u = 0; u < n; ++u) {
		if (!visited[u]) {
			s.clear();
			t.clear();
			dfs(u);

			if (!t.empty()) {
				int sz = t.size() - 1;
				int cnt = cntOrder(s, t);

				// Number of orders for current WCC
				ans = (1LL * ans * cnt) % MOD;
				// Number of ways to insert <sz> number to array of <curLen> elements
				ans = (1LL * ans * c[curLen + sz][sz]) % MOD;
				curLen += sz;
			}
		}
	}

	printf("%d\n", ans);  
}

int main() {
	input();
	solve();

	return 0;
}

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	private static Scanner in;
	private static PrintWriter out;
	private static final int MOD = (int)1e9 + 7;
	
	private static int n;
	private static int[] a, degIn;
	private static ArrayList<Integer> s, t;
	private static boolean[] visited;
	private static ArrayList<Integer>[] graph;
	
	private static boolean isSubset(int a, int b) {
		return (a & b) == a;
	}

	private static boolean isIntersect(int a, int b) {
		return (a & b) != 0;
	}

	// Solve for each weakly connected component (WCC)
	private static int cntOrder(ArrayList<Integer> s, ArrayList<Integer> t) {
		int p = s.size(), m = t.size();

		int[] inMask = new int[m];
		for(int x = 0; x < p; ++x)
			for(int i = 0; i < m; ++i)
				if (t.get(i) % s.get(x) == 0)
					inMask[i] |= 1 << x;

		int[] cnt = new int[1<<p];
		for(int mask = 0; mask < (1<<p); ++mask)
			for(int i = 0; i < m; ++i)
				if (isSubset(inMask[i], mask))
					++cnt[mask];

		int[][] dp = new int[m+1][1<<p];
		for(int i = 0; i < m; ++i)
			dp[1][inMask[i]] += 1;
		for(int k = 1; k < m; ++k) {
			for(int mask = 0; mask < (1<<p); ++mask) {
				for(int i = 0; i < m; ++i)
					if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
						dp[k+1][mask | inMask[i]] = (int)((dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD);
				dp[k+1][mask] = (int)((dp[k+1][mask] + (long)dp[k][mask] * (cnt[mask] - k)) % MOD);
			}
		}

		return dp[m][(1<<p)-1];
	}

	private static void dfs(int u) {
		visited[u] = true;
		if (degIn[u] == 0)
			s.add(a[u]);
		else
			t.add(a[u]);
	
		for(int v: graph[u])
			if (!visited[v])
				dfs(v);
	}
	
	private static void input() {
		n = in.nextInt();
		a = new int[n];
		for(int u = 0; u < n; ++u)
			a[u] = in.nextInt();
	}
	
	private static void solve() {
		// Pre-calculate C(n, k)
		int[][] c = new int[n][n];
		for(int i = 0; i < n; ++i) {
			c[i][0] = 1;
			for(int j = 1; j <= i; ++j)
				c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
		}
	
		// Building divisibility graph
		degIn = new int[n];
		graph = new ArrayList[n];
		for(int u = 0; u < n; ++u)
			graph[u] = new ArrayList<>();
		for(int u = 0; u < n; ++u) {
			for(int v = 0; v < n; ++v) {
				if (u != v && a[v] % a[u] == 0) {
					graph[u].add(v);
					graph[v].add(u);
					++degIn[v];
				}
			}
		}
	
		// Solve for each WCC of divisibility graph and combine result
		int ans = 1;
		int curLen = 0;
		visited = new boolean[n];
		for(int u = 0; u < n; ++u) {
			if (!visited[u]) {
				s = new ArrayList<>();
				t = new ArrayList<>();
				dfs(u);
	
				if (!t.isEmpty()) {
					int sz = t.size() - 1;
					int cnt = cntOrder(s, t);
	
					// Number of orders for current WCC
					ans = (int)(((long)ans * cnt) % MOD);
					// Number of ways to insert <sz> number to array of <curLen> elements
					ans = (int)(((long)ans * c[curLen + sz][sz]) % MOD);
					curLen += sz;
				}
			}
		}
	
		out.println(ans);
	}
	
	public static void main(String[] args) {
		in = new Scanner(System.in);
		out = new PrintWriter(System.out);

		input();
		solve();

		out.close();
	}
}

MOD = 1000000007


def isSubset(a, b):
	return (a & b) == a


def isIntersect(a, b):
	return (a & b) != 0


# Solve for each weakly connected component (WCC)
def cntOrder(s, t):
	p = len(s)
	m = len(t)

	inMask = [0 for i in range(m)]

	for x in range(p):
		for i in range(m):
			if t[i] % s[x] == 0:
				inMask[i] |= 1 << x

	cnt = [0 for mask in range(1<<p)]
	for mask in range(1<<p):
		for i in range(m):
			if isSubset(inMask[i], mask):
				cnt[mask] += 1

	dp = [[0 for mask in range(1<<p)] for k in range(m+1)]
	for i in range(m):
		dp[1][inMask[i]] += 1
	for k in range(m):
		for mask in range(1<<p):
			for i in range(m):
				if not isSubset(inMask[i], mask) and isIntersect(inMask[i], mask):
					dp[k+1][mask | inMask[i]] = (dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD
			dp[k+1][mask] = (dp[k+1][mask] + dp[k][mask] * (cnt[mask] - k)) % MOD

	return dp[m][(1<<p)-1]


def dfs(u):
	global a, graph, degIn, visited, s, t

	visited[u] = True
	if degIn[u] == 0:
		s.append(a[u])
	else:
		t.append(a[u])

	for v in graph[u]:
		if not visited[v]:
			dfs(v)


def main():
	global a, graph, degIn, visited, s, t

	# Reading input
	n = int(input())
	a = list(map(int, input().split()))

	# Pre-calculate C(n, k)
	c = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		c[i][0] = 1
		for j in range(1, i+1):
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD	

	# Building divisibility graph
	degIn = [0 for u in range(n)]
	graph = [[] for u in range(n)]
	for u in range(n):
		for v in range(n):
			if u != v and a[v] % a[u] == 0:
				graph[u].append(v)
				graph[v].append(u)
				degIn[v] += 1

	# Solve for each WCC of divisibility graph and combine result
	ans = 1
	curLen = 0
	visited = [False for u in range(n)]
	for u in range(n):
		if not visited[u]:
			s = []
			t = []
			dfs(u)

			if len(t) > 0:
				sz = len(t) - 1
				cnt = cntOrder(s, t)

				# Number of orders for current WCC
				ans = (ans * cnt) % MOD
				# Number of ways to insert <sz> number to array of <curLen> elements
				ans = (ans * c[curLen + sz][sz]) % MOD
				curLen += sz		

	print(ans)

if __name__ == "__main__":
	main()

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char* argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);

    vector<int> a(n), b(m);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; ++i)
        scanf("%d", &b[i]);

    int c0 = 0, c1 = 0;
    for(int i = 0; i < n; ++i)
        if (a[i]%2 == 0)
            ++c0;
        else
            ++c1;

    int k0 = 0, k1 = 0;
    for(int i = 0; i < m; ++i)
        if (b[i]%2 == 0)
            ++k0;
        else
            ++k1;

    int ans = min(c1, k0) + min(c0, k1);

    printf("%d", ans);

    return 0;
}

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int x;

bool isCompletion(int z) {
	int bitval = 0;
	z += 1; while (z % 2 == 0) {z /= 2; bitval++;}
	return (z == 1);
}

int MSB(int z) {
	for (int i=20; i>=0; i--) {
		if ((z >> i) & 1) return i;
	}
	return -1;
}

void Input() {
	cin >> x;
}

void Solve() {
	int i = 0; vector<int> xorCmd;
	while (!isCompletion(x)) {
		i = i + 1;
		if (i % 2 == 0) {x++; continue;}
		int r = MSB(x);
		if ((1 << r) != x) r++;
		x = (x ^ ((1 << r) - 1)); xorCmd.push_back(r);
	}
	cout << i << endl;
	for (auto z: xorCmd) cout << z << " "; cout << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); Input(); Solve();
	return 0;
}

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int x; vector<vector<int>> vis(2, vector<int>(1048576, INT_MAX));
vector<vector<pair<int, int>>> Last(2, vector<pair<int, int>>(1048576, {-1LL, -1LL}));

int isCompletion(int z) {
	int bitval = 0;
	z += 1; while (z % 2 == 0) {z /= 2; bitval++;}
	if (z != 1) return -1;
	return bitval;
}

void Input() {
	cin >> x;
}

void Solve() {
	queue<pair<int, int>> Q;
	vis[0][x] = 0; Q.push({0, x});
	int p1 = -1, p2 = -1;
	while (!Q.empty()) {
		pair<int, int> Token = Q.front();
		int p = Token.first, z = Token.second; Q.pop();
		if (isCompletion(z) != -1) {p1 = p; p2 = z; break;}
		if (p == 1) {
			if (vis[0][z+1] == INT_MAX) {
				vis[0][z+1] = vis[1][z] + 1;
				Last[0][z+1] = {1, z}; Q.push({0, z+1});
			}
		}
		else {
			for (int i=0; i<20; i++) {
				int t = (z ^ ((1 << i) - 1));
				if (vis[1][t] != INT_MAX) continue;
				vis[1][t] = vis[0][z] + 1;
				Last[1][t] = {0, z}; Q.push({1, t});
			}
		}
	}

	cout << vis[p1][p2] << endl;

	vector<int> xorCmd;
	while (Last[p1][p2] != make_pair(-1, -1)) {
		pair<int, int> Token = Last[p1][p2];
		int z = Token.first, t = Token.second;
		if (p1 == 1) xorCmd.push_back(isCompletion(p2 ^ t));
		p1 = z; p2 = t;
	}

	reverse(xorCmd.begin(), xorCmd.end());
	for (auto z: xorCmd) cout << z << " ";
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); Input(); Solve();
	return 0;
}

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
	long long a = rng();
    return a;
}
long long a, b;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    long long dif = abs(a - b);
    vector<int>v;
    for(int i = 1; i * i <= dif; ++i)
    {
        if(dif % i == 0)
        {
            v.push_back(i);
            if(i * i != dif)
                v.push_back(dif / i);
        }
    }
    long long ans = (1LL<<62);
    int vl = 0;
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i)
    {
        int nr = v[i];
        if(a % nr != b % nr)
            continue;
        if(a % nr == 0)
        {
            long long pans = (a * b)/__gcd(a, b);
            if(pans < ans)
                ans = pans, vl = 0;
        }
        else
        {
            long long pans = ((nr - a % nr + a) * (nr - b % nr + b))/__gcd((nr - a % nr + a), (nr - b % nr + b));
            if(pans < ans)
                ans = pans, vl = nr - a % nr;
        }
    }
    cout << vl;
    return 0;
}

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int a, b;

void Input() {
	cin >> a >> b;
}

void Solve() {
	if (a == b) {cout << "0\n"; return;}
	
	vector<int> Divisors;
	for (int i=1; i<=sqrt(max(a,b) - min(a,b)); i++) {
		if ((max(a,b) - min(a,b)) % i != 0) continue;
		int j = (max(a,b) - min(a,b)) / i;
		Divisors.push_back(i);
		if (i != j) Divisors.push_back(j);
	}
	
	pair<long long, int> Token = make_pair(LLONG_MAX, INT_MAX);
	for (auto d: Divisors) {
		int k = (d - a % d) % d;
		pair<long long, int> NewToken = make_pair(1LL * (0LL + a + k) / __gcd(0LL+a+k, 0LL+b+k) * (0LL + b + k), k);
		Token = min(Token, NewToken);
	}
	
	cout << Token.second << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); Input(); Solve();
	return 0;
}

// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

const int mod = 1000 * 1000 * 1000 + 7;
int add(int a, int b) {
    return (a + b >= mod ? a + b - mod : a + b);
}

const int max_n = 1001;
pair<int, bool> dp[2 * max_n][2 * max_n];

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n = input<int>();
    n *= 2;

    assert(n / 2 < max_n);
        
    
    dp[0][0] = make_pair(0, true);
    
    for (int len = 1; len <= n; ++len) {
        for (int bal = 0; bal <= n; ++bal) {
            // (len, bal) -> (len - 1, bal + 1)
            // (len, bal) -> (len - 1, bal - 1)

            int sum = 0;
            bool has = false;

            if (bal != 0) {
                sum = add(sum, dp[len - 1][bal - 1].first);
                has = has or dp[len - 1][bal - 1].second;
            }

            if (bal + 1 <= len - 1) {
                sum = add(sum, dp[len - 1][bal + 1].first);
                has = has or dp[len - 1][bal + 1].second;
            }

            if (has)
                dp[len][bal] = make_pair(add(sum, 1), false);
            else
                dp[len][bal] = make_pair(sum, true);
        }
    }
    
    cout << dp[n][0].first << "\n";
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

class Indexer {
private:
    map<int, int> id;
    vector<int> num;

public:
    int getId(int x) {
        if (!id.count(x)) {
            id[x] = num.size();
            num.push_back(x);
        }
        return id[x];
    }

    int getNum(int id) {
        return num[id];
    }

    int size() {
        return id.size();
    }
};

struct Edge {
    int u, v;
    bool avail;
};

class Graph {
private:
    int n;
    vector<Edge> e;
    vector<vector<int> > adj;

    vector<int> pos;
    list<int> path;

    void dfs(list<int>::iterator it, int u) {
        for(; pos[u] < adj[u].size(); ++pos[u]) {
            int id = adj[u][pos[u]];
            if (e[id].avail) {
                e[id].avail = false;
                int v = e[id].u + e[id].v - u;
                dfs(path.insert(it, u), v);
            }
        }
    }

public:
    Graph(int n): n(n) {
        adj.assign(n, vector<int>());
    }

    void addEdge(int u, int v) {
        adj[u].push_back(e.size());
        adj[v].push_back(e.size());
        e.push_back({u, v, false});
    }

    vector<int> eulerPath() {
        for(Edge &p: e)
            p.avail = true;
        path.clear();
        pos.assign(n, 0);

        vector<int> odd;
        for(int u = 0; u < n; ++u)
            if (adj[u].size() % 2 == 1)
                odd.push_back(u);
        if (odd.empty()) {
            odd.push_back(0);
            odd.push_back(0);
        }

        if (odd.size() > 2)
            return vector<int>();
        dfs(path.begin(), odd[0]);
        path.insert(path.begin(), odd[1]);

        return vector<int>(path.begin(), path.end());
    }
};

int main() {
    int n;
    scanf("%d", &n);

    vector<int> bprime(n-1);
    for(int i = 0; i < n-1; ++i)
        scanf("%d", &bprime[i]);

    vector<int> cprime(n-1);
    for(int i = 0; i < n-1; ++i)
        scanf("%d", &cprime[i]);

    Indexer ind;
    for(int i = 0; i < n-1; ++i) {
        if (bprime[i] > cprime[i]) {
            puts("-1");
            return 0;
        }

        bprime[i] = ind.getId(bprime[i]);
        cprime[i] = ind.getId(cprime[i]);
    }

    int k = ind.size();
    Graph g(k);
    for(int i = 0; i < n-1; ++i)
        g.addEdge(bprime[i], cprime[i]);

    vector<int> a = g.eulerPath();

    if (a.size() < n)
        puts("-1");
    else {
        for(int i = 0; i < n; ++i)
            printf("%d ", ind.getNum(a[i]));
        puts("");
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

void add(int &a, long long b) {
    a = (a + b) % MOD;
}

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);

    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(1<<m, 0)));
    dp[0][0][0] = 1;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= k; ++j) {
            for(int mask = 0; mask < (1<<m); ++mask) {
                int newMask = (mask << 1) % (1<<m);

                // Not visit planet i+1
                add(dp[i+1][j][newMask], dp[i][j][mask]);

                // Visit planet i+1
                if (j < k) {
                    int insertWays = __builtin_popcount(mask) + 1;
                    add(dp[i+1][j+1][newMask|1], 1LL*insertWays*dp[i][j][mask]);
                }
            }
        }
    }

    int ans = 0;
    for(int mask = 0; mask < (1<<m); ++mask)
        add(ans, dp[n][k][mask]);

    printf("%d", ans);
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

void add(int &a, long long b) {
    a = (a + b) % MOD;
}

struct Matrix {
    vector<vector<int>> a;
    int n, m;

    Matrix(int n, int m): n(n), m(m) {
        a.assign(n, vector<int>(m, 0));
    }

    friend Matrix operator * (Matrix a, Matrix b) {
        Matrix c(a.n, b.m);
        for(int i = 0; i < a.n; ++i)
            for(int j = 0; j < b.m; ++j)
                for(int k = 0; k < a.m; ++k)
                    add(c.a[i][j], 1LL * a.a[i][k] * b.a[k][j]);
        return c;
    }
};

Matrix identity(int n) {
    Matrix res(n, n);
    for(int i = 0; i < n; ++i)
        res.a[i][i] = 1;
    return res;
}

void power(Matrix &a, int n, Matrix &b) {
    while (n > 0) {
        if (n&1) b = a * b;
        a = a * a;
        n >>= 1;
    }
}

int n, k, m;

int toId(int j, int mask) {
    return j * (1<<m) + mask;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);

    Matrix dp((k+1) * (1<<m), 1);
    dp.a[0][0] = 1;

    Matrix f((k+1) * (1<<m), (k+1) * (1<<m));

    for(int j = 0; j <= k; ++j) {
        for(int mask = 0; mask < (1<<m); ++mask) {
            int newMask = (mask << 1) % (1<<m);
            int cur = toId(j, mask);

            f.a[toId(j, newMask)][cur] = 1;
            if (j < k)
                f.a[toId(j+1, newMask|1)][cur] = __builtin_popcount(mask) + 1;
        }
    }

    power(f, n, dp);

    int ans = 0;
    for(int mask = 0; mask < (1<<m); ++mask)
        add(ans, dp.a[toId(k, mask)][0]);

    printf("%d", ans);
}

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

void add(long long &a, long long b) {
    a = (a + b) % mod;
}

long long f[2][1005][1024];
int pc[1024];

long long solve(int n, int k, int m) {
    memset(f, 0, sizeof f);
    f[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        int x = i & 1, y = 1 - x;
        memset(f[y], 0, sizeof f[y]);
        for (int j = 0; j <= k; ++j) {
            for (int mask = 0; mask < (1 << m); ++mask) {
                int new_mask = mask >> 1;
                add(f[y][j][new_mask], f[x][j][mask]);
                add(f[y][j+1][new_mask + (1<<m-1)], f[x][j][mask] * (pc[mask] + 1));
            }
        }
    }
    long long ret = 0;
    for (int mask = 0; mask < (1 << m); ++mask)
        add(ret, f[n&1][k][mask]);
    return ret;
}

typedef vector <vector <long long>> mat;
mat operator *(const mat &a, const mat &b) {
    mat c(a.size(), vector <long long>(b[0].size(), 0));
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0; j < b.size(); ++j)
            for (int k = 0; k < b[0].size(); ++k)
                add(c[i][k], a[i][j] * b[j][k]);
    return c;
}
mat operator +(const mat &a, const mat &b) {
    mat c = a;
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0; j < a[0].size(); ++j)
            add(c[i][j], b[i][j]);
    return c;
}

mat A(int m) {
    mat a(1 << m, vector <long long>(1 << m, 0));
    for (int i = 0; i < (1 << m - 1); ++i)
        a[i][i*2] = a[i][i*2 + 1] = 1;
    return a;
}
mat B(int m) {
    mat b(1 << m, vector <long long>(1 << m, 0));
    for (int i = 0; i < (1 << m - 1); ++i) {
        b[i + (1<<m-1)][i*2] = pc[i] + 1;
        b[i + (1<<m-1)][i*2 + 1] = pc[i] + 2;
    }
    return b;
}
mat U(int m) {
    mat u(1 << m, vector <long long>(1 << m, 0));
    for (int i = 0; i < (1 << m); ++i)
        u[i][i] = 1;
    return u;
}
mat O(int m) {
    return mat(1 << m, vector <long long>(1 << m, 0));
}

void convo(vector <mat> &a, vector <mat> b, int m, int k) {
    int sz = min(k + 1, (int)(a.size() + b.size() + 1));
    a.resize(sz, O(m));
    for (int i = sz - 1; i >= 0; --i) {
        a[i] = a[i] * b[0];
        for (int j = 1; j <= i && j < b.size(); ++j)
            a[i] = a[i] + a[i-j] * b[j];
    }
}
long long solve3(int n, int k, int m) {
    vector <mat> ans, mul;
    --n;
    ans = mul = {A(m), B(m)};
    while (n) {
        if (n & 1) convo(ans, mul, m, k);
        convo(mul, mul, m, k);
        n >>= 1;
    }
    long long ret = 0;
    for (int i = 0; i < (1 << m); ++i)
        add(ret, ans[k][i][0]);
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int n, k, m;
    for (int i = 1; i < 1024; ++i) pc[i] = pc[i - (i&-i)] + 1;
    while (cin >> n >> k >> m)
        cout << solve3(n, k, m) << endl;
    return 0;
}

xuanquang1999 actually proposed ~10 problems yet our dear cdkrot denied half of them.
I also proposed 4 and got denied 3 first one as well :-P

Problem B is the last invented problem. I was walking around the computer labs, thinking of some photoshopped Catzilla cat memes, which led to me thinking of enlarging cute kittens, then coming up with this problem.

Ironicly though, my model greedy solution would actually shrink the cats instead.

Anyway, I forgot this picture about longcat:

neko_nyaaaaaaaaaaaaaaaaa and I after I finished writing statements of B:

MofK went haywire after seeing first AC of problem F2 by dreamoon_love_AA. Poor MofK, he wrote a superbly veryheckingfast solution for F2 and was still outmatched. :<
P/s: Funny, in Codeforces both solutions have the same max execution time :D

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int x, y, z, a, b, c;

void Input() {
	cin >> x >> y >> z;
	cin >> a >> b >> c;
}

void Solve() {
	if (x > a) {cout << "NO\n"; return;}
	if (x + y > a + b) {cout << "NO\n"; return;}
	if (x + y + z > a + b + c) {cout << "NO\n"; return;}
	cout << "YES\n";
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); Input(); Solve();
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<pii> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a.begin(), a.end(), greater<pii>());

    vector<int> ind(m*k);
    ll sumBeauty = 0;
    for(int i = 0; i < m*k; ++i) {
        sumBeauty += a[i].first;
        ind[i] = a[i].second;
    }

    sort(ind.begin(), ind.end());

    vector<int> division(k-1);
    for(int i = 0; i < k-1; ++i)
        division[i] = ind[(i+1)*m - 1];

    cout << sumBeauty << endl;
    for(int p: division)
        cout << p + 1 << " ";

    return 0;
}

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

long long n, b;

void Input() {
	cin >> n >> b;
}

void Solve() {
	long long ans = 1000000000000000000LL;
	for (long long i=2; i<=b; i++) {
		if (1LL * i * i > b) i = b;
		int cnt = 0;
		while (b % i == 0) {b /= i; cnt++;}
		if (cnt == 0) continue;
		long long tmp = 0, mul = 1;
		while (mul <= n / i) {mul *= i; tmp += n / mul;}
		ans = min(ans, tmp / cnt);
	}
	cout << ans << endl;
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

int dp[5000][5000][2];

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n = input<int>();

    vector<int> a(n);
    input_seq(ALL(a));

    for (int i = 0; i != n; ++i)
        for (int j = 0; j != n; ++j)
            dp[i][j][0] = dp[i][j][1] = (i == j ? 0 : TYPEMAX(int) / 2);
    

    for (int r = 0; r != n; ++r)
        for (int l = r; l >= 0; --l)
            for (int it = 0; it != 2; ++it) {
                int c = (it == 0 ? a[l] : a[r]);
                
                if (l)
                    dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][it] + int(c != a[l - 1]));

                if (r + 1 != n)
                    dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][it] + int(c != a[r + 1]));
            }

    cout << min(dp[0][n - 1][0], dp[0][n - 1][1]) << "\n";
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxN = 5008;

int n;
int dp[maxN][maxN];
vector<int> a(1), b;
vector<int> ans;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (x != a.back()) a.push_back(x);
	}
	n = a.size() - 1;

	b = a;
	reverse(b.begin() + 1, b.end());
}

void solve() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i] == b[j]) {dp[i][j] = dp[i-1][j-1] + 1;}
			else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}
		}
	}
}

void output() {
	cout << n - (dp[n][n] + 1)/2 << '\n';
}

int main() {
	
	input();
	solve();
	output();
	
	return 0;
}

For simplicity, assumed that the sequence a is [0, 1, 2, ..., n - 1]. Suppose that we randomly (and uniformly) select a subsequence S containing k elements from sequence a (when k is the number of ? query asked). Denote S = [s₁, s₂, ..., s_k].

Let D the GCD of all difference between consecutive elements in S. In other word, . Our solution will success if D = 1 and will fail otherwise. Let P the probability that our solution will pass (D = 1). Then the failing probability is 1 - P.

We will apply Möbius inversion to calculate P: Let f(x) the probability that D is divisible by x. Then, (where μ(x) is the Möbius function).

Now we need to calculate f(x). It can be shown that D is divisible by x if and only if for all 2 ≤ i ≤ k. In other word, there is some r from 0 to x - 1 such that for all 1 ≤ i ≤ k.

Let g(r) the number of ways to select a subsequence S such that for all 1 ≤ i ≤ k. Then, according to definition:

The denominator is simply . To calculate g(r), notice that for each i, the value of s_i can be x·j + r for some integer j. In other word, S must be a subsequence of the sequence a_r = [r, x + r, 2x + r, ...]. Let .

• If , a_r has q + 1 elements. Therefore,
• If , a_r has q elements. Therefore, .

In summary:

The complexity of this calculating method is O(n). My implementation of the above method can be found here.

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());

int n, Max = -1000000000, d = 0;
int queryRemaining = 60; vector<int> id;

void findMax() {
	int top = -1000000000, bot = +1000000000;
	while (top <= bot) {
		int hasHigher;
		int mid = (top + bot) / 2;
		cout << "> " << mid << endl;
		fflush(stdout); cin >> hasHigher;
		queryRemaining--;
		if (hasHigher) top = mid + 1;
		else {bot = mid - 1; Max = mid;}
	}
}

void findD() {
	vector<int> List; int RandomRange = n;
	while (queryRemaining > 0 && RandomRange > 0) {
		int demandedIndex = rng32() % RandomRange;
		cout << "? " << id[demandedIndex] << endl; fflush(stdout);
		int z; cin >> z; List.push_back(z);
		RandomRange--; queryRemaining--;
		swap(id[demandedIndex], id[RandomRange]);
	}
	sort(List.begin(), List.end());
	if (List.back() != Max) List.push_back(Max);
	for (int i=1; i<List.size(); i++) {
		d = __gcd(d, List[i] - List[i-1]);
	}
}

void Input() {
	cin >> n; id.resize(n);
	for (int i=0; i<n; i++) id[i] = i+1;
}

void Solve() {
	findMax(); findD();
	int Min = Max - d * (n - 1);
	cout << "! " << Min << " " << d;
	cout << endl; fflush(stdout);
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0);
	Input(); Solve(); return 0;
}

// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

const int mod = 1000 * 1000 * 1000 + 7;

int add(int a, int b) {
    return (a + b >= mod ? a + b - mod : a + b);
}

int sub(int a, int b) {
    return (a >= b ? a - b : mod + a - b);
}

int mult(int a, int b) {
    return (int64_t(a) * b) % mod;
}

int fpow(int a, int n, int r = 1) {
    while (n) {
        if (n % 2)
            r = mult(r, a);

        n /= 2;
        a = mult(a, a);
    }

    return r;
}


const int max_n = 4.1e5;
int tree[4 * max_n];
int modif[4 * max_n];
int64_t pmask[4 * max_n], pushmask[4 * max_n];

vector<int> primes, revprimes;

void build(int v, int l, int r, vector<int>& a) {
    modif[v] = 1;
    
    if (l == r - 1) {
        tree[v] = a[l];

        for (int i = 0; i != SZ(primes); ++i)
            if (a[l] % primes[i] == 0)
                pmask[v] |= (int64_t(1) << int64_t(i));
    } else {
        int m = l + (r - l) / 2;
        build(2 * v + 1, l, m, a);
        build(2 * v + 2, m, r, a);

        tree[v] = mult(tree[2 * v + 1], tree[2 * v + 2]);
        pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2];
    }
}

void push(int v, int vl, int vr) {
    if (modif[v] != 1)
        tree[v] = fpow(modif[v], vr - vl, tree[v]);

    pmask[v] |= pushmask[v];
    
    if (vl != vr - 1) {
        modif[2 * v + 1] = mult(modif[2 * v + 1], modif[v]);
        modif[2 * v + 2] = mult(modif[2 * v + 2], modif[v]);

        pushmask[2 * v + 1] |= pushmask[v];
        pushmask[2 * v + 2] |= pushmask[v];
    }

    modif[v] = 1;
    pushmask[v] = 0;
}

pair<int, int64_t> get(int v, int vl, int vr, int l, int r) {
    if (vr <= l or r <= vl)
        return make_pair<int, int64_t>(1, 0);
    
    push(v, vl, vr);

    if (l <= vl and vr <= r)
        return make_pair(tree[v], pmask[v]);

    int vm = vl + (vr - vl) / 2;
    
    auto r1 = get(2 * v + 1, vl, vm, l, r);
    auto r2 = get(2 * v + 2, vm, vr, l, r);

    return make_pair(mult(r1.first, r2.first), r1.second | r2.second);
}

void multiply(int v, int vl, int vr, int l, int r, int x, int64_t mask) {
    if (vr <= l or r <= vl)
        return;

    push(v, vl, vr);
    
    if (l <= vl and vr <= r) {
        pushmask[v] = mask;
        modif[v] = x;
        return;
    }

    int vm = vl + (vr - vl) / 2;
    
    multiply(2 * v + 1, vl, vm, l, r, x, mask);
    multiply(2 * v + 2, vm, vr, l, r, x, mask);

    pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2] | pushmask[2 * v + 1] | pushmask[2 * v + 2];
    tree[v] = fpow(x, min(vr, r) - max(l, vl), tree[v]);
}


int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    for (int i = 2; i <= 300; ++i) {
        bool ok = true;
        for (int j = 2; j * j <= i and ok; ++j)
            if (i % j == 0)
                ok = false;

        if (ok) {
            primes.push_back(i);
            revprimes.push_back(fpow(i, mod - 2));
        }
    }

    int n = input<int>();
    int q = input<int>();

    vector<int> a(n);
    input_seq(ALL(a));

    build(0, 0, n, a);

    for (int it = 0; it != q; ++it) {
        if (input<string>() == "TOTIENT") {
            int l = input<int>() - 1;
            int r = input<int>() - 1;
            
            pair<int, uint64_t> prod = get(0, 0, n, l, r + 1);
            for (int i = 0; i != SZ(primes); ++i)
                if (prod.second & (int64_t(1) << int64_t(i)))
                    prod.first = mult(mult(prod.first, primes[i] - 1), revprimes[i]);

            cout << prod.first << "\n";
        } else {
            int l = input<int>() - 1;
            int r = input<int>() - 1;
            int x = input<int>();

            int64_t msk = 0;
            for (int i = 0; i != SZ(primes); ++i)
                if (x % primes[i] == 0)
                    msk |= (int64_t(1) << int64_t(i));

            multiply(0, 0, n, l, r + 1, x, msk);
        }
    }
    
    return 0;
}

#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

const int Mod = 1000000007;

int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137
,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293}; // (size = 62)

int modPow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b % 2 == 0) {a = (1LL * a * a) % Mod; b /= 2;}
        else {res = (1LL * res * a) % Mod; b -= 1;}
    }
    return res;
}

struct ProTree {
	vector<int> Tree, Lazy;
	ProTree() {}
	ProTree(int n) {Tree.resize(n*4, 1); Lazy.resize(n*4, 1);}
	
	void Propagate(int node, int st, int en) {
		if (Lazy[node] == 1) return;
		Tree[node] = (1LL * Tree[node] * modPow(Lazy[node], (en - st + 1))) % Mod;
		if (st != en) {
			Lazy[node*2+1] = (1LL * Lazy[node*2+1] * Lazy[node]) % Mod;
			Lazy[node*2+2] = (1LL * Lazy[node*2+2] * Lazy[node]) % Mod;
		}
		Lazy[node] = 1;
	}
	
	void Multiply(int node, int st, int en, int L, int R, int val) {
		Propagate(node, st, en);
		if (st > en || en < L || R < st) return;
		if (L <= st && en <= R) {
			Lazy[node] = (1LL * Lazy[node] * val) % Mod;
			Propagate(node, st, en); return;
		}
		Multiply(node*2+1, st, (st+en)/2+0, L, R, val);
		Multiply(node*2+2, (st+en)/2+1, en, L, R, val);
		Tree[node] = (1LL * Tree[node*2+1] * Tree[node*2+2]) % Mod;
	}
	
	int Product(int node, int st, int en, int L, int R) {
		Propagate(node, st, en);
		if (st > en || en < L || R < st) return 1;
		if (L <= st && en <= R) return Tree[node];
		int p1 = Product(node*2+1, st, (st+en)/2+0, L, R);
		int p2 = Product(node*2+2, (st+en)/2+1, en, L, R);
		return ((1LL * p1 * p2) % Mod);
	}
};

struct OrTree {
	vector<long long> Tree, Lazy;
	OrTree() {}
	OrTree(int n) {Tree.resize(n*4); Lazy.resize(n*4);}
	
	void Propagate(int node, int st, int en) {
		if (Lazy[node] == 0) return;
		Tree[node] |= Lazy[node];
		if (st != en) {
			Lazy[node*2+1] |= Lazy[node];
			Lazy[node*2+2] |= Lazy[node];
		}
		Lazy[node] = 0;
	}
	
	void Update(int node, int st, int en, int L, int R, long long val) {
		Propagate(node, st, en);
		if (st > en || en < L || R < st) return;
		if (L <= st && en <= R) {
			Lazy[node] |= val;
			Propagate(node, st, en); return;
		}
		Update(node*2+1, st, (st+en)/2+0, L, R, val);
		Update(node*2+2, (st+en)/2+1, en, L, R, val);
		Tree[node] = (Tree[node*2+1] | Tree[node*2+2]);
	}
	
	long long Or(int node, int st, int en, int L, int R) {
		Propagate(node, st, en);
		if (st > en || en < L || R < st) return 0;
		if (L <= st && en <= R) return Tree[node];
		long long p1 = Or(node*2+1, st, (st+en)/2+0, L, R);
		long long p2 = Or(node*2+2, (st+en)/2+1, en, L, R);
		return (p1 | p2);
	}
};

int N, Q, l, r, x; string cmd;
vector<int> invPrime(62);
vector<int> A; ProTree PrTree; OrTree OSTree;
vector<long long> Mask(301, 0);

void PreprocessMask() {
	for (int z=1; z<=300; z++) {
		for (int i=0; i<62; i++) {
			if (z % prime[i] != 0) continue;
			Mask[z] |= (1LL << i);
		}
	}
}

void Input() {
    for (int i=0; i<62; i++) invPrime[i] = modPow(prime[i], Mod-2); PreprocessMask();
	cin >> N >> Q; A.resize(N); PrTree = ProTree(N); OSTree = OrTree(N);
	for (int i=0; i<N; i++) {
		cin >> A[i];
		PrTree.Multiply(0, 0, N-1, i, i, A[i]);
		OSTree.Update(0, 0, N-1, i, i, Mask[A[i]]);
	}
}

void Solve() {
	while (Q--) {
		cin >> cmd >> l >> r; l--; r--;
		if (cmd == "MULTIPLY") {
			cin >> x;
			PrTree.Multiply(0, 0, N-1, l, r, x);
			OSTree.Update(0, 0, N-1, l, r, Mask[x]);
		}
		else if (cmd == "TOTIENT") {
			int res = PrTree.Product(0, 0, N-1, l, r);
			long long SegMask = OSTree.Or(0, 0, N-1, l, r);
			for (int i=0; i<62; i++) {
			    if ((SegMask & (1LL << i)) == 0) continue;
			    res = (1LL * res * (prime[i] - 1)) % Mod;
			    res = (1LL * res * invPrime[i]) % Mod;
			}
			cout << res << endl;
		}
	}
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	Input(); Solve(); return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <unordered_set>
#include <string>
#include <map>
#include <unordered_map>
#include <random>
#include <set>
#include <cassert>
#include <functional>
#include <iomanip>
#include <queue>
#include <numeric>
#include <bitset>
#include <iterator>

using namespace std;

const int N = 100001;

mt19937 gen(time(NULL));
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define mp make_pair
#define endl '\n'
#define vi vector<int>

typedef long long ll;

template<typename T = int>
inline T read() {
	T val = 0, sign = 1; char ch;
	for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
		if (ch == '-') sign = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar())
		val = val * 10 + ch - '0';
	return sign * val;
}

const int mod = 1e9 + 7;
const int phi = 1e9 + 6;

const int M = 301, B = 500;
int P = 0;

inline int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

int mpow(int u, int p) {
	if (!p) return 1;
	return mul(mpow(mul(u, u), p / 2), (p & 1) ? u : 1);
}

vector<int> primes;
vector<int> pi;

int pw[M];
int lg[N];

bool pr(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			return false;
	return true;
}

void precalc() {
	forn(i, M)
		if (pr(i)) {
			primes.push_back(i);
			P++;
		}
	pi.resize(P);
	forn(i, M) {
		int x = 1;
		forn(j, B) {
			x = mul(x, i);
		}
		pw[i] = x;
	}

	forn(i, P)
		pi[i] = mpow(primes[i], phi - 1);
}

struct product_tree {
	vector<int> arr, block_product, block_update, single_update;
	int n;

	product_tree(vector<int>& a) : n(a.size()) {
		arr = a;
		while (n % B) {
			n++, arr.push_back(1);
		}
		block_product.resize(n / B, 1);
		block_update.resize(n / B, -1);
		single_update.resize(n / B, -1);

		for (int i = 0; i < n; i += B) {
			int x = 1;
			int pos = i / B;
			forn(j, B)
				x = mul(x, arr[i + j]);
			block_product[pos] = x;
		}
	}

	inline void add(int& u, int x, int mode) {
		if (mode) {
			if (u == -1)
				u = x;
			else
				u = mul(u, x);
		}
		else {
			if (u == -1)
				u = pw[x];
			else
				u = mul(u, pw[x]);
		}
	}

	void update(int pos, int x) {
		add(block_update[pos], x, 0);
		add(single_update[pos], x, 1);
	}

	void reconstruct(int pos) {
		int e = single_update[pos];
		if (e == -1) return;
		int x = 1;

		int l = pos * B, r = l + B;
		for (int i = l; i < r; i++) {
			arr[i] = mul(arr[i], e);
			x = mul(x, arr[i]);
		}

		single_update[pos] = block_update[pos] = -1;
		block_product[pos] = x;
	}

	void apply(int l, int r, int x) {
		int L = l / B, R = r / B;
		if (L == R) {
			reconstruct(L);
			for (int i = l; i <= r; i++) {
				arr[i] = mul(arr[i], x);
				block_product[L] = mul(block_product[L], x);
			}
			return;
		}
		reconstruct(L);
		for (int i = l; i < (L + 1) * B; i++) {
			arr[i] = mul(arr[i], x);
			block_product[L] = mul(block_product[L], x);
		}
		reconstruct(R);
		for (int i = R * B; i <= r; i++) {
			arr[i] = mul(arr[i], x);
			block_product[R] = mul(block_product[R], x);
		}
		for (int j = L + 1; j < R; j++)
			update(j, x);
	}

	int get(int l, int r) {
		int L = l / B, R = r / B;
		int ans = 1;
		if (L == R) {
			reconstruct(L);
			for (int i = l; i <= r; i++) {
				ans = mul(ans, arr[i]);
			}
			return ans;
		}
		reconstruct(L);
		for (int i = l; i < (L + 1) * B; i++) {
			ans = mul(ans, arr[i]);
		}
		reconstruct(R);
		for (int i = R * B; i <= r; i++) {
			ans = mul(ans, arr[i]);
		}
		for (int j = L + 1; j < R; j++) {
			ans = mul(ans, block_product[j]);
			if (block_update[j] != -1)
				ans = mul(ans, block_update[j]);
		}
		return ans;
	}
};

struct prime_tree {
	vector<ll> t, d;
	int n;

	prime_tree(vector<ll>& a) : n(a.size()) {
		t.resize(4 * n);
		d.resize(4 * n, -1);
		build(1, 0, n, a);
	}

	ll build(int u, int l, int r, vector<ll>& a) {
		if (l == r - 1) {
			return t[u] = a[l];
		}
		int m = (l + r) / 2;
		return t[u] = build(u << 1, l, m, a) | build(u << 1 | 1, m, r, a);
	}

	inline void add(ll& u, ll x) {
		if (u == -1)
			u = x;
		else
			u |= x;
	}

	void push(int u, int l, int r) {
		if (d[u] == -1) return;
		t[u] |= d[u];
		if (r - l > 1) {
			add(d[u << 1], d[u]);
			add(d[u << 1 | 1], d[u]);
		}
		d[u] = -1;
	}

	void update(int u, int l, int r, int L, int R, ll x) {
		push(u, l, r);
		if (L >= R || l > L || r < R) return;
		if (l == L && r == R) {
			add(d[u], x);
			push(u, l, r);
			return;
		}
		int m = (l + r) / 2;
		update(u << 1, l, m, L, min(m, R), x);
		update(u << 1 | 1, m, r, max(L, m), R, x);

		t[u] = t[u << 1] | t[u << 1 | 1];
	}

	ll get(int u, int l, int r, int L, int R) {
		push(u, l, r);
		if (L >= R || l > L || r < R) return 0;
		if (l == L && r == R) {
			return t[u];
		}
		int m = (l + r) / 2;
		return get(u << 1, l, m, L, min(m, R)) | get(u << 1 | 1, m, r, max(L, m), R);
	}

	ll get(int l, int r) {
		return get(1, 0, n, l, r + 1);
	}
	void apply(int l, int r, ll x) {
		update(1, 0, n, l, r + 1, x);
	}
};

ll transform(int x) {
	ll mask = 0;
	forn(i, P)
		if (x % primes[i] == 0) {
			mask |= (1LL << i);
		}
	return mask;
}

void solve() {
	int n, q; cin >> n >> q;

	vi a(n);
	vector<ll> _a;

	for (auto& v : a) {
		cin >> v;
		_a.push_back(transform(v));
	}

	auto Ptree = product_tree(a);
	auto Mtree = prime_tree(_a);

	int l, r, x;
	forn(i, q) {
		string s; cin >> s;
		if (s == "MULTIPLY") {
			cin >> l >> r >> x;
			l--, r--;
			Ptree.apply(l, r, x);
			Mtree.apply(l, r, transform(x));
		}
		else {
			cin >> l >> r;
			l--, r--;

			int product = Ptree.get(l, r);
			ll mask = Mtree.get(l, r);

			forn(j, 63)
				if (mask >> j & 1) {
					product = mul(product, primes[j] - 1);
					product = mul(product, pi[j]);
				}

			cout << product << endl;
		}
	}
}

signed main() {
	int t = 1;

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	precalc();

	while (t--) {
		clock_t z = clock();
		solve();
		debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
	}
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	map<int, int> cntx, cnty;
	
	while (n--) {
		int x, y;
		cin >> x >> y;
		cntx[x]++; cnty[y]++;
	}
	
	cout << min(cntx.size(), cnty.size()) << endl;
	
	return 0;
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	vector<int> cntx(101, 0);
	vector<int> cnty(101, 0);
	
	while (n--) {
		int x, y;
		cin >> x >> y;
		cntx[x]++; cnty[y]++;
	}
	
	int distinctx = 0, distincty = 0;
	for (int i=0; i<101; i++) {
	    distinctx += (cntx[i] > 0);
	    distincty += (cnty[i] > 0);
	}
	
	cout << min(distinctx, distincty) << endl;
	
	return 0;
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n; cin >> n;
	
	vector<int> a(n), b(n);
	for (auto &z: a) cin >> z;
	for (auto &z: b) cin >> z;
	
	long long Joy = 0;
	for (int i=0; i<n; i++) {
		if (b[i] < 2 || b[i] > a[i] * 2) {Joy--; continue;}
		int x = b[i] / 2, y = b[i] - x;
		Joy += 1LL * x * y;
	}
	cout << Joy << endl;
	
	return 0;
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n, k, w; string s;
	cin >> n >> k >> w >> s;
	
	vector< vector<int> > CandyGrp(k);
	
	for (int i=0; i<n; i++) {
	    if (s[i] == '0') continue;
	    CandyGrp[i % k].push_back(i);
	}
	
	while (w--) {
	    int l, r;
		cin >> l >> r; l--; r--;
		
		int res = 0;
		int demandedGroup = (l + k - 1) % k;
		int BoxesPerGroup = (r - l + 1) / k;
		
		for (int id=0; id<k; id++) {
		    
			int x = lower_bound(CandyGrp[id].begin(), CandyGrp[id].end(), l) - CandyGrp[id].begin();
			int y = upper_bound(CandyGrp[id].begin(), CandyGrp[id].end(), r) - CandyGrp[id].begin();
			
			if (id == demandedGroup) {
			    res += (BoxesPerGroup - (y - x));
			}
			else res += (y - x);
		}
		
		cout << res << endl;
	}
	
	return 0;
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

int dx[] = {-1, +0, +0, +1};
int dy[] = {+0, -1, +1, +0};
pair<int, int> Default = {-1, -1};

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n, m, k; cin >> n >> m >> k;
	
	vector<vector<int>> Dist(n+2, vector<int>(m+2, 4444));
	vector<vector<pair<int, int>>> Last(n+2, vector<pair<int, int>>(m+2, Default));
    
	stack<pair<int, int>> Cells;
	int cost = 0;
	
	queue<pair<int, int>> Q;
	Q.push({1, 1}); Dist[1][1] = 1;
	
	while (!Q.empty() && Cells.size() < k) {
		pair<int, int> C = Q.front(); Q.pop();
		Cells.push(C); int x = C.first, y = C.second;
		
		cost += Dist[x][y];
		
		for (int dir=0; dir<4; dir++) {
			if (x + dx[dir] < 1 || x + dx[dir] > n) continue;
			if (y + dy[dir] < 1 || y + dy[dir] > m) continue;
			
			if (Dist[x+dx[dir]][y+dy[dir]] != 4444) continue;
			
			Dist[x+dx[dir]][y+dy[dir]] = Dist[x][y] + 1;
			Q.push({x + dx[dir], y + dy[dir]});
			Last[x+dx[dir]][y+dy[dir]] = C;
		}
	}
	
	cout << cost << endl;
	
	while (!Cells.empty()) {
		int x = Cells.top().first, y = Cells.top().second; Cells.pop();
		stack<pair<int, int>> Traceback;
		
		while (x != -1 && y != -1) {
			Traceback.push({x, y});
			pair<int, int> NextCell = Last[x][y];
			x = NextCell.first; y = NextCell.second;
		}
		
		while (!Traceback.empty()) {
			pair<int, int> CurCell = Traceback.top();
			Traceback.pop();
			cout << "(" << CurCell.first << ", " << CurCell.second << ") ";
		}
		cout << endl;
	}
	
	return 0;
}

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

struct SegTree_Sum {
	int n; vector<long long> Tree, Lazy;
	SegTree_Sum() {}
	SegTree_Sum(int _n) {
		n = _n;
		Tree.resize(n*4);
		Lazy.resize(n*4);
	}
	
	void Propagate(int node, int st, int en) {
		if (Lazy[node] == 0) return;
		Tree[node] += Lazy[node] * (en - st + 1);
		if (st != en) {
			Lazy[node*2+1] += Lazy[node];
			Lazy[node*2+2] += Lazy[node];
		}
		Lazy[node] = 0;
	}
	
	void Update(int node, int st, int en, int L, int R, long long val) {
		Propagate(node, st, en);
		if (en < st || R < st || en < L) return;
		if (L <= st && en <= R) {
			Lazy[node] += val;
			Propagate(node, st, en); return;
		}
		Update(node*2+1, st, (st+en)/2+0, L, R, val);
		Update(node*2+2, (st+en)/2+1, en, L, R, val);
		Tree[node] = Tree[node*2+1] + Tree[node*2+2];
	}
	
	long long Sum(int node, int st, int en, int L, int R) {
		Propagate(node, st, en);
		if (en < st || R < st || en < L) return 0LL;
		if (L <= st && en <= R) return Tree[node];
		long long p1 = Sum(node*2+1, st, (st+en)/2+0, L, R);
		long long p2 = Sum(node*2+2, (st+en)/2+1, en, L, R);
		return (p1 + p2);
	}
	
	void RangeUpdate(int L, int R, long long val) {
		Update(0, 0, n-1, L, R, val);
	}
	
	long long RangeSum(int L, int R) {
		return Sum(0, 0, n-1, L, R);
	}
};

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	int n, m, w; cin >> n >> m >> w;
	
	long long TotalCandies = 0;
	
	SegTree_Sum TreeRow = SegTree_Sum(n);
	SegTree_Sum TreeCol = SegTree_Sum(m);
	
	while (w--) {
		int t, x1, y1, x2, y2;
		cin >> t >> x1 >> y1 >> x2 >> y2;
		
		if (t == 0) {
			int v; cin >> v;
			
			TotalCandies += 1LL * (x2 - x1 + 1) * (y2 - y1 + 1) * v;
			
			TreeRow.RangeUpdate(x1, x2, 1LL * v * (y2 - y1 + 1));
			TreeCol.RangeUpdate(y1, y2, 1LL * v * (x2 - x1 + 1));
		}
		else if (t == 1) {
			long long res = 0;
			
			res += TreeRow.RangeSum(x1, x2);
			res += TreeCol.RangeSum(y1, y2);
			res -= TotalCandies;
			
			cout << res << endl;
		}
	}
	
	return 0;
}