t = int(input())
for i in range(t):
    n, a, b = map(int, input().split())
    c = n // 3
    d = n % 3
    print(min((c + 1) * b, c * b + d * a, n * a))

t = int(input())
for i in range(t):
    s = input()
    pref2 = 0
    suf = 0
    for x in s:
        if x == '1' or x == '3':
            suf += 1
    ans = pref2 + suf
    for x in s:
        if x == '2':
            pref2 += 1
        if x == '1' or x == '3':
            suf -= 1
        ans = max(ans, pref2 + suf)
    print(len(s) - ans) 

t = int(input())
for i in range(t):
    n = int(input())
    c = list(map(int, input().split()))

    s = sum(c)
    ones = 0
    slots = 0
    for x in c:
        if x == 1:
            ones += 1
        else:
            slots += x // 2 - 1
    if ones == n - 1:
        slots += 1
    wasted = max(0, ones - slots)
    if s - wasted < 3:
        print(0)
    else:
        print(s - wasted)

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x, --x;
        for (auto &x : b) cin >> x, --x;
        vector<int> pa(n + 1, n), pb(n + 1, n), dp(n + 1, n);
        long long ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            pa[a[i]] = i;
            pb[b[i]] = i;
            if (a[i] == b[i]) {
                int x = a[i] + 1;
                if (pa[x] == pb[x]) {
                    dp[i] = dp[pa[x]];
                } else {
                    dp[i] = min(pa[x], pb[x]);
                }
            }
            if (pa[0] != pb[0]) {
                ans += min(pa[0], pb[0]) - i;
            } else {
                ans += dp[pa[0]] - i;
            }
        }
        cout << ans << '\n';
    }
}

import bisect
import sys
input = sys.stdin.readline

INF = int(1e9) + 7
A = int(1e6) + 3

n = int(input())
a = [list(map(int, input().split())) for i in range(2)]

minVal = [[INF] * A for i in range(2)]
pMin = [[INF] * A for i in range(2)]
sMin = [[INF] * A for i in range(2)]
for k in range(2):
    for i in range(n):
        minVal[k][a[k][i]] = min(minVal[k][a[k][i]], a[k ^ 1][i])

    for v in range(A - 1):
        pMin[k][v + 1] = min(pMin[k][v], minVal[k][v])
    
    for v in range(A - 2, -1, -1):
        sMin[k][v] = min(sMin[k][v + 1], minVal[k][v])

mid = 0
for i in range(n):
    if a[0][mid] + a[1][mid] > a[0][i] + a[1][i]:
        mid = i

m = int(input())
t = [list(map(int, input().split())) for i in range(3)]

def I(val, l, r):
    if val < l:
        return 0
    return min(val, r)

ans = []
for id in range(m):
    cur = I(a[0][mid], t[0][id], t[0][id] + t[2][id]) + I(a[1][mid], t[1][id], t[1][id] + t[2][id])
    for k in range(2):
        pos_l = t[k][id]
        pos_r = min(A - 1, t[k][id] + t[2][id])
        
        if pMin[k][pos_l] < INF:
            cur = min(cur, I(pMin[k][pos_l], t[k ^ 1][id], t[k ^ 1][id] + t[2][id]))
        if sMin[k][pos_r] < INF:
            cur = min(cur, pos_r + I(sMin[k][pos_r], t[k ^ 1][id], t[k ^ 1][id] + t[2][id]))
    ans.append(cur)

print("\n".join(map(str, ans)))

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int K = 3;
const int LN = 20;

vector<int> g[N];
int p[N];
pair<int, int> dp_down[N][K];
int dp_up[N];
int q_index;
int ans[N];
int f[N];

void upd_down(int idx, pair<int, int> p)
{
    if(dp_down[idx][K - 1] < p)
    {
        dp_down[idx][K - 1] = p;
        int j = K - 1;
        while(j != 0)
        {
            if(dp_down[idx][j - 1] < dp_down[idx][j])
            {
                swap(dp_down[idx][j - 1], dp_down[idx][j]);
                j--;
            }
            else break;
        }
    }
}

void upd(pair<int, int>& p, int x)
{
    if(p.second < x) p.second = x;
    if(p.first < p.second) swap(p.first, p.second);
}

int get_cur(int x)
{
    pair<int, int> cur_ans = {0, 0};
    for(int i = 0; i < K; i++)
        if(dp_down[x][i].second != f[x])
            upd(cur_ans, dp_down[x][i].first);
    if(f[x] != -1)
        upd(cur_ans, dp_up[x]);
    return cur_ans.second + 1;        
}

int get_full(int x)
{
    pair<int, int> cur_ans = {0, 0};
    for(int i = 0; i < K; i++)
        upd(cur_ans, dp_down[x][i].first);
    upd(cur_ans, dp_up[x]);
    return cur_ans.second + 1;    
}

void dfs1(int x, int parent = -1)
{
    p[x] = parent;
    for(auto y : g[x])
    {
        if(y > q_index) continue;
        if(y != parent)
        {
            dfs1(y, x);
            upd_down(x, make_pair(get_cur(y), y));
        }
    }
}

void dfs2(int x)
{
    if(p[x] != -1)
        dp_up[x] = get_cur(p[x]);
    for(auto y : g[x])
    {
        if(y > q_index) continue;
        if(y != p[x])
        {
            f[x] = y;
            dfs2(y);
            f[x] = -1;
        }
    }
}

int get_ans(int x)
{
    q_index = x + 2;
    for(int i = 1; i <= q_index; i++)
    {
        dp_up[i] = 0;
        for(int j = 0; j < K; j++)
            dp_down[i][j] = {0, -1};
        p[i] = -1;
        f[i] = -1;
    }
    dfs1(1);
    dfs2(1);
    int ans = 1;
    for(int i = 1; i <= q_index; i++)
        ans = max(ans, get_full(i));
    return ans;
}

void rec(int l, int r, int L, int R)
{
    if(l >= r) return;
    if(L == R)
    {
        for(int i = l; i < r; i++)
            ans[i] = L;
        return;
    }
    int mid = (l + r) / 2;
    ans[mid] = get_ans(mid);
    rec(l, mid, L, ans[mid]);
    rec(mid + 1, r, ans[mid], R);
}

void solve()
{
    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        g[x].push_back(i + 2);
        g[i + 2].push_back(x);
    }
    rec(0, q, 1, LN);
    for(int i = 0; i < q; i++)
        cout << ans[i] << " ";
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

There are two categories of people which might get affected by this decision:

• people who have got Accepted without satisfying this condition. I believe (and this is corroborated by 10 random solutions I checked) that getting Accepted in this problem while ignoring this condition altogether is nigh-impossible because you cannot use more than $$$n$$$ circles, and if you pick $$$n$$$ circles with radii of $$$10^3$$$ in a rectangle of size $$$(2 \cdot 10^5) \times (2 \cdot 10^5)$$$, you still cover less than $$$80\%$$$ of the area, meaning that you cannot get Accepted by simply putting circles "randomly" without caring about the fact that they must cover points. Random solutions I've checked actually verify this condition, so I believe that the issue only affected a very small portion of people who got Accepted (I couldn't find even a single submission affected).

• people who got WA on a later test. Not handling this condition means that you might pass more tests, but still won't pass the $$$36$$$-th test which actually forces you to choose circles covering the points. This means that some people got WA36 instead of WA2 which they should have received if the checker was correct, but it does not change their result overall.

This means that the issue with checker does not affect the round standings overall, hence I've decided to keep all the verdicts as they are.

t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    good = False
    for z in range(x * 2, y, x):
        if y % z != 0:
            good = True
            break
    if good:
        print('YES')
    else:
        print('NO')

t = int(input())
for i in range(t):
    x, y = map(int, input().split())
    print('YES' if y > 2 * x else 'NO')

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
void solve() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < (int)s.size() - 1; i++){
		ans += (s[i] == s[i + 1]);
	}
	cout << (ans <= 2 ? "YES\n" : "NO\n");
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

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

#define int long long

const int INF = 1'000'000'007;

void solve(){
  int n;
  cin >> n;
  vector<string> d(2);
  cin >> d[0] >> d[1];

  vector<int> dp(n + 1, INF);
  dp[0] = 0;
  for (int i = 0; i < n; i++){
    dp[i + 1] = min(dp[i + 1], dp[i] + (d[0][i] != d[1][i]));
    if (i + 1 < n){
      dp[i + 2] = min(dp[i + 2], dp[i] + (d[0][i] != d[0][i + 1]) + (d[1][i] != d[1][i + 1]));
    }
  }

  cout << dp[n] << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int t = 1;
	cin >> t;
	while(t--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MOD = 998'244'353;

int get0(int x){
    return 1ll + (x >= 3 ? (x - 3) / 4 + 1 : 0);
}

int get1(int x){
    return (x >= 1 ? (x - 1) / 4 + 1 : 0);
}

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

    int l0 = get0(x - 1) % MOD;
    int r0 = (get0(n) - l0) % MOD;
	int ans = l0 * r0;

    int l1 = get1(x - 1) % MOD;
    int r1 = (get1(n) - l1) % MOD;
	ans += l1 * r1;
    ans %= MOD;

    cout << ans << '\n';
}

signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}

#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

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

#define int long long

mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
 
void solve() {
	int n, r;
	cin >> n >> r;
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++){
		cin >> p[i].first >> p[i].second;
	}

	int w = 2 * r, h = ceil(sqrt(3) * r);

	auto is_in_circle = [&](int x, int y, int ox, int oy, int r){
		return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
	};

	int cov;
	vector<pair<int, int>> ans;

	do{
		ans.clear();
		cov = 0;
		
		int x0 = rng() % 100'000, y0 = rng() % 100'000;
		auto check_point = [&](int x, int y){
			int nearest_row = (y - y0) / h;
			for (int row = nearest_row - 2; row <= nearest_row + 2; row++){
				int nearest_col = (x - (x0 + (row % 2) * r)) / w;
				for (int col = nearest_col - 2; col <= nearest_col + 2; col++){
					int x_lat = x0 + col * w + (row % 2) * r;
					int y_lat = y0 + row * h;
					if (is_in_circle(x, y, x_lat, y_lat, r)){
						ans.emplace_back(x_lat, y_lat);
						cov++;
						return;
					}
				}
			}
		};

		for (int i = 0; i < n; i++){
			check_point(p[i].first, p[i].second);
		}
	} while(cov * 100 < 89 * n);

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());

	cout << ans.size() << '\n';
	for (auto [x, y] : ans){
		cout << x << ' ' << y << '\n';
	}
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	//cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

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

const int MODS[] = {some hidden number 1, some hidden number 2};
const int P = some hidden number 3;

int powP[2][1'000'007];
int inv_powP[2][1'000'007];

int bpow(int x, int p, int mod){
	int res = 1;
	while(p){
		if (p % 2 == 1){
			res = (res * x) % mod;
		}
		p >>= 1;
		x = (x * x) % mod;
	}
	return res;
}
 
void solve(){
	int n, l, k;
	cin >> n >> l >> k;
	string s;
	cin >> s;
 
	if (l * k > n){
		cout << "NO\n";
		return;
	}
 
	if (k == 1){
		cout << "YES\n";
		cout << s << '\n';
		return;
	}

	vector<vector<int>> h(2, vector<int>(n + 1));
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < n; j++){
			h[i][j + 1] = (h[i][j] + (s[j] - 'a' + 1) * powP[i][j]) % MODS[i];
		}
	}

	function<pair<int, int>(int, int)> get_h = [&](int l, int r){
		return make_pair((h[0][r + 1] - h[0][l] + MODS[0]) * inv_powP[0][l] % MODS[0],
		(h[1][r + 1] - h[1][l] + MODS[1]) * inv_powP[1][l] % MODS[1]);
	};
 
	function<int(int, int, int, int)> cmp_substring = [&](int l1, int r1, int l2, int r2){
		int len1 = r1 - l1 + 1;
		int len2 = r2 - l2 + 1;

		int l = 0, r = min(len1, len2) - 1;
		while(l <= r){
			int m = l + (r - l) / 2;
			if (get_h(l1, l1 + m) != get_h(l2, l2 + m)){
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}

		char ch1 = (l < len1 ? s[l1 + l] : 'a' - 1);
		char ch2 = (l < len2 ? s[l2 + l] : 'a' - 1);
 
		if (ch1 < ch2){
			return -1;
		}
		if (ch1 > ch2){
			return 1;
		}
		return 0;
	};
 
	int la = 0, ra = l - 1;
 
	for (int i = 0; i < n; i++){
		int cnt = i / l;
		if (i > 0 && cnt == 0){
			continue;
		}
		int len = i + max(0ll, (k - 1) - cnt) * l;
		if (n - len >= l){
			if (cmp_substring(i, i + n - len - 1, la, ra) == 1){
				la = i;
				ra = i + n - len - 1;
			}
		}
	}
 
	cout << "YES\n";
	cout << s.substr(la, ra - la + 1) << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	powP[0][0] = powP[1][0] = 1;
	inv_powP[0][0] = inv_powP[1][0] = 1;
	int inv_p[] = {bpow(P, MODS[0] - 2, MODS[0]), bpow(P, MODS[1] - 2, MODS[1])};

	for (int i = 1; i < 1'000'001; i++){
		for (int j = 0; j < 2; j++){
			powP[j][i] = powP[j][i - 1] * P % MODS[j];
			inv_powP[j][i] = inv_powP[j][i - 1] * inv_p[j] % MODS[j];
		}
	}

 
	int tests = 1;
	cin >> tests;
	while(tests--){
		solve();
	}
 
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int n, l, k;
string s;
string cur;
int zf[2000043];
mt19937 rnd(421337);
 
void z_function(const string& s) 
{
    int n = s.size();
    for(int i = 0; i < n; i++) zf[i] = 0;
    for (int i = 1, l = 0, r = 0; i < n; i++) 
    {
        if (i <= r)
            zf[i] = min(r - i, zf[i - l]);
        while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]])
            zf[i]++;
        if (i + zf[i] > r) 
        {
            l = i;
            r = i + zf[i];
        }
    }        
}
 
bool read()
{
    if (!(cin >> n >> l >> k))
        return false;
    cin >> s;
    return true;
}    
 
string find_best(vector<pair<int, int>> cand)
{
    while(true)
    {
        if(cand.size() == 1)
            return s.substr(cand[0].first, cand[0].second);
        int lf = cand[0].first;
        int rg = cand[0].first + cand[0].second;
        for(int i = 1; i < cand.size(); i++)
        {
            lf = min(lf, cand[i].first);
            rg = max(rg, cand[i].first + cand[i].second);
        }
        auto p = cand[0];
        cur = s.substr(p.first, p.second) + "?" + s.substr(lf, rg - lf);
        z_function(cur);
        vector<pair<int, int>> better;
        int len = p.second;
        for(int i = 0; i < cand.size(); i++)
        {
            if(cand[i] == p) continue;
            int L = cand[i].first - lf;
            int cur_len = cand[i].second;
            int lcp = zf[len + 1 + L];
            lcp = min(lcp, cur_len);
            if(lcp == cur_len || (len > lcp && cur[L + len + 1 + lcp] <= cur[lcp]))
                continue;
            better.push_back(cand[i]); 
        }
        if(better.empty())
            return s.substr(p.first, p.second);
        else
            cand = better;
    }
    return "";
}
 
void solve()
{
    if(k * 1ll * l > n)
    {
        cout << "NO\n";
        return;
    }
    if(k == 1)
    {
        cout << "YES\n" << s << "\n";
        return;
    }
    vector<pair<int, int>> cand;
    for(int i = 0; i < n; i++)
    {
        if(i > 0 && i < l) continue;
        int lf = i / l;
        int rg = (n - i) / l;
        if(lf + rg < k) continue;
        int need_rg = max(0, k - lf - 1);
        int len = (n - need_rg * l) - i;
        if(len >= l)
            cand.push_back(make_pair(i, len));    
    }
    shuffle(cand.begin(), cand.end(), rnd);
    if(cand.empty())
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n" << find_best(cand) << "\n";
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int tc = 1;
    cin >> tc;
    while (tc--)
    {
        read();
        solve();
    }
}

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<int> k;
vector<int> g;

bool read()
{
    if(!(cin >> n >> m)) return false;
    k.resize(m);
    for(int i = 0; i < m; i++) cin >> k[i];
    return true;
}

pair<vector<int>, vector<int>> get_chain(int start, int rank)
{
    if(rank == 0)
        return make_pair(vector<int>({start}), vector<int>());
    pair<vector<int>, vector<int>> p = get_chain(start, rank - 1);
    int cnt = g[rank - 1] / g[rank];
    for(int i = 1; i < cnt; i++)
    {
        p.second.push_back(k[rank]);
        int next_start = (p.first.back() + k[rank]) % k[0];
        pair<vector<int>, vector<int>> q = get_chain(next_start, rank - 1);
        for(auto x : q.first) p.first.push_back(x);
        for(auto x : q.second) p.second.push_back(x);
    }
    return p;
}

void solve()
{
    g = k;
    for(int i = 1; i < m; i++)
        g[i] = gcd(g[i - 1], k[i]);
    if(g.back() != 1)
    {
        cout << -1 << "\n";
        return;
    }   
    if(k[0] == 1)
    {
        for(int i = 0; i < n; i++)
        {
            if(i) cout << " ";
            cout << i;
        }
        cout << "\n";
        return;
    }
    pair<vector<int>, vector<int>> chain = get_chain(0, m - 1);
    vector<int> classes = chain.first;
    vector<int> add = chain.second;
    vector<int> ans;
    int new_begin = 0;
    for(int i = 0; i < classes.size(); i++)
    {
        int new_end = -1;
        for(int j = classes[i]; j < n; j += k[0])
            if(j != new_begin)
            {
                new_end = j;
                break;
            }
        ans.push_back(new_begin);
        for(int j = classes[i]; j < n; j += k[0])                                                   
            if(j != new_begin && j != new_end)
                ans.push_back(j);
        ans.push_back(new_end);
        if(i + 1 < classes.size())
            new_begin = new_end + add[i];
    }
    for(int i = 0; i < n; i++)
    {
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        read();
        solve();
    }
    return 0;
}

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val k = readLine()!!.toInt()
        val (a1, b1) = readLine()!!.split(" ").map { it.toInt() }
        val (a2, b2) = readLine()!!.split(" ").map { it.toInt() }
        println(if (a1 - b1 + a2 - b2 >= k) "NO" else "YES")
    }
}

fun main() = repeat(readln().toInt()) {
    var (a, b, c, d) = readln().split(" ").map { it.toInt() }
    if (a > b) a = b.also { b = a }
    if (c > d) c = d.also { d = c }
    println(d - a - maxOf(0, b - c))
}

fun printAns(n : Int, pos: MutableList<Int>) {
    if (n == 0) {
        println("NO")
        return
    }
    println("YES")
    println(n)
    val a = CharArray(n) { '.' }
    println(a.joinToString(""))
    for (i in pos) {
        a[i] = '*'
    }
    println(a.joinToString(""))
}

fun main() = repeat(readln().toInt()) {
    var k = readln().toInt()
    if (k == 1) {
        printAns(1, mutableListOf(0))
        return@repeat
    }
    var n = 0
    val pos = mutableListOf<Int>()
    if (k % 5 == 1 || k % 5 == 3) {
        n += 2
        pos.add(0)
        k -= 3
    }
    while (k >= 5) {
        n += 3
        pos.add(n - 2)
        k -= 5
    }
    if (k % 5 == 3) {
        n += 2
        pos.add(n - 1)
        k -= 3
    }
    printAns(if (k == 0) n else 0, pos)
}

import java.util.StringTokenizer

fun main() {
    val t = readLine()!!.toInt()
    repeat(t) {
        val st = StringTokenizer(readLine())
        st.nextToken()
        st.nextToken()

        val a = readLine()!!.split(" ").map { it.toInt() }
        val b = readLine()!!.split(" ").map { it.toInt() }

        val aTrimmed =
            if (a.size > 1) a.subList(1, a.size - 1) else a
        val bTrimmed =
            if (b.size > 1) b.subList(1, b.size - 1) else b

        val ok = aTrimmed.toSet().intersect(bTrimmed.toSet()).isNotEmpty()
        println(if (ok) "Yes" else "No")
    }
}

import kotlin.math.abs

fun main() {
    val (n, q) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }
    val xs = readln().split(" ").map { it.toLong() }
    val bl = IntArray(2 * n - 1) { 1 }
    for (i in 1 until n) {
        if (a[i] != a[i - 1]) bl[2 * i - 1] = abs(a[i] - a[i - 1]) - 1
    }
    val s = bl.scan(0L) { x, y -> x + y }
    
    fun getVal(x : Long) : Int {
        if (x > s.last()) return -1
        val i = s.binarySearch { if (it < x) -1 else 1 }.inv() - 1
        val j = i / 2
        if (i % 2 == 0) return a[j]
        if (a[j] == a[j + 1]) return 0
        val d = (a[j + 1] - a[j]) / abs(a[j + 1] - a[j])
        return a[j] + d * (x - s[i]).toInt()
    }
    
    println(xs.map { getVal(it) }.joinToString(" "))
}

const val MOD = 998244353;

fun add(x: Int, y: Int): Int {
    return ((x + y) % MOD + MOD) % MOD
}

fun mul(x: Int, y: Int): Int {
    return (x.toLong() * y % MOD).toInt()
}

fun main() = repeat(readln().toInt()) {
    val n = readln().toInt()
    val a = readln().split(" ").map { it.toInt() }
    val pw = generateSequence(1, { mul(it, 2) }).take(n + 1).toList()
    val cnt = a.scan(0) { x, y -> x + if (y == 0) 1 else 0 }
    val sum = mutableMapOf<Int, Int>()
    var ans = pw[cnt[n]]
    for (i in 0 until n) {
        if (a[i] == 0) continue
        val cur = sum.getOrDefault(a[i], 0)
        ans = add(ans, mul(cur, pw[cnt[n] - cnt[i]]))
        sum[a[i]] = add(cur, pw[cnt[i]]) 
    }
    println(ans)
}

import kotlin.math.*

fun main() {
    fun isqrt(a : Long) : Long {
        var s = max(0L, sqrt(a.toDouble()).toLong() - 2)
        while ((s + 1) * (s + 1) <= a)
            s++
        return s
    }
    repeat(readln().toInt()) {
        var (n, m, r) = readln().split(' ').map { it.toLong() }
        if (n > m)
            n = m.also { m = n }
        var ans = 0L
        for (i in 0..n) {
            val lf = if (i <= r) 1 + isqrt(r * r - i * i) else max(0L, m - r)
            val rg = if (n - i <= r) m - 1 - isqrt(r * r - (n - i) * (n - i)) else min(m, r)
            ans += max(0L, rg - lf + 1)
        }
        println(ans)
    }
}

import java.util.*

const val MOD = 998244353

fun add(x: Int, y: Int): Int {
    var result = x + y
    while (result >= MOD) result -= MOD
    while (result < 0) result += MOD
    return result
}

fun mul(x: Int, y: Int): Int {
    return ((x.toLong() * y) % MOD).toInt()
}

fun solve() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val a = IntArray(n) { scanner.nextInt() }
    var k = 0
    for (i in 0 until n) if (a[i] == -1) k++
    val ans = Array(k + 1) { IntArray(k + 1) }
    
    for (mex in 0..k) {
        val dp = Array(k + 1) { IntArray(mex + 1) }
        dp[0][0] = 1
        for (i in 0 until k) {
            for (j in 0..mex) {
                if (dp[i][j] == 0) continue
                val inc = mex - j
                val same = n - inc
                if (inc > 0) {
                    dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(inc, dp[i][j]))
                }
                dp[i + 1][j] = add(dp[i + 1][j], mul(same, dp[i][j]))
            }
        }
        for (i in 0..k) {
            ans[mex][i] = dp[i][mex]
        }
    }

    val unusedFirst = mutableSetOf<Int>()
    val unusedAll = mutableSetOf<Int>()
    for (i in 0..n) unusedAll.add(i)
    var cnt = 0
    for (i in 0 until n) {
        if (a[i] == -1) {
            cnt++
        } else {
            unusedFirst.remove(a[i])
            unusedAll.remove(a[i])
        }
        while (unusedFirst.size <= cnt) {
            unusedFirst.add(unusedAll.first())
            unusedAll.remove(unusedAll.first())
        }
        val unused = unusedFirst.toList()
        var sum = 0
        for (j in 0..cnt) {
            sum = add(sum, mul(ans[j][cnt], unused[j]))
        }
        print("$sum ")
    }
}

fun main() {
    val t = 1
    repeat(t) {
        solve()
    }
}

import kotlin.math.*
import java.util.*

const val MOD = 998244353
const val K = 7
const val A = 50

fun add(x: Int, y: Int): Int {
    var result = x + y
    while (result >= MOD) result -= MOD
    while (result < 0) result += MOD
    return result
}

fun mul(x: Int, y: Int): Int {
    return (x.toLong() * y % MOD).toInt()
}

fun gcd(x: Int, y: Int): Int {
    return if (x == 0) y else gcd(y % x, x)
}

fun solve() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val m = scanner.nextInt()
    val c = IntArray(m) { scanner.nextInt() }
    val dist = Array(A + 1) { IntArray(A + 1) }
    
    for (i in 1..A) {
        for (j in 1..A) {
            var diff = i * j / gcd(i, j) / gcd(i, j)
            for (k in 2..A) {
                while (diff % k == 0) {
                    diff /= k
                    dist[i][j]++
                }
            }
        }
    }

    val dp = IntArray(1 shl K)
    dp[0] = 1
    for (i in 0 until m) {
        val cur = c[i]
        val ndp = IntArray(1 shl K)
        for (j in 0 until (1 shl K)) {
            var popcount = 0
            val shifted = (j shl 1) and ((1 shl K) - 1)
            ndp[shifted] = add(ndp[shifted], dp[j])
            for (k in 0 until K) {
                if ((j shr k) and 1 == 1) popcount++
            }
            val unused = n - popcount
            if (unused > 0 && i >= dist[1][cur] - 1) {
                ndp[shifted + 1] = add(ndp[shifted + 1], mul(unused, dp[j]))
            }
            for (k in 0 until K) {
                if ((j shr k) and 1 == 0) continue
                val idx = i - k - 1
                if (idx >= 0 && dist[c[idx]][cur] > k + 1) continue
                var new_mask = shifted + 1
                if (k != K - 1) new_mask -= 1 shl (k + 1)
                ndp[new_mask] = add(ndp[new_mask], dp[j])
            }
        }
        for (k in dp.indices) {
            dp[k] = ndp[k]
        }
    }
    var ans = 0
    for (x in dp) ans = add(ans, x)
    println(ans)
}

fun main() {
    val t = 1
    repeat(t) {
        solve()
    }
}

First, let's try to solve it with only one query. Which characters should we use, and where do we put them?

Greedy idea: let's use the maximum possible number of Is, then the maximum possible number of Vs, and only then use Xs. It's because if we replace any I with V, it increases the value by at least $$$3$$$, and if we replace any V with X, it increases the value by exactly $$$5$$$.

Okay, now we know which characters in which quantities we use. Now, let's choose their ordering in such a way that the number of pairs "IV" and "IX" is the maximum possible. V and X differ only in their costs, so let's replace every X (both in the original string and in characters we will use in the query) with V, and add the number of replaced characters times $$$5$$$ to the answer.

Now imagine the following process. We replace every question mark with I and evaluate the string. But if we have too few Is in a query, we should change some of Is to Vs. When we change an I to a V, one of the following three things can happen:

• we either increase the number of pairs "IV" by 1;
• or we don't change it;
• or we decrease it by 1.

Obviously, we want to make as many changes that increase the number of such pairs as we can, then as many changes that keep it as it is as we can, and only then apply changes that decrease it. Let's calculate two variables inc and same — the maximum number of changes of the first and the second type we can make.

Every segment of question marks is independent of each other. Suppose a segment is "isolated"; then the number of increasing changes is its length divided by $$$2$$$ (because it is the maximum number of pairs we can have), and the number of changes of the second type is its length modulo $$$2$$$ (because if it has even length, every character I we replace after making the pairs "breaks" one pair, and if it has odd length, we can transform an "IIV" pattern into an "IVV" pattern).

However, if there is an I before the segment or a V after it, they can also participate in forming pairs, so each of them increases its length by $$$1$$$. V after the segment also reduces the number of "increasing" operations by $$$1$$$, because we initially already have one pair "IV".

And that's about it: calculate the length of each segment of question marks, use it to calculate the values of inc and same. Then replace all question marks by Is to calculate the value of the string in the "perfect" case (when we have enough Is to replace), then use inc and same to find out how many replacements I $$$\rightarrow$$$ V increase or keep the number of pairs "IV". Processing queries also becomes easy if we know these values.

#include<bits/stdc++.h>

using namespace std;

int cost(char c)
{
    if(c == 'I') return 1;
    return 5;
}

int eval(string s)
{
    int n = s.size();
    int ans = 0;
    for(int i = 0; i < n; i++)
        if(s[i] == 'I' && i + 1 < n && s[i + 1] == 'V')
            ans--;
        else ans += cost(s[i]);
    return ans;    
}

void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'X')
        {
            s[i] = 'V';
            ans += 5;
        }
    }
    int inc = 0;
    int same = 0;
    int qcount = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] != '?') continue;
        int r = i;
        while(r < n && s[r] == '?') r++;
        int len = r - i;
        if(i > 0 && s[i - 1] == 'I') len++;
        if(r < n && s[r] == 'V') 
        {
            inc--;
            len++;
        }
        inc += len / 2;
        same += len % 2;
        qcount += (r - i);
        i = r - 1;        
    }
    for(int i = 0; i < n; i++)
        if(s[i] == '?') s[i] = 'I';
    ans += eval(s);
    for(int i = 0; i < q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int used_v = max(0, min(b, qcount - c));
        int used_x = max(0, qcount - c - b);
        int cur = ans;
        cur += used_v * 4 + used_x * 9;
        int rep = used_v + used_x;
        cur -= min(inc, rep) * 2;
        rep -= (inc + same);
        cur += max(0, rep) * 2;
        cout << cur << "\n";  
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() }
  val p = a.runningReduce { x, y -> minOf(x, y) }
  val ans = (1..n).filter { i -> a[i - 1] != p[i - 1] }
  println(ans.size)
  println(ans.joinToString(" "))    
}

fun main() = repeat(readln().toInt()) {
  val (n, m) = readln().split(" ").map { it.toInt() }
  val a = readln().split(" ").map { it.toInt() }
  val b = readln().split(" ").map { it.toInt() }
  val k = a.intersect(b).size
  println(2 * minOf(n - k, m - k) + if (n > m) 2 else 1)
}

@file:Suppress("CanBeVal")

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
import kotlin.math.max
import kotlin.math.min

private fun solveTest() {
    val n = readInt()
    val res = emptyList<String>().toMutableList()
    for (i in 0..n - 1) {
        if (i % 2 == 0) {
            for (j in i..n - 1) {
                res.add("pushfront a[" + j + "]")
                res.add("min")
            }
            res.add("popback")
        } else {
            for (j in i..n - 1) {
                res.add("min")
                res.add("popfront")
            }
        }
    }
    println(res.size)
    for (s in res) {
        println(s)
    }
}

private fun solve() {
//    repeat(readInt()) {
    solveTest()
//    }
}

// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}

private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}

private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}

private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}

private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toLong() }
        val a = readln().split(' ').map { it.toLong() }
        // n * resVal - a.sum() <= k
        val resVal = (k + a.sum()) / n
        if (resVal < a.maxOrNull()!!) {
            println(-1)
            return@repeat
        }
        val minEl = a.minOrNull()!!
        var ans = a.sumOf { resVal - it } - (resVal - minEl)
        if (minEl < resVal)
            ans -= a.count { it == minEl } - 1
        println(ans)
    }
}

const val MOD = 998244353;

fun main() = repeat(readln().toInt()) {
  val s = readln()
  var pw = 1
  repeat(s.drop(1).count { it == '?' }) {
    pw = pw * 2 % MOD
  }
  var ans = 0
  if (s[0] == '1' || s[0] == '?') {
    ans = (ans + pw) % MOD
  }
  if (s[0] == '0' || s[0] == '?') {
    val x = if (s.indexOf('0', 1) == -1) 1 else 0 
    ans = (ans + pw - x) % MOD
  }
  println(ans)
}

@file:Suppress("CanBeVal")

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
import kotlin.math.max
import kotlin.math.min

private fun solveTest() {
    val n = readInt()
    val a = readInts(n)
    val c = intarr(n)
    for (x in a) {
        c[x - 1]++
    }
    val res = intarr(n, Int.MAX_VALUE)
    c.sort()
    var j = 0
    for (k in 0..n) {
        while (j < n && c[j] <= k) j++
        var s = 0
        for (i in j..n) {
            val d = k + (n - i)
            if (s < n)
            res[s] = min(res[s], d)
            if (i < n) s += (c[i] - k)
        }
    }
    for (i in 1 .. n - 1) {
        res[i] = min(res[i], res[i - 1])
    }
    println(res)
}

private fun solve() {
    repeat(readInt()) {
        solveTest()
    }
}

// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}

private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}

private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}

private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}

private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

@file:Suppress("CanBeVal")

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
import kotlin.collections.HashMap
import kotlin.math.max
import kotlin.math.min

private fun solveTest() {
    val n = readInt()
    val p = TreeMap<Int, MutableList<Int>>()
    repeat(n) {
        val x = readInt()
        val y = readInt()
        if (!p.containsKey(y)) {
            p[y] = mutableListOf()
        }
        p[y]!!.add(x)
    }
    var lastY = Int.MIN_VALUE
    var lastD = mutableMapOf<Int, Int>()
    var res = 0L
    for (y in p.keys) {
        if (y != lastY + 1) {
            lastD.clear()
        }
        var d = mutableMapOf<Int, Int>()

        val xx = p[y]!!
        xx.sort()

        var lastX = Int.MIN_VALUE
        val st = mutableListOf<Pair<Int, Int>>()
        var sum1 = 0L
        var sum2 = 0L
        for (x in xx) {
            val dd = lastD.getOrDefault(x, 0) + 1
            d[x] = dd

            if (x != lastX + 1) {
                st.clear()
                sum1 = 0
                sum2 = 0
            }

            var c = 1
            while (st.isNotEmpty() && st.last().first > dd) {
                c += st.last().second
                sum1 -= st.last().first * st.last().second
                st.removeLast()
            }
            sum1 += c * dd
            st.add(dd to c)
            sum2++

            res += (sum1 - sum2 - dd + 1) * 4
            res += (sum2 - 1) * 2
            res += (dd - 1) * 2
//            println("" + y + " " + x + " " + dd + " " + sum1 + " " + sum2 + " " + res)
            lastX = x
        }

        lastY = y
        lastD = d
    }
    println(res)
}

private fun solve() {
    repeat(readInt()) {
        solveTest()
    }
}

// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}

private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}

private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}

private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}

private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

@file:Suppress("CanBeVal")

import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.io.PrintWriter
import java.util.*
import kotlin.collections.HashMap
import kotlin.math.max
import kotlin.math.min

private fun solveTest() {
    val n = readInt()
    val m = readInt()
    val g = Array(n) { mutableListOf<Int>() }
    repeat(m) {
        val x = readInt() - 1
        val y = readInt() - 1
        g[x].add(y)
        g[y].add(x)
    }
    val z = intarr(n, 0)
    var a = (0..n - 1).toMutableSet()
    var res = Int.MAX_VALUE

    while (!a.isEmpty()) {
        var v = a.iterator().next()
        a.remove(v)
        z[v] = 1
        var s = mutableSetOf<Int>()
        for (x in g[v]) {
            if (z[x] == 0) s.add(x)
        }
        var k = 0
        while (true) {
            var ok = false
            for (x in a) {
                if (!s.contains(x) && z[x] == 0) {
                    z[x] = 1
                    a.remove(x)
                    var ss = mutableSetOf<Int>()
                    for (y in g[x]) {
                        if (z[y] == 0 && s.contains(y)) {
                            ss.add(y)
                        }
                    }
                    ok = true
                    s = ss
                    k++
                    break
                }
            }
            if (!ok) {
                res = min(res, k)
                break
            }
        }
    }

    if (res == 0) {
        println("" + res + " " + 0)
    } else {
        println("" + res + " " + (n - 1))
    }
}

private fun solve() {
//    repeat(readInt()) {
        solveTest()
//    }
}

// TEMPLATE
fun main(args: Array<String>) {
    reader = BufferedReader(InputStreamReader(System.`in`))
    out = PrintWriter(OutputStreamWriter(System.out))
    solve()
    out.close()
}

private lateinit var out: PrintWriter
private lateinit var reader: BufferedReader
private var tokenizer: StringTokenizer? = null
private fun read(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
        tokenizer = StringTokenizer(readLn())
    }
    return tokenizer!!.nextToken()
}

private fun readInt() = read().toInt()
private fun readLong() = read().toLong()
private fun readLn() = reader.readLine()!!
private fun readInts() = readLn().split(" ").map { it.toInt() }
private fun readInts(sz: Int) = Array(sz) { readInt() }
private fun readLongs() = readLn().split(" ").map { it.toLong() }
private fun readLongs(sz: Int) = Array(sz) { readLong() }
private fun print(b: Boolean) = out.print(b)
private fun print(i: Int) = out.print(i)
private fun print(d: Double) = out.print(d)
private fun print(l: Long) = out.print(l)
private fun print(s: String) = out.print(s)
private fun print(message: Any?) = out.print(message)
private fun print(a: Array<Int>) = a.forEach { print("$it ") }
private fun <T> print(a: Array<out T>) = a.forEach { print("$it ") }
private fun <T> print(a: Collection<T>) = a.forEach { print("$it ") }
private fun println(b: Boolean) = out.println(b)
private fun println(i: Int) = out.println(i)
private fun println(d: Double) = out.println(d)
private fun println(l: Long) = out.println(l)
private fun println(s: String) = out.println(s)
private fun println() = out.println()
private fun println(message: Any?) = out.println(message)
private fun <T> println(a: Array<out T>) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: IntArray) {
    a.forEach { print("$it ") }
    println()
}

private fun println(a: LongArray) {
    a.forEach { print("$it ") }
    println()
}

private fun <T> println(a: Collection<T>) {
    a.forEach { print("$it ") }
    println()
}

private fun intarr(sz: Int, v: Int = 0) = IntArray(sz) { v }
private fun longarr(sz: Int, v: Long = 0) = LongArray(sz) { v }
private fun intarr2d(n: Int, m: Int, v: Int = 0) = Array(n) { intarr(m, v) }
private fun longarr2d(n: Int, m: Int, v: Long = 0) = Array(n) { longarr(m, v) }
private fun <T> init(vararg elements: T) = elements
private fun VI(n: Int = 0, init: Int = 0) = MutableList(n) { init }
private fun VVI(n: Int = 0, m: Int = 0, init: Int = 0) = MutableList(n) { VI(m, init) }
private fun <T1 : Comparable<T1>, T2 : Comparable<T2>> pairCmp(): Comparator<Pair<T1, T2>> {
    return Comparator { a, b ->
        val res = a.first.compareTo(b.first)
        if (res == 0) a.second.compareTo(b.second) else res
    }
}

import kotlin.math.min

const val K = 17
const val N = K * 2
const val MOD = 998244353

fun add(x: Int, y: Int): Int {
    return ((x + y) % MOD + MOD) % MOD
}

fun mul(x: Int, y: Int): Int {
    return (x.toLong() * y % MOD).toInt()
}

fun binpow(x: Int, y: Int): Int {
    var z = 1
    var base = x
    var exponent = y
    while (exponent > 0) {
        if (exponent % 2 == 1) z = mul(z, base)
        base = mul(base, base)
        exponent /= 2
    }
    return z
}

data class State(
    var unpaired: Int = 0,
    var unpairedLess: Int = 0,
    var pairedLess: Int = 0,
    var flag: Int = 0,
    var ways: Int = 0
)

fun comp(a: State, b: State): Boolean {
    if (a.unpaired != b.unpaired) return a.unpaired < b.unpaired
    if (a.unpairedLess != b.unpairedLess) return a.unpairedLess < b.unpairedLess
    if (a.pairedLess != b.pairedLess) return a.pairedLess < b.pairedLess
    return a.flag < b.flag
}

fun fix(v: MutableList<State>) {
    v.sortWith(compareBy(State::unpaired).thenBy { it.unpairedLess }.thenBy { it.pairedLess }.thenBy { it.flag })
    val v2 = mutableListOf<State>()
    for (s in v) {
        if (s.ways == 0) continue
        if (v2.isEmpty() || comp(v2.last(), s)) {
            v2.add(s)
        } else {
            v2.last().ways = add(v2.last().ways, s.ways)
        }
    }
    v.clear()
    v.addAll(v2)
}

val fact = IntArray(N)
val rfact = IntArray(N)
val g = Array(N) { mutableListOf<Int>() }
val dp = Array(N) { mutableListOf<MutableList<State>>() }
var n = 0

fun choose(x: Int, y: Int): Int {
    return mul(fact[x], mul(rfact[y], rfact[x - y]))
}

fun merge2(x: MutableList<State>, y: MutableList<State>): MutableList<State> {
    val res = mutableListOf<State>()
    for (a in x) {
        for (b in y) {
            for (pairLess in 0..min(a.unpairedLess, b.unpairedLess)) {
                for (pairGreater in 0..min(a.unpaired - a.unpairedLess, b.unpaired - b.unpairedLess)) {
                    var numOfChoices = mul(fact[pairLess], fact[pairGreater])
                    numOfChoices = mul(numOfChoices, choose(a.unpairedLess, pairLess))
                    numOfChoices = mul(numOfChoices, choose(a.unpaired - a.unpairedLess, pairGreater))
                    numOfChoices = mul(numOfChoices, choose(b.unpairedLess, pairLess))
                    numOfChoices = mul(numOfChoices, choose(b.unpaired - b.unpairedLess, pairGreater))
                    numOfChoices = mul(numOfChoices, a.ways)
                    numOfChoices = mul(numOfChoices, b.ways)
                    var flag = 0
                    if (a.unpairedLess > 0 || b.unpairedLess > 0) flag = 1
                    if (a.unpairedLess < a.unpaired || b.unpairedLess < b.unpaired) flag = 2
                    res.add(State(a.unpaired + b.unpaired - 2 * pairLess - 2 * pairGreater, a.unpairedLess + b.unpairedLess - pairLess * 2, a.pairedLess + b.pairedLess + pairLess, maxOf(flag, a.flag), numOfChoices))
                }
            }
        }
    }
    fix(res)
    return res
}

fun merge(a: MutableList<MutableList<State>>, b: MutableList<MutableList<State>>): MutableList<MutableList<State>> {
    val res = MutableList(2) { mutableListOf<State>() }
    for (i in 0..1) {
        for (j in 0..1) {
            if (i == 1 && j == 1) continue
            val cur = merge2(a[i], b[j])
            res[i + j].addAll(cur)
        }
    }
    for (i in 0..1) fix(res[i])
    return res
}

fun getDp(s: MutableList<State>, cntLess: Int, flag: Int): Int {
    for (x in s) {
        if (x.unpaired == 0 && x.pairedLess == cntLess && x.flag == flag) return x.ways
    }
    return 0
}

fun forceSpecial(a: MutableList<MutableList<State>>): MutableList<MutableList<State>> {
    val res = MutableList(2) { mutableListOf<State>() }
    for (x in a[0]) {
        when (x.flag) {
            0 -> res[1].add(x)
            1 -> {
                res[0].add(x.copy())
                res[1].add(x.copy())
            }
            else -> res[0].add(x)
        }
    }
    for (x in a[1]) {
        res[1].add(x)
    }
    fix(res[0])
    fix(res[1])
    return res
}

fun dfs(v: Int, p: Int) {
    val children = mutableListOf<Int>()
    for (x in g[v]) {
        if (x != p) {
            dfs(x, v)
            children.add(x)
        }
    }
    if (g[v].size == 1 && v != p) {
        val s1 = State(1, 1, 0, 0, 1)
        val s2 = State(1, 0, 0, 0, 1)
        dp[v] = mutableListOf(mutableListOf(s1, s2), mutableListOf())
        fix(dp[v][0])
        return
    }
    var aux = MutableList(2) { mutableListOf<State>() }
    aux[0].add(State(0, 0, 0, 0, 1))
    for (c in children) {
        aux = merge(aux, dp[c])
    }
    dp[v] = forceSpecial(aux)
}

fun main() {
    val reader = System.`in`.bufferedReader()
    n = reader.readLine().toInt()
    for (i in 0 until n - 1) {
        val (x, y) = reader.readLine().split(" ").map { it.toInt() }
        g[x - 1].add(y - 1)
        g[y - 1].add(x - 1)
    }
    val leaves = mutableListOf<Int>()
    val nonLeaves = mutableListOf<Int>()
    for (i in 0 until n) {
        if (g[i].size == 1) leaves.add(i) else nonLeaves.add(i)
    }
    fact[0] = 1
    for (i in 1..n) fact[i] = mul(fact[i - 1], i)
    for (i in 0..n) rfact[i] = binpow(fact[i], MOD - 2)
    var ans = 0
    if (leaves.size % 2 == 0) {
        val root = nonLeaves[0]
        dfs(root, root)
        ans = mul(fact[leaves.size / 2], getDp(dp[root][0], 0, 2))
        println("${leaves.size / 2} $ans")
    } else {
        print("${(leaves.size + 1) / 2} ")
        for (x in leaves) {
            dfs(x, x)
            for (j in 0..leaves.size / 2) {
                val cur = getDp(dp[x][1], j, 0)
                ans = add(ans, mul(cur, mul(fact[j], fact[leaves.size / 2 - j])))
            }
        }
        println(ans)
    }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int a, x, y;
    cin >> a >> x >> y;
    cout << ((a < x) == (a < y) ? "YES" : "NO") << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	for (int i = 1; i < n; i++) {
		if (abs(a[i - 1] - a[i]) <= 1) {
			cout << 0 << endl;
			return;
		}
	}
	for (int i = 1; i + 1 < n; i++) {
		if (a[i - 1] < a[i] && a[i] > a[i + 1]) {
			cout << 1 << endl;
			return;
		}
		if (a[i - 1] > a[i] && a[i] < a[i + 1]) {
			cout << 1 << endl;
			return;
		}
	}
	cout << -1 << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        int x = max(a[n - 1], 2 * a[i]) - a[i] - a[j];
        int k = upper_bound(a.begin(), a.begin() + j, x) - a.begin();
        ans += j - k;
      }
    }
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

const int N = int(2e5) + 5;

int n;
vector<int> g[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	fore (i, 0, n)
		g[i].clear();
	
	fore (i, 0, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

vector<int> used;
vector<pair<int, int>> ans;

void dfs(int v, bool in) {
	used[v] = 1;
	for (int to : g[v]) {
		if (used[to])
			continue;
		if (in)
			ans.emplace_back(to, v);
		else
			ans.emplace_back(v, to);
		dfs(to, !in);
	}
}

inline void solve() {
	int r = 0;
	while (r < n && sz(g[r]) != 2)
		r++;
	if (r >= n) {
		cout << "NO\n";
		return;
	}

	used.assign(n, 0);
	ans.clear();

	ans.emplace_back(r, g[r][0]);
	ans.emplace_back(g[r][1], r);
	used[r] = 1;

	dfs(g[r][0], true);
	dfs(g[r][1], false);

	cout << "YES\n";
	sort(ans.begin(), ans.end());
	for (auto [u, v] : ans)
		cout << u + 1 << " " << v + 1 << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while (t--)  {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

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

const int M = 5e5;
const int INF = 1e9;

int main() {
  vector<int> dp(M + 1, INF);
  dp[1] = 1;
  for (int m = 2; m <= M; ++m) {
    for (int i = 1; i * i <= m; ++i) {
      if (m % i != 0) continue;
      if (m / i > 2) dp[m] = min(dp[m], dp[i] + dp[m / i - 2]);
      if (i > 2) dp[m] = min(dp[m], dp[m / i] + dp[i - 2]);
    }
  }
  
  int q;
  cin >> q;
  while (q--) {
    int m;
    cin >> m;
    cout << (dp[m] == INF ? -1 : dp[m]) << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 500043;

vector<int> divisors[N];

int dp[N], dp2[N];

int calc(int x);

int calc2(int x)
{
    if(dp2[x] != -1) return dp2[x];
    if(x == 1) return dp2[x] = 0;
    dp2[x] = calc(x);
    for(auto y : divisors[x]) dp2[x] = min(dp2[x], calc(y) + calc2(x / y));
    return dp2[x];
}

int calc(int x)
{
    if(dp[x] != -1) return dp[x];
    if(x == 1) return dp[x] = 0;
    if(x == 3) return dp[x] = 1;
    return dp[x] = calc2(x - 2) + 1;
}                       

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i = 2; i < N; i++)
        for(int j = i * 2; j < N; j += i)
            divisors[j].push_back(i);
    for(int i = 0; i < N; i++) dp[i] = dp2[i] = -1;

    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int x;
        cin >> x;
        if(x % 2 == 0) cout << -1 << endl;
        else cout << calc(x + 2) << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 543;
const long long INF64 = (long long)(1e18);

long long e[N][N];
long long d[N][N];
int n, m;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j) e[i][j] = INF64;
    for(int i = 0; i < m; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        --x;
        --y;
        swap(x, y);
        e[x][y] = min(e[x][y], (long long)w);
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            d[i][j] = e[i][j];
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        long long op;
        cin >> op;
        vector<long long> a(n);
        for(int j = 0; j < n; j++) cin >> a[j];
        vector<long long> min_dist = a;
        vector<long long> min_one_edge = a;
        for(int j = 0; j < n; j++)
            for(int k = 0; k < n; k++)
            {
                min_dist[k] = min(min_dist[k], a[j] + d[j][k]);
                min_one_edge[k] = min(min_one_edge[k], a[j] + e[j][k]);
            }
        vector<long long> min_op(n, INF64);
        for(int j = 0; j < n; j++)
            for(int k = 0; k < n; k++)
            {
                if(d[j][k] < e[j][k]) min_op[k] = min(min_op[k], (d[j][k] + a[j]) - (min_one_edge[k] - 1));
            }               
        for(int j = 0; j < n; j++)
        {
            if(min_op[j] <= op) cout << 1;
            else cout << 0;
        }
        cout << endl;
    }
    
    return 0;
}

One day before the contest, shnirelman completely destroyed problem H in less than 15 minutes. Thankfully, I had an idea of a replacement problem.

const val chars = "01ABab"

fun main() = repeat(readln().toInt()) {
  val a = readln().split(" ").map { it.toInt() }
  println(a.mapIndexed { i, x -> 
    CharArray (x) { j -> chars[i * 2 + j % 2] }
  }.flatMap { it.asIterable() }.joinToString(""))
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt() * 2
  val a = readln().split(" ").map { it.toInt() }.sorted()
  println(if ((1 until n - 1 step 2).any { i ->
    a[i + 1] - a[i] < maxOf(a[i] - a[i - 1], a[i + 2] - a[i + 1])
  }) "NO" else "YES")
}

const val coins = "BSG"

fun main() {
  val s = readln()
  val sum = Array(3) { 
    s.map { c -> if (c == coins[it]) 1 else 0 }
     .scan(0) { x, y -> x + y }
  }
  
  val q = readln().toInt()
  println((0 until q).map {
    val (l, r) = readln().split(" ").map { it.toInt() }
    val cnt = sum.map { it[r] - it[l - 1] }
    cnt.max() + cnt.min()
  }.joinToString("\n"))
}

import kotlin.system.exitProcess

fun main() {
    val (nString, h) = readln().split(" ")

    fun ask(pos: Int): String {
        println("? ${pos + 1}")
        System.out.flush()
        val resp = readln()
        if (resp == "-1")
            exitProcess(0)
        return resp
    }

    fun isLower(s: String) = s[0].isLowerCase()

    val lowerCaseFirst = isLower(ask(0))
    fun lowerOrEqual(a: String, b: String) : Boolean {
        if (isLower(a) == isLower(b))
            return a <= b;
        return isLower(a) == lowerCaseFirst
    }
    var l = 0
    var r = nString.toInt()
    while (r - l > 1) {
        val mid = (l + r) / 2
        if (lowerOrEqual(ask(mid), h))
            l = mid
        else
            r = mid
    }
    println("! ${l + 1}")
}

fun main() = repeat(readLine()!!.toInt()) {
    val n = readLine()!!.toInt()
    var s = readLine()!!
    var a = readLine()!!.split(" ").map { it.toInt() }
    
    var ans = 0.toLong()
    
    repeat(2) {
        var sum = 0.toLong()
        for (i in 0 until n) {
            if (s[i] == '<')
                ans = maxOf(ans, sum + a[i])
            sum += maxOf(a[i], 0)
        }
        a = a.reversed()
        s = s.reversed().replace('<', '.').replace('>', '<').replace('.', '>')
    }
    
    println(ans)
}

const val N = 505
const val INF = 1e9.toInt()

fun main() {
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() - 1}
  val b = readln().split(" ").map { it.toInt() - 1}
  
  val cnt = Array(N) { IntArray(N) { 0 } }
  val dp = Array(2) { Array(N) { IntArray(N) { INF } } }
  dp[0][0][0] = 0

  for (t in 0 until 2 * n) {
    val ct = t and 1
    val nt = ct xor 1
    
    if (t < n) {
      for (i in 0 until N) for (j in 0 until N) {
        if (a[t] <= i || b[t] <= j) ++cnt[i][j];
      } 
    }

    dp[nt].forEach { it.fill(INF) }
    for (i in 0 until N) for (j in 0 until N) {
      if (dp[ct][i][j] != INF) {
        val lft = minOf(t + 1, n) - i - j
        if (cnt[i][j] > i + j) {
          dp[nt][i + 1][j] = minOf(dp[nt][i + 1][j], dp[ct][i][j] + lft - 1)
          dp[nt][i][j + 1] = minOf(dp[nt][i][j + 1], dp[ct][i][j] + lft - 1)
        } else {
          if (t < n || lft == 0) dp[nt][i][j] = minOf(dp[nt][i][j], dp[ct][i][j] + lft)
        }
      }
    }
  }

  var ans = INF
  for (i in 0 until N) for (j in 0 until N) ans = minOf(ans, dp[0][i][j])
  if (ans == INF) ans = -1
  println(ans)
}

fun main() {
    data class ModInt(val value : Int = 0) {
        val MOD = 998244353
        operator fun plus(oth : ModInt) : ModInt {
            val cur = (this.value + oth.value) % MOD
            return ModInt(cur)
        }
        operator fun times(oth : ModInt) : ModInt {
            val cur = value.toLong() * oth.value % MOD
            return ModInt(cur.toInt())
        }
        fun pow(k: Int) : ModInt {
            var ans = ModInt(1)
            var a = ModInt(value)
            var curPw = k
            while (curPw > 0) {
                if (curPw % 2 == 1)
                    ans *= a
                a *= a
                curPw /= 2
            }
            return ans
        }
        fun inverse() = this.pow(MOD - 2)
        override fun toString() = this.value.toString()
    }

    val n = readln().toInt()
    val a = readln().split(" ").map { it.toInt() }

    val factorials = (1..n).runningFold(ModInt(1)) { acc, it -> acc * ModInt(it) }
    val invFact = factorials.map { it.inverse() }

    fun choose(n : Int, k : Int) : ModInt {
        if (k < 0 || n < k)
            return ModInt(0)
        return factorials[n] * invFact[k] * invFact[n - k]
    }

    val sum = a.sumOf { it.toLong() }
    val delta = List(n) { n - it - 1 - a[it] }.sortedDescending()

    var ansVal = sum
    var ansCnt = ModInt(1)

    var curSum = 0L
    var lf = 0
    var rg = 0
    for (k in 1..n) {
        curSum += delta[k - 1]
        while (delta[lf] > delta[k - 1])
            lf++
        while (rg < delta.size && delta[rg] >= delta[k - 1])
            rg++
        val curVal = sum + curSum - k.toLong() * (k - 1) / 2
        val curCnt = choose(rg - lf, k - lf)
        if (ansVal < curVal) {
            ansVal = curVal
            ansCnt = ModInt(0)
        }
        if (ansVal == curVal) {
            ansCnt += curCnt
        }
    }
    println("$ansVal $ansCnt")
}

import java.util.*

data class Node(var x: Int = 0, var a: Int = 0, var b: Int = 0)

fun get(n: Node, x: Int): Int {
    return when {
        n.x == -1 -> x
        x < n.x -> n.a
        else -> n.b
    }
}

fun combine(a: Node, b: Node): Node {
    return when {
        a.x == -1 -> b
        b.x == -1 -> a
        else -> Node(a.x, get(b, a.a), get(b, a.b))
    }
}

fun emptyNode(): Node {
    return Node(-1, -1, -1)
}

fun fromLength(len: Int): Node {
    return if (len == -1) emptyNode() else Node(len, len, len - 1)
}

const val N = 300003
const val M = 300001

val S = sortedSetOf<Int>()
val T = Array<Node>(4 * N) { emptyNode() }

fun recalc(v: Int) {
    T[v] = combine(T[v * 2 + 1], T[v * 2 + 2])
}

fun build(v: Int, l: Int, r: Int) {
    if (l == r - 1) {
        T[v] = emptyNode()
    } else {
        val m = (l + r) / 2
        build(v * 2 + 1, l, m)
        build(v * 2 + 2, m, r)
        recalc(v)
    }
}

fun upd(v: Int, l: Int, r: Int, pos: Int, x: Int) {
    if (l == r - 1) {
        T[v] = fromLength(x)
    } else {
        val m = (l + r) / 2
        if (pos < m) upd(v * 2 + 1, l, m, pos, x)
        else upd(v * 2 + 2, m, r, pos, x)
        recalc(v)
    }
}

fun get(v: Int, l: Int, r: Int, L: Int, R: Int): Node {
    if (L >= R) return emptyNode()
    if (L == l && R == r) return T[v]
    val m = (l + r) / 2
    return combine(get(v * 2 + 1, l, m, L, minOf(m, R)), get(v * 2 + 2, m, r, maxOf(L, m), R))
}

fun prepare() {
    build(0, 0, M)
    upd(0, 0, M, 0, 0)
    S.add(0)
}

fun insertValue(x: Int) {
    val it = S.ceiling(x)
    if (it != null) {
        upd(0, 0, M, it, it - x)
    }
    S.lower(x)?.let { upd(0, 0, M, x, x - it) }
    S.add(x)
}

fun eraseValue(x: Int) {
    upd(0, 0, M, x, -1)
    S.remove(x)
    val it = S.ceiling(x)
    if (it != null) {
        val y = it
        S.lower(y)?.let { upd(0, 0, M, y, y - it) }
    }
}

fun getGrundy(x: Int): Int {
    val n = get(0, 0, M, 0, x)
    val it = S.lower(x)
    val y = it ?: return x
    val valY = get(n, 0)
    val dist = x - y
    return if (dist <= valY) dist - 1 else dist
}

fun main() {
    val q = readln().toInt()
    
    prepare()
    println((0 until q).map {
        val params = readln().split(" ").map { it.toInt() }
        val (t, x) = params.take(2)
        if (t == 1) {
            if (S.contains(x)) eraseValue(x) else insertValue(x)
            null
        } else {
            val res = params.drop(2).fold(0) { r, y -> r xor getGrundy(y) }
            if (res == 0) "Second" else "First"
        }
    }.filterNotNull().joinToString("\n"))
}

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val x = IntArray(m)
    val y = IntArray(m)
    val edgeId = mutableMapOf<Pair<Int, Int>, Int>()
    val inDeg = IntArray(n)
    val outDeg = IntArray(n)

    for (i in 0 until m) {
        val (xi, yi) = readLine()!!.split(" ").map { it.toInt() }
        x[i] = xi - 1
        y[i] = yi - 1
        edgeId[Pair(x[i], y[i])] = i
        inDeg[y[i]]++
        outDeg[x[i]]++
    }

    var c = 0
    for (i in 0 until n) {
        c = maxOf(c, inDeg[i], outDeg[i])
    }

    val color = Array(n * 2) { IntArray(c) { -1 } }
    for (i in 0 until m) {
        val a = x[i]
        val b = y[i] + n
        var ca = 0
        while (color[a][ca] != -1) ca++
        var cb = 0
        while (color[b][cb] != -1) cb++
        color[a][ca] = b
        color[b][cb] = a
        if (ca != cb) {
            var cur = b
            while (cur != -1) {
                val temp = color[cur][cb]
                color[cur][cb] = color[cur][ca]
                color[cur][ca] = temp
                cur = color[cur][cb]
                val tempCa = ca
                ca = cb
                cb = tempCa
            }
        }
    }

    val ans = MutableList(m) { 0 }
    for (i in 0 until n) {
        for (j in 0 until c) {
            if (color[i][j] != -1) {
                ans[edgeId[Pair(i, color[i][j] - n)]!!] = j
            }
        }
    }

    val xsAdd = mutableListOf<Int>()
    val ysAdd = mutableListOf<Int>()
    var k = 0
    for (i in 0 until c) {
        val nxt = IntArray(n) { -1 }
        val pre = IntArray(n) { -1 }
        for (j in 0 until m) {
            if (ans[j] == i) {
                nxt[x[j]] = y[j]
                pre[y[j]] = x[j]
            }
        }
        val parts = mutableListOf<Pair<Int, Int>>()
        for (j in 0 until n) {
            if (pre[j] == -1) {
                var l = j
                var r = j
                while (nxt[r] != -1) r = nxt[r]
                parts.add(Pair(l, r))
            }
        }
        val p = parts.size
        k += p
        for (j in 0 until p) {
            xsAdd.add(parts[j].second)
            ysAdd.add(parts[(j + 1) % p].first)
        }
        for (j in 0 until p) {
            ans += i
        }
    }

    println(k)
    for (i in 0 until k) {
        println("$$${xsAdd[i] + 1} $$${ysAdd[i] + 1}")
    }
    println(c)
    for (x in ans) {
        print("${x + 1} ")
    }
    println()
}

If $$$k=1$$$, there is only one "starting" element. So, the last element you paint must be on the border (the $$$1$$$-st or the $$$n$$$-th element of the array).

If $$$k \gt 1$$$, the greedy solution actually works since any element between two elements which were initially chosen can be the last element. So, out of $$$(k+1)$$$ maximums, you can initially paint them all blue, except for the middle of them. But if $$$k=1$$$, you need another solution.

t = int(input())
for i in range(t):
    n = int(input())
    s = list(input().split())
    s = "".join(s)
    if "101" in s:
        print('NO')
    else:
        print('YES')

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    hasColor = [0] * (n * m)
    hasBad = [0] * (n * m)
    for i in range(n):
        for j in range(m):
            hasColor[a[i][j] - 1] = 1
            if i + 1 < n and a[i][j] == a[i + 1][j]:
                hasBad[a[i][j] - 1] = 1
            if j + 1 < m and a[i][j] == a[i][j + 1]:
                hasBad[a[i][j] - 1] = 1
    print(sum(hasColor) + sum(hasBad) - 1 - max(hasBad))

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

const int MOD = 998244353;

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> dp(4, 0);
    dp[0] = 1;
    while (n--) {
      int x;
      cin >> x;
      if (x == 2) dp[x] = add(dp[x], dp[x]);
      dp[x] = add(dp[x], dp[x - 1]);
    }
    cout << dp[3] << '\n';
  }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int n = s.size();
    int i = 0;
    while (i < n / 2 && s[i] == s[n - i - 1]) ++i;
    n -= 2 * i;
    s = s.substr(i, n);
    int ans = n;
    for (int z = 0; z < 2; ++z) {
      int l = 0, r = n;
      while (l <= r) {
        int m = (l + r) / 2;
        vector<int> cnt(26);
        for (int i = 0; i < m; ++i)
          cnt[s[i] - 'a']++;
        bool ok = true;
        for (int i = 0; i < min(n / 2, n - m); ++i) {
          char c = s[n - i - 1];
          if (i < m) {
            ok &= cnt[c - 'a'] > 0;
            cnt[c - 'a']--;
          } else {
            ok &= (c == s[i]);
          }
        }
        for (auto x : cnt)
          ok &= (x % 2 == 0);
        if (ok) {
          r = m - 1;
        } else {
          l = m + 1;
        }
      }
      ans = min(ans, r + 1); 
      reverse(s.begin(), s.end());
    }
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}

const int INF = int(1e9);
const li INF64 = li(1e18);

string s;
int a, b, ab, ba;

inline bool read() {
	if(!(cin >> s))
		return false;
	cin >> a >> b >> ab >> ba;
	return true;
}

int process(vector<int> &rem, int &tot) {
	int placed = 0;
	sort(rem.begin(), rem.end(), greater<int>());
	while (!rem.empty() && tot > 0) {
		int cnt = min(rem.back() / 2, tot);
		placed += cnt;
		tot -= cnt;
		rem.back() -= 2 * cnt;
		if (rem.back() == 0)
			rem.pop_back();
	}
	return placed;
}

int remnants(vector<int> &rem, int &tot) {
	int placed = 0;
	for (int &cur : rem) {
		int cnt = min(tot, (cur - 2) / 2);
		placed += cnt;
		tot -= cnt;
		cur -= 2 * cnt + 2;
	}
	return placed;
}

inline void solve() {
	s.push_back(s.back());
	int eq = 0, placedPairs = 0;
	vector<int> remAB, remBA;

	int lst = 0;
//	cerr << "s = " << s << endl;
	fore (i, 1, sz(s)) {
		if (s[i] != s[i - 1])
			continue;
		
		if (s[lst] == s[i - 1]) {
			// ABA..A or BAB..B
			eq += (i - lst) / 2;
		}
		else {
			int len = i - lst;
			if (s[lst] == 'A') {
				// ABA..B
				remAB.push_back(len);
			}
			else {
				// BAB..A
				remBA.push_back(len);
			}
		}
//		cerr << lst << ", " << i << endl;
		lst = i;
	}
	s.pop_back();
	
	placedPairs += process(remAB, ab);
	assert(remAB.empty() || ab == 0);

	placedPairs += process(remBA, ba);
	assert(remBA.empty() || ba == 0);

	placedPairs += remnants(remAB, ba);
	placedPairs += remnants(remBA, ab);

	int remPlaced = min(eq, ab + ba);
	placedPairs += remPlaced;

	int needA = count(s.begin(), s.end(), 'A') - placedPairs;
	int needB = count(s.begin(), s.end(), 'B') - placedPairs;

	if (needA <= a && needB <= b)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;             

const int N = 400043;
const int BUF = N * 20;

int* where[BUF];
int val[BUF];
int cur = 0;

void change(int& x, int y)
{
    val[cur] = x;
    where[cur] = &x;
    x = y;
    cur++;
}

void rollback()
{
    cur--;
    (*where[cur]) = val[cur];
}

struct DSU
{
    vector<int> p, s;
    int n;
    int comps;

    int get(int x)
    {
        if(p[x] == x) return x;
        return get(p[x]);
    }

    void merge(int x, int y)
    {
        x = get(x);
        y = get(y);
        if(x == y) return;
        change(comps, comps - 1);
        if(s[x] < s[y]) swap(x, y);
        change(p[y], x);
        change(s[x], s[x] + s[y]);    
    }

    DSU(int n = 0)
    {
        this->n = n;
        s = vector<int>(n, 1);
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        comps = n;
    }
};

struct edge
{
    char g;
    int x;
    int y;
    edge(char g = 'A', int x = 0, int y = 0) : g(g), x(x), y(y) {};
};

DSU A, united;
vector<edge> T[4 * N];
int ans[N];

void dfs(int v, int l, int r)
{
    int state = cur;
    for(auto e : T[v])
    {
        united.merge(e.x, e.y);
        if(e.g == 'A') A.merge(e.x, e.y);   
    }
    if(l == r - 1)
    {
        ans[l] = A.comps - united.comps;
    }
    else
    {
        int m = (l + r) / 2;
        dfs(v * 2 + 1, l, m);
        dfs(v * 2 + 2, m, r);
    }
    while(state != cur) rollback();
}

void add_edge(int v, int l, int r, int L, int R, edge e)
{
    if(L >= R) return;
    if(L == l && R == r) T[v].push_back(e);
    else
    {
        int m = (l + r) / 2;
        add_edge(v * 2 + 1, l, m, L, min(m, R), e);
        add_edge(v * 2 + 2, m, r, max(L, m), R, e);
    }
}

map<pair<int, int>, int> last[2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    A = DSU(n);
    united = DSU(n);
    for(int i = 0; i < q; i++)
    {
        string s;
        int x, y;
        cin >> s >> x >> y;
        --x;
        --y;
        int idx = (s[0] == 'A' ? 0 : 1);
        if(x > y) swap(x, y);
        if(last[idx].count(make_pair(x, y)) == 0)
        {
            last[idx][make_pair(x, y)] = i;
        }
        else
        {
            add_edge(0, 0, q, last[idx][make_pair(x, y)], i, edge(s[0], x, y));
            last[idx].erase(make_pair(x, y));
        }
    }
    for(int i = 0; i < 2; i++)
        for(auto a : last[i])
            add_edge(0, 0, q, a.second, q, edge(char(i + 'A'), a.first.first, a.first.second));
    dfs(0, 0, q);
    for(int i = 0; i < q; i++)
        cout << ans[i] << "\n";
}

#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 (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = a[n - 1];
    for (int i = 0; i < n - 1; ++i)
      ans += max(0, a[i] - b[i + 1]);
    cout << ans << '\n';
  }
}

t = int(input())
for i in range(t):
    n, a, b, c = map(int, input().split())
    sum = a + b + c
    d = n // sum * 3
    if n % sum == 0:
        print(d)
    elif n % sum <= a:
        print(d + 1)
    elif n % sum <= a + b:
        print(d + 2)
    else:
        print(d + 3)

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    q = list(map(int, input().split()))
    used = [False for i in range(n + 1)]
    for i in q:
        used[i] = True
    l = len(q)
    for i in range(m):
        if l == n or (l == n-1 and not used[a[i]]):
            print(1, end='')
        else:
            print(0, end='')
    print()

def calcLessThanX(a, x):
    n = len(a)
    s = sum(a)
    j = 0
    ans = 0

    for i in range(n-1, -1, -1):
        while j < n and s - a[i] - a[j] >= x:
            j += 1
        ans += (n - j)

    for i in range(n):
        if s - a[i] - a[i] < x:
            ans -= 1
    
    return ans // 2

for _ in range(int(input())):
    n, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    
    a = sorted(a)
    print(calcLessThanX(a, y+1) - calcLessThanX(a, x))

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

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    vector<pair<int, int>> ev;
    for (int i = 0; i < n; ++i) {
      ev.emplace_back(a[i], 1);
      ev.emplace_back(b[i], 2);
    }
    sort(ev.begin(), ev.end());
    long long ans = 0;
    int cnt = n, bad = 0;
    for (int i = 0; i < 2 * n;) {
      auto [x, y] = ev[i];
      if (bad <= k) ans = max(ans, x * 1LL * cnt);
      while (i < 2 * n && ev[i].first == x) {
        bad += (ev[i].second == 1);
        bad -= (ev[i].second == 2);
        cnt -= (ev[i].second == 2);
        ++i;
      }
    }
    cout << ans << '\n';
  }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> segs({{1, -q}, {m, m}, {n + q + 1, n}});
    while (q--) {
      int x;
      cin >> x;
      bool ins = false;
      for (auto& [l, r] : segs) {
        if (x < l) l = max(1, l - 1);
        else if (x > r) r = min(n, r + 1);
        else {
          ins = true;
          if (l == r) l = n + q, r = -q;
        }
      }
      if (ins) {
        segs[0] = {1, max(segs[0].second, 1)};
        segs[2] = {min(segs[2].first, n), n};
      }
      int lf = 0, rg = -1, ans = 0;
      for (auto [l, r] : segs) {
        if (l > r) continue;
        if (l > rg) {
          ans += max(0, rg - lf + 1);
          lf = l; rg = r;
        }
        rg = max(rg, r);
      }
      ans += max(0, rg - lf + 1);
      cout << ans << ' ';
     }
     cout << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

const int INF = int(1e9);

int n, q;
vector<int> id, ch;

bool read() {
    if (!(cin >> n >> q))
        return false;
    id.resize(q);
    ch.resize(q);
    fore (i, 0, q) {
        char c;
        cin >> id[i] >> c;
        id[i]--;
        ch[i] = c == '+' ? 1 : -1;
    }
    return true;
}

int getDist(int s, int t) {
    int pSum = 0, cMin = 0;
    fore (e, 0, q) {
        if (id[e] == t)
            pSum += ch[e] < 0;
        if (id[e] == s)
            pSum -= ch[e] > 0;
        cMin = min(cMin, pSum);
    }
    return -cMin + 1;
}

inline void solve() {
    vector<vector<int>> minDist(n, vector<int>(n, INF));

    fore (i, 0, n) fore (j, 0, n)
        minDist[i][j] = getDist(i, j);

    vector<int> len(n, 0);
    fore (e, 0, q)
        len[id[e]] += ch[e] > 0;
    
    vector< vector<int> > d(1 << n, vector<int>(n, INF));
    fore (i, 0, n)
        d[1 << i][i] = 1;
    
    fore (mask, 1, 1 << n) fore (lst, 0, n) {
        if (d[mask][lst] == INF)
            continue;
        fore (nxt, 0, n) {
            if ((mask >> nxt) & 1)
                continue;
            int nmask = mask | (1 << nxt);
            d[nmask][nxt] = min(d[nmask][nxt], d[mask][lst] + minDist[lst][nxt]);
        }
    }
    int ans = INF;
    fore (lst, 0, n)
        ans = min(ans, d[(1 << n) - 1][lst] + len[lst]);
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);

    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    int sum = 0;
    for (auto& x : a) {
      if (sum + x <= k) sum += x;
      else break;
    }
    cout << k - sum << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        vector<int> c(n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &c[i]);
            --c[i];
        }
        vector<int> cnt(n);
        for(auto x : c) cnt[x]++;
        int exactly1 = 0, morethan1 = 0;
        for(auto x : cnt)
            if (x == 1)
                exactly1++;
            else if(x > 1)
                morethan1++;
        printf("%d\n", morethan1 + (exactly1 + 1) / 2 * 2);
    }
}

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> vals;
    int sum = 0;
    for (int i = n - 1; i > 0; --i) {
      sum += (s[i] == '1' ? 1 : -1);
      if (sum > 0) vals.push_back(sum);
    }
    sort(vals.begin(), vals.end());
    int ans = 1;
    while (k > 0 && !vals.empty()) {
      k -= vals.back();
      vals.pop_back();
      ++ans;
    }
    cout << (k > 0 ? -1 : ans) << '\n';
  }
}

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

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

struct Seg {
	int l, r;

	bool operator< (const Seg &oth) const {
		if (l != oth.l)
			return l < oth.l;
		return r < oth.r;
	};
};

void solve() {
	int n;
	cin >> n;
	vector<Seg> seg(n);
	for (int i = 0; i < n; i++)
		cin >> seg[i].l >> seg[i].r;
	
	vector<int> ans(n, 0);
	for (int k = 0; k < 2; k++) {
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);

		sort(ord.begin(), ord.end(), [&seg](int i, int j){
			if (seg[i].l != seg[j].l)
				return seg[i].l < seg[j].l;
			return seg[i].r > seg[j].r;
		});

		set<int> bounds;
		for (int i : ord) {
			auto it = bounds.lower_bound(seg[i].r);
			if (it != bounds.end())
				ans[i] += *it - seg[i].r;
			bounds.insert(seg[i].r);
		}

		for (auto &s : seg) {
			s.l = -s.l;
			s.r = -s.r;
			swap(s.l, s.r);
		}
	}

	map<Seg, int> cnt;
	for (auto s: seg)
		cnt[s]++;
	for (int i = 0; i < n; i++)
		if (cnt[seg[i]] > 1)
			ans[i] = 0;
	
	for (int a : ans)
		cout << a << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int t; cin >> t;
	while (t--)
		solve();
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
vector<vector<int>> g;
 
struct LCA {
	vector<vector<pair<int, int>>> st;
	vector<int> pw;
 
	void build(vector<pair<int, int>> a) {
		int n = a.size();
		int lg = 32 - __builtin_clz(n);
		st.resize(lg, vector<pair<int, int>>(n));
		st[0] = a;
		for (int j = 1; j < lg; ++j) {
			for (int i = 0; i < n; ++i) {
				st[j][i] = st[j - 1][i];
				if (i + (1 << (j - 1)) < n)
					st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
			}
		}
		pw.resize(n + 1);
		for (int i = 2; i <= n; ++i)
			pw[i] = pw[i / 2] + 1;
	}
 
	vector<int> d, fst, par;
	vector<pair<int, int>> ord;
 
	int lca(int v, int u) {
		int l = fst[v], r = fst[u];
		if (l > r) swap(l, r);
		++r;
		int len = pw[r - l];
		assert(len < int(st.size()));
		return min(st[len][l], st[len][r - (1 << len)]).second;
	}
 
	void init(int v, int p = -1) {
		if (fst[v] == -1) fst[v] = ord.size();
		ord.push_back({ d[v], v });
		for (int u : g[v]) if (u != p) {
			par[u] = v;
			d[u] = d[v] + 1;
			init(u, v);
			ord.push_back({ d[v], v });
		}
	}
 
	LCA(int r = 0) {
		int n = g.size();
		d.resize(n);
		fst.assign(n, -1);
		par.assign(n, -1);
		ord.clear();
		init(r);
 
		build(ord);
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(2 * n);
	forn(i, 2 * n){
		cin >> a[i];
		--a[i];
	}
	g.resize(2 * n);
	forn(i, 2 * n - 1){
		int v, u;
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	vector<int> l(n, -1), r(n, -1);
	forn(i, 2 * n){
		if (l[a[i]] == -1) l[a[i]] = i;
		else r[a[i]] = i;
	}
	vector<char> res(2 * n, 1);
	forn(rt, 2 * n) if (a[rt] == 0){
		LCA d(rt);
		vector<int> state(2 * n, 0);
		
		auto mark = [&](int v){
			while (v != -1 && state[v] != 1){
                state[v] = 1;
				v = d.par[v];
			}
		};
		auto markdel = [&](int v){
			queue<int> q;
			q.push(v);
			state[v] = -1;
			while (!q.empty()){
				int v = q.front();
				q.pop();
				mark(l[a[v]] ^ r[a[v]] ^ v);
				for (int u : g[v]) if (u != d.par[v] && state[u] == 0){
					state[u] = -1;
					q.push(u);
				}
			}
		};
		
		forn(i, n) mark(d.lca(l[i], r[i]));
		for (int i = 2 * n - 1; i >= 0; --i) if (state[i] == 0)
			markdel(i);
		vector<char> cur(2 * n, 0);
        for (int i = 0; i < 2 * n; ++i) if (state[i] == 1)
            cur[i] = 1;
        reverse(cur.begin(), cur.end());
		res = min(res, cur);
	}
	reverse(res.begin(), res.end());
	cout << count(res.begin(), res.end(), 1) << '\n';
	forn(i, 2 * n) if (res[i])
		cout << i + 1 << " ";
	cout << '\n';
	return 0;
}

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int N = 200 * 1000 + 13;
const int K = 5;

using li = long long;
using mat = array<array<li, K>, K>;

const li INF = 1e18;

int n, q;
li a[N], b[N];
mat t[4 * N];

mat init(li a, li b) {
  mat c;
  forn(i, K) forn(j, i + 1) c[j][i] = -INF;
  c[0][0] = c[2][2] = c[4][4] = 0;
  c[0][1] = c[2][3] = a + b;
  c[0][2] = c[2][4] = a + b + b;
  c[1][1] = c[3][3] = a;
  c[1][2] = c[3][4] = a + b;
  return c;
}

mat combine(mat a, mat b) {
  mat c = init(-INF, -INF);
  forn(i, K) forn(j, i + 1) forn(k, j + 1)
    c[k][i] = max(c[k][i], a[k][j] + b[j][i]);
  return c;
}

void build(int v, int l, int r) {
  if (l + 1 == r) {
    t[v] = init(a[l], b[l]);
    return;
  }
  int m = (l + r) / 2;
  build(v * 2 + 1, l, m);
  build(v * 2 + 2, m, r);
  t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int v, int l, int r, int p) {
  if (l + 1 == r) {
    t[v] = init(a[l], b[l]);
    return;
  }
  int m = (l + r) / 2;
  if (p < m) upd(v * 2 + 1, l, m, p);
  else upd(v * 2 + 2, m, r, p);
  t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}

mat get(int v, int l, int r, int L, int R) {
  if (L >= R) return init(-INF, -INF);
  if (l == L && r == R) return t[v];
  int m = (l + r) / 2;
  return combine(
    get(v * 2 + 1, l, m, L, min(m, R)),
    get(v * 2 + 2, m, r, max(m, L), R)
  );
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  forn(i, n) cin >> a[i];
  forn(i, n) cin >> b[i];
  build(0, 0, n);
  cin >> q;
  forn(_, q) {
    int t, x, y;
    cin >> t >> x >> y;
    --x;
    if (t == 1) {
      a[x] = y;
      upd(0, 0, n, x);
    } else if (t == 2) {
      b[x] = y;
      upd(0, 0, n, x);
    } else {
      auto res = get(0, 0, n, x, y);
      cout << res[0][4] << '\n';
    }
  }
}

fun main() = repeat(readln().toInt()) {
  readln().toInt()
  val a = readln().split(" ").map { it.toInt() }
  println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous")
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt()
  println((listOf(1) + (n downTo 2)).joinToString(" "))
}

fun main() = repeat(readln().toInt()) {
  val a = readln().split("+")
  val ans = a.foldIndexed(0L) { i, res, s ->
    res + if (i == 0 || i == a.size - 1)
      s.toLong()
    else 
      (1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() }
  }
  println(ans)
}

fun main() {
    repeat(readln().toInt()) {
        val (n, h, b) = readln().split(' ').map { it.toLong() }
        val grid = Array(2) { readln() }
        val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!!
        val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } }
        val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } }

        val ans = minOf(
            (wolvesLeft + wolvesRight) * h,
            wolvesLeft * h + 2 * b,
            wolvesRight * h + 2 * b,
            3 * b
        )
        println(ans)
    }
}

const val INF = 1e9.toInt()
const val vars = "RPS"

fun main() = repeat(readln().toInt()) {  
  val a = readln().map { vars.indexOf(it) }
  
  fun calc(a : List<Int>) : Int {
    if (a[0] != 0) return INF
    val balance = a.zipWithNext().fold(0) { s, (x, y) ->
      s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0)
    }
    return a.size + maxOf(balance, 0)
  }
  
  println(minOf(
    calc(a),
    calc(listOf(0) + a),
    calc(listOf(0, 2) + a)
   ))
}

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() - 1 }
  
  val prev = IntArray(n + 1) { -1 }
  val pos = IntArray(n) { -1 } 
  
  for (i in 0 until n) {
    for (j in a[i]-1..a[i]+1) {
      if (0 <= j && j < n) {
        prev[i] = maxOf(prev[i], pos[j])
      }
    }
    pos[a[i]] = i
  }
  
  val st = mutableListOf(n)
  var ans = 0L
  for (i in (n - 1) downTo 0) {
    while (st.size > 0 && prev[st.last()] >= i) {
      st.removeLast()
    }
    ans += st.last() - i
    st.add(i)
  }
  
  println(ans)
}

const val LOG = 19

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val p = readln().split(" ").map { it.toInt() - 1 }
  val ans = IntArray(n - 1) { n }
  
  fun rec(step: Int, p: List<Int>) {
    if (p.size == 1 || step == LOG) return
    for (cur in listOf(p, p.reversed())) {
      val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y }
      a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) }
      rec(step + 1, b.map { (x, _) -> x} + cur.last())
    }
  }
  
  rec(1, p)
  
  println(ans.joinToString(" "))
}

const val INF = 1e9.toInt()
const val B = 5

fun main() = repeat(readln().toInt()) {
  val (n, m, k) = readInts()
  val a = Array(n) { readInts() }
  
  var ans = 0
  
  for (bit in 0 until B) {
    val g = Array(n) { ArrayList<Pair<Int, Int>>() }
    for (i in 0 until n) {
      for (j in 0 until i) {
        val cnt = IntArray(4) { 0 }
        for (x in 0 until m) {
          val f = (a[i][x] shr bit) and 1
          val s = (a[j][x] shr bit) and 1
          ++cnt[f * 2 + s];
        }
        val f1 = (cnt[0] < k && cnt[3] < k)
        val f2 = (cnt[1] < k && cnt[2] < k)
        if (f1 != f2) {
          g[i].add(j to if (f2) 1 else 0)
          g[j].add(i to if (f2) 1 else 0)
        } else if (!f1) {
          return@repeat println("-1")
        }
      }
    }
    
    val color = IntArray(n) { -1 }
    val cnt = IntArray(2) { 0 }
    var ok = true
    
    fun dfs(v: Int, c: Int) {
      color[v] = c
      ++cnt[c]
      for ((u, d) in g[v]) {
        if (color[u] != -1) {
          if ((c xor d) != color[u]) {
            ok = false
          }
        } else {
          dfs(u, c xor d)
        }
      }
    }
    
    for (v in 0 until n) {
      if (color[v] != -1) continue
      cnt.fill(0)
      dfs(v, 0)
      if (!ok) return@repeat println("-1")
      ans += cnt.min() shl bit
    }
  }
  
  println(maxOf(0, ans))
}

fun readInts() = readln().split(" ").map { it.toInt() }

class Query(val t: Int, val x: Int)

class BIT(val mx: Int) {
	val f = LongArray(mx) { 0L }
	
	fun upd_pr(pos: Int, x: Int) {
		var i = pos
		while (i < mx) {
			f[i] = f[i] + x
			i = i or (i + 1)
		}
	}

	fun get_pr(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i >= 0) {
			res += f[i]
			i = (i and (i + 1)) - 1
		}
		return res
	}

	fun upd_su(pos: Int, x: Int) {
		var i = pos
		while (i >= 0) {
			f[i] = f[i] + x
			i = (i and (i + 1)) - 1
		}
	}

	fun get_su(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i < mx) {
			res += f[i]
			i = i or (i + 1)
		}
		return res
	}
}

fun main() {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }
	val q = Array(n) { Query(-1, -1) }
	for (i in 0 until n) {
		val (t, x) = readLine()!!.split(" ").map { it.toInt() }
		q[i] = Query(t, x - 1)
	}
	
	val d = IntArray(n + 1) { 0 }
	
	fun apply(coef: Int) {	
		var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
		for (i in 0 until n) {
			qs[0].add(Pair(i, n + 1))
		}
		
		var len = n + 1
		while (true) {
			val posq = IntArray(n) { -1 }
			val poss = IntArray(n) { -1 }
			val sv = IntArray(n) { -1 }
			val fq = BIT(n)
			val fs = BIT(n)
			
			var cntq = 0
			var cnts = 0
			val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
			var j = 0
			
			var last = true
			for (l in 0 until n + 1) {
				for (it in qs[l]) {
					val i = it.first
					val r = it.second
					if (r - l == 1) {
						d[l] += coef
						continue
					}
					
					last = false
					val m = (l + r) / 2
					while (j < m) {
						val x = q[j].x
						if (q[j].t == 1) {
							posq[x] = cntq
							sv[x] = cnts
							cntq += 1
							cnts += 1
							fq.upd_pr(posq[x], a[x])
						}
						else if (q[j].t == 2){
							poss[x] = cnts
							cnts += 1
							fs.upd_su(poss[x], a[x])
						}
						else{
							fq.upd_pr(posq[x], -a[x])
							posq[x] = -1
							poss[x] = sv[x]
							fs.upd_su(poss[x], a[x])
						}
						j += 1
					}
					assert(j == m)
					if (poss[i] == -1 || posq[i] == -1) {
						nqs[m].add(Pair(i, r))
						continue
					}
					val tq = fq.get_pr(posq[i] - 1)
					val ts = fs.get_su(poss[i] + 1)
					var ok = true
					if (coef == 1) {
						ok = tq - a[i] >= ts
					}
					else {
						ok = tq + a[i] > ts
					}
					if (ok) {
						nqs[m].add(Pair(i, r))
					}
					else {
						nqs[l].add(Pair(i, m))
					}
				}
			}
			qs = nqs
			if (last) {
				break
			}
		}
		println("")
	}
	
	apply(1)
	apply(-1)
	for (i in 0 until n) {
		d[i + 1] += d[i]
	}
	val res = d.map { x -> (if (x == 0) "Yes" else "No") }
	println(res.take(res.size - 1).joinToString(separator = "\n"))
}

class Query(val t: Int, val x: Int)

class BIT(val mx: Int) {
    val f = LongArray(mx) { 0L }
    
    fun upd_pr(pos: Int, x: Int) {
        var i = pos
        while (i < mx) {
            f[i] = f[i] + x
            i = i or (i + 1)
        }
    }

    fun get_pr(pos: Int) : Long {
        var res = 0L
        var i = pos
        while (i >= 0) {
            res += f[i]
            i = (i and (i + 1)) - 1
        }
        return res
    }

    fun upd_su(pos: Int, x: Int) {
        var i = pos
        while (i >= 0) {
            f[i] = f[i] + x
            i = (i and (i + 1)) - 1
        }
    }

    fun get_su(pos: Int) : Long {
        var res = 0L
        var i = pos
        while (i < mx) {
            res += f[i]
            i = i or (i + 1)
        }
        return res
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val q = Array(n) { Query(-1, -1) }
    for (i in 0 until n) {
        val (t, x) = readLine()!!.split(" ").map { it.toInt() }
        q[i] = Query(t, x - 1)
    }
    val fq = BIT(n)
    val fs = BIT(n)
    
    val d = IntArray(n + 1) { 0 }
    val posq = IntArray(n) { -1 }
    val poss = IntArray(n) { -1 }
    val sv = IntArray(n) { -1 }
    var cntq = 0
    var cnts = 0
    
    fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) {
        if (l == r - 1) {
            d[l] += all.size * coef
            return
        }
        
        val m = (l + r) / 2
        
        val who_chg = ArrayList<Int>()
        val idx_chg = ArrayList<Int>()
        val val_chg = ArrayList<Int>()
        val chq = ArrayList<Pair<Int, Int>>()
        val chs = ArrayList<Pair<Int, Int>>()
        
        for (i in l until m) {
            val x = q[i].x
            if (q[i].t == 1) {
                who_chg.add(0)
                idx_chg.add(x)
                val_chg.add(posq[x])
                posq[x] = cntq
                who_chg.add(2)
                idx_chg.add(x)
                val_chg.add(sv[x])
                sv[x] = cnts
                cntq += 1
                cnts += 1
                chq.add(Pair(posq[x], -a[x]))
                fq.upd_pr(posq[x], a[x])
            }
            else if (q[i].t == 2){
                who_chg.add(1)
                idx_chg.add(x)
                val_chg.add(poss[x])
                poss[x] = cnts
                cnts += 1
                chs.add(Pair(poss[x], -a[x]))
                fs.upd_su(poss[x], a[x])
            }
            else{
                chq.add(Pair(posq[x], a[x]))
                fq.upd_pr(posq[x], -a[x])
                who_chg.add(0)
                idx_chg.add(x)
                val_chg.add(posq[x])
                posq[x] = -1
                who_chg.add(1)
                idx_chg.add(x)
                val_chg.add(poss[x])
                poss[x] = sv[x]
                who_chg.add(2)
                idx_chg.add(x)
                val_chg.add(sv[x])
                sv[x] = -1
                chs.add(Pair(poss[x], -a[x]))
                fs.upd_su(poss[x], a[x])
            }
        }
    
        val tol = ArrayList<Int>()
        val tor = ArrayList<Int>()
        
        for (x in all) {
            if (poss[x] == -1 || posq[x] == -1) {
                tor.add(x)
                continue
            }
            val tq = fq.get_pr(posq[x] - 1)
            val ts = fs.get_su(poss[x] + 1)
            var ok = true
            if (coef == 1) {
                ok = tq - a[x] >= ts
            }
            else {
                ok = tq + a[x] > ts
            }
            if (ok) {
                tor.add(x)
            }
            else {
                tol.add(x)
            }
        }
    
        calc(m, r, coef, tor)
        
        who_chg.reverse()
        idx_chg.reverse()
        val_chg.reverse()
        
        for (i in 0 until who_chg.size) {
            if (who_chg[i] == 0) {
                posq[idx_chg[i]] = val_chg[i]
            }
            else if (who_chg[i] == 1) {
                poss[idx_chg[i]] = val_chg[i]
            }
            else {
                sv[idx_chg[i]] = val_chg[i]
            }
        }
        
        for (i in l until m) {
            if (q[i].t == 1) {
                cntq -= 1
                cnts -= 1
            }
            else if (q[i].t == 2){
                cnts -= 1
            }
        }

        for (it in chq) {
            fq.upd_pr(it.first, it.second)
        }
        for (it in chs) {
            fs.upd_su(it.first, it.second)
        }
        
        calc(l, m, coef, tol)
    }
    
    val all = ArrayList<Int>()
    for (i in 0 until n) {
        all.add(i)
    }
    calc(0, n + 1, 1, all)
    calc(0, n + 1, -1, all)
    for (i in 0 until n) {
        d[i + 1] += d[i]
    }
    val res = d.map { x -> (if (x == 0) "Yes" else "No") }
    println(res.take(res.size - 1).joinToString(separator = "\n"))
}

fun main() {
    val ans = IntArray(101) { Int.MAX_VALUE }
    ans[0] = 0
    for (i in ans.indices) {
        for ((d, c) in listOf(1 to 1, 3 to 0, 5 to 0)) {
            if (i + d in ans.indices) ans[i + d] = minOf(ans[i + d], ans[i] + c)
        }
    }
    repeat(readInt()) {
        println(ans[readInt()])
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (k, m) = readInts()
        println(maxOf(0, 2 * k - (m % (3 * k))))
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        val (n, k) = readLongs()
        println(n - k.countTrailingZeroBits())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

fun main() {
    repeat(readInt()) {
        readInt()
        val d = mutableListOf(mutableListOf<Long>())
        for (i in readLongs()) {
            if (i == 0L) {
                d.add(mutableListOf())
            } else {
                d.last().add(i)
            }
        }
        println(d.sumOf { l -> 2 * l.sum() - ((l.indices step 2).takeIf { l.size % 2 == 1 }?.maxOfOrNull { l[it] } ?: 0) })
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private fun solve(): String {
    val (n, k) = readInts()
    var ans = listOf(n - 1, n)
    repeat(k - 1) {
        val min = ans.min()
        val prevStart = min - ans.size + 1
        if (prevStart <= 0) {
            return "-1"
        }
        ans = ans.zip(prevStart .. min).flatMap { (a, b) -> listOf(a, b) }.dropLast(1)
    }
    ans = (1 until ans.min()) + ans
    return ans.joinToString(" ")
}
fun main() {
    repeat(readInt()) {
        println(solve())
    }
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

private const val MOD =  1000000007

@JvmInline
@Suppress("NOTHING_TO_INLINE")
private value class ModInt(val x: Int) {
    inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
    inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
    inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
    fun power(p_: Int): ModInt {
        var a = this
        var res = ModInt(1)
        var p = p_
        while (p != 0) {
            if ((p and 1) == 1) res *= a
            a *= a
            p = p shr 1
        }
        return res
    }

    inline operator fun div(other: ModInt) = this * other.inv()
    inline fun inv() = power(MOD - 2)

    companion object {
        inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
        inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
    }
}

@JvmInline
private value class ModIntArray(val storage:IntArray) {
    operator fun get(index: Int) = ModInt(storage[index])
    operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
    val size get() = storage.size
}
private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })

private const val COMB_MAX = 400_010

private val fs = ModIntArray(COMB_MAX) { ModInt(1) }.apply {
    for (i in 1 until size) {
        set(i, get(i - 1) * ModInt.from(i))
    }
}
private val ifs = ModIntArray(COMB_MAX) { fs[it].inv() }

private fun cnk(n: Int, k: Int) = if (n >= k) fs[n] * ifs[k] * ifs[n - k] else ModInt(0)

fun main() {
    val (n, k) = readInts()
    val ans = ModIntArray(n + 1) { ModInt(0) }

    for (diff in -n..n) {
        val ways = maxOf(0, diff - 1)
        val ll = maxOf(1, diff)
        val rr = minOf(n, n - 1 + diff)
        ans[ways] += ModInt(maxOf(0, rr - ll)) * cnk(n - diff - 1, k - 2)
    }
    for (i in 1 until n) {
        ans[i] += cnk(n - i - 1, k - 1)
    }
    for (j in 0 until n - 1) {
        ans[n - j - 1] += cnk(j, k - 1)
    }
    println(ans.storage.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import kotlin.math.abs
import kotlin.math.sign

fun main() {
    readInts()
    val x = readInts()
    val h = readInts()
    val ord = buildList {
        for (i in x.indices.sortedBy { x[it] }) {
            while (isNotEmpty() && h[i] - h[last()] >= x[i] - x[last()]) {
                removeLast()
            }
            if (isEmpty() || h[last()] - h[i] <= x[i] - x[last()]) {
                add(i)
            }
        }
    }.map { x[it] to h[it] }

    fun nextAfter(pos: Int) = ord.binarySearch { (x, _) -> if (x >= pos) 1 else -1 }.inv()
    fun coverBy(idx: Int, pos: Int) = ord.getOrNull(idx)?.let { (x, h) -> maxOf(0, abs(x - pos) - h) } ?: Int.MAX_VALUE
    fun cover(pos: Int): Int {
        val a = nextAfter(pos)
        return minOf(coverBy(a - 1, pos), coverBy(a, pos))
    }

    fun cover2(l: Int, r: Int): Int {
        val a = nextAfter((l + r) / 2)
        return minOf(maxOf(coverBy(a, l), coverBy(a, r)), maxOf(coverBy(a - 1, l), coverBy(a - 1, r)))
    }

    val ans = List(readInt()) {
        val (l, r) = readInts()
        minOf(
            cover(l) + cover(r),
            cover2(l, r)
        )
    }
    println(ans.joinToString(" "))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

import java.math.BigInteger

fun main() = repeat(readLine()!!.toInt()) {
  val (n, hp) = readLine()!!.split(" ").let { (n, hp) -> n.toInt() to BigInteger(hp) } 
  val s = readLine()!!.split(" ").map { BigInteger(it) }
  val m = readLine()!!.toInt()
  val c = Array(m) { readLine()!!.split(" ").drop(1).map { it.toInt() - 1 } }
  val delta = Array(m) { BigInteger.ZERO }
  val minDelta = Array(m) { BigInteger.ZERO }
  for (i in 0 until m) {
    var curHP = BigInteger.ZERO
    for (id in c[i]) {
      if (id < n) {
        curHP += s[id]
        minDelta[i] = minOf(minDelta[i], curHP)
      } else {
        minDelta[i] = minOf(minDelta[i], curHP + minDelta[id - n])
        curHP += delta[id - n]
      }
    }
    delta[i] = curHP
  }
  
  fun rec(remHP : BigInteger, idCompSpell : Int) : Int {
    var curHP = remHP
    for (id in c[idCompSpell]) {
      if (id < n) {
        curHP += s[id]
        if (curHP <= BigInteger.ZERO)
          return id + 1
      } else {
        if (curHP + minDelta[id - n] <= BigInteger.ZERO)
          return rec(curHP, id - n)
        curHP += delta[id - n]
      }
    }
    return -1
  }
  
  println(rec(hp, m - 1))
}

fun readTree(n: Int) : List<BooleanArray> {
    val p = listOf(null) + readInts().map { it - 1 }
    return List(n) { a -> BooleanArray(n) { b -> a in generateSequence(b) { p[it] } } }
}
fun main() {
    val n = readInt()
    val t1 = readTree(n)
    val t2 = readTree(n)
    val masks = LongArray(n) { a ->
        (0 until n).filter { b -> a != b && t1[a][b] == t2[a][b] && t1[b][a] == t2[b][a] }.sumOf { 1L shl it }
    }
    val data = mutableMapOf<Long, Int>()
    data[0] = 0
    fun compute(mask: Long) : Int = data.getOrPut(mask) {
        val index = mask.countTrailingZeroBits()
        maxOf(compute(mask xor (1L shl index)), compute(mask and masks[index]) + 1)
    }
    println(2 * (n - compute((1L shl n) - 1)))
}

private fun readInt() = readln().toInt()
private fun readLongs() = readStrings().map { it.toLong() }
private fun readStrings() = readln().split(" ")
private fun readInts() = readStrings().map { it.toInt() }

const val M = 1000
const val K = 10

fun main() {  
  val (n, q) = readLine()!!.split(" ").map { it.toInt() }
  val a = readLine()!!.split(" ").map { it.toInt() }
  val b = readLine()!!.split(" ").map { it.toInt() }
  val l = IntArray(q)
  val r = IntArray(q)
  for (i in 0 until q) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() - 1}
    l[i] = x
    r[i] = y
  }
  val s = b.scan(0, Int::plus)
  val ev = Array(n) { mutableListOf<Int>() }
  for (i in 0 until n) {
    for (j in 1 until K) {
      val x = s[i] - (a[i] + j - 1) / j + 1
      val pos = s.binarySearch { if (it < x) -1 else 1 }.inv()
      if (pos < i) ev[pos].add(i)
    }
  }
  val qr = Array(n) { mutableListOf<Int>() }
  for (i in 0 until q) qr[l[i]].add(i)
  val f = IntArray(n) { 0 }
  fun inc(i : Int) = generateSequence(i) { (it or (it + 1)).takeIf { it < n } }.forEach { ++f[it] }
  fun sum(i : Int) = generateSequence(i) { ((it and (it + 1)) - 1).takeIf { it >= 0 } }.sumOf { f[it] }
  for (i in 0 until n) inc(i)
  val ans = IntArray(q) { 0 }
  for (i in 0 until n) {
    for (j in ev[i]) inc(j)
    for (j in qr[i]) {
      var cur = b[l[j]]
      for (x in 1 until M.coerceAtMost(r[j] - l[j] + 1)) {
        ans[j] += (a[l[j] + x] + cur - 1) / cur
        cur += b[l[j] + x]
      }
      if (l[j] + M <= r[j]) ans[j] += sum(r[j]) - sum(l[j] + M - 1)
    }
  }
  println(ans.joinToString("\n"))
}