t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    cnt0 = a.count(0)
    if cnt0 >= 2:
        print(a[0] + a[-1])
    else:
        print(-1)

#include<bits/stdc++.h>

using namespace std;

void solve()
{
    long long x, y, k;
    cin >> x >> y >> k;
    long long ans = 0;
    for(long long i = 0; i < min(y, k); i++)
        ans += (y + i) % (x + i);
    long long full = max(0ll, k - y);
    ans += full * (y - x);
    cout << ans << endl;    
}

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

#include<bits/stdc++.h>

using namespace std;

void solve()
{
    int x, y;
    cin >> x >> y;
    int s = x + y;
    for(int d = (1 << 30); d >= 1; d >>= 1)
        if((s & d) != 0 && x >= d)
            x -= d;
    cout << s << " " << x << endl;    
}

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

#include<bits/stdc++.h>

using namespace std;

const int K = 3;
const int INF = int(1e9);

pair<int, int> get_segment(char c)
{
    if(c == '0') return {K, K};
    if(c == '-') return {0, K - 1};
    return {K + 1, K * 2};
}

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> dp(n + 1, vector<int>(2 * K + 1, INF));
    dp[0][K] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2 * K + 1; j++)
        {
            if(dp[i][j] == INF) continue;
            auto [l, r] = get_segment(s[i]);
            for(int k = l; k <= r; k++)
            {
                if(k == j) continue;
                int& d = dp[i + 1][k];
                d = min(d, max(dp[i][j], abs(k - j)));
            }
        }
    int ans = *min_element(dp[n].begin(), dp[n].end());
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

int get(int c00, int c11, int cd)
{                                      
    int len = c00 + c11 + cd;
    int lf = len / 4;
    int rg = 1e8;
    int ans = 1e8;
    while(rg >= lf)
    {
        int mid = (lf + rg) / 2;
        int need_break = max(0, c00 - mid) + max(0, c11 - mid);
        if(need_break + cd / 2 <= mid)
        {
            ans = mid;
            rg = mid - 1;
        }
        else
            lf = mid + 1;
    }
    return ans;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> pref1(n + 1), prefdiff(n);
    for(int i = 0; i < n; i++)
        pref1[i + 1] = pref1[i] + (s[i] - '0');
    for(int i = 0; i + 1 < n; i++)
        prefdiff[i + 1] = prefdiff[i] + (s[i] != s[i + 1]);

    for(int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        if(l == r)
            cout << 3 << "\n";
        else
        {
            int c1 = pref1[r] - pref1[l - 1];
            int cd = prefdiff[r - 1] - prefdiff[l - 1];
            if(s[l - 1] != s[r - 1])
                cd++;
            int c0 = (r - l + 1) - c1;
            int c00 = c0 - (cd / 2);
            int c11 = c1 - (cd / 2);
            cout << get(c00, c11, cd) * 4 - (r - l + 1) << "\n";
        }
    }
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 3010;

vector<pair<int, int>> g[N];
int p[N];
int pe[N];
int used[N];
int n, m;
vector<int> bad_edges;
int cycle[N];
int xs[N], ys[N];

void dfs1(int x)
{
    for(auto [y, i] : g[x])
        if(p[y] == -1)
        {
            p[y] = x;
            pe[y] = i;
            dfs1(y);
        }
        else if(p[x] != y)
            bad_edges.push_back(i);
}

void go_to_root(int x)
{
    while(x != 0)
    {
        cycle[pe[x]] ^= 1;
        x = p[x];
    }
}

void dfs2(int x)
{
    used[x] = true;
    for(auto [y, i] : g[x])
        if(cycle[i] == 0 && !used[y])
            dfs2(y); 
}

void solve()
{
    cin >> n >> m;
    bad_edges.clear();
    for(int i = 0; i < n; i++)
    {
        g[i].clear();
        p[i] = -1;
        pe[i] = -1;
    }
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        xs[i] = x;
        ys[i] = y;
        g[x].push_back(make_pair(y, i));
        g[y].push_back(make_pair(x, i));
    }
    
    p[0] = 0;
    dfs1(0);
    sort(bad_edges.begin(), bad_edges.end());
    bad_edges.erase(unique(bad_edges.begin(), bad_edges.end()), bad_edges.end());

    int k = bad_edges.size();
    for(int mask = 1; mask < (1 << k); mask++)
    {
        for(int edge = 0; edge < m; edge++) cycle[edge] = 0;
        for(int bit = 0; bit < k; bit++)
            if((mask >> bit) & 1)
            {                                                               
                go_to_root(xs[bad_edges[bit]]);
                go_to_root(ys[bad_edges[bit]]);
                cycle[bad_edges[bit]] ^= 1;
            }
        for(int vertex = 0; vertex < n; vertex++)
            used[vertex] = 0;
        dfs2(0);
        bool good = true;
        for(int vertex = 0; vertex < n; vertex++)
            if(!used[vertex])
                good = false;
        if(good)
        {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

const int N = 200043;

int mind[N];
int fact[N];
int ifact[N];

void precalc()
{
    for(int i = 2; i < N; i++)
        for(int j = i; j < N; j += i)
            if(mind[j] == 0)
                mind[j] = i;

    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
    ifact[N - 1] = inv(fact[N - 1]);
    for(int i = N - 1; i >= 1; i--)
        ifact[i - 1] = mul(ifact[i], i);
}

int choose(int n, int k)
{
    if(n < 0 || n < k || k < 0) return 0;
    return mul(fact[n], mul(ifact[k], ifact[n - k]));
}

int n;

vector<int> factorize(int x)
{
    vector<int> res;
    while(x != 1)
    {
        res.push_back(mind[x]);
        x /= mind[x];
    }
    return res;
}

void gen(const vector<int>& d, int i, long long cur, int m, vector<pair<long long, int>>& res)
{
    if(i == d.size()) res.push_back(make_pair(cur, m));
    else
    {
        gen(d, i + 1, cur, m, res);
        gen(d, i + 1, cur * 1ll * d[i], -m, res);
    }
} 

void solve()
{
    cin >> n;
    vector<pair<pair<long long, int>, int>> edges;
    for(int i = 1; i < n; i++)
    {
        auto f1 = factorize(i);
        auto f2 = factorize(i + 1);
        for(auto x : f2) f1.push_back(x);
        sort(f1.begin(), f1.end());
        f1.erase(unique(f1.begin(), f1.end()), f1.end());
        vector<pair<long long, int>> pos;
        gen(f1, 0, 1, 1, pos);
        for(auto [x, s] : pos)
        {
            if(x == 1) continue;
            edges.push_back(make_pair(make_pair(x, s), i));
        }
    }
    
    int ans = 1;
    int l = 0;
    sort(edges.begin(), edges.end());
    while(l < edges.size())
    {
        int r = l;
        while(r < edges.size() && edges[r].first.first == edges[l].first.first)
            r++;
        vector<int> e;
        for(int i = l; i < r; i++)
            e.push_back(edges[i].second);
        long long i = edges[l].first.first;
        int m = edges[l].first.second;
        if(m != 0)
        {
            int absent = n / i;
            int cur = mul(fact[n], ifact[n - absent]);
            int lf = 0;
            while(lf < e.size())
            {
                int rg = lf;
                int nxt = e[lf];
                while(rg < e.size() && e[rg] == nxt)
                {
                    rg++;
                    nxt++;
                }
                vector<int> cnt(2);
                for(int k = e[lf]; k <= e[rg - 1] + 1; k++)
                {
                    if(k % i != 0)
                        cnt[k % 2]++;     
                }
                //cout << cnt[0] << " " << cnt[1] << endl;
                cur = mul(cur, choose(cnt[0] + cnt[1], cnt[0]));
                lf = rg;
            }
            //cout << i << " " << cur << endl;
            ans = add(ans, -1 * m * add(cur, -1));
        }
        l = r;
    }
    cout << ans << endl;
}

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

t = int(input())
for i in range(t):
    n = int(input())
    good = True
    for j in range(2, n + 1):
        if (n + 1) % j == 0:
            good = False
    if good:
        print('YES')
    else:
        print('NO')  

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

void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	vector<pair<int, int>> b;
	for (int i = 0; i < n; i++){
		if (b.empty() || b.back().first != a[i]){
			b.emplace_back(a[i], 1);
		}
		else{
			b.back().second++;
		}
	}
	int m = b.size();
	for (int i = 0; i < m - 1; i++){
		if (b[i].second > 1 && b[i + 1].second > 1){
			cout << m + 2 << '\n';
			return;
		}
	}
	for (int i = 0; i < m; i++){
		if (i < m - 1 && b[i].second > 1 && (i + 2 >= m || b[i + 2].first != b[i].first)){
			cout << m + 1 << '\n';
			return;
		}
		if (i > 0 && b[i].second > 1 && (i - 2 < 0 || b[i - 2].first != b[i].first)){
			cout << m + 1 << '\n';
			return;
		}
	}
	cout << m << '\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;
}
 

def get_k_last(l, k):
    if k < len(l):
        return l[len(l)-k:]
    else:
        return l

t = int(input())
for _ in range(t):
    n, m, x, y = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    c = []
    d = []
    e = []
    i = 0
    j = 0
    while i < x and j < y:
        if a[i] == b[j]:
            c.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            d.append(a[i])
            i += 1
        else:
            e.append(b[j])
            j += 1
    d.extend(a[i:])
    e.extend(b[j:])
    
    res = sorted(get_k_last(d, n) + get_k_last(e, m) + c)
    res = get_k_last(res, n + m - 1)
    print(sum(res))

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

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

	int su = x + y;
	int k = 0;
	while((k + 1) * (k + 2) / 2 <= su){
		k++;
	}

	int p1x = k * (k + 1) / 2 - y;
	int p1y = y;

	int p2x = x;
	int p2y = k * (k + 1) / 2 - x;

	vector<pair<int, int>> cand;
	if ((p1x + p2x) < 0){
		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
		cand.emplace_back((p1x + p2x - 1) / 2, k * (k + 1) / 2 - (p1x + p2x - 1) / 2);
	}
	else{
		cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2);
		cand.emplace_back((p1x + p2x + 1) / 2, k * (k + 1) / 2 - (p1x + p2x + 1) / 2);
	}

	auto best = cand[0];
	for (auto [p, q] : cand){
		if (p < 0){
			p = 0;
		}
		if (q < 0){
			q = 0;
		}
		if ((p - x) * (p - x) + (q - y) * (q - y) < 
			(best.first - x) * (best.first - x) + (best.second - y) * (best.second - y)){
				best = {p, q};
		}
	}

	string ans(k, 'Y');
	for (int i = 0; i < k; i++){
		if (best.first >= k - i){
			ans[i] = 'X';
			best.first -= (k - i);
		}
	}

	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;

const int N = 1000043;

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

vector<int> get_dist(int x)
{
    vector<int> d(n, -1);
    d[x] = 0;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(auto y : g[k])
            if(d[y] == -1)
            {
                d[y] = d[k] + 1;
                q.push(y);
            }   
    }
    return d;
}

void remove_edge(int x, int y)
{
    int idx = -1;
    for(int i = 0; i < g[x].size(); i++)
        if(g[x][i] == y)
            idx = i;
    g[x].erase(g[x].begin() + idx, g[x].begin() + idx + 1);    
} 

vector<int> process(int v)
{
    vector<int> d(n, -1), p(n, -1);
    queue<int> q;
    q.push(v);
    d[v] = 0;
    vector<int> visited;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        visited.push_back(k);
        for(auto y : g[k])
            if(d[y] == -1)
            {
                d[y] = d[k] + 1;
                q.push(y);
                p[y] = k;
            }
    }
    int max_dist = *max_element(d.begin(), d.end());
    vector<bool> has_end(n, false);
    has_end[v] = true;
    for(auto x : visited)
        if(d[x] == max_dist)
        {
            int cur = x;
            while(!has_end[cur])
            {
                has_end[cur] = true;
                cur = p[cur];
            }
        }

    vector<int> res;
    for(auto x : visited)
    {
        if(!has_end[x]) continue;
        int good_children = 0;
        for(auto y : g[x])
            if(p[x] != y && has_end[y]) good_children++;
        if(good_children != 1) res.push_back(d[x]);
    }   
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

void solve()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        g[i].clear();
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    auto dist0 = get_dist(0);
    int e1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
    auto dist1 = get_dist(e1);
    int e2 = max_element(dist1.begin(), dist1.end()) - dist1.begin();
    auto dist2 = get_dist(e2);
    int d = dist1[e2];

    int x = -1, y = -1;
    for(int i = 0; i < n; i++)
        if(dist1[i] + dist2[i] == d)
        {
            if(dist1[i] == dist2[i] - 1)
                x = i;
            else if(dist1[i] == dist2[i] + 1)
                y = i;
        }

    remove_edge(x, y);
    remove_edge(y, x);
    auto ans1 = process(x);
    auto ans2 = process(y);

    vector<bool> res(n + 1);
    for(auto x : ans1)
        for(auto y : ans2)
            res[x + y + 1] = true;
    int cnt = 0;
    for(auto x : res)
        if(x) cnt++;
    cout << cnt;
    for(int i = 0; i <= n; i++)
        if(res[i])
            cout << " " << i;
    cout << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 43;
const long long INF64 = (long long)(1e18);

int n;
int cost[N];

void upd(long long& x, long long y)
{
    if(x > y) x = y;
}

bool check_bit(int x, int y)
{
    return bool((x >> y) & 1);
}

long long calc_dp(const vector<vector<int>>& c)
{
    int n = c.size();
    int m = c[0].size();
    int full = (1 << m) - 1;
    vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(m, vector<long long>(1 << m, INF64)));
    dp[0][0][0] = 0;
    for(int i = 0; i < n; i++)
    {
        int i1 = i & 1;
        int i2 = i1 ^ 1;
        for(int j = 0; j < m; j++)
            for(int f = 0; f < (1 << m); f++)
                dp[i2][j][f] = INF64;
        for(int j = 0; j < m; j++)
            for(int f = 0; f < (1 << m); f++)
            {
                if(dp[i1][j][f] == INF64) continue;
                int ni = i1;
                int nj = j + 1;
                if(nj == m)
                {
                    ni = i2;
                    nj = 0;
                }
                bool can = true;
                if(i > 0 && j + 2 < m && check_bit(f, m - 1) && check_bit(f, m - 2) && check_bit(f, m - 3))
                    can = false;
                if(can)
                {
                    int nf = ((f << 1) & full) | 1;
                    upd(dp[ni][nj][nf], dp[i1][j][f]); 
                }
                int nf = (f << 1) & full;
                upd(dp[ni][nj][nf], dp[i1][j][f] + c[i][j]);
            }
    }   
    return *min_element(dp[n & 1][0].begin(), dp[n & 1][0].end());
}

long long calc_comp(int x)
{
    int d2 = 0, d3 = 0;
    int p2 = 1, p3 = 1;
    while(x * (p2 * 2) <= n)
    {
        p2 *= 2;
        d2++;
    }
    while(x * (p3 * 3) <= n)
    {
        p3 *= 3;
        d3++;
    }
    d2++;
    d3++;
    vector<int> pow2(d2, 1), pow3(d3, 1);
    for(int i = 1; i < d2; i++)
        pow2[i] = pow2[i - 1] * 2;
    for(int i = 1; i < d3; i++)
        pow3[i] = pow3[i - 1] * 3;
    vector<vector<int>> cur(d3, vector<int>(d2, 0));
    for(int i = 0; i < d2; i++)
        for(int j = 0; j < d3; j++)
            if(x * 1ll * pow2[i] * 1ll * pow3[j] <= n)
                cur[j][i] = cost[x * pow2[i] * pow3[j]];
    return calc_dp(cur);
}   

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> cost[i];
    long long ans = 0;
    for(int i = 1; i <= n; i++)
        if(i % 2 != 0 && i % 3 != 0)
            ans += calc_comp(i);
    cout << ans << endl; 
}

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

t = int(input())
for i in range(t):
    k = int(input())
    a = list(map(int, input().split()))
    if max(a) > 2 or a.count(2) > 1:
        print('YES')
    else:
        print('NO')    

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

const int INF = 1'000'000'007;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}

	vector<int> pref1(n + 1);
	vector<int> pref2(n + 1);
	for (int i = 0; i < n; i++){
		pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1);
		pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1);
	}

	int mn = INF;
	for (int i = 1; i < n; i++){
		if (pref2[i] - mn >= 0){
			cout << "YES\n";
			return;
		}
		if (pref1[i] >= 0){
			mn = min(mn, pref2[i]);
		}
	}

	cout << "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;

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

    vector<int> a(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
    }
    
    vector<int> lens;

    int cur = 1;
    for (int i = 1; i < n; i++) 
        if (a[i] != a[i - 1]) 
        {
            lens.push_back(cur);
            cur = 1;
        } 
        else cur++;
    lens.push_back(cur);
    sort(lens.begin(), lens.end());

    int m = (int)lens.size();
    int d = 0;

    int ans = 0;
    int i = 0;
    while(i < m)
    {
        int len = lens[i];
        int x = len - 1;
        int q = m - i;
        int curLen = n - d - x * q;
        if (curLen <= k && (k - curLen) % q == 0)
            ans++;
            
        int j = i;
        while (j < m && lens[j] == len)
            j++;
        d += (j - i) * lens[i];
        i = j;
    }

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

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

void upd(int& x, int y)
{
    if(x < y) x = y;
}

void solve()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    vector<int> ps(n + 1), pt(m + 1);
    for(int i = 0; i < n; i++)
        ps[i + 1] = (ps[i] + (s[i] - '0')) % 10;
    for(int i = 0; i < m; i++)
        pt[i + 1] = (pt[i] + (t[i] - '0')) % 10;
    n++;
    m++;
    if(ps.back() != pt.back())
    {
        cout << -1 << "\n";
        return;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            if(i < n) upd(dp[i + 1][j], dp[i][j]);
            if(j < m) upd(dp[i][j + 1], dp[i][j]);
            if(i < n && j < m && ps[i] == pt[j]) upd(dp[i + 1][j + 1], dp[i][j] + 1);
        }
    cout << dp[n][m] - 1 << "\n";
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
        solve();
    return 0;
}

#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())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

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);
const ld EPS = 1e-9;

int l, r, n;

void solve() {
	cin >> l >> r >> n;
	
	int k = 63 - __builtin_clzll(r);
	int x = -1, y = -1;
	if (l >= (1ll << k)) {
		int p = 30;
		while (((l >> p) & 1) == ((r >> p) & 1))
			p--;
		assert(p >= 0);
		x = l;
		y = l - (l & ((1 << p) - 1)) + (1 << p);
	}
	else {
		x = max(l, (1 << (k - 1)));
		y = 1ll << k;
	}
	cerr << l << " " << r << ": " << x << " " << y << endl;
	assert(l <= x && x < y && y <= r);

	auto getBinary = [](int v) {
		vector<int> rep;
		while (v > 0) {
			rep.push_back(v & 1);
			v >>= 1;
		}
		reverse(rep.begin(), rep.end());
		return rep;
	};

	auto x_bits = getBinary(x);
	auto y_bits = getBinary(y);

	string ans(n, '0');
	fore (i, 0, n)
		ans[i] = '0' + (x_bits[i % x_bits.size()] & y_bits[i % y_bits.size()]);
	cout << ans << endl;
}

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--) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MX = 200000;
const int REBUILD_EVERY = 5000;

struct item {
    int value, cnt;
    int l, r;

    item(): value(0), cnt(0), l(0), r(0) {}
    item(int x): value(x), cnt(1), l(0), r(0) {}
};

vector<item> treap(1);

int copy(int v) {
    treap.push_back(treap[v]);
    return int(treap.size()) - 1;
}

int cnt(int v) {
    return v ? treap[v].cnt : 0;
}

void upd_cnt(int v) {
    if (v) {
        treap[v].cnt = cnt(treap[v].l) + cnt(treap[v].r) + 1;
    }
}

int merge(int l, int r) {
    if (!l || !r) {
        return l ? l : r;
    }

    int rang = rng() % (cnt(l) + cnt(r));

    if (rang < cnt(l)) {
        int res = copy(l);
        treap[res].r = merge(treap[res].r, r);
        upd_cnt(res);
        return res;
    } else {
        int res = copy(r);
        treap[res].l = merge(l, treap[res].l);
        upd_cnt(res);
        return res;
    }
}

int find_first(int v) {
    if (!treap[v].l) {
        return treap[v].value;
    } else {
        return find_first(treap[v].l);
    }
}

void dfs(int v) {
    if (!v) {
        return;
    }

    if (treap[v].l) {
        dfs(treap[v].l);
    }

    cout << treap[v].value << ' ';

    if (treap[v].r) {
        dfs(treap[v].r);
    }
}

pair<int, int> split(int t, int key, int add = 0) {
    if (!t) {
        return make_pair(0, 0);
    }

    t = copy(t);

    int cur_key = add + cnt(treap[t].l);

    if (key <= cur_key) {
        auto [l, r] = split(treap[t].l, key, add);
        treap[t].l = r;
        r = t;
        upd_cnt(t);
        return {l, r};
    } else {
        auto [l, r] = split(treap[t].r, key, add + 1 + cnt(treap[t].l));
        treap[t].r = l;
        l = t;
        upd_cnt(t);
        return {l, r};
    }
}

int change(int x, int it) {
    auto [l, r] = split(it, x, 0);
    auto [rl, rr] = split(r, x, 0);
    auto [l1, r1] = split(it, MX - x, 0);
    return merge(rl, l1);
}

void collect_values(int v, vector<int>& values) {
    if (!v) {
        return;
    }

    collect_values(treap[v].l, values);
    values.push_back(treap[v].value);
    collect_values(treap[v].r, values);
}

int build_balanced(const vector<int>& values, int l, int r) {
    if (l >= r) {
        return 0;
    }

    int m = (l + r) / 2;

    treap.emplace_back(values[m]);
    int v = int(treap.size()) - 1;

    treap[v].l = build_balanced(values, l, m);
    treap[v].r = build_balanced(values, m + 1, r);

    upd_cnt(v);
    return v;
}

int rebuild(int tr) {
    vector<int> values;
    values.reserve(cnt(tr));

    collect_values(tr, values);

    treap.clear();
    treap.emplace_back();

    return build_balanced(values, 0, int(values.size()));
}

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

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

    vector<int> ans(n);

    treap.reserve((size_t)((1 << 25) * 1.5));

    int tr = 0;

    for (int i = 0; i < MX; i++) {
        treap.emplace_back(i);
        tr = merge(tr, int(treap.size()) - 1);
    }

    int changed_iterations = 0;

    for (int i = n - 1; i >= 0; i--) {
        tr = change(a[i], tr);
        ans[i] = find_first(tr);

        changed_iterations++;

        if (changed_iterations % REBUILD_EVERY == 0) {
            tr = rebuild(tr);
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << ans[i] << ' ';
    }
}

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;
}

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;
}