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

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

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

const int MOD = 998244353;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;             

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    int ans = a[n - 1];
    for (int i = 0; i < n - 1; ++i)
      ans += max(0, a[i] - b[i + 1]);
    cout << ans << '\n';
  }
}

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

const int INF = int(1e9);

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

struct Seg {
	int l, r;

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

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

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

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

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

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

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

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

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

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

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

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

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

const li INF = 1e18;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

const val LOG = 19

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

private const val MOD =  1000000007

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

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

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

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

private const val COMB_MAX = 400_010

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

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

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

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

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

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

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

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

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

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

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

import java.math.BigInteger

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

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

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

const val M = 1000
const val K = 10

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

for _ in range(int(input())):
    ab = input()
    for i in range(1, len(ab)):
        if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
            print(ab[:i], ab[i:])
            break
    else:
        print(-1)

for _ in range(int(input())):
    s = input()
    cnt = [0, 0]
    for i in range(len(s)):
        cnt[int(s[i])] += 1
    for i in range(len(s) + 1):
        if (i == len(s) or cnt[1 - int(s[i])] == 0):
            print(len(s) - i)
            break
        cnt[1 - int(s[i])] -= 1

from sys import stdin, stdout

LOG = 30
cnt = [0 for i in range(LOG)]
ans = []
for _ in range(int(stdin.readline())):
    t, v = map(int, stdin.readline().split())
    if t == 1:
        cnt[v] += 1
    else:
        nw = 0
        for i in range(LOG):
            r = (v % (2 << i)) // (1 << i)
            if r > nw + cnt[i]:
                ans.append(0)
                break
            v -= r
            nw = (nw + cnt[i] - r) // 2
        else:
            ans.append(nw >= (v >> 30))
stdout.write('\n'.join(["YES" if x else "NO" for x in ans]))

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int normalize(long long x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> a(n);
        vector <int> nextMin(n);
        vector <int> dpSum(n + 2);
        vector <int> dpNext(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        
        stack <int> stMin;
        nextMin[n - 1] = n;
        dpSum[n] = 1;
        for (int pos = n - 1; pos >= 0; --pos) {
            while(!stMin.empty() && a[stMin.top()] > a[pos])
                stMin.pop();
            nextMin[pos] = stMin.empty() ? n : stMin.top();
            stMin.push(pos);
            
            int nxtPos = nextMin[pos];
            int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]);
            if (nxtPos != n) {
                dpPos = normalize(dpPos + dpNext[nxtPos]);
                dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]);
            }
            dpSum[pos] = normalize(dpPos + dpSum[pos + 1]);
            
            //cout << pos << ' ' << nxtPos << ' ' << dpPos << endl;
        }
        
        int res = 0;
        int mn = a[0];
        for(int i = 0; i < n; ++i) {
            mn = min(mn, a[i]);
            if (a[i] == mn) {
                res = normalize(res + dpSum[i] - dpSum[i + 1]);
            }
        }
        cout << res << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 111;

struct edge
{
    int y, c, w, f;
    edge() {};
    edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
};

vector<edge> e;
vector<int> g[N];

int rem(int x)
{
    return e[x].c - e[x].f;
}

void add_edge(int x, int y, int c, int w)
{
    g[x].push_back(e.size());
    e.push_back(edge(y, c, w, 0));
    g[y].push_back(e.size());
    e.push_back(edge(x, 0, -w, 0));
}

int n, m, s, t, v;

pair<int, long long> MCMF()
{
    int flow = 0;
    long long cost = 0;
    while(true)
    {
        vector<long long> d(v, (long long)(1e18));
        vector<int> p(v, -1);
        vector<int> pe(v, -1);
        queue<int> q;
        vector<bool> inq(v);
        q.push(s);
        inq[s] = true;
        d[s] = 0;
        while(!q.empty())
        {
            int k = q.front();
            q.pop();
            inq[k] = false;
            for(auto ei : g[k])
            {
                if(rem(ei) == 0) continue;
                int to = e[ei].y;
                int w = e[ei].w;
                if(d[to] > d[k] + w)
                {
                    d[to] = d[k] + w;
                    p[to] = k;
                    pe[to] = ei;
                    if(!inq[to])
                    {
                        inq[to] = true;
                        q.push(to);
                    }
                }
            }
        }
        if(p[t] == -1) break;
        flow++;
        cost += d[t];
        int cur = t;
        while(cur != s)
        {
            e[pe[cur]].f++;
            e[pe[cur] ^ 1].f--;
            cur = p[cur];
        }
    }
    return make_pair(flow, cost);
}

int get_sum(const vector<int>& v)
{
    int sum = 0;
    for(auto x : v) sum += x;
    return sum;
}

int main()
{
    cin >> n >> m;
    s = n + m;
    t = n + m + 1;
    v = n + m + 2;
    int sum_matrix = 0;
    vector<int> A(n), B(m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            sum_matrix += x;
            if(x == 1)
                add_edge(i, j + n, 1, 0);
            else
                add_edge(i, j + n, 1, 1);
        }
    for(int i = 0; i < n; i++)
    {
        cin >> A[i];
        add_edge(s, i, A[i], 0);
    }
    for(int i = 0; i < m; i++) 
    {
        cin >> B[i];
        add_edge(i + n, t, B[i], 0);
    }
    
    auto res = MCMF();
    if(res.first != get_sum(A) || res.first != get_sum(B))
        cout << -1 << endl;
    else
        cout << sum_matrix - res.first + res.second * 2 << endl;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second

using namespace std;

struct sparse_table {
    vector<vector<int>> st;
    vector<int> pw;
    
    sparse_table() {}
    
    sparse_table(const vector<int> &a) {
        int n = a.size();
        int logn = 32 - __builtin_clz(n);
        st.resize(logn, vector<int>(n));
        forn(i, n)
            st[0][i] = a[i];
        for (int j = 1; j < logn; ++j) forn(i, n) {
            st[j][i] = st[j - 1][i];
            if (i + (1 << (j - 1)) < n)
                st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
        }
        pw.resize(n + 1);
        pw[0] = pw[1] = 0;
        for (int i = 2; i <= n; ++i)
            pw[i] = pw[i >> 1] + 1;
    }
    
    int get(int l, int r) {
        if (l >= r) return 1e9;
        int len = pw[r - l];
        return min(st[len][l], st[len][r - (1 << len)]);
    }
};

struct suffix_array {
    vector<int> c, pos;
    vector<pair<pair<int, int>, int>> p, nw;
    vector<int> cnt;
    int n;
    
    void radix_sort(int max_al) {
        cnt.assign(max_al, 0);
        forn(i, n) ++cnt[p[i].x.y];
        for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
        nw.resize(n);
        forn(i, n) nw[--cnt[p[i].x.y]] = p[i];
        cnt.assign(max_al, 0);
        forn(i, n) ++cnt[nw[i].x.x];
        for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i];
    }
    
    vector<int> lcp;
    sparse_table st;
    
    int get_lcp(int l, int r) {
        l = c[l], r = c[r];
        if (l > r) swap(l, r);
        return st.get(l, r);
    }
    
    suffix_array(const string &s) {
        n = s.size();
        c = vector<int>(s.begin(), s.end());
        int max_al = *max_element(c.begin(), c.end()) + 1;
        p.resize(n);
        for (int k = 1; k < n; k <<= 1) {
            for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1))
                p[i] = make_pair(make_pair(c[i], c[j]), i);
            radix_sort(max_al);
            c[p[0].y] = 0;
            for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x);
            max_al = c[p.back().y] + 1;
        }
        lcp.resize(n);
        int l = 0;
        forn(i, n) {
            l = max(0, l - 1);
            if (c[i] == n - 1)
                continue;
            while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l])
                ++l;
            lcp[c[i]] = l;
        }
        pos.resize(n);
        forn(i, n)
            pos[i] = p[i].y;
        st = sparse_table(lcp);
    }
};

int main() {
    string s;
    int n;
    cin >> n;
    cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    auto sa = suffix_array(s + "#" + t + "$");
    vector<vector<int>> ev0(n), ev1(n);
    long long base = 0;
    vector<long long> dt(n + 2);
    vector<int> d1(n);
    forn(i, n){
        int len0 = sa.get_lcp(i, 2 * n - i + 1);
        base += len0;
        dt[i - len0] += 1;
        dt[i] -= 1;
        dt[i + 1] -= 1;
        dt[i + len0 + 1] += 1;
        if (i - len0 - 1 >= 0 && i + len0 < n){
            ev0[i - len0 - 1].push_back(i);
            ev0[i + len0].push_back(i);
        }
        int len1 = sa.get_lcp(i, 2 * n - i);
        d1[i] = len1;
        dt[i - len1 + 1] += 1;
        dt[i + 1] -= 2;
        dt[i + len1 + 1] += 1;
        base += len1;
        if (i - len1 >= 0 && i + len1 < n){
            ev1[i - len1].push_back(i);
            ev1[i + len1].push_back(i);
        }
    }
    vector<long long> dx(n + 1);
    long long curt = 0, val = 0;
    forn(i, n){
        curt += dt[i];
        val += curt;
        dx[i] = val;
    }
    long long ans = base;
    int pos = -1, nc = -1;
    bool gr = false;
    forn(i, n) forn(c, 26) if (c != s[i] - 'a'){
        long long cur = base;
        for (int j : ev0[i]){
            if (j <= i && c == s[2 * j - i - 1] - 'a')
                cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2));
            else if (j > i && c == s[2 * j - i - 1] - 'a')
                cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1));
        }
        for (int j : ev1[i]){
            if (c != s[2 * j - i] - 'a') continue;
            if (j < i)
                cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1));
            else
                cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1));
        }
        cur += d1[i];
        cur -= dx[i];
        bool upd = false;
        if (cur > ans){
            upd = true;
        }
        else if (cur == ans){
            if (c < s[i] - 'a'){
                if (pos == -1 || gr)
                    upd = true;
            }
            else{
                if (pos < i && gr)
                    upd = true;
            }
        }
        if (upd){
            ans = cur;
            pos = i;
            nc = c;
            gr = c > s[i] - 'a';
        }
    }
    cout << ans << endl;
    if (pos != -1) s[pos] = nc + 'a';
    cout << s << endl;
    return 0;
}

fun main() {
    repeat(readInt()) {
        println(readln().dropLastWhile { it == '0' }.dropLast(1))
    }
}

private fun readInt() = readln().toInt()

fun main() = repeat(readLine()!!.toInt()) {
  val s = readLine()!!.toCharArray()
  val x = s.indexOf('-').takeIf { it >= 0 } ?: 0
  val y = s.lastIndexOf('+').takeIf { it >= x } ?: x
  s[x] = s[y].also { s[y] = s[x] }
  val bal = s.runningFold(0) { cur, c -> cur + if (c == '-') -1 else 1 }
  println(if (bal.min() == 0) "$$${x + 1} $$${y + 1}" else "-1")
}

fun main() {
    repeat(readInt()) {
        readInt()
        val s = readln() + '.' + readln()
        println(s.split(".").sumOf { maxOf(0, it.length - 1) })
    }
}
 
private fun readInt() = readln().toInt()

private fun solve() : Boolean {
    val n = readInt()
    val a = readInts().toIntArray()
    var dropped = false
    for (i in 1 until n) {
        if (a[i] == a[i-1]) {
            a[i]++
        } else if (a[i] < a[i-1]) {
            if (dropped) return false
            dropped = true
            if (i != 1) {
                when {
                    a[i-2] > a[i] -> a[i] = a[i-1]
                    a[i-2] == a[i] -> a[i]++
                    else -> {}
                }
            }
        }
    }
    return true
}
fun main() {
    repeat(readInt()) {
        println(if (solve()) "YES" else "NO")
    }
}

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

fun main() = repeat(readLine()!!.toInt()) {
  val n = readLine()!!.toInt()
  val a = readLine()!!.split(" ").map { it.toLong() }
  val b = readLine()!!.split(" ").map { it.toLong() }
  val dp = Array(3) { LongArray(3) { 0 } }
  for ((x, y) in a zip b) {
    for (i in 0..2) for (j in 0..2) {
      dp[i][j] += maxOf(
      	(if (i == 1) x else 0) + (if (j == 1) y else 0),
      	(if (i == 1) y else 0) + (if (j == 1) x else 0)
      );
    }
    for (i in 0..2) for (j in 0..2) {
      if (i < 2) dp[i + 1][j] = maxOf(dp[i + 1][j], dp[i][j]);
      if (j < 2) dp[i][j + 1] = maxOf(dp[i][j + 1], dp[i][j]);
    }
  }
  println(dp[2][2]);
}

fun best(a: List<Int>, k: Int): Long {
    val r = LongArray(4)
    var sum = 0L
    for (v in a) {
        sum += v
        r[0] = maxOf(r[0], -sum)
        r[1] = maxOf(r[1], r[0] + sum)
        r[2] = maxOf(r[2], r[1] - sum)
        r[3] = maxOf(r[3], r[2] + sum)
    }
    return r[2 * k - 1]
}

fun main() {
    repeat(readInt()) {
        readInt()
        val a = readInts()
        val b = readInts()
        val mins = a.zip(b).map { minOf(it.first, it.second) }
        val maxs = a.zip(b).map { maxOf(it.first, it.second) }
        println(maxOf(best(mins, 1) + best(maxs, 1), best(maxs, 2)))
    }
}

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

fun main() {
    repeat(readInt()) {
        val (n, k) = readInts()
        val g = List(n) { mutableListOf<Int>() }
        repeat(n - 1) {
            val (a, b) = readInts().map { it - 1 }
            g[a].add(b)
            g[b].add(a)
        }
        val size = IntArray(n)
        fun dfs(v: Int, p:Int) : Int {
            size[v] = 1 + g[v].sumOf { if (it == p) 0 else dfs(it, v) }
            return size[v]
        }
        dfs(0, 0)
        val ns = size.map { it.toLong() * (n - it) }.sortedDescending()
        println(ns.subList(0, k - 1).sum() + ns.subList(k - 1, ns.size).sum() * 2)
    }
}

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

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        val t = readln().split(' ').map { it.toLong() }

        fun Long.genMoments() = List(n) { (it + 1) * this }

        val sPeriod = t[0]
        val lPeriod = t.firstOrNull { it % sPeriod != 0L }

        val sMoments = sPeriod.genMoments()
        val lMoments = lPeriod?.genMoments() ?: listOf()

        val req = sMoments.union(lMoments).sorted().take(n)
        println(if (req == t) "VALID" else "INVALID")
    }
}

private fun digitSum(a: Int) = a.toString().toCharArray().sumOf { it.digitToInt() }
private fun List<Int>.lowerBound(x: Int) = binarySearch { if (it < x) -1 else 1 }.inv()
fun main() {
    val n = readInt()
    val a = readInts()
    val pw10 = buildList<Int> {
        add(1)
        repeat(9) { add(last() * 10) }
        removeAt(0)
    }
    val d = pw10.map { p -> a.map { it % p }.sorted() }
    val ds = a.sumOf { digitSum(it) }
    println(a.map { x ->
        ds + n * digitSum(x) - 9 * pw10.indices.sumOf {
            n - d[it].lowerBound(pw10[it] - (x % pw10[it]))
        }
    }.joinToString(" "))
}

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

val MOD = 998244353

fun main() {
	val (n, k, c) = readLine()!!.split(' ').map { it.toInt() }
	val t = readLine()!!
	val cnt = n / k + 1
	val dp = Array(2) { IntArray(cnt) {0} }
	val pw = IntArray(cnt) {1}
	dp[0][0] = 1
	for (ii in 0 until n % k) {
		val i = ii and 1
		val ni = i xor 1
		var sum = 0
		val cur = c - (t[ii].toInt() - 'a'.toInt()) - 1
		var pr = 1
		for (j in 1 until cnt) {
			pw[j] = (pw[j - 1] * (cur + 1).toLong() % MOD).toInt()
		}
		for (j in 0 until cnt) {
			sum = ((sum * cur.toLong() + pr * dp[i][j].toLong()) % MOD).toInt()
			pr = (pr * c.toLong() % MOD).toInt()
			dp[ni][j] = (sum * pw[cnt - j - 1].toLong() % MOD).toInt()
		}
	}
	var ans = 0
	for (i in 0 until cnt) {
		ans = (ans + dp[n % k % 2][i]) % MOD
	}
	for (i in 0 until n) {
		if (i % k >= n % k) {
			ans = (ans * c.toLong() % MOD).toInt()
		}
	}
	println(ans)
}

import kotlin.math.abs

fun main() {
    val n = readInt()
    val c = readInts()
    val g = List(n) { mutableListOf<Pair<Int, Int>>() }
    repeat(n - 1) {
        val (a, b, w) = readInts()
        g[a - 1].add(b - 1 to w)
        g[b - 1].add(a - 1 to w)
    }
    val size = List(2) { IntArray(n) }
    var ans = 0L
    fun dfs(v: Int, p: Int) {
        size[c[v]][v] = 1
        for ((u, w) in g[v]) {
            if (u != p) {
                dfs(u, v)
                size[0][v] += size[0][u]
                size[1][v] += size[1][u]
                ans += abs(size[0][u] - size[1][u]) * w.toLong()
            }
        }
    }
    dfs(0, 0)
    println(ans)
}

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

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

const int N = 109;

int t;
int n;
int s[N], e[N];
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> s[i] >> e[i];
        }
        
        bool ok = true;
        for (int i = 1; i < n; ++i) 
            if (s[i] >= s[0] && e[i] >= e[0])
                ok = false;
        
        if (!ok) {
            puts("-1");
            continue;
        }
        
        cout << s[0] << endl;
    }
    return 0;
}

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

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    li mnA = *min_element(a.begin(), a.end());
    li sA = accumulate(a.begin(), a.end(), 0LL);
    li mnB = *min_element(b.begin(), b.end());
    li sB = accumulate(b.begin(), b.end(), 0LL);
    li ans = min(mnA * n + sB, mnB * n + sA);
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998'244'353;

void upd(int &a, int b) {
    a = (a * 1LL * b) % MOD;
}


int t;
string s;

int main() {
	cin >> t;
	for (int tc = 0; tc < t; ++tc) {
	    cin >> s;
	    int res = 1;
	    int k = s.size();
	    int n = s.size();
	    for (int l = 0; l < n; ) {
	        int r = l + 1;
	        while(r < n && s[l] == s[r])
	            ++r;
            upd(res, r - l);
            --k;
            l = r;
	    }
	    
	    for (int i = 1; i <= k; ++i)
	        upd(res, i);
        cout << k << ' ' << res << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int MOD = 998244353;
int n;
int a[N];

void add(int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
}

int sum(int a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
    if (a < 0)
        a += MOD;
    return a;
}

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

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    int res = 0;    
    for (int b = 0; b < 30; ++b) {
        int cur = 0;
        vector <int> cnt(2);
        vector <int> sumOfL(2);
        cnt[0] = 1;
        int x = 0;
        for (int i = 0; i < n; ++i) {
            x ^= ((a[i] >> b) & 1);
            int sumOfR = mul(cnt[x ^ 1], i + 1);
            add(cur, sum(sumOfR, -sumOfL[x ^ 1]));
            
            ++cnt[x];
            add(sumOfL[x], i + 1);
        }
        
        add(res, mul(1 << b, cur));
    }
    
    cout << res << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 123;

int n;
int color[N];
int countColors[N][N];
int p[N];
vector<int> g[N];
int deg[N];

void add_edge(int x, int y)
{
	g[x].push_back(y);
	g[y].push_back(x);
}

bool tryTwoColors()
{
	int v1 = n + 1;
	int v2 = n + 2;
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1)
		{
			add_edge(i, p[i]);
		}
	}
	for(int i = 2; i <= n; i++)
	{
		if(deg[i] == 1)
			add_edge(i, v1);
	}
	for(int i = 2; i <= n; i++)
	{
		if(p[i] != 1 && deg[p[i]] == 1)
			add_edge(i, v2);
	}
	add_edge(v1, v2);
	bool bad = false;
	for(int i = 2; i <= n + 2; i++)
		if(color[i] == 0)
		{
			color[i] = 1;
			queue<int> q;
			q.push(i);
			while(!q.empty())
			{
				int k = q.front();
				q.pop();
				for(auto y : g[k])
				{
					if(color[y] == 0)
					{
						color[y] = 3 - color[k];
						q.push(y);
					}
					else if(color[y] == color[k])
						bad = true;
				}
			}
		}
	if(bad)
		for(int i = 2; i <= n + 2; i++)
			color[i] = 0;
	return !bad;
}

void tryThreeColors()
{
	for(int i = 2; i <= n; i++)
		if(p[i] == 1)
			color[i] = 1;
		else
			color[i] = (color[p[i]] % 3) + 1;
}

int findVertex(const vector<int>& colors)
{
	int s = colors.size();
	for(int i = 2; i <= n; i++)
	{
		if(vector<int>(countColors[i], countColors[i] + s) == colors)
			return i;
	}
	return -1;
}

int main()
{
	cin >> n;
	for(int i = 2; i <= n; i++)
	{
		cin >> p[i];
		deg[p[i]]++;
	}
	
	if(*max_element(p + 2, p + n + 1) == 1)
	{
		for(int i = 2; i <= n; i++)
			color[i] = 1;
	}
	else if (!tryTwoColors())
		tryThreeColors();
	
	int colorsUsed = *max_element(color + 2, color + n + 1);
	
	cout << colorsUsed << endl;
	for(int i = 2; i <= n; i++)
	{
		cout << color[i];
		if(i == n) cout << endl;
		else cout << " ";
	}
	cout.flush();
	
	for(int i = 2; i <= n; i++)
	{
		countColors[i][color[i]]++;
		countColors[p[i]][color[i]]++;
	}
	
	while(true)
	{
		int resp;
		cin >> resp;
		if(resp == -1 || resp == 1)
			exit(0);
		vector<int> counts(colorsUsed + 1);
		for(int i = 1; i <= colorsUsed; i++)
			cin >> counts[i];
		int v = findVertex(counts);
		assert(v != -1);
		cout << color[v] << endl;
		cout.flush();
	}
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> h(n), a(n);
		forn(i, n) scanf("%d", &h[i]);
		forn(i, n) scanf("%d", &a[i]);
		int mxa = *max_element(a.begin(), a.end()) + 1;
		
		int l = mxa == 1 ? 0 : (__lg(mxa - 1) + 1);
		vector<vector<pair<int, int>>> st(l, vector<pair<int, int>>(mxa, make_pair(0, -1)));
		vector<vector<int>> st2(l, vector<int>(mxa));
		forn(i, n){
			if (h[i] > st[0][a[i]].first){
				st2[0][a[i]] = st[0][a[i]].first;
				st[0][a[i]] = {h[i], i};
			}
			else if (h[i] > st2[0][a[i]]){
				st2[0][a[i]] = h[i];
			}
		}
		
		auto combine = [&st, &st2](int i, int x, int y){
			int mx = max(st[i][x].first, st[i][y].first);
			if (mx == st[i][x].first)
				return max(st2[i][x], st[i][y].first);
			return max(st[i][x].first, st2[i][y]);
		};
		
		for (int j = 1; j < l; ++j) forn(i, mxa){
			if (i + (1 << (j - 1)) < mxa){
				st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				st2[j][i] = combine(j - 1, i, i + (1 << (j - 1)));
			}
			else{
				st[j][i] = st[j - 1][i];
				st2[j][i] = st2[j - 1][i];
			}
		}
		vector<int> pw(mxa + 1);
		for (int i = 2; i <= mxa; ++i) pw[i] = pw[i / 2] + 1;
		
		auto getmx = [&st, &pw](int l, int r){
			int len = pw[r - l];
			return max(st[len][l], st[len][r - (1 << len)]);
		};
		auto getmx2 = [&st, &st2, &pw, &combine](int l, int r){
			int len = pw[r - l];
			if (st[len][l].second != st[len][r - (1 << len)].second)
				return combine(len, l, r - (1 << len));
			return max(st2[len][l], st2[len][r - (1 << len)]);
		};
		
		vector<long long> svmx(mxa), svmx2(mxa);
		vector<int> svwho(mxa, -1);
		for (int x = 1; x < mxa; ++x){
			for (int l = 1; l < mxa; l += x){
				int r = min(mxa, l + x);
				int ac = (l - 1) / x + 1;
				auto tmp = getmx(l, r);
				long long mx = tmp.first * 1ll * ac;
				int who = tmp.second;
				long long mx2 = getmx2(l, r) * 1ll * ac;
				if (who == -1) continue;
				if (mx > svmx[x]){
					svmx2[x] = svmx[x];
					svmx[x] = mx;
					svwho[x] = who;
				}
				else if (mx > svmx2[x]){
					svmx2[x] = mx;
				}
				svmx2[x] = max(svmx2[x], mx2);
			}
		}
		
		vector<long long> ans(n);
		forn(i, mxa) if (svwho[i] != -1)
			ans[svwho[i]] = max(ans[svwho[i]], svmx[i] - svmx2[i]);
		
		forn(i, n) printf("%lld ", ans[i]);
		puts("");
	}
	return 0;
}

fun main() = repeat(readLine()!!.toInt()) {
	val (b, c, h) = readLine()!!.split(' ').map { it.toInt() }
	println(minOf(b - 1, c + h) * 2 + 1)
}

#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);
    for (auto &x : a) {
      cin >> x;
      x %= k;
      if (!x) x = k;
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    stable_sort(ord.begin(), ord.end(), [&](int i, int j) {
      return a[i] > a[j];
    });
    for (auto &x : ord) cout << x + 1 << ' ';
    cout << endl;
  }
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    
    vector<int> lf(n), rg(n);
    lf[0] = -1;
    for (int i = 0; i < n; ++i) {
        if (i > 0) lf[i] = lf[i - 1];
        if (s[i] == '0') lf[i] = i;
    }
    rg[n - 1] = n;
    for (int i = n - 1; i >= 0; --i) {
        if (i + 1 < n) rg[i] = rg[i + 1];
        if (s[i] == '1') rg[i] = i;
    }
    
    set<pair<int, int>> st;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        int ll = rg[l - 1], rr = lf[r - 1];
        if (ll > rr) {
            st.insert({-1, -1});
        } else {
            st.insert({ll, rr});
        }
    }
    
    cout << st.size() << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif   
    int t;
    cin >> t;
    while (t--) solve();
}

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

ans = 0
l = 0
while l < n:
    r = l + 1
    hasTwo = (a[l] == 2)
    hasMiddleZero = False
    while r < n:
        if r - 1 > l and a[r - 1] == 0:
            hasMiddleZero = True
        if a[r] == 2:
            hasTwo = True
        good = (not hasMiddleZero) and (hasTwo or a[l] != 0 or a[r] != 0)
        if not good:
            break
        r += 1
    l = r
    ans += 1
    
print(ans)

#include <bits/stdc++.h>

using namespace std;

bool comp(const pair<int, int> &a, const pair<int, int> &b){
    return a.second < b.second;
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> stmn, stmx;
    stmn.push_back({-1, -1});
    stmx.push_back({n, -1});
    long long ans = 0;
    int len = 0;
    set<pair<int, int>> cur;
    cur.insert({-1, 0});
    cur.insert({-1, 1});
    for (int i = 0; i < n; ++i){
        int x;
        scanf("%d", &x);
        --x;
        
        while (stmn.back().first > x){
            auto it = cur.lower_bound({stmn.back().second, 0});
            auto me = it;
            auto prv = it; --prv;
            ++it;
            len -= me->first - prv->first;
            if (it != cur.end() && it->second == 0)
                len += it->first - prv->first;
            cur.erase(me);
            stmn.pop_back();
        }
        len += i - cur.rbegin()->first;
        cur.insert({i, 0});
        stmn.push_back({x, i});
        
        while (stmx.back().first < x){
            auto it = cur.lower_bound({stmx.back().second, 1});
            auto me = it;
            auto prv = it; --prv;
            ++it;
            if (it != cur.end() && it->second == 0)
                len += me->first - prv->first;
            cur.erase(me);
            stmx.pop_back();
        }
        cur.insert({i, 1});
        stmx.push_back({x, i});
        
        ans += len;
    }
    printf("%lld\n", ans - n);
}

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200000;
const int NODES = 32 * N;
const int INF = int(2e9);

int n;
int a[N];
int nx[NODES][2], cnt[NODES], fn[NODES];
int nodeCount = 1;

void addInt(int x, int pos) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (nx[ind][bit] == 0) {
            nx[ind][bit] = nodeCount++;
        }
        ind = nx[ind][bit];
        ++cnt[ind];
    }
    fn[ind] = pos;
}

void addInt(int x) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        ind = nx[ind][bit];
        ++cnt[ind];
    }
}

void removeInt(int x) {
    int ind = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        ind = nx[ind][bit];
        --cnt[ind];
    }
}

PII findXor(int x) {
    int ind = 0, res = 0;
    for (int i = 29; i >= 0; --i) {
        int bit = (x >> i) & 1;
        if (cnt[nx[ind][bit]]) {
            ind = nx[ind][bit];
        } else {
            ind = nx[ind][bit ^ 1];
            res |= 1 << i;
        }
    }
    return mp(res, fn[ind]);
}

int par[200000], ra[200000];

void dsuInit() {
    forn(i, n) par[i] = i, ra[i] = 1;
}

int dsuParent(int v) {
    if (v == par[v]) return v;
    return par[v] = dsuParent(par[v]);
}

int dsuMerge(int u, int v) {
    u = dsuParent(u);
    v = dsuParent(v);
    if (u == v) return 0;
    if (ra[u] < ra[v]) swap(u, v);
    par[v] = u;
    ra[u] += ra[v];
    return 1;
}

vector<int> v[200000];
vector<pair<int, PII> > toMerge;
vector<int> g[200000];
int color[200000];

void coloring(int x, int c){
	if(color[x] != -1) return;
	color[x] = c;
	for(auto y : g[x]) coloring(y, c ^ 1);
}

int main() {
    scanf("%d", &n);
    forn(i, n) scanf("%d", a + i);
    forn(i, n) addInt(a[i], i);
    dsuInit();
    for (int merges = 0; merges < n - 1; ) {
        forn(i, n) v[i].clear();
        forn(i, n) v[dsuParent(i)].pb(i);
        toMerge.clear();
        forn(i, n) if (!v[i].empty()) {
            for (int x : v[i]) {
                removeInt(a[x]);
            }
            pair<pair<int, int>, int> res = mp(mp(INF, INF), INF);
            for (int x : v[i]) {
                res = min(res, mp(findXor(a[x]), x));
            }
            toMerge.pb(mp(res.first.first, mp(res.second, res.first.second)));
            for (int x : v[i]) {
                addInt(a[x]);
            }
        }
        for (auto p : toMerge) {
            if (dsuMerge(p.second.first, p.second.second)) {
                ++merges;
				g[p.second.first].pb(p.second.second);
				g[p.second.second].pb(p.second.first);
            }
        }
    }
	forn(i, n) color[i] = -1;
	coloring(0, 1);
	forn(i, n) printf("%d", color[i]);
	puts("");
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		string s;
		cin >> s;
		int ans = 1;
		if(s[0] == '0') ans = 0;
		if(s[0] == '?') ans = 9;
		for(int j = 1; j < s.size(); j++)
			if(s[j] == '?')
				ans *= 10;
		cout << ans << endl;
	}
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		int n;
		scanf("%d", &n);
		vector<int> a(n);
		for(int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		vector<int> a1(n);
		for(int i = 0; i < n; i++)
			scanf("%d", &a1[i]);
		int diffl = -1, diffr = -1;
		for(int j = 0; j < n; j++)
		{
			if(a[j] != a1[j])
			{
				diffr = j;
				if(diffl == -1)
					diffl = j;
			}
		}
		while(diffl > 0 && a1[diffl - 1] <= a1[diffl])
			diffl--;
		while(diffr < n - 1 && a1[diffr + 1] >= a1[diffr])
			diffr++;
		printf("%d %d\n", diffl + 1, diffr + 1);
	}
}

for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = n
	for x in range(26):
		c = chr(x + ord('a'))
		i = 0
		cur = 0
		while i < n:
			j = i
			while j < n and (s[j] == c) == (s[i] == c):
				j += 1
			if s[i] != c:
				cur = max(cur, j - i)
			i = j
		if cur == 0:
			ans = 0
			break
		pw = 0
		while (1 << pw) <= cur:
			pw += 1
		ans = min(ans, pw)
	print(ans)

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toInt() }
        val l = readln().split(' ').map { it.toInt() }
        val r = readln().split(' ').map { it.toInt() }

        var ans = 2e9.toInt()
        var cntShort = 0
        var lenLong = 0
        for (i in 0 until n) {
            val curLen = r[i] - l[i] + 1
            if(curLen > 1)
                lenLong += curLen
            else
                cntShort++

            if (lenLong < k) {
                if (lenLong + cntShort >= k) {
                    val cntSegs = (i + 1 - cntShort) + (k - lenLong)
                    ans = minOf(ans, r[i] + 2 * cntSegs)
                }
            }
            else {
                ans = minOf(ans, r[i] - (lenLong - k) + 2 * (i + 1 - cntShort))
                break
            }
        }
        if (ans == 2e9.toInt())
            ans = -1
        println(ans)
    }
}

#include <bits/stdc++.h>

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

const long long INF64 = 1e18;

long long dp[2][11][11][6];

int main(){
	int t;
	cin >> t;
	while (t--){
		int k;
		cin >> k;
		string s;
		cin >> s;
		int n = s.size();
		forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1) dp[0][balo][balc][mv] = INF64;
		dp[0][k][k][0] = 0;
		int act = 0;
		forn(ii, n){
			int i = ii & 1;
			int ni = i ^ 1;
			forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1)
				dp[ni][balo][balc][mv] = INF64;
			forn(mv, k + 1) forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) if (dp[i][balo][balc][mv] != INF64){
				int bal = act - balo + balc;
				if (balo >= 0 && mv < k)
					dp[i][balo - 1][balc][mv + 1] = min(dp[i][balo - 1][balc][mv + 1], dp[i][balo][balc][mv] + bal);
				if (balc >= 0 && mv < k && bal > 0)
					dp[i][balo][balc - 1][mv + 1] = min(dp[i][balo][balc - 1][mv + 1], dp[i][balo][balc][mv]);
				if (s[ii] == '('){
					dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv] + bal);
					if (balo + 1 <= 2 * k)
						dp[ni][balo + 1][balc][mv] = min(dp[ni][balo + 1][balc][mv], dp[i][balo][balc][mv]);
				}
				else{
					if (bal > 0)
						dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv]);
					if (balc + 1 <= 2 * k)
						dp[ni][balo][balc + 1][mv] = min(dp[ni][balo][balc + 1][mv], dp[i][balo][balc][mv]);
				}
			}
			act += (s[ii] == '(' ? 1 : -1);
		}
		printf("%lld\n", *min_element(dp[n & 1][k][k], dp[n & 1][k][k] + k + 1));
	}
}

for _ in range(int(input())):
	k = int(input())
	s = input()
	n = len(s)
	st = []
	cnt = [0 for i in range(n + 1)]
	ans = 0
	for i in range(n):
		if s[i] == '(':
			ans += len(st)
			st.append(i)
		else:
			cnt[(i - st.pop()) // 2] += 1
	for i in range(n, -1, -1):
		t = min(k, cnt[i])
		ans -= t * i
		k -= t
	print(ans)

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

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

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int main(){
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	vector<int> fact(2 * n + 1), rfact(2 * n + 1);
	fact[0] = 1;
	for (int i = 1; i <= 2 * n; ++i) fact[i] = mul(fact[i - 1], i);
	rfact[2 * n] = binpow(fact[2 * n], MOD - 2);
	for (int i = 2 * n - 1; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
	auto cnk = [&](int n, int k){
		if (k < 0 || n < 0 || k > n) return 0;
		return mul(fact[n], mul(rfact[k], rfact[n - k]));
	};
	auto snb = [&](int n, int k){
		return cnk(n + k, k);
	};
	
	int pw2 = 1;
	int ans = 0;
	for (int i = m; i >= 0; --i){
		int cur = 0;
		if (n - (m - i) * 1ll * (k + 1) - i * 1ll * (2 * k + 1) >= 0)
			cur = mul(snb(n - (m - i) * (k + 1) - i * (2 * k + 1), m), mul(pw2, cnk(m, i)));
		ans = add(ans, i & 1 ? -cur : cur);
		pw2 = mul(pw2, 2);
	}
	
	printf("%d\n", ans);
}

This will most likely cause issues for authors who get their blogs downvoted for some reasons other than their blogs being trash. For example, if participants choose to downvote the announcement for a contest.

And it can be very easily abused by registering a bunch of new accounts and downvoting anyone you don't like.

I don't think it can be done in any way other than requiring a specific CF rating for posting. And if this rating limit is set too low, nothing stops the people who want to post their trash from just taking part in a contest and then posting whatever they want. But if the limit is set higher, it will make so that actual participants of CF contest will be unable to post a genuine question. upd: And, unfortunately, it's not like people with high rating don't post pure BS. So, that's a no.

Come on. I hope I don't need to explain why this will only make matters worse.

#include <bits/stdc++.h>

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

using namespace std;

int n, m, m2;
vector<vector<char>> g;

int T;
vector<int> mt;
vector<int> used;

bool try_kuhn(int v){
    if (used[v] == T)
        return false;
    used[v] = T;
    forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
        mt[u] = v;
        return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    vector<string> b(m, string(n, '0'));
    forn(i, n){
        string t;
        cin >> t;
        forn(j, m) b[j][i] = t[j];
    }
    
    vector<string> nw = b;
    sort(nw.begin(), nw.end());
    nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
    m2 = nw.size();
    g.assign(m2, vector<char>(m2, 0));
    forn(i, m2) forn(j, m2) if (i != j){
        bool in = true;
        forn(k, n) in &= nw[i][k] >= nw[j][k];
        if (in) g[i][j] = 1;
    }
    
    mt.assign(m2, -1);
    used.assign(m2, -1);
    T = 0;
    int k = m2;
    forn(i, m2) if (try_kuhn(i)){
        ++T;
        --k;
    }
    
    vector<int> nxt(m2, -1);
    vector<char> st(m2, true);
    forn(i, m2) if (mt[i] != -1){
        nxt[mt[i]] = i;
        st[i] = false;
    }
    
    vector<int> gr(m2), req(m2);
    int t = 0;
    forn(i, m2) if (st[i]){
        int v = i;
        int pos = 2;
        while (v != -1){
            gr[v] = t;
            req[v] = pos;
            ++pos;
            v = nxt[v];
        }
        ++t;
    }
    assert(t == k);
    
    vector<int> num(m);
    forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
    
    printf("%d\n", k);
    forn(i, m) printf("%d ", gr[num[i]] + 1);
    puts("");
    forn(i, m) printf("%d ", req[num[i]]);
    puts("");
    forn(i, n){
        vector<int> l(k, 1);
        forn(j, m2) if (nw[j][i] == '1')
            l[gr[j]] = max(l[gr[j]], req[j]);
        forn(j, k)
            printf("%d ", l[j]);
        puts("");
    }
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    s = input()
    print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

int add(int a, int b){
    a += b;
    if (a >= MOD)
        a -= MOD;
    return a;
}

int mul(int a, int b){
    return a * 1ll * b % MOD;
}

int binpow(int a, int b){
    int res = 1;
    while (b){
        if (b & 1)
            res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    vector<int> fact(4 * n + 1);
    fact[0] = 1;
    fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
    vector<int> rfact(4 * n + 1);
    rfact.back() = binpow(fact.back(), MOD - 2);
    for (int i = int(fact.size()) - 2; i >= 0; --i)
        rfact[i] = mul(rfact[i + 1], i + 1);
    
    auto cnk = [&](int n, int k){
        return mul(fact[n], mul(rfact[k], rfact[n - k]));
    };
    
    vector<vector<int>> sv(n + 1, vector<int>(5));
    forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
    
    vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
    forn(ii, n + 1){
        int i = ii & 1;
        int ni = i ^ 1;
        dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
        for (int t = 1; t <= 4; ++t)
            dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
        forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
            dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
            for (int t = 1; p + t <= 4; ++t)
                dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
        }
    }
    
    int ans = 0;
    forn(sum, k + 1){
        ans = add(ans, mul(mul(mul(
            sum < k ? 1 : 4 * n - k, 
            dp[(n & 1) ^ 1][sum][4]), 
            mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))), 
            mul(fact[4], fact[sum]))
        );
    }
    
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

#define N 200000

int a[N], n, s;

bool can(int x) {
    int l = x - 1, r = n - 1;
    while (l < r) {
        if (a[r] > s - a[l]) return false;
        ++l;
        if (l < r) {
            if (a[l] > s - a[r]) return false;
            --r;
        }
    }
    return true;
}


int main() {
    long long sum = 0;
    scanf("%d %d\n", &n, &s);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    sort(a, a + n, greater<int>());

    int l = 1, r = n;
    while (l < r) {
        int m = (l + r) >> 1;
        if (can(m)) r = m;
        else l = m + 1;
    }

    long long ans = sum + r;
    cout << ans << endl;

    return 0;
}

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

void solve() 
{
    int n, a, b;
    cin >> n >> a >> b;
    int x = (n + a - 1) / a;
    if(a > b) x = 1;
    cout << x << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

typedef long long li;

const li INF64 = 1e18;

struct base{
    int x, w, c;
};

li area(const base &a, const base &b){
    return (a.c + b.c) * li(abs(a.x - b.x));
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<base> a(n);
    forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
    sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
    vector<li> dp(n, -INF64);
    li ans = 0;
    forn(i, n){
        dp[i] = max(dp[i], -a[i].w * 200ll);
        for (int j = i + 1; j < n; ++j)
            dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
        ans = max(ans, dp[i]);
    }
    printf("%.15Lf\n", ans / (long double)(200));
    return 0;
}

#include <bits/stdc++.h>     

using namespace std;

mt19937 rnd(42);
uniform_int_distribution<int> d(1, 2);

int ask(int t, int i)
{
    cout << t << " " << i + 1 << endl;
    int x;
    cin >> x;
    return x;
}

void giveAnswer(const string& s)
{
    cout << 0 << " " << s << endl;
    int x;
    cin >> x;
    assert(x == 1);
}

void guessOne(string& s, int i)
{
    int res = ask(1, i);
    if(res == 0)
        s[i] = '1';
    else
        s[i] = s[res - 1];
}

char inv(char c)
{
    if(c == '0') return '1';
    return '0';
}

void guessTwo(string& s, int i)
{
    if(s[1] == '0')
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                s[i - 1] = '1';
            }
            else
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                s[i - 1] = '0';
            }
            else
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
        }
    }
    else
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '1';
                s[i - 1] = '1';
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '0';
                s[i - 1] = '0';
            }
        }
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s(n, '0');
        for(int j = 1; j < n; j += 2)
        {
            if(j == 1) guessOne(s, j);
            else guessTwo(s, j);
        }
        if(n % 2 == 1) guessOne(s, n - 1);
        giveAnswer(s);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    g[y - 1].push_back(x - 1);
  }
    
  vector<int> ans(n, -1);
  for (int s = 0; s < n; ++s) {
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) 
      for (int j : g[i]) ++deg[j];
    priority_queue<pair<int, int>> q;
    for (int v = 0; v < n; ++v)
      if (deg[v] == 0 && v != s)
        q.push({a[v], v});
    for (int i = n; i > 0; --i) {
      if (q.empty() || q.top().first < i) {
        if (deg[s] == 0 && i <= a[s])
          ans[s] = i;
        break;
      }
      int v = q.top().second;
      q.pop();
      for (int u : g[v]) {
        --deg[u];
        if (deg[u] == 0 && u != s)
          q.push({a[u], u});
      }
    }
  }
  
  for (int &x : ans) cout << x << ' ';
}
 

#include <bits/stdc++.h>

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

using namespace std;

const string al = "KQRBN";

const int INF = 1e9;

struct mv{ int dx, dy; };
struct piece{ int x, y, t; };
struct seg{ int l, r; };
struct pos{ int x, y; };

bool operator <(const pos &a, const pos &b){
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

vector<vector<mv>> mvs({
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
    {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
});

int main() {
    int sx, sy, fx, fy;
    cin >> sx >> sy >> fx >> fy;
    swap(sx, sy), swap(fx, fy);
    --sx, --fx;
    
    int k;
    cin >> k;
    vector<piece> a(k);
    forn(i, k){
        string t;
        cin >> t >> a[i].x >> a[i].y;
        swap(a[i].x, a[i].y);
        --a[i].x;
        a[i].t = al.find(t[0]);
    }
    
    sort(a.begin(), a.end(), [](const piece &a, const piece &b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    
    vector<int> base({sy, fy});
    forn(i, k) base.push_back(a[i].y);
    vector<int> ys;
    for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
        ys.push_back(i);
    sort(ys.begin(), ys.end());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    
    vector<vector<char>> tk(8, vector<char>(ys.size()));
    forn(i, k){
        a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
        tk[a[i].x][a[i].y] = true;
    }
    sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
    fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
    
    vector<vector<char>> bad = tk;
    
    forn(i, k){
        int x = a[i].x, y = a[i].y;
        if (a[i].t == 0 || a[i].t == 4){
            for (auto it : mvs[a[i].t]){
                int nx = x + it.dx;
                int ny = y + it.dy;
                if (0 <= nx && nx < 8)
                    bad[nx][ny] = true;
            }
        }
        else{
            for (auto it : mvs[a[i].t]){
                for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
                    if (nx < 0 || nx >= 8) break;
                    if (ny < 0 || ny >= int(ys.size())) break;
                    if (tk[nx][ny]) break;
                    bad[nx][ny] = true;
                }
            }
        }
    }
    
    vector<vector<int>> d(8, vector<int>(ys.size(), INF));
    vector<vector<pos>> p(8, vector<pos>(ys.size()));
    set<pair<int, pos>> q;
    d[sx][sy] = 0;
    q.insert({0, {sx, sy}});
    while (!q.empty()){
        int x = q.begin()->second.x;
        int y = q.begin()->second.y;
        q.erase(q.begin());
        if (x == fx && y == fy){
            cout << d[x][y] << endl;
            return 0;
        }
        for (int ny : {y - 1, y, y + 1}){
            if (ny < 0 || ny >= int(ys.size())) continue;
            int dy = max(1, abs(ys[y] - ys[ny]));
            for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
                int nd = d[x][y] + dy;
                if (d[nx][ny] > nd){
                    q.erase({d[nx][ny], {nx, ny}});
                    d[nx][ny] = nd;
                    p[nx][ny] = {x, y};
                    q.insert({d[nx][ny], {nx, ny}});
                }
            }
        }
    }
    
    cout << -1 << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long total = 0;
    for(int i = 0; i < n; i++)
    {
        total += n * 1ll * (a[i] + b[i]);
        total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
        total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
    }
    for(int i = 0; i < n; i++)
        total -= (n - 1) * 1ll * abs(a[i] - b[i]);
    cout << total << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n;
vector< vector<int> > a;

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

void solve() {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += accumulate(a[i].begin(), a[i].end(), 0LL);
    
    int mn = a[0][n - 1];
    for (int i = 0; i < n; i++)
        mn = min(mn, a[i][n - 1 - i]);
    
    cout << sum - mn << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    
    if(read()) {
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char>> ds(n, vector<char>(7));
    forn(i, n){
        int t;
        cin >> t;
        forn(_, t){
            string s;
            cin >> s;
            ds[i][find(days, days + 7, s) - days] = true;
        }
    }
    vector<int> h(m);
    forn(i, m) cin >> h[i];
    vector<vector<int>> a(k);
    forn(i, k){
        int p;
        cin >> p;
        a[i].resize(p);
        forn(j, p){
            cin >> a[i][j];
            --a[i][j];
        }
    }
    int j = 0;
    vector<int> ans(k, -1), lst(k);
    int done = 0;
    vector<map<int, int>> cur(7);
    vector<set<int>> wk(n);
    forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
        ++cur[j][a[i][0]];
    forn(i, k)
        wk[a[i][0]].insert(i);
    for (int d = 1;; ++d){
        if (j < m && h[j] == d){
            ++j;
            continue;
        }
        int wd = (d - 1) % 7;
        vector<int> now, sv;
        for (auto it : cur[wd]) now.push_back(it.first);
        for (int x : now){
            forn(i, 7){
                auto it = cur[i].find(x);
                if (it != cur[i].end()){
                    if (it->second == 1)
                        cur[i].erase(it);
                    else
                        --it->second;
                }
            }
            int y = *wk[x].begin();
            sv.push_back(y);
            wk[x].erase(wk[x].begin());
        }
        forn(i, now.size()){
            int y = sv[i];
            ++lst[y];
            if (lst[y] == int(a[y].size())){
                ans[y] = d;
                ++done;
                continue;
            }
            wk[a[y][lst[y]]].insert(y);
            forn(j, 7) if (ds[a[y][lst[y]]][j])
                ++cur[j][a[y][lst[y]]];
        }
        if (done == k) break;
    }
    forn(i, k) cout << ans[i] << " ";
    cout << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int a = 1;
    for (int g = 2; g * g <= n; ++g) {
      if (n % g == 0) {
        a = n / g;
        break;
      }
    }
    cout << a << ' ' << n - a << '\n';
  }
}
 

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin >> t;
  while (t--) {
    string x;
    cin >> x;
    int k;
    cin >> k;
    int n = x.size();
    vector<vector<int>> pos(10);
    for (int i = 0; i < n; ++i)
      pos[x[i] - '0'].push_back(i);
    for (int i = 0; i < 10; ++i)
      reverse(pos[i].begin(), pos[i].end());
    string ans;
    int lst = 0, len = n - k;
    for (int i = 0; i < len; ++i) {
      for (int d = (i == 0); d <= 9; ++d) {
        while (!pos[d].empty() && pos[d].back() < lst)
          pos[d].pop_back();
        if (!pos[d].empty() && pos[d].back() - lst <= k) {
          ans += d + '0';
          k -= pos[d].back() - lst;
          lst = pos[d].back() + 1;
          break;
        }
      }
    }
    cout << ans << '\n';
  }
}