for _ in range(int(input())):
	n = int(input())
	s = input()
	print("NO" if s.count('1') == n else "YES")

fun main(args: Array<String>) {
    repeat(readln().toInt()) {
        val (n, p, l, t) = readln().split(' ').map { it.toLong() }
        val cntTasks = (n + 6) / 7
        
        fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t
        var lf = 0L
        var rg = n
        while (rg - lf > 1) {
            val mid = (lf + rg) / 2
            if (calc(mid) >= p)
                rg = mid
            else
                lf = mid
        }
        println(n - rg)
    }
}

from math import gcd
 
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	for i in range(n - 1):
		g = gcd(g, a[i + 1] - a[i])
	g = max(g, 1)
	a.sort()
	j = n - 1
	res = a[-1]
	while True:
		while j >= 0 and a[j] > res:
			j -= 1
		if j < 0 or a[j] != res:
			break
		res -= g
	print((a[-1] * (n + 1) - (sum(a) + res)) // g)

#include <bits/stdc++.h>
 
using namespace std;
 
#define x first
#define y second
 
using pt = pair<int, int>;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<pt> pos(n + 1);
  for (int i = 0; i < n; ++i) {
    pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L');
    pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D');
  }
  map<pt, vector<int>> mp;
  for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i);
  auto check = [&](pt p, int l, int r) {
  	if (!mp.count(p)) return false;
  	auto it = lower_bound(mp[p].begin(), mp[p].end(), l);
  	return it != mp[p].end() && *it <= r;
  };
  while (q--) {
  	int x, y, l, r;
  	cin >> x >> y >> l >> r;
  	int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y;
  	bool f = check({x, y}, 0, l - 1)
  	       | check({nx, ny}, l, r - 1)
  	       | check({x, y}, r, n);
  	cout << (f ? "YES" : "NO") << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = int(1e6) + 99;
 
int nxt;
int to[N][26];
int sum[N];
long long res;
 
void add(const string& s) {
    int v = 0;
    ++sum[v];
    for (auto c : s) {
        int i = c - 'a';
        if (to[v][i] == -1)
            to[v][i] = nxt++;
        v = to[v][i];
        ++sum[v];
    }
}
 
void upd(const string& s) {
    int curLen = s.size();
    int v = 0;
    
    for (auto c : s) {
        int i = c - 'a';
        if (to[v][i] == -1) {
            res += sum[v] * 1LL * curLen;
            break;
        } else {
            int nxtV = to[v][i];
            res += (sum[v] - sum[nxtV]) * 1LL * curLen;
            --curLen;
            v = nxtV;
        }
    }
}
 
void solve(int n, vector <string> v) {
    int sumSizes = 0;
    for (int i = 0; i < n; ++i)
        sumSizes += v[i].size();
        
    nxt = 1;
    memset(sum, 0, sizeof sum);
    memset(to, -1, sizeof to);
    
    for(int i = 0; i < n; ++i) 
        add(v[i]);
    for (int i = 0; i < n; ++i) {
        reverse(v[i].begin(), v[i].end());
        upd(v[i]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector <string> v(n);
    for (int i = 0; i < n; ++i) 
        cin >> v[i];
    
    res = 0;
    solve(n, v);
    for(int i = 0; i < n; ++i)
        reverse(v[i].end(), v[i].end());
    solve(n, v);
    
    cout << res << endl;
    
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 200043;
const int K = 20;
 
typedef array<int, K> base;
int a[N];
vector<int> g[N];
vector<int> path_up[N];
int tin[N], tout[N];
int T = 0;
int fup[N][K];
 
base make_empty()
{
    base b;
    for(int i = 0; i < K; i++)
        b[i] = 0;
    return b;
}
 
int reduce(const base& b, int x)
{
    for(int i = K - 1; i >= 0; i--)
        if(x & (1 << i))
            x ^= b[i];
    return x;
}   
 
bool add(base& b, int x)
{
    x = reduce(b, x);
    if(x != 0)
    {
        for(int i = K - 1; i >= 0; i--)
            if(x & (1 << i))
            {
                b[i] = x;
                return true;
            }
    }   
    return false;
}
 
bool check(const base& b, int x)
{
    return reduce(b, x) == 0;
}
 
vector<int> rebuild_path(const vector<int>& path, int v)
{
    base b = make_empty();
    vector<int> ans;
    if(add(b, a[v])) ans.push_back(v);
    for(auto x : path) if(add(b, a[x])) ans.push_back(x);
    return ans;
}
 
void dfs(int v, int u)
{
    tin[v] = T++;      
    if(u == v)
        path_up[v] = rebuild_path(vector<int>(0), v);
    else
        path_up[v] = rebuild_path(path_up[u], v);
    fup[v][0] = u;
    for(int i = 1; i < K; i++)
        fup[v][i] = fup[fup[v][i - 1]][i - 1];
    for(auto y : g[v])
        if(y != u)
            dfs(y, v);
    tout[v] = T++;   
}
 
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int LCA(int x, int y)
{
    if(is_ancestor(x, y)) return x;
    for(int i = K - 1; i >= 0; i--)
        if(!is_ancestor(fup[x][i], y))
            x = fup[x][i];
    return fup[x][0];
}
 
bool query(int x, int y, int k)
{
    base b = make_empty();
    int z = LCA(x, y);
    for(auto v : path_up[x])
        if(!is_ancestor(v, y))
            add(b, a[v]);
    for(auto v : path_up[y])
        if(!is_ancestor(v, x))
            add(b, a[v]);
    add(b, a[z]);
    return check(b, k);            
}
 
int main()
{
    int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0, 0);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		int x, y, k;
		scanf("%d %d %d", &x, &y, &k);
		--x;
		--y;
		if(query(x, y, k)) puts("YES");
		else puts("NO");
	}
}

#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, x;
    cin >> n >> x;
    int prev = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
      int a; cin >> a;
      ans = max(ans, a - prev);
      prev = a;
    }
    ans = max(ans, 2 * (x - prev));
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> cnt(n);
        long long res = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cin >> cnt[i];
            if (cnt[i] > cur) 
                res += cnt[i] - cur;
            cur = cnt[i];
        }
        
        cout << res - 1 << endl;
    }
    return 0;
}

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x, y = min(a), max(a)
	res = []
	while x != y:
		res.append(x % 2)
		x = (x + res[-1]) // 2
		y = (y + res[-1]) // 2
	print(len(res))
	if len(res) <= n:
		print(*res)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &it : a) cin >> it;
    
    vector<int> pref(n), suf(n);
    for (int i = 0; i < n; ++i) {
        pref[i] = a[i] + (n - i - 1);
        suf[i] = a[i] + i;
    }
    for (int i = 1; i < n; ++i) {
        pref[i] = max(pref[i], pref[i - 1]);
    }
    for (int i = n - 2; i >= 0; --i) {
        suf[i] = max(suf[i], suf[i + 1]);
    }
    
    int ans = 2e9;
    for (int i = 0; i < n; ++i) {
        int cur = a[i];
        if (i > 0) cur = max(cur, pref[i - 1]);
        if (i + 1 < n) cur = max(cur, suf[i + 1]);
        ans = min(ans, cur);
    }
    
    cout << ans << endl;
    
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const li INF = 1e18;
const int N = 555555;
 
int n;
int a[N];
vector<int> g[N];
li dp[N];
li ans;
 
void calc(int v, int p) {
  vector<li> sum(4, -INF);
  sum[0] = 0;
  for (int u : g[v]) if (u != p) {
    calc(u, v);
    for (int i = 3; i >= 0; --i) {
      sum[min(i + 1, 3)] = max(sum[min(i + 1, 3)], sum[i] + dp[u]);
    }
  }
  dp[v] = -INF;
  for (int j = 0; j < 4; ++j) {
    dp[v] = max(dp[v], sum[j] + (j == 1 ? 0 : a[v]));
    ans = max(ans, sum[j] + (j == 2 ? 0 : a[v]));
  }
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) g[i].clear();
    for (int i = 0; i < n - 1; ++i) {
      int x, y;
      cin >> x >> y;
      --x; --y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    ans = 0;
    calc(0, -1);
    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())
#define all(a) (a).begin(), (a).end()
 
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	fore(i, 0, sz(v)) {
		if(i) out << " ";
		out << v[i];
	}
	return out;
}
 
pt operator+ (const pt &a, const pt &b) {
	return {a.x + b.x, a.y + b.y};
}
pt operator- (const pt &a, const pt &b) {
	return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
	return a.x * 1ll * b.x + a.y * 1ll * b.y;
}
li operator %(const pt &a, const pt &b) {
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
 
int n;
vector<pt> old, nw;
 
inline bool read() {
	if(!(cin >> n))
		return false;
	old.resize(n);
	nw.resize(n);
	fore (i, 0, n) {
		old[i].x = i;
		cin >> old[i].y;
	}
	fore (i, 0, n) {
		nw[i].x = i;
		cin >> nw[i].y;
	}
	return true;
}
 
inline ld getTr(const pt &a, const pt &b) {
	pt tmp = b - a;
	pt v = {-tmp.y, tmp.x};
	ld c = v * a;
	ld y0 = (c - v.x * 0) / v.y;
	ld y1 = (c - v.x * li(n - 1)) / v.y;
	return (y0 + y1);
}
 
vector<pt> hull(const vector<pt> &ps, int l, int r) {
	vector<pt> h;
	fore (i, l, r) {
		while (sz(h) > 1 && (h[sz(h) - 1] - h[sz(h) - 2]) % (ps[i] - h[sz(h) - 1]) >= 0)
			h.pop_back();
		h.push_back(ps[i]);
	}
	return h;
}
 
inline void solve() {
	vector<ld> maxTr(n - 1, 0);
	fore (t, 0, 2) {
		auto h = hull(old, n / 2, n);
 
		auto best = [&](const pt &p) {
			int l = -1, r = sz(h) - 1;
			while (r - l > 1) {
				int mid = (l + r) >> 1;
				if ((h[mid] - p) % (h[mid + 1] - h[mid]) >= 0)
					l = mid;
				else
					r = mid;
			}
			return h[r].x;
		};
		
		vector<ld> bs(n / 2 + 1, 0);
		for (int i = n / 2 - 1; i >= 0; i--) {
			int j = best(old[i]);
			bs[i] = getTr(old[i], old[j]);
			bs[i] = max(bs[i], bs[i + 1]);
		}
		
		ld lans = 0;
		fore (i, 0, n / 2) {
			int j = best(nw[i]);
			lans = max(lans, getTr(nw[i], old[j]));
			maxTr[i] = max({maxTr[i], lans, bs[i + 1]});
		}
		
		reverse(all(old));
		reverse(all(nw));
		swap(old, nw);
		fore (i, 0, n)
			old[i].x = nw[i].x = i;
		
		reverse(all(maxTr));
	}
			
	maxTr.push_back(maxTr.back());
	cout << maxTr << endl;
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(12);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if y < x:
      print(x)
    else:
      print(y + max(0, y - x - k))

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a;

inline void read() {
  cin >> n;
  a.clear();
  for (int i = 0; i < 2 * n; i++) {
      int x;
      cin >> x;
      a.pb(x);
  }
}
inline void solve() {
    sort(all(a));
    vector<pair<int, int> > pts;
    for (int i = 0; i < n; i++) {
        pts.pb(mp(a[i], a[i + n]));
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc);
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        cout << pts[i].ft << ' ' << pts[i].sc << endl;
    }
}
 
int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

n = int(input())
s = input().split()
ans = 0
cnt = [[0 for k in range(46)] for k in range(6)]
for y in s:
    cnt[len(y)][sum([int(c) for c in y])] += 1
for L in s:
    for lenr in range(len(L) % 2, len(L) + 1, 2):
        l = len(L) + lenr
        suml = sum([int(c) for c in L[:l // 2]])
        sumr = sum([int(c) for c in L[l // 2:]])
        if suml - sumr >= 0:
            ans += cnt[lenr][suml - sumr]
for R in s:
    for lenl in range(len(R) % 2, len(R), 2):
        l = len(R) + lenl
        suml = sum([int(c) for c in R[-l // 2:]])
        sumr = sum([int(c) for c in R[:-l // 2]])
        if suml - sumr >= 0:
            ans += cnt[lenl][suml - sumr]
print(ans)

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

const int LOG = 20;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  vector<array<int, 2>> t({{-1, -1}});
  auto add = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j] == -1) {
        t[v][j] = t.size();
        t.push_back({-1, -1});
      }
      v = t[v][j];
    }
  };  
  for (int x : a) add(x);
  auto get = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j ^ 1] != -1) j ^= 1;
      x ^= j << i;
      v = t[v][j];
    }
    return x;
  };
  for (int x = 0; x < n; ++x) {
    if (get(x) == n - 1) {
      for (int i : a) cout << (x ^ i) << ' ';
      break;
    }
  }
}

//

#include <bits/stdc++.h>

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

using namespace std;

struct card{
  int x, y;
  card() {}
  card(int x, int y) : x(x), y(y) {}
};

void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){
  if (used[v]) return;
  used[v] = true;
  dfs(g[v], g, res, used);
  res[v] = -res[g[v]];
}

void solve(){
  vector<vector<card>> a(2);
  vector<vector<int>> prpos(2);
  forn(z, 2){
    int n;
    scanf("%d", &n);
    a[z].resize(n);
    forn(i, n) scanf("%d", &a[z][i].x);
    forn(i, n) scanf("%d", &a[z][i].y);
    sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){
      return a.x > b.x;
    });
    prpos[z].resize(n + 1, -1);
    forn(i, n){
      if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y)
        prpos[z][i + 1] = i;
      else
        prpos[z][i + 1] = prpos[z][i];
    }
  }
  int n = a[0].size();
  vector<int> g(n + a[1].size());
  forn(z, 2) forn(i, a[z].size()){
    int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){
      return a.x > b.x;
    }) - a[z ^ 1].begin();
    g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n;
  }
  vector<int> res(g.size());
  vector<char> used(g.size());
  forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true;
  int w = 0, l = 0;
  forn(i, n){
    if (!used[i]) dfs(i, g, res, used);
    w += res[i] == 1;
    l += res[i] == -1;
  }
  printf("%d %d %d\n", w, n - l - w, l);
}

int main(){
  int t;
  scanf("%d", &t);
  while (t--) solve();
}

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

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

const int MOD = 1e9 + 7;
const int N = 40;

using mat = array<array<int, N>, N>;

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

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

mat mul(mat x, mat y) {
  mat res;
  forn(i, N) forn(j, N) res[i][j] = 0;
  forn(i, N) forn(j, N) forn(k, N)
    res[i][j] = add(res[i][j], mul(x[i][k], y[k][j]));
  return res;
}

template<class T>
T binpow(T x, int y, T e) {
  T res = e;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, x, k;
    cin >> n >> x >> k;
    mat a, e;
    forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k);
    forn(i, N) forn(j, N) e[i][j] = (i == j);
    mat b = binpow(a, n - 1, e);
    int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1));
    forn(i, x) forn(j, x) ans = add(ans, -b[i][j]);
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(42);

struct node
{
  long long x;
  int y;
  int cnt;
  int sum;
  int push;
  node* l;
  node* r;
  node() {};
  node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {};
};

typedef node* treap;
typedef pair<treap, treap> ptt;

int getSum(treap t)
{
  return (t ? t->sum : 0);
}

int getCnt(treap t)
{
  return (t ? t->cnt : 0);
}

treap fix(treap t)
{
  if(!t) return t;
  int p = t->push;
  if(p != 0)
  {
    if(t->l) t->l->push += p;
    if(t->r) t->r->push += p;
    t->x += p;
    t->push = 0;
  }
  t->sum = getSum(t->l) + t->cnt + getSum(t->r);
  return t;
}

treap merge(treap a, treap b)
{
  a = fix(a);
  b = fix(b);
  if(!a) return b;
  if(!b) return a;
  if(a->y > b->y)
  {
    a->r = merge(a->r, b);
    return fix(a);
  }
  else
  {
    b->l = merge(a, b->l);
    return fix(b);
  }
}

bool hasKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return false;
  if(t->x == x) return true;
  if(t->x < x) return hasKey(t->r, x);
  return hasKey(t->l, x);
}

ptt splitKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(t->x < x)
  {
    ptt p = splitKey(t->r, x);
    t->r = p.first;
    return make_pair(fix(t), p.second);
  }
  else
  {
    ptt p = splitKey(t->l, x);
    t->l = p.second;
    return make_pair(p.first, fix(t));
  }
}

long long kthMax(treap t, int k)
{
  t = fix(t);
  if(!t) return -1;
  int sumR = getSum(t->r);
  if(sumR >= k) return kthMax(t->r, k);
  if(sumR + t->cnt >= k) return t->x;
  return kthMax(t->l, k - sumR - t->cnt);
}

int getCntByKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return 0;
  if(t->x == x) return t->cnt;
  if(t->x > x) return getCntByKey(t->l, x);
  return getCntByKey(t->r, x);
}

treap increaseKey(treap t, long long x, int cnt)
{
  t = fix(t);
  if(!t) return t;
  if(t->x == x)
  {
    t->cnt += cnt;
  }
  else if(t->x > x)
  {
    t->l = increaseKey(t->l, x, cnt);
  }
  else
  {
    t->r = increaseKey(t->r, x, cnt);
  }
  return fix(t);
}

treap insert(treap t, long long x, int y, int cnt)
{
  t = fix(t);
  if(!t || t->y < y)
  {
    ptt p = splitKey(t, x);
    treap res = new node(x, y, cnt, cnt, 0, p.first, p.second);
    return fix(res);
  }
  if(t->x > x)
    t->l = insert(t->l, x, y, cnt);
  else
    t->r = insert(t->r, x, y, cnt);
  return fix(t);
}

treap insertMain(treap t, long long x, int cnt)
{
  if(hasKey(t, x))
    return increaseKey(t, x, cnt);
  else
    return insert(t, x, rnd(), cnt);
}

treap eraseKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return NULL;
  if(t->x > x)
  {
    t->l = eraseKey(t->l, x);
    return fix(t);
  }
  if(t->x < x)
  {
    t->r = eraseKey(t->r, x);
    return fix(t);
  }
  treap tnew = merge(t->l, t->r);
  delete t;
  return tnew;
}

ptt splitSum(treap t, int k)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(k == 0) return make_pair(t, treap(NULL));
  long long x = kthMax(t, k);
  int cnt = getCntByKey(t, x);
  t = eraseKey(t, x);
  ptt p = splitKey(t, x);
  k -= getSum(p.second);
  if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second);
  if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL));
  return p;
}

long long minKey(treap t)
{
  t = fix(t);
  if(!t) return 1e18;
  if(t->l) return minKey(t->l);
  return t->x;
}

treap decreaseUpToKLargest(treap t, int k, int& res)
{
  if(!k) return t;
  t = fix(t);
  k = min(k, getSum(t));
  res = k;
  ptt p = splitSum(t, k);
  if(p.second)
  {
    p.second->push--;
    for(int i = 0; i < 2; i++)
    {
        long long x = minKey(p.second);
        int cntMin = getCntByKey(p.second, x);
        p.second = eraseKey(p.second, x);
        if(x != 0 && cntMin != 0)
          p.first = insertMain(p.first, x, cntMin);
    }
  }
  return merge(p.first, p.second);
}

void destroy(treap t)
{
  if(!t) return;
  if(t->l) destroy(t->l);
  if(t->r) destroy(t->r);
  delete t;
}

void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<long long> r(n), b(n);
  for(int i = 0; i < n; i++) cin >> r[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  long long sum = 0;
  for(int i = 0; i < n; i++) sum += r[i] + b[i];
  long long flow = 0;
  treap t = NULL;
  for(int i = 0; i < n; i++)
  {
    long long d = min(r[i], b[i]);
    flow += d;
    r[i] -= d;
    b[i] -= d;
    if(s[i] == '0')
    {
      int add = 0;
      if(r[i] > 1e9) r[i] = 1e9;
      t = decreaseUpToKLargest(t, r[i], add);
      flow += add;
    }
    else
    {
      if(r[i] != 0) t = insertMain(t, r[i], 1);
    }
  }
  cout << sum - flow << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

int n;

inline void read() {
	cin >> n;
}

inline void solve() {
	for (int x = 1; x <= 20; x++) {
	    for (int y = 1; y <= 20; y++) {
	        if (x + y >= n || x == y) continue;
	        int z = n - x - y;
	        if (z == x || z == y) continue;
	        if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
	            continue;
	        }
	        puts("YES");
	        cout << x << ' ' << y << ' ' << z << endl;
	        return;
	    }
	}
	puts("NO");
}

int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  auto dist = [](int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  };
 
  int t;
  cin >> t;
  while (t--) {
    int px, py, ax, ay, bx, by;
    cin >> px >> py >> ax >> ay >> bx >> by;
    double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
    double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
    double ab = dist(ax, ay, bx, by);
    double ans = 1e9;
    ans = min(ans, max(pa, oa));
    ans = min(ans, max(pb, ob));
    ans = min(ans, max({ab / 2, pa, ob}));
    ans = min(ans, max({ab / 2, pb, oa}));
    cout << setprecision(10) << fixed << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200000;

int t;

int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        long long pos;
        cin >> s >> pos;
        --pos;
        
        int curLen = s.size();
        vector <char> st;
        bool ok = pos < curLen;
        s += '$';
        
        for (auto c : s) {
            while (!ok && st.size() > 0 && st.back() > c) {
                pos -= curLen;
                --curLen;
                st.pop_back();
                
                if(pos < curLen) 
                    ok = true;
            }
            st.push_back(c);
        }
        
        cout << st[pos];
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

const int N = 300009;

int bp(int a, int n) {
    int res = 1;
    while(n > 0) {
        if (n & 1)
            res = (res * 1LL * a) % MOD;
        a = (a * 1LL * a) % MOD;
        n >>= 1;
    }
    return res;
}

int n, m;
string s;
int inv[N];

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

int main() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i){
	    inv[i] = bp(i, MOD - 2);
    }
    
    cin >> n >> m >> s;
    
    int res = 1, k = n;
    bool isZero = false;
    for (int i = 0; i < s.size(); ++i) 
        if (s[i] == '?') {
            if (i == 0) {
                isZero = true;
            } else {
                upd(res, i);
            }
        }
    
    cout << (isZero? 0 : res) << endl;
    
    for(int i = 0; i < m; ++i) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        
        if (s[pos] == '?' && (c == '<' || c == '>')) {
            if (pos == 0)
                isZero = false;
            else
                upd(res, inv[pos]);
        } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
            if (pos == 0)
                isZero = true;
            else
                upd(res, pos);
        }
        
        s[pos] = c;
        cout << (isZero? 0 : res) << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> a(n), b(m);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, m) scanf("%d", &b[i]);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&a](int i, int j){
		return a[i] > a[j];
	});
	vector<vector<int>> mn(m, vector<int>(n + 2));
	forn(i, m){
		int r = 0;
		forn(l, n + 2){
			r = min(n + 1, max(r, l + 1));
			while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
			mn[i][l] = r;
		}
	}
	vector<int> dp(1 << m, n + 1);
	dp[0] = 0;
	vector<int> p(1 << m, -1);
	forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
		dp[mask | (1 << i)] = mn[i][dp[mask]];
		p[mask | (1 << i)] = mask;
	}
	int mask = (1 << m) - 1;
	if (dp[mask] > n){
		puts("NO");
		return 0;
	}
	puts("YES");
	vector<vector<int>> ans(n);
	forn(_, m){
		int i = __builtin_ctz(mask ^ p[mask]);
		for (int j = dp[p[mask]]; j < dp[mask]; ++j)
			ans[i].push_back(ord[j]);
		mask = p[mask];
	}
	forn(i, m){
		printf("%d", int(ans[i].size()));
		for (int x : ans[i]) printf(" %d", x + 1);
		puts("");
	}
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3003;
 
int n;
int k[4];
vector<int> a[4];
 
struct segtree {
  int sz;
  int tot;
  vector<int> t, p;
  
  segtree(int sz) : sz(sz) {
    tot = 0;
    t = vector<int>(4 * sz);
    p = vector<int>(4 * sz);
    build(0, 0, sz);
  }
  
  void build(int v, int l, int r) {
    if (l + 1 == r) {
      t[v] = -l;
      return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void push(int v) {
    if (p[v] == 0) return;
    if (v + 1 < 2 * sz) {
      t[v * 2 + 1] += p[v];
      p[v * 2 + 1] += p[v];
      t[v * 2 + 2] += p[v];
      p[v * 2 + 2] += p[v];
      p[v] = 0;
    }
  } 
  
  void upd(int v, int l, int r, int L, int R, int x) {
    if (L >= R) return;
    if (l == L && r == R) {
      t[v] += x;
      p[v] += x;
      return;
    }
    push(v);
    int m = (l + r) / 2;
    upd(v * 2 + 1, l, m, L, min(m, R), x);
    upd(v * 2 + 2, m, r, max(L, m), R, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void upd(int pos, int x) { 
    tot += x;
    upd(0, 0, sz, max(0, pos), sz, x);
  }
  
  int get(int v, int l, int r, int L, int R) {
    if (L >= R) return -1e9;
    if (l == L && r == R) return t[v];
    push(v);
    int m = (l + r) / 2;
    return max(
      get(v * 2 + 1, l, m, L, min(m, R)),
      get(v * 2 + 2, m, r, max(L, m), R)
    );
  }
  
  int get(int L) {
    return get(0, 0, sz, max(0, L), sz);
  }
  
  int getBad(int v, int l, int r) {
    if (t[v] <= 0) return -1;
    if (l + 1 == r) return l;
    push(v);
    int m = (l + r) / 2;
    if (t[v * 2 + 1] > 0) {
      return getBad(v * 2 + 1, l, m);
    } else {
      return getBad(v * 2 + 2, m, r);
    }
  }
  
  int getBad() {
    return getBad(0, 0, sz);
  }
};  
 
int main() {
  cin >> n;
  int sz = 1;
  for (int i = 0; i < n; ++i) {
    int t, s;
    cin >> t >> s;
    a[t].push_back(s);
    sz = max(sz, s + 1);
  }
  for (int t = 1; t < 4; ++t) {
    sort(a[t].begin(), a[t].end());
    k[t] = a[t].size();
  }
  reverse(a[2].begin(), a[2].end());
  int ans = 1e4;
  for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
    segtree L(sz), R(sz);
    multiset<int> used;
    for (int x : a[1]) L.upd(x, +1);
    for (int x : a[2]) R.upd(x, +1);
    for (int x : a[3]) {
      L.upd(x - len, +1);
      if (L.t[0] <= 0) {
        used.insert(x - len);
      } else {
        L.upd(x - len, -1);
        L.upd(x, +1);
        R.upd(x, +1);
      }
    }
    for (int i = 0; i <= k[2]; ++i) {
      if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
        ans = min(ans, n + (k[3] - (int)used.size()) + 2); 
      if (i == k[2]) break;
      R.upd(a[2][i], -1);
      L.upd(a[2][i] - len, +1);
      int pos;
      while ((pos = L.getBad()) != -1) {
        auto it = used.upper_bound(pos);
        if (it == used.begin()) break;
        --it;
        L.upd(*it, -1);
        L.upd(*it + len, +1);
        R.upd(*it + len, +1);
        used.erase(it);
      }
    }
  }
  if (ans == 1e4) ans = -1;
  cout << ans << '\n';
}

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		string s;
		cin >> s;
		if(s.find("1") < s.find("3"))
			cout << 13;
		else
			cout << 31;
		cout << endl;
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string a, b;
        cin >> a >> b;
        bool ok = false;
        for (int i = 0; i + 1 < a.size(); ++i) {
            if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
                ok = true;
            }
        }
        
        if (ok) 
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200000;
 
int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        cin >> s;
        int maxSortedPref = 0;
        int minNotSortedPref = 0;
        int bal = 0;
        bool good = true;
        
        for (auto c : s) {
            if (c == '+') {
                ++bal;
            } else if (c == '-') {
                --bal;
                maxSortedPref = min(maxSortedPref, bal);
                if (bal < minNotSortedPref)
                    minNotSortedPref = 0;
            } else if (c == '1') {
                maxSortedPref = max(maxSortedPref, bal);
            } else {
                if (bal <= 1) {
                    good = false;
                    break;
                }
                if (minNotSortedPref == 0 || minNotSortedPref > bal)
                    minNotSortedPref = bal;
            }
            if(minNotSortedPref <= maxSortedPref && minNotSortedPref != 0) {
                good = false;
                break;
            }
        }
        
        if (good)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
vector<int> has0, has1;
vector<vector<int>> g;
 
bool ans;
 
bool dfs(int x, int d)
{
	if(has0[x] && (has1[x] || d <= 1))
		ans = false;
	bool res = false;
	for(auto y : g[x])
		res |= dfs(y, d + 1);
	if(has0[x] && res)
		ans = false;
	return res || has1[x];
}
 
void solve()
{
	ans = true;
	has0.push_back(0);
	has1.push_back(0);
	g.push_back(vector<int>());
	int ts = 1;
	
	string s;
	cin >> s;
	vector<int> st = {0};
	for(auto x : s)
	{
		int cur = st.back();
		if(x == '0')
			has0[cur] = 1;
		if(x == '1')
			has1[cur] = 1;
		if(x == '+')
		{
			g[cur].push_back(ts);
			st.push_back(ts);
			ts++;
			has0.push_back(0);
			has1.push_back(0);
			g.push_back(vector<int>());
		}
		if(x == '-')
			st.pop_back();
	}
	
	dfs(0, 0);
	cout << (ans ? "YES\n" : "NO\n");
	
	has0.clear();
	has1.clear();
	g.clear();
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200 * 1000 + 5;
 
int t;
int n;
int a[N];
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc){
    	cin >> n;
    	for (int i = 0; i < n; ++i)
    	    cin >> a[i];
    	
    	int cnt = 0;
    	for (int i = 1; i < n; ++i)
    	    cnt += (a[i - 1] >= a[i]);
    	    
    	int res = n, cnt2 = 0;
        for (int i = 0; i <= n; ++i) {
            bool isMultipliedByNegative = (i > 0);
            res = min(res, isMultipliedByNegative + cnt + cnt2);
            
            if (i + 1 < n)
                cnt -= (a[i] >= a[i + 1]);
            if (i > 0)
                cnt2 += (a[i - 1] <= a[i]);
        }
        
        cout << res << endl;
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int x, int y)
{
	x += y;
	while(x >= MOD) x -= MOD;
	while(x < 0) x += MOD;
	return x;
}
 
int sub(int x, int y)
{
	return add(x, -y);
}
 
int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y & 1) z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}
 
int main()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	vector<vector<int>> dp(n + 1, vector<int>(k, 0));
	dp[0][0] = 1;
	for(int i = 0; i < n; i++)
	{
		int cur = 0;
		for(int j = k - 1; j >= 1; j--)
		{
			cur = add(cur, dp[i][j]);
			dp[i + 1][j] = cur;
		}
		for(int j = k - 1; j >= 0; j--)
		{
			int nxt = (j + 1) % k;
			dp[i + 1][nxt] = add(dp[i + 1][nxt], mul(dp[i][j], k - j));
		}
		ans = add(ans, mul(dp[i + 1][0], binpow(k, n - (i + 1))));
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int K = 4;
const int N = 2 * int(1e6) + 43;
 
pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
	return make_pair(a.first + b.first, a.second + b.second);
}
 
pair<long long, long long> operator-(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
	return make_pair(a.first - b.first, a.second - b.second);
}
 
// prefix sums for an array of pairs
vector<pair<long long, long long>> pref_sums(const vector<pair<long long, long long>>& a)
{
	int n = a.size();
	vector<pair<long long, long long>> ans(n);
	ans[0] = a[0];
	for(int i = 1; i < n; i++)
		ans[i] = ans[i - 1] + a[i];
	return ans;
}
 
// for an array of pairs denoting linear functions, evaluate
// them in the corresponding points
vector<long long> eval(const vector<pair<long long, long long>>& a)
{
	int n = a.size();
	vector<long long> ans(n);
	for(int i = 0; i < n; i++)
		ans[i] = a[i].first * i + a[i].second;
	return ans;
}
 
void solve()
{
	int n;
	scanf("%d", &n);
	vector<vector<int>> a(n, vector<int>(K));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			scanf("%d", &a[i][j]);
	vector<int> b(K);
	for(int i = 0; i < K; i++)
		scanf("%d", &b[i]);
	
	int deck_size = 0;
	for(int i = 0; i < K; i++)
		deck_size += b[i];
	
	// calculate the remaining number of cards for each player
	long long full = deck_size;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			full += a[i][j];
	vector<int> remain(n, full / n);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			remain[i] -= a[i][j];
	
	// for every player, calculate the maximum number of cards
	// they already have among all suits
	// and store it in a multiset
	vector<int> min_val(n);
	for(int i = 0; i < n; i++)
		min_val[i] = *max_element(a[i].begin(), a[i].end());
	multiset<int> min_vals;
	for(int i = 0; i < n; i++)
		min_vals.insert(min_val[i]);
	
	// for every mask of suits and every player, calculate
	// the number of cards in those suits they already have
	vector<vector<int>> already_has(1 << K, vector<int>(n));
	for(int mask = 0; mask < (1 << K); mask++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < K; j++)
				if(mask & (1 << j))
					already_has[mask][i] += a[i][j];
	// for every mask of suits and every player, calculate the
	// maximum value of x such that if that player can receive 
	// no more than x cards in each suit, the vertex of that
	// player should belong to T in the cut
	vector<vector<int>> max_x(1 << K, vector<int>(n));
	for(int mask = 0; mask < (1 << K); mask++)
		for(int i = 0; i < n; i++)
		{
			int suits = __builtin_popcount(mask);
			if (suits == 0) max_x[mask][i] = N - 2;
			else
			{
				// incoming edges have capacity of
				// x - a[i][j]
				int incoming = -already_has[mask][i];
				// outgoing edge has capacity of remain[i]
				// find the maximum x such that
				// suits * x + incoming < remains[i]
				int x = (remain[i] - incoming) / suits;
				x = min(x, N - 2);
				max_x[mask][i] = x;
			}
		}
	
	// for every mask and for all players, calculate the sum of 
	// values they add to the cut if they can have no more than
	// x cards of each suit in the mask
	vector<vector<long long>> add_to_cut(1 << K, vector<long long>(N));
	for(int mask = 0; mask < (1 << K); mask++)
	{
		int suits = __builtin_popcount(mask);
		vector<pair<long long, long long>> aux(N);
		for(int i = 0; i < n; i++)
		{
			// for the i-th player, they add remains[i] to
			// the minimum cut if x > max_x[mask][i]
			// otherwise, they add
			// suits * x - already_has[mask][i]
			int incoming = -already_has[mask][i];
			// add [suits * x - incoming] on segment [0, max_x]
			int x = max_x[mask][i];
			pair<long long, long long> f1 = {suits, incoming};
			aux[0] = aux[0] + f1;
			aux[x + 1] = aux[x + 1] - f1;
			// add remain[i] on [max_x + 1, N)
			pair<long long, long long> f2 = {0, remain[i]};
			aux[x + 1] = aux[x + 1] + f2;
			aux[N - 1] = aux[N - 1] - f2;
		}
		// sum up those functions and evaluate them
		add_to_cut[mask] = eval(pref_sums(aux));
	}
	
	// now we're ready to solve the problem!
	vector<int> ans(n);
	// iterate on the player we want to maximize
	for(int i = 0; i < n; i++)
	{
		// iterate on the suits they will maximize
		for(int j = 0; j < K; j++)
		{
			int d = min(remain[i], b[j]);
			int max_cards = a[i][j] + d;
			b[j] -= d;
			// find the maximum current score over all others
			min_vals.erase(min_vals.find(min_val[i]));
			int max_rival = *min_vals.rbegin();
			min_vals.insert(min_val[i]);
			if(max_rival >= max_cards)
				ans[i] = max(ans[i], 0);
			else
			{
				// binary search on the maximum cards over all
				// opponents
				int L = max_rival - 1;
				int R = max_cards;
				while(R - L > 1)
				{
					int mid = (L + R) / 2;
					long long min_cut = 1e18;
					long long req_flow = deck_size - remain[i];
					// iterate on the mask of suit vertices
					// which belong to S
					for(int mask = 0; mask < (1 << K); mask++)
					{
						int suits = __builtin_popcount(mask);
						long long cur_cut = 0;
						for(int z = 0; z < K; z++)
							if(!(mask & (1 << z)))
								cur_cut += b[z];
						cur_cut += add_to_cut[mask][mid];
						// don't forget to discard our player
						// from the flow network!
						if(mid > max_x[mask][i])
							cur_cut -= remain[i];
						else
						{
							long long add = mid * suits - already_has[mask][i];
							cur_cut -= add;
						}
						min_cut = min(min_cut, cur_cut);
					}
					if(min_cut < req_flow)
						L = mid;
					else
						R = mid;
				}
				ans[i] = max(ans[i], max_cards - R);
			}
			b[j] += d;
		}
	}
	
	for(int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	puts("");
}
 
int main()
{
	int t = 1;
	for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
	string s;
	cin >> s;
	int n = s.size();
	string a, b;
	for (int i = 0; i < 2 * n; ++i) {
	  a += "()"[i & 1];
	  b += ")("[i < n];
	}
	if (a.find(s) == string::npos) {
	  cout << "YES\n" << a << '\n';
	} else if (b.find(s) == string::npos) {
	  cout << "YES\n" << b << '\n';
	} else {
	  cout << "NO\n";
	}
  }
}

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int m, k, a1, ak;
		cin >> m >> k >> a1 >> ak;
		int taken_k = m / k;
		int taken_1 = m % k;
		int taken_fancy_1 = max(0, taken_1 - a1);
		int left_regular_1 = max(0, a1 - taken_1);
		int taken_fancy_k = max(0, taken_k - ak);
		int to_replace = min(left_regular_1 / k, taken_fancy_k);
		int ans = taken_fancy_1 + taken_fancy_k - to_replace;
		cout << ans << endl;
	}
}

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int m, k, a1, ak;
		cin >> m >> k >> a1 >> ak;
		// function which calculates the number of fancy coins taken
		// if we take exactly x coins of value k
		auto f = [m, k, a1, ak](int x)
		{
			int taken_1 = m - k * x;
			return max(0, taken_1 - a1) + max(0, x - ak);
		};
		
		int lf = 0;
		int rg = m / k;
		while(rg - lf > 2)
		{
			int mid = (lf + rg) / 2;
			if(f(mid) < f(mid + 1))
				rg = mid + 1;
			else
				lf = mid;
		}
		int ans = 1e9;
		for(int i = lf; i <= rg; i++) ans = min(ans, f(i));
		cout << ans << endl;
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 0;
    int mn = n + 1, mnWin = n + 1;
    while (n--) {
      int x;
      cin >> x;
      if (mn < x && x < mnWin) {
      	ans += 1;
      	mnWin = x;
      }
      mn = min(mn, x);
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
using li = long long;
 
const int N = 111;
 
int n;
string s;
int dp[2][N][N * N];
 
int main() {
  cin >> s;
  n = s.size();
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i + 1; ++j) {
      for (int cnt = 0; cnt <= j * (i + 1 - j); ++cnt) {
        dp[1][j][cnt] = n;   
      }
    }
    for (int j = 0; j <= i; ++j) {
      for (int cnt = 0; cnt <= j * (i - j); ++cnt) {
        dp[1][j + 1][cnt] = min(dp[1][j + 1][cnt], dp[0][j][cnt] + (s[i] != '0'));
        dp[1][j][cnt + j] = min(dp[1][j][cnt + j], dp[0][j][cnt] + (s[i] != '1'));
      }
    } 
    swap(dp[0], dp[1]);
  }
  int cnt0 = count(s.begin(), s.end(), '0');
  cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n';
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int INF = 1e9;
const int AL = 26;
 
struct query{
	int f, t, ans;
};
 
struct edge{
	int u, w;
};
 
int main() {
	cin.tie(0);
	iostream::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	
	int m;
	cin >> m;
	vector<query> a(m);
	forn(i, m){
		cin >> a[i].f >> a[i].t;
		--a[i].f, --a[i].t;
		a[i].ans = abs(a[i].f - a[i].t);
	}
	
	int k = n - 1 + AL * AL;
	vector<vector<edge>> g(k);
	forn(i, n - 1){
		int j = n - 1 + (s[i] - 'a') * AL + (s[i + 1] - 'a');
		g[i].push_back({j, 0});
		g[j].push_back({i, 1});
		if (i > 0){
			g[i].push_back({i - 1, 1});
			g[i - 1].push_back({i, 1});
		}
	}
	
	for (int st = n - 1; st < k; ++st){
		vector<int> d(k, INF);
		d[st] = 0;
		deque<int> q;
		q.push_back(st);
		while (!q.empty()){
			int v = q.front();
			q.pop_front();
			for (auto it : g[v]){
				if (d[it.u] <= d[v] + it.w) continue;
				d[it.u] = d[v] + it.w;
				if (it.w == 0) q.push_front(it.u);
				else q.push_back(it.u);
			}
		}
		forn(i, m){
			a[i].ans = min(a[i].ans, d[a[i].f] + d[a[i].t] - 1);
		}
	}
	
	forn(i, m) cout << a[i].ans << '\n';
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int INF = 1e9;
 
struct bracket{
	int a, b, c;
};
 
struct point{
	int x, y;
};
 
long long cross(const point &a, const point &b){
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
 
long long dot(const point &a, const bracket &b){
	return a.x * 1ll * b.a + a.y * 1ll * b.b;
}
 
bool operator <(const point &a, const point &b){
	return cross(a, b) > 0;
}
 
int main() {
	int t;
	cin >> t;
	while (t--){
		int n;
		cin >> n;
		vector<bracket> val;
		forn(i, 2 * n){
			int a, b;
			string c;
			cin >> a >> b >> c;
			val.push_back({a, b, c[0] == '(' ? 1 : -1});
		}
		map<point, vector<int>> opts;
		forn(i, 2 * n) forn(j, 2 * n){
			int dx = val[i].b - val[j].b;
			int dy = val[j].a - val[i].a;
			if (dx <= 0 || dy <= 0) continue;
			opts[{dx, dy}].push_back(i);
			opts[{dx, dy}].push_back(j);
		}
		opts[{1, INF}];
		vector<int> ord(2 * n), rord(2 * n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&](int i, int j){
			long long di = dot({INF, 1}, val[i]);
			long long dj = dot({INF, 1}, val[j]);
			if (di != dj) return di < dj;
			return val[i].c > val[j].c;
		});
		forn(i, 2 * n) rord[ord[i]] = i;
		int neg = 0, cur = 0;
		vector<int> bal(1, 0);
		for (int i : ord){
			cur += val[i].c;
			bal.push_back(cur);
			neg += cur < 0;
		}
		bool ans = neg == 0;
		vector<int> prv;
		for (auto it : opts){
			vector<int> tot = prv;
			for (int x : it.second) tot.push_back(x);
			sort(tot.begin(), tot.end(), [&](int i, int j){
				return rord[i] < rord[j];
			});
			tot.resize(unique(tot.begin(), tot.end()) - tot.begin());
			for (int x : tot) neg -= bal[rord[x] + 1] < 0;
			vector<int> tmp = tot;
			sort(tot.begin(), tot.end(), [&](int i, int j){
				long long di = dot(it.first, val[i]);
				long long dj = dot(it.first, val[j]);
				if (di != dj) return di < dj;
				return val[i].c > val[j].c;
			});
			vector<int> nrord(tot.size());
			forn(i, tot.size()) nrord[i] = rord[tmp[i]];
			forn(i, tot.size()) rord[tot[i]] = nrord[i];
			for (int x : tot){
				bal[rord[x] + 1] = bal[rord[x]] + val[x].c;
				neg += bal[rord[x] + 1] < 0;
			}
			if (neg == 0){
				ans = true;
				break;
			}
			prv = it.second;
		}
		puts(ans ? "YES" : "NO");
	}
	return 0;
}

for _ in range(int(input())):
	n, k, x = map(int, input().split())
	if x != 1:
		print("YES")
		print(n)
		print(*([1] * n))
	elif k == 1 or (k == 2 and n % 2 == 1):
		print("NO")
	else:
		print("YES")
		print(n // 2)
		print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1)))

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

pt A, B, C;

inline bool read() {
	if(!(cin >> A.x >> A.y))
		return false;
	cin >> B.x >> B.y;
	cin >> C.x >> C.y;
	return true;
}

int dist(const pt &A, const pt &B) {
	return abs(A.x - B.x) + abs(A.y - B.y);
}

inline void solve() {
	cout << (dist(A, B) + dist(A, C) - dist(B, C)) / 2 + 1 << endl;
}

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

import sys
for _ in range(int(sys.stdin.readline())):
	s = [int(c) for c in sys.stdin.readline().strip()]
	n = len(s)
	m = int(sys.stdin.readline())
	l = sys.stdin.readline()
	r = sys.stdin.readline()
	mx = 0
	for i in range(m):
		li = int(l[i])
		ri = int(r[i])
		nmx = mx
		for c in range(li, ri + 1):
			cur = mx
			while cur < n and s[cur] != c:
				cur += 1
			nmx = max(nmx, cur)
		mx = nmx + 1
	print("YES" if mx > n else "NO")

#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;
    li delta = 0, ans = 0;
    li sum = 0, mx = 0;
    for (int i = 0; i < n; ++i) {
      li x; cin >> x;
      sum += x;
      mx = max(mx, sum);
      if (sum - mx < delta) {
        delta = sum - mx;
        ans = mx;
      }
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = int(1e9) + 7;

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

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	int lim = 1;
	while (lim * (lim + 1) < k * 2) ++lim;
	vector<vector<vector<int>>> dp(2, vector<vector<int>>(2 * lim + 1, vector<int>(k + 1)));
	dp[0][lim][0] = 1;
	forn(ii, n){
		int i = ii & 1;
		int ni = i ^ 1;
		dp[ni] = vector<vector<int>>(2 * lim + 1, vector<int>(k + 1));
		forn(j, 2 * lim + 1) forn(t, k + 1) if (dp[i][j][t]){
			forn(z, 2){
				int nj = j + z - a[ii];
				int nt = t + abs(nj - lim);
				if (nt <= k) dp[ni][nj][nt] = add(dp[ni][nj][nt], dp[i][j][t]);
			}
		}
	}
	int ans = 0;
	for (int t = k & 1; t <= k; t += 2)
		ans = add(ans, dp[n & 1][lim][t]);
	printf("%d\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

const int LOGN = 19;
const int N = (1 << LOGN) + 555;

struct comp {
	double x, y;
	comp(double x = .0, double y = .0) : x(x), y(y) {}
	inline comp conj() { return comp(x, -y); }
};

inline comp operator +(const comp &a, const comp &b) {
	return comp(a.x + b.x, a.y + b.y);
}

inline comp operator -(const comp &a, const comp &b) {
	return comp(a.x - b.x, a.y - b.y);
}

inline comp operator *(const comp &a, const comp &b) {
	return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

inline comp operator /(const comp &a, const double &b) {
	return comp(a.x / b, a.y / b);
}

namespace FFT {
	const double PI = acosl(-1.0);
	vector<comp> w[LOGN];
	vector<int> rv;

	void precalc() {
		forn(st, LOGN) {
			w[st].resize(1 << st);
			forn(i, 1 << st) {
				double ang = PI / (1 << st) * i;
				w[st][i] = comp(cos(ang), sin(ang));
			}
		}
		rv.assign(1 << LOGN, 0);
	    fore(i, 1, sz(rv))
			rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
	}
	
	inline void fft(comp a[N], int n, bool inv) {
		int ln = __builtin_ctz(n);
		forn(i, n) {
	        int ni = rv[i] >> (LOGN - ln);
	        if(i < ni) swap(a[i], a[ni]);
	    }
	
		for(int st = 0; st < ln; st++) {
			int len = 1 << st;
			for(int k = 0; k < n; k += (len << 1))
				fore(pos, k, k + len) {
					comp l = a[pos];
					comp r = a[pos + len] * w[st][pos - k];
					
					a[pos] = l + r;
					a[pos + len] = l - r;
				}
		}
	
		if(inv) {
			forn(i, n)
				a[i] = a[i] / n;
			reverse(a + 1, a + n);
		}
	}
	
	comp aa[N], bb[N], cc[N];
	
	inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) {
		int ln = 1;
		while(ln < (sza + szb)) // sometimes works max(sza, szb)
			ln <<= 1;
			
		forn(i, ln)
			aa[i] = (i < sza ? a[i] : comp());
		forn(i, ln)
			bb[i] = (i < szb ? b[i] : comp());
			
		fft(aa, ln, false);
		fft(bb, ln, false);
		
		forn(i, ln)
			cc[i] = aa[i] * bb[i];
			
		fft(cc, ln, true);
		
		szc = ln;
		forn(i, szc)
			c[i] = int(cc[i].x + 0.5);
	}
}

const int MOD = int(1e9) + 7;
int norm(int a) {
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}

li l, t;
int n;
vector<int> v;

inline bool read() {
	if(!(cin >> l >> t >> n))
		return false;
	v.resize(n);
	fore (i, 0, n)
		cin >> v[i];
	return true;
}

int mu[N], minD[N];
vector<int> divs[N];

void precalcDivs(int N) {
	fore (d, 1, N) {
		for (int v = d; v < N; v += d)
			divs[v].push_back(d);
	}
	
	mu[1] = 1;
	fore (d, 2, N) {
		if (minD[d] == 0)
			minD[d] = d;
		
		if (minD[d] != minD[d / minD[d]])
			mu[d] = -mu[d / minD[d]];
		
		for (int v = 2 * d; v < N; v += d) {
			if (minD[v] == 0)
				minD[v] = d;
		}
	}
}

int vs[2][N], res[N], ps[N];
li mxk[N];

inline void solve() {
	FFT::precalc();

	fore (i, 0, n) {
		vs[0][v[i]] = 1;
		vs[1][v[i]] = 1;
	}
	int sz = 1 + *max_element(v.begin(), v.end());
	
	int szRes = 0;
	FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
	
	fore (i, 0, szRes) {
		if (!(i & 1) && vs[0][i >> 1] > 0)
			res[i]--;
		if (res[i] > 0) {
			ps[i] = 1;
		}
	}
	
	memset(vs[1], 0, sizeof vs[1]);
	fore (i, 0, n)
		vs[1][sz - 1 - v[i]] = 1;
	FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
	
	fore (i, sz, szRes) {
		if (res[i] > 0) {
			ps[i - sz + 1] = 1;
		}
	}
	
	precalcDivs(2 * sz);
	
	int ans = 0;
	for (int i = N - 1; i > 0; i--) {
		if (ps[i] > 0)
			mxk[i] = max(mxk[i], t * 1ll * i / (2ll * l));
		
		for (int d : divs[i]) {
//			ans += mu[d] * (mxk[i] / d);
			ans = norm(ans + mu[d] * int((mxk[i] / d) % MOD));
			mxk[i / d] = max(mxk[i / d], mxk[i] / d);
		}
	}
	cout << ans << endl;
}

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

t = int(input())
for i in range(t):
    n = int(input())
    print('Alice' if n >= 5 else 'Bob')

for _ in range(int(input())):
	q = int(input())
	a = []
	cnt = 0
	for x in map(int, input().split()):
		nw_cnt = cnt + (len(a) > 0 and a[-1] > x)
		if nw_cnt == 0 or (nw_cnt == 1 and x <= a[0]):
			a.append(x)
			cnt = nw_cnt
			print('1', end="")
		else:
			print('0', end="")
	print()

#include <bits/stdc++.h>

using namespace std;

const int val[] = {1, 10, 100, 1000, 10000};
const int INF = 1e9;

string s;
int dp[2][5][2];

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> s;
    reverse(s.begin(), s.end());
    for (int j = 0; j < 5; ++j)
      dp[0][j][0] = dp[0][j][1] = -INF;
    dp[0][0][0] = 0;
    for (auto c : s) {
      int x = c - 'A';
      for (int j = 0; j < 5; ++j)
        dp[1][j][0] = dp[1][j][1] = -INF;
      for (int j = 0; j < 5; ++j) {
      	for (int t = 0; t < 2; ++t) {
      	  for (int y = 0; y < 5; ++y) {
      	  	int nj = max(j, y);
      	  	int nt = t + (x != y);
      	  	if (nt < 2) dp[1][nj][nt] = max(dp[1][nj][nt], dp[0][j][t] + (y < nj ? -val[y] : val[y]));
      	  }	
      	}
      }
      swap(dp[0], dp[1]);
    }
    int ans = -INF;
    for (int j = 0; j < 5; ++j)
      ans = max(ans, max(dp[0][j][0], dp[0][j][1]));
    cout << ans << '\n';
  }
}

def replace_char(s, i, c):
    return s[:i] + c + s[i + 1:]
    
def id(c):
    return ord(c) - ord('A')
    
def evaluate(s):
    t = s[::-1]
    ans = 0
    max_id = -1
    for x in t:
        i = id(x)
        if max_id > i:
            ans -= 10 ** i
        else:
            ans += 10 ** i
        max_id = max(max_id, i)
    return ans

t = int(input())
for i in range(t):
    s = input()
    candidates = []
    for x in ['A', 'B', 'C', 'D', 'E']:
        for y in ['A', 'B', 'C', 'D', 'E']:
            if not (x in s):
                continue
            candidates.append(replace_char(s, s.find(x), y))
            candidates.append(replace_char(s, s.rfind(x), y))
    print(max(map(evaluate, candidates)))

#include<bits/stdc++.h>

using namespace std;

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

void solve()
{
	int n;
	scanf("%d", &n);
	vector<pair<int, int>> s(n);
	for(int i = 0; i < n; i++)
		scanf("%d %d", &s[i].first, &s[i].second);
	
	vector<pair<int, int>> pairs;
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			if(max(s[i].first, s[j].first) <= min(s[i].second, s[j].second))
				pairs.push_back(make_pair(min(s[i].first, s[j].first), max(s[i].second, s[j].second)));
			
	int cnt_pairs = 0;
	sort(pairs.begin(), pairs.end(), comp);
	int last_pos = -1;
	for(auto x : pairs)
		if(x.first > last_pos)
		{
			cnt_pairs++;
			last_pos = x.second;
		}
		
	printf("%d\n", n - cnt_pairs * 2);
}

int main()
{
	int t;
	scanf("%d", &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;

struct seg{
	int l, r;
};

bool operator <(const seg &a, const seg &b){
	return a.l < b.l;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> a(n);
		forn(i, n) scanf("%d", &a[i]);
		long long m;
		scanf("%lld", &m);
		map<seg, int> used;
		used[{0, n}] = n;
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){
			return a[x] > a[y];
		});
		long long ans = 0;
		int j = 0;
		vector<long long> cnt(n + 1);
		for (int i = n; i >= 0; --i){
			while (j < n && a[ord[j]] >= i){
				auto it = used.upper_bound({ord[j], -1});
				--it;
				auto tmp = it->first;
				cnt[tmp.r - tmp.l] += it->second - i;
				used.erase(it);
				if (tmp.l != ord[j])
					used[{tmp.l, ord[j]}] = i;
				if (tmp.r != ord[j] + 1)
					used[{ord[j] + 1, tmp.r}] = i;
				++j;
			}
		}
		for (int i = n; i > 0; --i){
			long long t = min(cnt[i], m / i);
			ans += t * 1ll * (i - 1);
			m -= t * 1ll * i;
			if (t != cnt[i] && m > 0){
				ans += m - 1;
				m = 0;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define x first
#define y second
const int MAXN = 2e6 + 16;
int a[MAXN], b[MAXN];
pair<int, int> v[MAXN];
int section(pair<int, int> a) {
    if (a.x > 0 && a.y >= 0)
        return 0;
    else if (a.x <= 0 && a.y > 0)
        return 1;
    else if (a.x < 0 && a.y <= 0)
        return 2;
    else
        return 3;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (section(a) != section(b))
        return section(a) < section(b);
    else
        return (__int128)a.x * (__int128)b.y - (__int128)a.y * (__int128)b.x > 0;
}
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
signed main() {
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
		vector<int> t(4);
		for(int j = 0; j < 4; j++)
			cin >> t[j];
		a[i] = t[0] - t[1];
		b[i] = t[2] - t[3];
	}
    int it = 0;
    __int128 sx = 0, sy = 0;
    for (int i = 0; i < n; ++i) {
        v[i << 1].x = a[it];
        v[i << 1].y = b[it];
        ++it;
        v[i << 1 ^ 1].x = -v[i << 1].x;
        v[i << 1 ^ 1].y = -v[i << 1].y;
        if (!v[i << 1].x && !v[i << 1].y) {
            --i, --n;
            continue;
        }
        if (v[i << 1].y < 0 || (!v[i << 1].y && v[i << 1].x < 0))
            sx += v[i << 1].x, sy += v[i << 1].y;
    }
    sort(v, v + 2 * n, cmp);
    __int128 ans = sx * sx + sy * sy;
    for (int i = 0; i < 2 * n; ++i) {
        sx += v[i].x;
        sy += v[i].y;
        ans = std::max(ans, sx * sx + sy * sy);
    }
    print(ans);

    return 0;
}

for _ in range(int(input())):
	x, k = map(int, input().split())
	if x % k != 0:
		print(1)
		print(x)
	else:
		print(2)
		print(1, x - 1)

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = 1, cur = 1;
        for(int i = 1; i < n; i++)
        {
            if(s[i] != s[i - 1]) cur = 1;
            else cur++;
            ans = max(ans, cur);
        }
        cout << ans + 1 << endl;
    }    
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    char x = '0';
    for (auto& c : s) {
      if (c == '?') c = x;
      x = c;
    }
    cout << s << '\n';
  }
}

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> bal(n + 1);
        for(int j = 0; j < n; j++)
            if(s[j] == '(')
                bal[j + 1] = bal[j] + 1;
            else
                bal[j + 1] = bal[j] - 1;

        if(bal.back() != 0)
            cout << -1 << endl;
        else
        {
            if(*min_element(bal.begin(), bal.end()) == 0 || *max_element(bal.begin(), bal.end()) == 0)
            {
                cout << 1 << endl;
                for(int j = 0; j < n; j++)
                {
                    if(j) cout << " ";
                    cout << 1;
                }
                cout << endl;
            }
            else
            {
                cout << 2 << endl;
                vector<int> ans;
                int cur = 0;
                while(cur < n)
                {
                    int w = (s[cur] == '(' ? 1 : 2);
                    do
                    {
                        cur++;
                        ans.push_back(w);
                    }
                    while(bal[cur] != 0);
                }
                for(int j = 0; j < n; j++)
                {
                    if(j) cout << " ";
                    cout << ans[j];
                }
                cout << endl;
            }
        }
    }    
}

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

int main() {
	int k;
	scanf("%d", &k);
	vector<int> a(1 << k);
	forn(i, 1 << k){
		scanf("%d", &a[i]);
		if (a[i] != -1) --a[i];
	}
	int ans = 1;
	for (int st = k - 1; st >= 0; --st){
		int big = 1 << st, fr = 0;
		vector<int> na(1 << st);
		forn(i, 1 << st){
			int mn = min(a[2 * i], a[2 * i + 1]);
			int mx = max(a[2 * i], a[2 * i + 1]);
			if (mn == -1){
				if (mx >= (1 << st)){
					--big;
					na[i] = -1;
				}
				else if (mx != -1){
					na[i] = mx;
				}
				else{
					na[i] = -1;
					++fr;
				}
				continue;
			}
			if ((a[2 * i] < (1 << st)) == (a[2 * i + 1] < (1 << st))){
				puts("0");
				return 0;
			}
			na[i] = mn;
			--big;
		}
		forn(_, fr) ans = ans * 2ll % MOD;
		for (int i = 1; i <= big; ++i) ans = ans * 1ll * i % MOD;
		a = na;
	}
	printf("%d\n", ans);
}

#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, k;
		scanf("%d%d", &n, &k);
		vector<int> a(n);
		forn(i, n) scanf("%d", &a[i]);
		
		vector<int> pr(n + 1), su(n + 1);
		auto check = [&](long long x){
			forn(_, 2){
				priority_queue<int> cur;
				pr[0] = 0;
				long long cursum = 0;
				forn(i, n){
					cur.push(a[i]);
					cursum += a[i];
					while (cursum > x){
						cursum -= cur.top();
						cur.pop();
					}
					pr[i + 1] = cur.size();
				}
				reverse(a.begin(), a.end());
				swap(pr, su);
			}
			reverse(su.begin(), su.end());
			forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
			return false;
		};
		
		long long l = 1, r = accumulate(a.begin(), a.end(), 0ll);
		long long res = 0;
		while (l <= r){
			long long m = (l + r) / 2;
			if (check(m)){
				res = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%lld\n", res);
	}
}

#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, k;
		scanf("%d%d", &n, &k);
		vector<int> a(n);
		forn(i, n) scanf("%d", &a[i]);
		vector<pair<int, int>> xs(n);
		forn(i, n) xs[i] = {a[i], i};
		sort(xs.begin(), xs.end());
		forn(i, n) a[i] = lower_bound(xs.begin(), xs.end(), make_pair(a[i], i)) - xs.begin();
		
		vector<int> lstpr(n), lstsu(n);
		forn(_, 2){
			set<int> cur;
			forn(i, n){
				auto it = cur.insert(a[i]).first;
				if (it == cur.begin())
					lstpr[i] = n;
				else
					lstpr[i] = *(--it);
			}
			swap(lstpr, lstsu);
			reverse(a.begin(), a.end());
		}
		
		vector<int> pr(n + 1), su(n + 1);
		vector<int> prv(n + 2), nxt(n + 2);
		
		auto check = [&](long long x){
			forn(_, 2){
				int cnt = 0;
				prv[n + 1] = n;
				nxt[n] = n + 1;
				pr[0] = 0;
				int mn = 1e9;
				long long cursum = 0;
				forn(i, n){
					if (mn < a[i]){
						pr[i + 1] = cnt;
						continue;
					}
					nxt[a[i]] = nxt[lstpr[i]];
					prv[nxt[a[i]]] = a[i];
					prv[a[i]] = lstpr[i];
					nxt[prv[a[i]]] = a[i];
					cursum += xs[a[i]].first;
					++cnt;
					while (cursum > x){
						mn = min(mn, prv[n + 1]);
						cursum -= xs[prv[n + 1]].first;
						prv[n + 1] = prv[prv[n + 1]];
						nxt[prv[n + 1]] = n + 1;
						--cnt;
					}
					pr[i + 1] = cnt;
				}
				reverse(a.begin(), a.end());
				swap(lstpr, lstsu);
				swap(pr, su);
			}
			reverse(su.begin(), su.end());
			forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
			return false;
		};
		
		long long l = 1, r = 0;
		for (int x : a) r += xs[x].first;
		long long res = 0;
		while (l <= r){
			long long m = (l + r) / 2;
			if (check(m)){
				res = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%lld\n", res);
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    s = s.substr(0, s.size() / 2);
    int k = unique(s.begin(), s.end()) - s.begin();
    cout << (k == 1 ? "NO" : "YES") << '\n';
  }
}

for _ in range(int(input())):
	n, k = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	ans = 0
	pr = [0] * (n + 1)
	for i in range(n):
		pr[i + 1] = pr[i] + a[i]
	for i in range(k + 1):
		ans = max(ans, pr[n - (k - i)] - pr[2 * i])
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    n = unique(a.begin(), a.end()) - a.begin();
    int ans = n;
    for (int i = 0; i + 2 < n; ++i) {
      ans -= (a[i] < a[i + 1] && a[i + 1] < a[i + 2]);
      ans -= (a[i] > a[i + 1] && a[i + 1] > a[i + 2]);
    }
    cout << ans << '\n';
  }
}

n, q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
pr = [10**9 for i in range(n + 1)]
for i in range(n):
	pr[i + 1] = min(pr[i], a[i] - i)
s = sum(a) - n * (n - 1) // 2
ans = []
for k in map(int, input().split()):
	if k < n:
		ans.append(min(pr[k] + k, a[k]))
		continue
	if k % 2 == n % 2:
		ns = s - pr[n] * n
		ans.append(pr[n] + k - (max(0, (k - n) // 2 - ns) + n - 1) // n)
	else:
		nmn = min(pr[n - 1], a[n - 1] - k)
		ns = (s + (n - 1) - k) - nmn * n
		ans.append(nmn + k - (max(0, (k - (n - 1)) // 2 - ns) + n - 1) // n)
print(*ans)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y, int mod = MOD)
{
	return ((x + y) % mod + mod) % mod;
}

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

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

vector<int> psum(vector<int> v)
{
	vector<int> ans(1, 0);
	for(auto x : v) ans.push_back(add(ans.back(), x));
	return ans;
}

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	cin >> a[0];
	int x, y, m, k;
	cin >> x >> y >> m >> k;
	for(int i = 1; i < n; i++)
		a[i] = add(mul(a[i - 1], x, m), y, m);
	
	for(int i = 0; i <= k; i++)
		a = psum(a);
	long long ans = 0;
	
	for(int i = 1; i <= n; i++)
		ans ^= (a[i + 1] * 1ll * i);
	cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

int n;
vector<long long> dp_before, dp_cur;
vector<vector<long long>> bst;

void compute(int l, int r, int optl, int optr){
	if (l > r) return;
	int mid = (l + r) / 2;
	pair<long long, int> best = {-1, -1};
	for (int k = optl; k <= min(mid, optr); k++)
		best = max(best, {(k ? dp_before[k - 1] : 0) + bst[k][mid], k});
	dp_cur[mid] = best.first;
	int opt = best.second;
	compute(l, mid - 1, optl, opt);
	compute(mid + 1, r, opt, optr);
}

struct node{
    long long c0;
    int c1;
};

vector<node> f;

void update(int x, int a, int b){
	for (int i = x; i < int(f.size()); i |= i + 1){
		f[i].c0 += b;
		f[i].c1 += a;
	}
}

void update(int l, int r, int a, int b){
	update(l, a, b);
	update(r, -a, -b);
}

long long get(int pos, int x){
	long long res = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		res += f[i].c0 + f[i].c1 * 1ll * pos;
	return res;
}

int main() {
	int k, x, m;
	scanf("%d%d%d%d", &n, &k, &x, &m);
	vector<seg> a(n);
	forn(i, n) scanf("%d%d", &a[i].l, &a[i].r);
	sort(a.begin(), a.end(), [&](const seg &a, const seg &b){
		return a.l + a.r < b.l + b.r;
	});
	
	vector<int> pos;
	forn(i, n){
		pos.push_back(a[i].l);
		pos.push_back(a[i].r - m);
	}
	sort(pos.begin(), pos.end());
	pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
	int cds = pos.size();
	
	vector<array<int, 4>> npos(n);
	forn(i, n){
		npos[i][0] = lower_bound(pos.begin(), pos.end(), a[i].l - m) - pos.begin();
		npos[i][1] = lower_bound(pos.begin(), pos.end(), a[i].l) - pos.begin();
		npos[i][2] = lower_bound(pos.begin(), pos.end(), a[i].r - m) - pos.begin();
		npos[i][3] = lower_bound(pos.begin(), pos.end(), a[i].r) - pos.begin();
	}
	
	vector<long long> pr(n + 1);
	forn(i, n) pr[i + 1] = pr[i] + x - (m + a[i].r - a[i].l);
	
	auto upd = [&](int i){
		if (a[i].r - a[i].l >= m){
			update(npos[i][0], npos[i][1], 1, m - a[i].l);
			update(npos[i][1], npos[i][2], 0, m);
			update(npos[i][2], npos[i][3], -1, a[i].r);
		}
		else{
			update(npos[i][0], npos[i][2], 1, m - a[i].l);
			update(npos[i][2], npos[i][1], 0, a[i].r - a[i].l);
			update(npos[i][1], npos[i][3], -1, a[i].r);
		}
	};
	
	bst.resize(n, vector<long long>(n, -1));
	vector<vector<int>> opt(n, vector<int>(n));
	forn(r, n) for (int l = r; l >= 0; --l){
		if (l == r) f.assign(cds, {0, 0});
		upd(l);
		int L = (l == r ? (l == 0 ? 0 : opt[l - 1][l - 1]) : opt[l][r - 1]);
		int R = (l == r ? int(pos.size()) - 1 : opt[l + 1][r]);
		for (int k = L; k <= R; ++k){
			long long cur = pr[r + 1] - pr[l] + get(pos[k], k);
			if (cur > bst[l][r]){
				bst[l][r] = cur;
				opt[l][r] = k;
			}
		}
	}
	
	dp_before.resize(n);
	dp_cur.resize(n);
	for (int i = 0; i < n; i++)
		dp_before[i] = bst[0][i];

	for (int i = 1; i < k; i++){
		compute(0, n - 1, 0, n - 1);
		dp_before = dp_cur;
	}
	
	printf("%lld\n", dp_before[n - 1]);
	return 0;
}

for _ in range(int(input())):
	n, k = map(int, input().split())
	for x in range(2):
		if n - x * k >= 0 and (n - x * k) % 2 == 0:
			print("YES")
			break
	else:
		print("NO")

for _ in range(int(input())):
	a, b = map(int, input().split())
	ans = a + b
	for m in range(1, 100000):
		ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1))
	print(ans)

#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> s(2);
		for(int j = 0; j < 2; j++)
			scanf("%d", &s[j]);
		vector<pair<int, int>> a(n);
		for(int j = 0; j < n; j++)
		{
			scanf("%d", &a[j].first);
			a[j].second = j + 1;
		}
		sort(a.begin(), a.end());
		reverse(a.begin(), a.end());
		vector<vector<int>> lists(2);
		for(int j = 0; j < n; j++)
		{
			int cost1 = s[0] * (lists[0].size() + 1);
			int cost2 = s[1] * (lists[1].size() + 1);
			if(cost1 < cost2)
				lists[0].push_back(a[j].second);
			else
				lists[1].push_back(a[j].second);
		}
		for(int j = 0; j < 2; j++)
		{
		    cout << lists[j].size();
		    for(auto x : lists[j]) cout << " " << x;
		    cout << endl;
		}
	}
}

fun main() {
    repeat(readln().toInt()) {
        val (n, k) = readln().split(' ').map { it.toInt() }
        val f = readln().split(' ').map { it.toLong() }
        val d = readln().split(' ').map { it.toLong() }

        fun checkAround(pos : Long) : Int {
            val qs = Array(2 * k + 1) { MutableList(0) { 0 } }

            fun inside(x : Long, pos: Long) = (pos - k <= x) && (x <= pos + k)
            for (i in f.indices) {
                var newD = maxOf(1L, pos / f[i])
                if (newD != d[i] && newD + 1 != d[i] && inside(d[i] * f[i], pos)) {
                    val id = (i + 1)
                    qs[(d[i] * f[i] - pos + k).toInt()].add(id)
                }
                repeat(2) {
                    if (inside(newD * f[i], pos)) {
                        val id = if (newD == d[i]) (i + 1) else -(i + 1)
                        qs[(newD * f[i] - pos + k).toInt()].add(id)
                    }
                    newD++
                }
                
            }

            val cntPerId = IntArray(n) { 0 }
            var cntDistinct = 0
            var cntGood = 0

            fun addToSeg(cid : Int) {
                val id = -1 + if (cid > 0) cid else -cid
                val c = if (cid > 0) 1 else 0

                if (cntPerId[id] == 0)
                    cntDistinct++
                cntPerId[id]++

                cntGood += c
            }
            fun eraseFromSeg(cid : Int) {
                val id = -1 + if (cid > 0) cid else -cid
                val c = if (cid > 0) 1 else 0

                cntPerId[id]--
                if (cntPerId[id] == 0)
                    cntDistinct--

                cntGood -= c
            }
            var ans = 0
            for (p in 0 until k)
                qs[p].forEach { addToSeg(it) }
            for (p in 0..k) {
                qs[p + k].forEach { addToSeg(it) }
                if (cntDistinct == n)
                    ans = maxOf(ans, cntGood)
                qs[p].forEach { eraseFromSeg(it) }
            }
            return n - ans
        }

        var ans = n
        for (i in f.indices) {
            ans = minOf(ans, checkAround(d[i] * f[i]))
        }
        println(ans)
    }
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const li INF = (li)(1e18);
const int N = 200043;

struct data
{
	array<array<long long, 2>, 2> d;
	data() {
	    for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
	};
	data(li x)
	{
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
		d[0][0] = 0;
		d[1][1] = x;
	};
	data(data l, data r)
	{
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				d[i][j] = INF;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					for(int x = 0; x < 2; x++)
					{
						if(j == 0 && k == 0) continue;
						d[i][x] = min(d[i][x], l.d[i][j] + r.d[k][x]);
					}
	};
};

data T[4 * N];
li a[N];

void recalc(int v)
{
	T[v] = data(T[v * 2 + 1], T[v * 2 + 2]);
}

void build(int v, int l, int r)
{
	if(l == r - 1) T[v] = data(a[l]);
	else
	{
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m, r);
		recalc(v);
	}
}

void upd(int v, int l, int r, int pos, li val)
{
	if(l == r - 1)
	{
		a[l] = val;
		T[v] = data(a[l]);
	}
	else
	{
		int m = (l + r) / 2;
		if(pos < m)
			upd(v * 2 + 1, l, m, pos, val);
		else
			upd(v * 2 + 2, m, r, pos, val);
		recalc(v);
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++)
	{
		scanf("%lld", &a[i]);
	}
	build(0, 0, n - 1);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		int x;
		li k;
		scanf("%d %lld", &x, &k);
		upd(0, 0, n - 1, x - 1, k);
		printf("%lld\n", T[0].d[1][1] * 2);
	}
}

#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

const int N = 200002;
const int V = 50 * N;

using pt = pair<int, int>;

int n, m;
pt a[N];
vector<pt> t[4 * N];
int p[N], rk[N], vs[N];
int cntV;
pt g[V];
bool ans[V];

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

int k;
int* ptr[V];
int val[V];

void upd(int &a, int b) {
  ptr[k] = &a;
  val[k] = a;
  k += 1;
  a = b;
}

int getp(int v) {
  return p[v] == v ? v : getp(p[v]);
}

void unite(int v, int u) {
  v = getp(v), u = getp(u);
  if (v == u) return;
  if (rk[v] > rk[u]) swap(v, u);
  upd(p[v], u);
  g[cntV] = {vs[v], vs[u]};
  upd(vs[u], cntV++);
  if (rk[v] == rk[u])
    upd(rk[u], rk[u] + 1);
}

void solve(int v, int l, int r) {
  int cur = k;
  for (auto& [v, u] : t[v]) 
    unite(v, u);
  if (l + 1 == r) {
    ans[vs[getp(0)]] = 1;
  } else {
    int m = (l + r) / 2;
    solve(v * 2 + 1, l, m);
    solve(v * 2 + 2, m, r);
  }
  while (k > cur) {
    k -= 1;
    (*ptr[k]) = val[k];
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> a[i].first >> a[i].second;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    int L = max(a[x].first, a[y].first);
    int R = min(a[x].second, a[y].second);
    upd(0, 0, N, L, R + 1, {x, y});
  }
  
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    rk[i] = 1;
    vs[i] = i;
    g[i] = {-1, -1};
  }
  
  cntV = n;
  solve(0, 0, N);
  
  queue<int> q;
  for (int i = 0; i < cntV; ++i) if (ans[i]) 
    q.push(i);
  
  while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : {g[v].first, g[v].second}) {
      if (u != -1 && !ans[u]) {
        ans[u] = true;
        q.push(u);
      }
    }
  }
  
  for (int i = 0; i < n; ++i) if (ans[i])
    cout << i + 1 << ' ';
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    string s;
    cin >> s;
    vector<int> cnt(10);
    for (auto c : s) ++cnt[c - '0'];
    int mx = *max_element(cnt.begin(), cnt.end());
    if (mx == 4) cout << -1;
    else if (mx == 3) cout << 6;
    else cout << 4;
    cout << '\n';
  }
}

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toLong()
        var l = (-1).toLong()
        var r = 1e9.toLong()
        while (r - l > 1) {
            val mid = (l + r) / 2
            if (mid * mid >= n)
                r = mid
            else
                l = mid
        }
        println(r - 1)
    }
}

import kotlin.math.sqrt

fun main() {
    repeat(readln().toInt()) {
        val n = readln().toLong()
        var ans = sqrt(n.toDouble()).toLong()
        while (ans * ans > n)
            ans--
        while (ans * ans < n)
            ans++
        println(ans - 1)
    }
}

def solve(n, k):
    if n == 0:
        return []
    if k < n:
        a = [-1 for i in range(n)]
        if k > 0:
            a[k - 1] = 200
        a[k] = -400
    else:
        a = solve(n - 1, k - n)
        a.append(1000)
    return a

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    b = solve(n, k)
    print(*b)

#include <bits/stdc++.h>

using namespace std;

const long long pw10 = 1e12;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    string s;
    cin >> s;
    int n = s.size();
    int cnt0 = 0, cnt1 = count(s.begin(), s.end(), '1');
    long long ans = 1e18;
    if (n == 1) ans = 0;
    for (int i = 0; i < n - 1; ++i) {
      cnt0 += s[i] == '0';
      cnt1 -= s[i] == '1';
      int k = cnt0 + cnt1 + (s[i] == '1') + (s[i + 1] == '0');
      long long cur = (n - k) * (pw10 + 1);
      if (s[i] > s[i + 1]) cur += pw10;
      ans = min(ans, cur); 
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	vector<int> v(n);
	forn(i, n) scanf("%d", &v[i]);
	vector<vector<int>> ans(a + 1, vector<int>(b + 1));
	forn(cd, a + b + 1){
		int l = max(0, cd - b), r = min(a, cd);
		int sum = 0;
		for (int x : v){
			sum += x;
			l = max({l, sum, cd + sum - b});
			r = min({r, a + sum, sum + cd});
		}
		if (l > r) l = r = max(0, cd - b);
		int res = l;
		for (int x : v){
			if (x > 0)
				res -= min({res, x, b - (cd - res)});
			else
				res += min({cd - res, -x, a - res});
		}
		forn(c, cd + 1) if (c <= a && cd - c <= b){
			ans[c][cd - c] = (c < l ? res : (c > r ? res + r - l : res + c - l));
		}
	}
	forn(i, a + 1){
		forn(j, b + 1)
			printf("%d ", ans[i][j]);
		puts("");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

void solve(){
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> b(n);
	forn(i, n) scanf("%d", &b[i]);
	
	vector<long long> pr(2 * n + 1);
	forn(i, 2 * n) pr[i + 1] = pr[i] + a[i % n];
	
	vector<long long> dist(n);
	vector<long long> cost(n);
	int cnt = 0;
	for (int i = 2 * n - 1; i >= 0; --i){
		if (i < n){
			if (b[i] == 2){
				dist[i] = 1;
				cost[i] = a[i] * 2;
			}
			else if (cnt == 0){
				dist[i] = 1;
				cost[i] = a[i];
			}
			else{
				int j = lower_bound(pr.begin() + i, pr.begin() + i + cnt + 1, pr[i] + k) - pr.begin();
				assert(j > i);
				dist[i] = j - i;
				if (pr[j] - pr[i] <= k)
					cost[i] = pr[j] - pr[i];
				else
					cost[i] = 2 * (pr[j] - pr[i]) - k;
			}
		}
		if (b[i % n] == 2) ++cnt;
		else cnt = 0;
	}
	
	int pw = 0;
	while ((1 << pw) <= n) ++pw;
	
	vector<vector<long long>> distk(pw, dist);
	vector<vector<long long>> costk(pw, cost);
	for (int j = 1; j < pw; ++j) forn(i, n){
		distk[j][i] = distk[j - 1][i] + distk[j - 1][(i + distk[j - 1][i]) % n];
		costk[j][i] = costk[j - 1][i] + costk[j - 1][(i + distk[j - 1][i]) % n];
	}
	
	forn(i, n){
		int pos = i;
		long long tot = 0;
		long long ans = 0;
		for (int j = pw - 1; j >= 0; --j) if (tot + distk[j][pos] <= n){
			tot += distk[j][pos];
			ans += costk[j][pos];
			pos = (pos + distk[j][pos]) % n;
		}
		if (tot < n) ans += pr[i + n] - pr[i + tot];
		printf("%lld ", ans);
	}
	puts("");
}

int main(){
	int tc;
	scanf("%d", &tc);
	while (tc--) solve();
}

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

const int MOD = 998244353;

int add(int x, int y)
{
    return ((x + y) % MOD + MOD) % MOD;
}

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

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

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

int divide(int x, int y)
{
    return mul(x, inv(y));
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> a(n);
    for(int i = 0; i < n; i++)    
        scanf("%d", &a[i]);
    
    reverse(a.begin(), a.end());

    vector<int> fact(n + 1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = mul(fact[i - 1], i);

    // for each player, we find the first player which doesn't conflict with them
    vector<int> first_no_conflict(n);
    for(int i = 0; i < n; i++)
    {
        if(i) first_no_conflict[i] = first_no_conflict[i - 1];
        while(first_no_conflict[i] < n && a[first_no_conflict[i]] >= a[i] - k)
            first_no_conflict[i]++;
    }

    vector<int> dp(n + 1);
    if(a[0] - a[1] > k) dp[1] = 1;
    for(int i = 1; i < n; i++)
    {
        // first choice: put a[i] on the first position
        // then we put all which conflict with a[i] on any position other than 1
        int no_of_conflicting = first_no_conflict[i] - i - 1;
        // put all conflicting with a[i] on any position other than 1
        // the first one chooses from i positions, the second - from i+1 positions, and so on
        // so the number of ways is fact[i + no_of_conflicting - 1] / fact[i - 1]
        dp[i + no_of_conflicting + 1] = add(dp[i + no_of_conflicting + 1], mul(dp[i], divide(fact[i + no_of_conflicting - 1], fact[i - 1])));

        // second choice: put a[i] on any other position
        dp[i + 1] = add(dp[i + 1], mul(dp[i], i));
    }

    printf("%d\n", dp[n]);
}