for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			print(i + 1, i + 2)
			break
	else:
		print(-1, -1)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s;
    cin >> n >> s;
    vector<int> id;
    for (int i = 0; i < n; ++i) if (s[i] == '2')
      id.push_back(i);
    int k = id.size();
    if (k == 1 || k == 2) {
      cout << "NO\n";
      continue;
    }
    vector<string> t(n, string(n, '='));
    for (int i = 0; i < n; ++i) t[i][i] = 'X';
    for (int i = 0; i < k; ++i) {
      int x = id[i], y = id[(i + 1) % k];
      t[x][y] = '+';
      t[y][x] = '-';
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) cout << t[i] << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int mx = *max_element(a.begin(), a.end());
    int cmx = count(a.begin(), a.end(), mx);
    int k = count(a.begin(), a.end(), mx - 1);
    int ans = 1, sub = 1;
    for (long long i = 1; i <= n; ++i) {
      ans = ans * i % MOD;
      if (i != k + 1) sub = sub * i % MOD;
    }
    if (cmx == 1) ans = (ans - sub + MOD) % MOD;
    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 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);

int n, m, k;
vector<int> x, y;
vector<pt> ps;

inline bool read() {
	if(!(cin >> n >> m >> k))
		return false;
	x.resize(n);
	fore (i, 0, n)
		cin >> x[i];
	y.resize(m);
	fore (i, 0, m)
		cin >> y[i];
	ps.resize(k);
	fore (i, 0, k)
		cin >> ps[i].x >> ps[i].y;
	
	return true;
}

inline void solve() {
	li ans = 0;
	
	fore (_i, 0, 2) {
		vector<int> cntY(m, 0);
		sort(all(ps));
		
		vector<pt> bord(k);
		
		int u = 0;
		while (u < k) {
			int v = u;
			while (v < k && ps[v].x == ps[u].x)
				v++;
			
			fore (i, u, v) {
				int r = int(lower_bound(all(y), ps[i].y) - y.begin());
				int l = r;
				if (y[l] > ps[i].y)
					l--;
				assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
				
				bord[i] = {l, r};
			}
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				ans += cntY[bord[i].x];
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				cntY[bord[i].x]++;
			
			u = v;
		}
		
		
		fore (i, 0, k)
			swap(ps[i].x, ps[i].y);
		swap(x, y);
		swap(n, m);
	}
	
	cout << ans << endl;
}

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

#include <bits/stdc++.h>     

using namespace std;

const int MOD = 998244353;

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

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

int binpow(int x, int y)
{
 	int z = 1;
 	while(y)
 	{
 	 	if(y & 1) z = mul(z, x);
 	 	x = mul(x, x);
 	 	y >>= 1;
 	}
 	return z;
}

vector<int> evaluate(int n, int choice_mask)
{
 	int cur_place = n / 2 + 1;
 	int cur_bit = n - 2;
 	vector<int> p(n);
 	vector<int> c(n);
 	for(int i = 0; i < n; i++)
 		c[i] = i;
 	while(c.size() != 1)
 	{
 		vector<int> nc;
 	 	for(int i = 0; i < c.size(); i += 2)
 	 	{
 	 	 	if(choice_mask & (1 << cur_bit))
 	 	 	{
 	 	 		p[c[i]] = cur_place;
 	 	 		nc.push_back(c[i + 1]);
 	 	 	}
 	 	 	else
 	 	 	{
 	 	 		p[c[i + 1]] = cur_place;
 	 	 		nc.push_back(c[i]);
 	 	 	}
 	 	 	cur_bit--;
 	 	}
 	 	c = nc;
 	 	cur_place /= 2;
  		cur_place++;
	}
	p[c[0]] = 1;
	return p;
}

vector<int> adjust(int n, vector<int> p, bool winning)
{
	for(int i = 0; i < n; i++)
	{
		if(p[i] == 1)
		{
		 	if(!winning) p[i]++;	
		}
		else
		 	p[i] = p[i] * 2 - 1;
	}
	return p;
}	

int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
{
	if(partial)
		p = adjust(n, p, winning);
 	int res = 0;
 	for(int i = 0; i < n; i++)
 		res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
 	return res;
}

int main()
{
 	int k, A, h;
 	cin >> k >> A >> h;
 	if(k <= 4)
 	{
 		for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
 		{             
 			vector<int> p = evaluate(1 << k, i);
 			if(get_hash(1 << k, p, A) == h)
 			{
 		 		for(auto x : p) cout << x << " ";
 		 		cout << endl;
 		 		return 0;
 			}
 		}
 	}
 	else
 	{
 		int mask_left = -1;
 		int mask_right = -1;
 		bool left_win = false;
 		for(int c = 0; c < 2; c++)
 		{
 		 	map<int, int> left_map;
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int left_hash = get_hash(16, p, A, true, c == 0, 0);
 		 	 	left_map[left_hash] = i;	
 		 	}
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int right_hash = get_hash(16, p, A, true, c == 1, 16);
 		 	 	int left_hash = add(h, MOD - right_hash);
 		 	 	if(left_map.count(left_hash))
 		 	 	{
 		 	 	 	mask_left = left_map[left_hash];
 		 	 	 	mask_right = i;
 		 	 	 	left_win = (c == 0);
 		 	 	}
 		 	}
 	 	}
 	 	if(mask_left != -1)
 		{
 	 		vector<int> ans_left = evaluate(16, mask_left);
 	 		vector<int> ans_right = evaluate(16, mask_right);
 	 		ans_left = adjust(16, ans_left, left_win);
 	 		ans_right = adjust(16, ans_right, !left_win);
 	 		for(auto x : ans_left)
 	 			cout << x << " ";
 	   		for(auto x : ans_right)
 	   			cout << x << " ";
 	   		return 0;
 		}        
 	}
 	cout << -1 << endl;
 	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

vector<vector<char>> g;
map<long long, bool> dp;

void brute(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		vector<vector<char>> dp2(1 << n, vector<char>(n));
		vector<int> pos1(n), pos2(n);
		forn(i, p.size()){
			pos1[p[i]] = pos2[p[i]];
			pos2[p[i]] = i;
		}
		forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
		forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
			forn(j, n) if (!((mask >> j) & 1)){
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
			}
		}
		forn(i, n) if (dp2[(1 << n) - 1][i]){
			long long num = 0;
			for (int x : p) num = num * 6 + x;
			dp[num] = true;
			break;
		}
		return;
	}
	for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
		p[x] = p[y] = n;
		brute(n + 1, p);
		p[x] = p[y] = -1;
	}
}

bool dfs(vector<int> p){
	vector<int> used(int(p.size()), -1);
	int cnt = 0;
	forn(i, p.size()) if (used[p[i]] == -1)
		used[p[i]] = cnt++;
	long long num = 0;
	for (int& x : p){
		x = used[x];
		num = num * 6 + x;
	}
	if (dp.count(num)) return dp[num];
	bool res = false;
	vector<int> cur(cnt);
	forn(i, p.size()) ++cur[p[i]];
	forn(i, p.size()) if (cur[p[i]] > 2){
		int x = p[i];
		for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
			p[i] = p[j] = cnt;
			if (dfs(p)){
				res = true;
				break;
			}
			p[i] = p[j] = x;
		}
		break;
	}
	return dp[num] = res;
}

void brute2(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		dfs(p);
		return;
	}
	forn(i, n + 1){
		for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
			p[x] = p[y] = i;
			brute2(max(n, i + 1), p);
			p[x] = p[y] = -1;
		}
	}
}

int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	g.resize(n, vector<char>(n));
	forn(_, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v][u] = g[u][v] = 1;
	}
	vector<int> cur(n, -1);
	brute(0, cur);
	brute2(0, cur);
	vector<long long> fact(k + 1);
	fact[0] = 1;
	for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
	long long ans = 0;
	for (auto it : dp) if (it.second){
		long long num = it.first;
		long long mx = 1;
		while (num){
			mx = max(mx, num % 6 + 1);
			num /= 6;
		}
		if (mx <= k){
			ans += fact[k] / fact[k - mx];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    cout << max(6LL, n + 1) / 2 * 5 << '\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 x first
#define y second

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

const int INF = int(1e9);

int W, H;
int x1, y1, x2, y2;
int w, h;

inline bool read() {
	if(!(cin >> W >> H))
		return false;
	cin >> x1 >> y1 >> x2 >> y2;
	cin >> w >> h;
	return true;
}

inline void solve() {
	int ans = INF;
	if (x2 - x1 + w <= W) {
		ans = min(ans, max(0, w - x1));
		ans = min(ans, max(0, x2 - (W - w)));
	}
	if (y2 - y1 + h <= H) {
		ans = min(ans, max(0, h - y1));
		ans = min(ans, max(0, y2 - (H - h)));
	}
	if (ans == INF)
		cout << -1 << endl;
	else
		cout << double(ans) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif	
	cout << fixed << setprecision(9);
	int t; cin >> t;
	while(t--) {
		(read());
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 2e9 + 10;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n;
		scanf("%d", &n);
		vector<vector<int>> a(2, vector<int>(n));
		forn(i, 2) forn(j, n)
			scanf("%d", &a[i][j]);
		int ans = INF;
		int sum1 = 0, sum2 = 0;
		forn(i, n) sum1 += a[0][i];
		forn(i, n){
			sum1 -= a[0][i];
			ans = min(ans, max(sum1, sum2));
			sum2 += a[1][i];
		}
		printf("%d\n", ans);
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<vector<int>> pr(6, vector<int>(n + 1));
  string t = "abc";
  int cur = 0;
  do {
    for (int i = 0; i < n; ++i)
      pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
    ++cur;
  } while (next_permutation(t.begin(), t.end()));
  while (m--) {
    int l, r;
    cin >> l >> r;
    int ans = n;
    for (int i = 0; i < 6; ++i)
      ans = min(ans, pr[i][r] - pr[i][l - 1]);
    cout << ans << "\n";
  }
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

vector<int> t, ps;

void push(int v){
	if (v * 2 + 1 < int(ps.size())){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v];
	ps[v] = 0;
}

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

int get(){
	return t[1] + ps[1];
}

struct seg{
	int l, r, w;
};

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<seg> a(n);
	forn(i, n){
		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
		--a[i].l, --a[i].r;
	}
	--m;
	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
		return a.w < b.w;
	});
	t.resize(4 * m);
	ps.resize(4 * m);
	int ans = INF;
	int j = 0;
	forn(i, n){
		while (j < n && get() == 0){
			upd(1, 0, m, a[j].l, a[j].r, 1);
			++j;
		}
		if (get() == 0){
			break;
		}
		ans = min(ans, a[j - 1].w - a[i].w);
		upd(1, 0, m, a[i].l, a[i].r, -1);
	}
	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 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);

int n, q;
vector< array<int, 3> > es;

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	es.resize(q);
	fore (i, 0, q) {
		cin >> es[i][0] >> es[i][1] >> es[i][2];
		es[i][0]--;
		es[i][1]--;
	}
	return true;
}

vector< vector<pt> > g;

const int LOG = 19;
vector<int> up[LOG];
vector<int> tin, tout;
vector<int> xr;
int T = 0;

void dfs(int v, int p, int curXor) {
	tin[v] = T++;
	xr[v] = curXor;
	up[0][v] = p;
	fore (pw, 1, LOG)
		up[pw][v] = up[pw - 1][up[pw - 1][v]];
	
	for (auto [to, w] : g[v]) {
		if (to == p)
			continue;
		dfs(to, v, curXor ^ w);
	}
	tout[v] = T;
}

void buildLCA() {
	fore (pw, 0, LOG)
		up[pw].resize(n);
	tin.assign(n, -1);
	tout.assign(n, -1);
	xr.assign(n, 0);
	
	T = 0;
	fore (v, 0, n) {
		if (tin[v] != -1)
			continue;
		dfs(v, v, 0);
	}
}

int isPar(int p, int v) {
	return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int lca(int u, int v) {
	if (isPar(u, v)) return u;
	if (isPar(v, u)) return v;
	
	for (int pw = LOG - 1; pw >= 0; pw--) {
		if (!isPar(up[pw][v], u))
			v = up[pw][v];
	}
	return up[0][v];
}

vector<int> par, rk;

void init(int n) {
	par.assign(n, 0);
	iota(par.begin(), par.end(), 0);
	rk.assign(n, 1);
}

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

bool unite(int u, int v) {
	u = top(u);
	v = top(v);
	if (u == v)
		return false;
	if (rk[u] < rk[v])
		swap(u, v);
	par[v] = u;
	rk[u] += rk[v];
	return true;
}

vector<int> F;
void inc(int pos, int val) {
	for(; pos < sz(F); pos |= pos + 1)
		F[pos] += val;
}
int sum(int pos) {
	int ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += F[pos];
	return ans;
}

void addOnPath(int v, int l) {
	while (v != l) {
		inc(tin[v], 1);
		inc(tout[v], -1);
		v = up[0][v];
	}
}

inline void solve() {
	init(n);
	g.resize(n);
	
	vector<int> ans(q, -1);
	fore (i, 0, q) {
		int u = es[i][0];
		int v = es[i][1];
		int x = es[i][2];
		
		if (unite(u, v)) {
			ans[i] = 1;
			g[u].emplace_back(v, x);
			g[v].emplace_back(u, x);
		}
	}
	
	buildLCA();
	F.assign(2 * n + 5, 0);
	
	fore (i, 0, q) {
		if (ans[i] != -1)
			continue;
		
		ans[i] = 0;
		int u = es[i][0];
		int v = es[i][1];
		int x = es[i][2];
		
		int xorPath = xr[u] ^ xr[v];
		if ((xorPath ^ x) != 1)
			continue;
		
		int l = lca(u, v);
		int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
		if (usedOnPath > 0)
			continue;
		
		ans[i] = 1;
		addOnPath(u, l);
		addOnPath(v, l);
	}
	
	for (int res : ans)
		cout << (res ? "YES" : "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);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

def maxSum(x):
	return x ** 2

def getAns(x):
	res = 1
	while maxSum(res) < x:
		res += 1
	return res

def main():
	t = int(input())
	for i in range(t):
		print(getAns(int(input())))

main()

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;
    int m = unique(s.begin(), s.end()) - s.begin();
    cout << n * a + max(n * b, (m / 2 + 1) * b) << '\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 x first
#define y second

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

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n;
vector<li> a;

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

li d(const pt &a, const pt &b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

inline void solve() {
	li ans = 0;
	fore (i, 0, n) {
		fore (j, i, n) {
			if (i + 2 <= j) {
				bool ok = true;
				fore (i1, i, j) fore (i2, i1 + 1, j) {
					if (d(pt(a[i1], i1), pt(a[j], j)) == d(pt(a[i1], i1), pt(a[i2], i2)) + d(pt(a[i2], i2), pt(a[j], j)))
						ok = false;
				}
				if (!ok)
					break;
			}
			ans++;
		}
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);

	int t; cin >> t;
	
	while(t--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

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);
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int N = 200 * 1000 + 55;
int f[N], inf[N];

void precalc() {
	f[0] = inf[0] = 1;
	fore (i, 1, N) {
		f[i] = mul(f[i - 1], i);
		inf[i] = binPow(f[i], MOD - 2);
	}
}

int C(int n, int k) {
	if (k < 0 || n < k)
		return 0;
	return mul(f[n], mul(inf[n - k], inf[k]));
}

int n, l, r;

inline bool read() {
	if(!(cin >> n >> l >> r))
		return false;
	return true;
}

inline void solve() {
	int half = n / 2;
	int st = min(1 - l, r - n);
	
	int ans = mul(st, C(n, half));
	if (n & 1)
		ans = norm(ans + mul(st, C(n, half + 1)));
	
	for (int k = st + 1; ; k++) {
		int lf = max(1, l + k);
		int rg = min(n, r - k);
		
		if (rg + 1 - lf < 0)
			break;
		
		ans = norm(ans + C(rg + 1 - lf, half - (lf - 1)));
		if (n & 1)
			ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1)));
	}
	
	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);
	
	precalc();
	int t; cin >> t;
	while (t--) {
		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;

int n, k;
string s;

bool check(int d){
	vector<int> lst(k, n);
	vector<vector<int>> pos(n + 1, vector<int>(k, n + 1));
	for (int i = n - 1; i >= 0; --i){
		if (s[i] != '?'){
			lst[s[i] - 'a'] = i;
		}
		int cur = n;
		forn(j, k){
			pos[i][j] = (i + d <= cur ? i + d : pos[i + 1][j]);
			cur = min(cur, lst[j]);
		}
		cur = n;
		for (int j = k - 1; j >= 0; --j){
			if (i + d > cur) pos[i][j] = pos[i + 1][j];
			cur = min(cur, lst[j]);
		}
	}
	vector<int> dp(1 << k, n + 1);
	dp[0] = 0;
	forn(mask, 1 << k) if (dp[mask] < n + 1){
		forn(i, k) if (!((mask >> i) & 1))
			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], pos[dp[mask]][i]);
	}
	return dp[(1 << k) - 1] <= n;
}

int main() {
	cin >> n >> k;
	cin >> s;
	int l = 1, r = n;
	int res = 0;
	while (l <= r){
		int m = (l + r) / 2;
		if (check(m)){
			res = m;
			l = m + 1;
		}
		else{
			r = m - 1;
		}
	}
	cout << res << endl;
	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 edge2{
	int u, w;
};

vector<vector<edge2>> g;

struct edge3{
	int v, u, w;
};

bool operator <(const edge3 &a, const edge3 &b){
	if (a.w != b.w)
		return a.w < b.w;
	if (min(a.v, a.u) != min(b.v, b.u))
		return min(a.v, a.u) < min(b.v, b.u);
	return max(a.v, a.u) < max(b.v, b.u);
}

vector<vector<int>> comps;
vector<int> p;

bool unite(int a, int b){
	a = p[a], b = p[b];
	if (a == b) return false;
	if (comps[a].size() < comps[b].size()) swap(a, b);
	for (int v : comps[b]){
		p[v] = a;
		comps[a].push_back(v);
	}
	comps[b].clear();
	return true;
}

vector<int> mn;

void dfs(int v, int p, int d){
	mn[v] = d;
	for (auto e : g[v]) if (e.u != p)
		dfs(e.u, v, max(d, e.w));
}

int main() {
	int n, q, s, d;
	scanf("%d%d%d%d", &n, &q, &s, &d);
	--s;
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> idx(a[n - 1] + 1);
	forn(i, n) idx[a[i]] = i;
	comps.resize(n);
	p.resize(n);
	forn(i, n) comps[i] = vector<int>(1, i), p[i] = i;
	g.resize(n);
	set<int> pos(a.begin(), a.end());
	int cnt = n;
	while (cnt > 1){
		vector<edge3> es;
		for (const vector<int> &comp : comps) if (!comp.empty()){
			for (int i : comp)
				pos.erase(a[i]);
			edge3 mn = {-1, -1, INF};
			for (int i : comp){
				for (int dx : {-d, d}){
					auto it = pos.lower_bound(a[i] + dx);
					if (it != pos.end())
						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
					if (it != pos.begin()){
						--it;
						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
					}
				}
			}
			for (int i : comp)
				pos.insert(a[i]);
			assert(mn.v != -1);
			es.push_back(mn);
		}
		for (auto e : es){
			if (unite(e.v, e.u)){
				--cnt;
				g[e.v].push_back({e.u, e.w});
				g[e.u].push_back({e.v, e.w});
			}
		}
	}
	mn.resize(n);
	dfs(s, -1, 0);
	forn(_, q){
		int i, k;
		scanf("%d%d", &i, &k);
		--i;
		puts(mn[i] <= k ? "Yes" : "No");
	}
	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 edge2{
	int u, w;
};

vector<vector<edge2>> g;

struct edge3{
	int v, u, w;
	edge3(){}
	edge3(int v, int u, int w) : v(v), u(u), w(w) {
		if (v > u) swap(v, u);
	}
};

bool operator <(const edge3 &a, const edge3 &b){
	if (a.w != b.w)
		return a.w < b.w;
	if (a.v != b.v)
		return a.v < b.v;
	return a.u < b.u;
}

vector<int> p, rk;

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

bool unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return false;
	if (rk[a] < rk[b]) swap(a, b);
	rk[a] += rk[b];
	p[b] = a;
	return true;
}

vector<int> mn;

void dfs(int v, int p, int d){
	mn[v] = d;
	for (auto e : g[v]) if (e.u != p)
		dfs(e.u, v, max(d, e.w));
}

int main() {
	int n, q, s, d;
	scanf("%d%d%d%d", &n, &q, &s, &d);
	--s;
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	p.resize(n);
	rk.resize(n);
	forn(i, n) rk[i] = 1, p[i] = i;
	g.resize(n);
	int cnt = n;
	int iter = 0;
	while (cnt > 1){
		++iter;
		vector<edge3> es(n, edge3(-1, -1, INF));
		int j, mn1, mn2;
		j = 0, mn1 = -1, mn2 = -1;
		forn(i, n) getp(i);
		forn(i, n){
			while (j < n && a[i] - a[j] > d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				++j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = 0, mn1 = -1, mn2 = -1;
		forn(i, n){
			while (j < n && a[j] - a[i] <= d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				++j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = n - 1, mn1 = -1, mn2 = -1;
		for (int i = n - 1; i >= 0; --i){
			while (j >= 0 && a[j] - a[i] > d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				--j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = n - 1, mn1 = -1, mn2 = -1;
		for (int i = n - 1; i >= 0; --i){
			while (j >= 0 && a[i] - a[j] <= d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				--j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		for (auto e : es) if (e.v != -1){
			if (unite(e.v, e.u)){
				--cnt;
				g[e.v].push_back({e.u, e.w});
				g[e.u].push_back({e.v, e.w});
			}
		}
	}
	mn.resize(n);
	dfs(s, -1, 0);
	forn(_, q){
		int i, k;
		scanf("%d%d", &i, &k);
		--i;
		puts(mn[i] <= k ? "Yes" : "No");
	}
	return 0;
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (r, b, d) = readLine()!!.split(' ').map { it.toInt() }
        println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO")
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }
        println(if (n * m - 1 == k) "YES" else "NO")
    }
}

#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);
    forn(_, t){
        int n;
        scanf("%d", &n);
        vector<int> s(n), u(n);
        forn(i, n){
            scanf("%d", &s[i]);
            --s[i];
        }
        forn(i, n){
            scanf("%d", &u[i]);
        }
        vector<vector<int>> bst(n);
        forn(i, n) bst[s[i]].push_back(u[i]);
        forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>());
        vector<vector<long long>> pr(n, vector<long long>(1, 0));
        forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x);
        vector<long long> ans(n);
        forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k)
            ans[k - 1] += pr[i][bst[i].size() / k * k];
        forn(i, n)
            printf("%lld ", ans[i]);
        puts("");
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  int n;
  cin >> n;
  vector<li> a(n), b(n);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  vector<li> pr(n + 1, 0);
  for (int i = 0; i < n; ++i)
    pr[i + 1] = pr[i] + a[i] * b[i];
  li ans = pr[n];
  for (int c = 0; c < n; ++c) {
    li cur = a[c] * b[c];
    for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) {
      cur += a[l] * b[r];
      cur += a[r] * b[l];
      ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    }
    cur = 0;
    for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) {
      cur += a[l] * b[r];
      cur += a[r] * b[l];
      ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    }
  }
  cout << ans << 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 point{
    int a, b, c, d;
};

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

int n;
vector<point> a;
map<frac, int> sv;

frac norm(long long x, long long y){
    long long g = __gcd(x, y);
    return {x / g, y / g};
}

vector<vector<pt>> g;
vector<int> used;
vector<pt> ans;

int dfs(int v){
    used[v] = 1;
    int cur = -1;
    for (auto it : g[v]){
        int u = it.x;
        int i = it.y;
        if (used[u] == 1) continue;
        int nw = i;
        if (!used[u]){
            int tmp = dfs(u);
            if (tmp != -1){
                ans.push_back({nw, tmp});
                nw = -1;
            }
        }
        if (nw != -1){
            if (cur != -1){
                ans.push_back({cur, nw});
                cur = -1;
            }
            else{
                cur = nw;
            }
        }
    }
    used[v] = 2;
    return cur;
}

int main() {
    scanf("%d", &n);
    a.resize(n);
    forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
    g.resize(2 * n);
    forn(i, n){
        frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c);
        frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d));
        if (!sv.count(f1)){
            int k = sv.size();
            sv[f1] = k;
        }
        if (!sv.count(f2)){
            int k = sv.size();
            sv[f2] = k;
        }
        g[sv[f1]].push_back({sv[f2], i});
        g[sv[f2]].push_back({sv[f1], i});
    }
    used.resize(sv.size());
    forn(i, sv.size()) if (!used[i])
        dfs(i);
    printf("%d\n", int(ans.size()));
    for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 6;
const int M = 400;
const int INF = int(1e9);

int a[N];
int b[N];
int c[N][N];
int n, m;

struct state
{
    vector<int> need;
    int v2;
    int v1;
    int rem;
    state() {};
    state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {};
};

int get_code(const vector<int>& v)
{
    int ans = 0;
    for(int i = 0; i < v.size(); i++)
        ans = ans * 5 + v[i];
    return ans;
}

int get_code(const state& s)
{
    int code = get_code(s.need);
    code = code * 6 + s.v2;
    code = code * 6 + s.v1;
    code = code * 5 + s.rem;
    return code; 
}

vector<int> get_vector(int code, int n)
{
    vector<int> res(n);
    for(int i = n - 1; i >= 0; i--)
    {
        res[i] = code % 5;
        code /= 5;
    }
    return res;
}

state get_state(int code)
{
    int rem = code % 5;
    code /= 5;
    int v1 = code % 6;
    code /= 6;
    int v2 = code % 6;
    code /= 6;
    vector<int> need = get_vector(code, n);
    return state(need, v1, v2, rem);
}

const int Z = 40 * int(1e6);
int dp[Z];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> c[i][j];
    for(int i = 0; i < Z; i++)
        dp[i] = INF;
    state start(vector<int>(n, 0), 0, 0, 0);
    int ans = INF;
    dp[get_code(start)] = 0;
    for(int i = 0; i < Z; i++)
    {
        if(dp[i] == INF) continue;
        state s = get_state(i);
        for(int f = 0; f <= 4; f++)
        {
            if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2])
                continue;
            int add = (f == 0 ? 0 : c[s.v1][s.v2]);
            state nw = s;
            nw.need[s.v1] += f;
            nw.rem += f;
            if(s.v1 == n - 1)
            {
                nw.v1 = 0;
                nw.v2 = s.v2 + 1;
                nw.rem = 0;
            }
            else
            {
                nw.v1 = s.v1 + 1;
            }
            if(nw.need == vector<int>(a, a + n))
                ans = min(ans, dp[i] + add);
            if(nw.v2 < m)
            {
                int code = get_code(nw);
                dp[code] = min(dp[code], dp[i] + add);
            }
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;

}

fun main() {
    repeat(readLine()!!.toInt()) {
        readLine()!!.toInt()
        println(readLine()!!.split(' ').count { it != "2" })
    }
}

for t in range(int(input())):
	a, b, c = map(int, input().split())
	print("1" + "0" * (a - 1), "1" * (b - c + 1) + "0" * (c - 1))

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> a(n);
  for (int& x : a) scanf("%d", &x);
  while (q--) {
    int x;
    scanf("%d", &x);
    int p = find(a.begin(), a.end(), x) - a.begin();
    printf("%d ", p + 1);
    rotate(a.begin(), a.begin() + p, a.begin() + p + 1);
  }
}

#include <bits/stdc++.h>

using namespace std;

int n, k;
int cur[26];
vector<int> path;

void dfs(int v) {
  while (cur[v] < k) {
    int u = cur[v]++;
    dfs(u);
    path.push_back(u);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  dfs(0);
  printf("a");
  for (int i = 0; i < n - 1; ++i)
    printf("%c", path[i % path.size()] + 'a');
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300043;
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, MOD - 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 % 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));
}

string s[N];
int p[N];
int n, m;
char buf[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%s", buf);
        s[i] = buf;
    }
    p[0] = divide(1, 2);
    for(int i = 1; i < N; i++)
        if(i % 2 == 1)
            p[i] = sub(p[i - 1], divide(1, binpow(2, i)));
        else
            p[i] = add(p[i - 1], divide(1, binpow(2, i)));
    int ans = 0;
    int w = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(s[i][j] != '*')
                w = add(w, 1);
    for(int i = 0; i < n; i++)
    {
        int c = 0;
        for(int j = 0; j < m; j++)
        {
            if(s[i][j] == '*')
                c = 0;
            else
                c++;
            if(c > 0)
                ans = add(ans, p[c]);
        }
    }
    for(int j = 0; j < m; j++)
    {
        int c = 0;
        for(int i = 0; i < n; i++)
        {
            if(s[i][j] == '*')
                c = 0;
            else
                c++;
            if(c > 0)
                ans = add(ans, p[c]);
        }
    }
    ans = mul(ans, binpow(2, w));
    cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;
const int K = 161;
const int AL = 26;

struct node{
	int nxt[AL];
	bool term;
	node(){
		memset(nxt, -1, sizeof(nxt));
		term = false;
	};
	int& operator [](const int x){
		return nxt[x];
	}
};

vector<node> trie;

int tot;

void add(const string &s){
	int cur = 0;
	int d = 1;
	for (const char &c : s){
		++d;
		if (trie[cur][c - 'a'] == -1){
			trie[cur][c - 'a'] = trie.size();
			trie.push_back(node());
			tot += d;
		}
		cur = trie[cur][c - 'a'];
	}
	trie[cur].term = true;
}

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

typedef array<array<int, K>, K> mat;

mat operator *(const mat &a, const mat &b){
	mat c;
	forn(i, K) forn(j, K) c[i][j] = 0;
	forn(i, K) forn(j, K) forn(k, K)
		c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
	return c;
}

mat binpow(mat a, long long b){
	mat res;
	forn(i, K) forn(j, K) res[i][j] = i == j;
	while (b){
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

map<pair<int, int>, int> num;
queue<pair<int, int>> q;

int get(int v, int u){
	if (v > u) swap(v, u);
	if (!num.count({v, u})){
		int k = num.size();
		assert(k < K);
		num[{v, u}] = k;
		q.push({v, u});
	}
	return num[{v, u}];
}

int main() {
	int n;
	long long m;
	cin >> n >> m;
	trie = vector<node>(1, node());
	tot = 1;
	forn(i, n){
		string s;
		cin >> s;
		add(s);
	}
	q.push({0, 0});
	num[q.front()] = 0;
	mat init;
	forn(i, K) forn(j, K) init[i][j] = 0;
	while (!q.empty()){
		int v = q.front().first;
		int u = q.front().second;
		q.pop();
		int x = get(v, u);
		forn(c, AL){
			int tov = trie[v][c];
			int tou = trie[u][c];
			if (tov == -1 || tou == -1) continue;
			++init[x][get(tov, tou)];
			if (trie[tov].term) ++init[x][get(0, tou)];
			if (trie[tou].term) ++init[x][get(tov, 0)];
			if (trie[tov].term && trie[tou].term) ++init[x][0];
		}
	}
	init = binpow(init, m);
	printf("%d\n", init[0][0]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int K = 10;
const int Z = 1 << K;

int rem[Z];
int t[N];

int get(int r)
{
    int result = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        result ^= t[r];
    return result;
}

void change(int i, int delta)
{
    for (; i < N; i = (i | (i + 1)))
        t[i] ^= delta;
}

int get(int l, int r)
{
    return get(r) - get(l - 1);
}

int ans[N];
int c[N];
int cnt[N];
int n, m;
int ls[N];
int rs[N];
vector<int> qs[N];
vector<int> qs2[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &c[i]);
        cnt[c[i]]++;
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        ls[i] = l;                                                                         
        rs[i] = r;
        qs[l].push_back(i);
        qs2[r + 1].push_back(i);
    }
    for(int i = m; i >= 1; i--)
    {
        for(int j = 0; j < cnt[i]; j++)
        {
            rem[i % (1 << K)]++;
            int r = i;
            while(true)
            {
                int l = r - Z + 1;
                l = max(1, l);
                if(l > r)
                    break;
                int diff = i - l;
                diff >>= K;
                change(l, diff);
                change(r + 1, diff);
                r -= Z;
            }
        }
        for(auto x : qs[i])
        {
            int cur = (get(i)) << K;
            for(int k = 0; k < Z; k++)
            {
                int dist = (k - i) % Z;
                if(dist < 0)
                    dist += Z;
                if(rem[k] & 1)
                    cur ^= dist;
            }
            ans[x] ^= cur;
        }
        for(auto x : qs2[i])
        {
            int cur = (get(ls[x])) << K;
            for(int k = 0; k < Z; k++)
            {
                int dist = (k - ls[x]) % Z;
                if(dist < 0)
                    dist += Z;
                if(rem[k] & 1)
                    cur ^= dist;
            }
            ans[x] ^= cur;
        }
    }
    for(int i = 0; i < q; i++)
        if(ans[i] == 0)
            printf("B");
        else
            printf("A");
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() }
        val (w, b) = readLine()!!.split(' ').map { it.toInt() }

        if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b)
            println("YES")
        else
            println("NO")
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    int i = s.find("11");
    int j = s.rfind("00");
    cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
  }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val c = readLine()!!.split(' ').map { it.toInt() }

        val mn = intArrayOf(1e9.toInt(), 1e9.toInt())
        val rem = longArrayOf(n.toLong(), n.toLong())
        var sum = 0L
        var ans = 1e18.toLong()
        for (i in c.indices) {
            mn[i % 2] = minOf(mn[i % 2], c[i])
            rem[i % 2]--
            sum += c[i]
            if (i > 0) {
                val cur = sum + rem[0] * mn[0] + rem[1] * mn[1]
                ans = minOf(ans, cur)
            }
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 2e7 + 13;

int main() {
  vector<int> mind(N, -1), val(N);
  mind[1] = 1;
  for (int i = 2; i < N; ++i) if (mind[i] == -1)
    for (int j = i; j < N; j += i) if (mind[j] == -1)
      mind[j] = i;
  for (int i = 2; i < N; ++i) {
    int j = i / mind[i];
    val[i] = val[j] + (mind[i] != mind[j]);
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int c, d, x;
    scanf("%d%d%d", &c, &d, &x);
    int ans = 0;
    for (int i = 1; i * i <= x; ++i) {
      if (x % i != 0) continue;
      int k1 = x / i + d; 
      if (k1 % c == 0) ans += 1 << val[k1 / c];
      if (i * i == x) continue;
      int k2 = i + d;
      if (k2 % c == 0) ans += 1 << val[k2 / c]; 
    }
    printf("%d\n", ans);
  }
}

#include <bits/stdc++.h>

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

using namespace std;

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 main() {
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 0)));
	int ans = 0;
	forn(i, n + 1) forn(j, m + 1){
		if (i < n) dp[i + 1][j][0] = add(dp[i + 1][j][0], 1);
		if (j < m) dp[i][j + 1][1] = add(dp[i][j + 1][1], 1);
		if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][0]);
		if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][1]);
		if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][0]);
		if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][1]);
		ans = add(ans, dp[i][j][0]);
		ans = add(ans, dp[i][j][1]);
	}
	forn(i, n){
		int j = i;
		while (j + 1 < n && s[j] != s[j + 1]) ++j;
		int len = j - i + 1;
		int val = (len * 1ll * (len + 1) / 2) % MOD * (m + 1) % MOD;
		ans = add(ans, -val);
		i = j;
	}
	forn(i, m){
		int j = i;
		while (j + 1 < m && t[j] != t[j + 1]) ++j;
		int len = j - i + 1;
		int val = (len * 1ll * (len + 1) / 2) % MOD * (n + 1) % MOD;
		ans = add(ans, -val);
		i = j;
	}
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

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 main() {
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 0))));
	int ans = 0;
	forn(i, n + 1) forn(j, m + 1){
		if (i < n) dp[i + 1][j][0][1] = add(dp[i + 1][j][0][1], 1);
		if (j < m) dp[i][j + 1][1][2] = add(dp[i][j + 1][1][2], 1);
		forn(mask, 4){
			if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][0][mask]);
			if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][1][mask]);
			if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][0][mask]);
			if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][1][mask]);
		}
		ans = add(ans, dp[i][j][0][3]);
		ans = add(ans, dp[i][j][1][3]);
	}
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

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 k;
vector<vector<int>> g;
vector<vector<int>> dp;

int dfs(int v, int p = -1){
	dp[v][0] = 1;
	int h = 0;
	for (int u : g[v]) if (u != p){
		int nh = dfs(u, v);
		vector<int> tmp(max(h, nh + 1) + 1);
		forn(i, h + 1) forn(j, nh + 1){
			if (i + j + 1 <= k)
				tmp[max(i, j + 1)] = add(tmp[max(i, j + 1)], mul(dp[v][i], dp[u][j]));
			if (i <= k && j <= k)
				tmp[i] = add(tmp[i], mul(dp[v][i], dp[u][j]));
		}
		h = max(h, nh + 1);
		forn(i, h + 1){
			dp[v][i] = tmp[i];
		}
	}
	return h;
}

int main() {
	int n;
	scanf("%d%d", &n, &k);
	g.resize(n);
	dp.resize(n, vector<int>(n, 0));
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs(0);
	int ans = 0;
	forn(i, k + 1) ans = add(ans, dp[0][i]);
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 1000043;

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 % 2 == 1)
            z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int global_hash = 0;

void reverse(deque<pair<int, int>>& d)
{
    stack<pair<int, int>> s;
    while(!d.empty())
    {
        s.push(d.back());
        d.pop_back();
    }
    while(!s.empty())
    {
        d.push_front(s.top());
        s.pop();
    }
}

void safe_push_front(deque<pair<int, int>>& d, int c, int& res)
{
    int z = d.front().first ^ 1;
    res = add(res, mul(binpow(2, c), z));
    d.push_front(make_pair(z, c));
}

void safe_push_back(deque<pair<int, int>>& d, int c, int& res)
{
    int z = d.back().first ^ 1;
    res = add(res, mul(binpow(2, c), z));
    d.push_back(make_pair(z, c));
}

deque<pair<int, int>> ds[N];

struct path
{
    int s;
    int t;
    int d;
    int c;

    path() {};
    path(int s, int t, int d, int c) : s(s), t(t), d(d), c(c) {};

    void push_front(int i)
    {
        safe_push_front(ds[d], i, c);
    }

    void push_back(int i)
    {
        safe_push_back(ds[d], i, c);
    }

    void pop_front()
    {
        ds[d].pop_front();
    }

    void pop_back()
    {
        ds[d].pop_back();
    }

    int front()
    {
        return ds[d].front().second;
    }

    int back()
    {
        return ds[d].back().second;
    }

    void reverse()
    {
        ::reverse(ds[d]);
        swap(s, t);
    }

    int size()
    {
        return ds[d].size();
    }
};

path link_to_left(path x, path y)
{
    path z = x;
    while(y.size() > 0)
    {
        z.push_back(y.front());
        y.pop_front();
    }
    z.t = y.t;
    return z;
}

path link_to_right(path x, path y)
{
    path z = y;
    while(x.size() > 0)
    {
        z.push_front(x.back());
        x.pop_back();
    }
    z.s = x.s;
    return z;
}

int cur = 0;

path make(int x, int y, int i)
{
    int cost = i;
    ds[cur].push_back(make_pair(0, cost));
    return path(x, y, cur++, 0);    
}

set<int> paths;
vector<int> paths_v[N];
path ps[N];

path merge(path x, path y, int v)
{
    if(x.size() > y.size())
        swap(x, y);
    if(y.s == v)
    {
        if(x.t != v)
            x.reverse();
        return link_to_right(x, y);    
    }
    else
    {
        if(x.s != v)
            x.reverse();
        return link_to_left(y, x);
    }    
}

int cur2 = 0;       

void modify(vector<int>& v, int x, int y)
{
    for(int i = 0; i < v.size(); i++)
        if(v[i] == x)
            v[i] = y;
}   

void reassign(path p, int x, int y)
{
    modify(paths_v[p.s], x, y);
    modify(paths_v[p.t], x, y);    
}

void merge_paths(int x, int y, int v)
{
    if(x == y)
    {                         

    }
    else
    {
        global_hash = sub(global_hash, ps[x].c);
        global_hash = sub(global_hash, ps[y].c);
        ps[cur2++] = merge(ps[x], ps[y], v);
        paths.erase(x);
        paths.erase(y);
        paths.insert(cur2 - 1);
        reassign(ps[x], x, cur2 - 1);
        reassign(ps[y], y, cur2 - 1);
        global_hash = add(global_hash, ps[cur2 - 1].c);   
    }
}

void relax(int v)
{
    while(paths_v[v].size() >= 2)
    {
        int x = paths_v[v].back();
        paths_v[v].pop_back();
        int y = paths_v[v].back();
        paths_v[v].pop_back();
        merge_paths(x, y, v);
    }
}

void add_edge(int x, int y, int i)
{
    //cerr << x << " " << y << " " << i << endl;
    int c = cur2;
    ps[cur2++] = make(x, y, i);
    paths_v[x].push_back(c);
    paths_v[y].push_back(c);
    paths.insert(c);
    relax(x);
    relax(y);
}

void print_coloring()
{
    vector<int> ans;
    for(auto x : paths)
    {
        for(auto y : ds[ps[x].d])
        {
            if(y.first == 1)
                ans.push_back(y.second);
        }
    }
    printf("%d", int(ans.size()));
    for(auto x : ans)
        printf(" %d", x);
    puts("");
    fflush(stdout);
}

int e = 0;

void process_query()
{
    int t;
    scanf("%d", &t);
    if(t == 1)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        y += 200001;
        add_edge(x, y, ++e);
        printf("%d\n", global_hash);
        fflush(stdout);
    }
    else
        print_coloring();
}

void print_info()
{
    cerr << "Paths\n";
    for(auto x : paths)
        cerr << x << " start: " << ps[x].s << " " << " end: " << ps[x].t << endl;
    cerr << "Vertices\n";
    for(int i = 0; i < N; i++)
        if(!paths_v[i].empty())
        {
            cerr << i << ": ";
            for(auto x : paths_v[i])
                cerr << x << " ";
            cerr << endl;
        }

}
        
int main()
{
    int n1, n2, m;
    scanf("%d %d %d", &n1, &n2, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        y += 200001;
        add_edge(x, y, ++e);
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        //print_info();
        process_query();
    }
}

#include <bits/stdc++.h>

using namespace std;

bool solve() {
  string s;
  cin >> s;
  vector<int> d(3);
  int x = s[0] - 'A';
  int y = s.back() - 'A';
  if (x == y)
    return false;
  d[x] = 1; d[y] = -1;
  if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
    d[3 ^ x ^ y] = -1;
  else
    d[3 ^ x ^ y] = 1;
  int bal = 0;
  for (char c : s) {
    bal += d[c - 'A'];
    if (bal < 0) return false;
  }
  return bal == 0;
}

int main() {
  int t; cin >> t;
  while (t--) {
    cout << (solve() ? "YES\n" : "NO\n");
  }
}

for _ in range(int(input())):
    n, U, R, D, L = map(int, input().split())
    for mask in range(16):
        rU, rR, rD, rL = U, R, D, L
        if mask & 1:
            rU -= 1
            rL -= 1
        if mask & 2:
            rL -= 1
            rD -= 1
        if mask & 4:
            rD -= 1
            rR -= 1
        if mask & 8:
            rR -= 1
            rU -= 1
        if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
            print("YES")
            break
    else:
        print("NO")

#include <bits/stdc++.h>

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

using namespace std;

int calc(const vector<int> &a, const vector<int> &b){
    int n = a.size();
    int m = b.size();
    vector<int> su(n + 1);
    int r = m - 1;
    for (int i = n - 1; i >= 0; --i){
        su[i] = su[i + 1];
        while (r >= 0 && b[r] > a[i]) --r;
        if (r >= 0 && b[r] == a[i]) ++su[i];
    }
    int ans = 0;
    int j = 0;
    r = 0;
    forn(l, m){
        while (j < n && a[j] <= b[l] + j) ++j;
        while (r < m && b[r] - b[l] < j) ++r;
        ans = max(ans, r - l + su[j]);
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        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> al, bl, ar, br;
        forn(i, n){
            if (a[i] < 0) al.push_back(-a[i]);
            else ar.push_back(a[i]);
        }
        forn(i, m){
            if (b[i] < 0) bl.push_back(-b[i]);
            else br.push_back(b[i]);
        }
        reverse(al.begin(), al.end());
        reverse(bl.begin(), bl.end());
        printf("%d\n", calc(al, bl) + calc(ar, br));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 505;

int n;
int a[N][N];
int c[2 * N];
vector<pair<int, int>> e;

int calc(vector<int> ls) {
  if (sz(ls) == 1)
    return ls[0];
  
  int res = -1;
  for (int u : ls)
    res = max(res, a[ls[0]][u]);
  
  vector<vector<int>> ch;
  ch.push_back({ls[0]});
  for (int i = 1; i < sz(ls); ++i) {
    int v = ls[i];
    int group = -1;
    for (int j = 0; j < sz(ch); ++j) {
      if (a[v][ch[j][0]] != res) {
        group = j;
        break;
      }
    }
    if (group == -1) {
      group = sz(ch);
      ch.push_back({});
    }
    ch[group].push_back(v);
  }
  
  int v = n++;
  c[v] = res;
  for (int i = 0; i < sz(ch); ++i) {
    int u = calc(ch[i]);
    e.emplace_back(u, v);
  }
  return v;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      cin >> a[i][j];
  for (int i = 0; i < n; ++i)
    c[i] = a[i][i];
  vector<int> ls(n);
  iota(ls.begin(), ls.end(), 0);
  int root = calc(ls);
  cout << n << '\n';
  for (int i = 0; i < n; ++i)
    cout << c[i] << ' ';
  cout << '\n' << root + 1 << '\n';
  for (auto it : e)
    cout << it.first + 1 << ' ' << it.second + 1 << '\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 x first
#define y second

typedef pair<int, int> pt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    map<pt, int> allEdges;
    set<pt> difPairs, eqPairs;
    
    fore (q, 0, m) {
        char tp; cin >> tp;
        if (tp == '+') {
            int u, v;
            char c;
            cin >> u >> v >> c;
            
            if (allEdges.count({v, u})) {
                if (allEdges[{v, u}] == c)
                    eqPairs.emplace(min(u, v), max(u, v));
                else
                    difPairs.emplace(min(u, v), max(u, v));
            }
            allEdges[{u, v}] = c;
            
        } else if (tp == '-') {
            int u, v;
            cin >> u >> v;
            if (eqPairs.count({min(u, v), max(u, v)}))
                eqPairs.erase({min(u, v), max(u, v)});
            if (difPairs.count({min(u, v), max(u, v)}))
                difPairs.erase({min(u, v), max(u, v)});
            
            allEdges.erase({u, v});
        } else {
            int k;
            cin >> k;
            
            bool hasAns = !eqPairs.empty();
            if (k & 1)
                hasAns |= !difPairs.empty();
            cout << (hasAns ? "YES" : "NO") << '\n';
        }
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300043;

int n, m;
set<int> g[N];
set<int> g2[N];

vector<int> res;

void euler(int x)
{
    while(!g2[x].empty())
    {
        int y = *g2[x].begin();
        g2[x].erase(y);
        g2[y].erase(x);
        euler(y);
    }
    res.push_back(x);
}

bool check(int c)
{
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    res = vector<int>();
    euler(c);
    int curm = 0;
    for(int i = 1; i <= n; i++)
        curm += g[i].size();
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    for(int i = 1; i < res.size(); i++)
    {
        int x = res[i - 1];
        int y = res[i];
        if(g2[x].count(y) != 1)
            return false;
        g2[x].erase(y);
        g2[y].erase(x);
    }
    return curm / 2 + 1 == res.size();    
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].insert(y);
        g[y].insert(x);
    }
    for(int i = 1; i <= n; i++)
    {
        set<int> pr = g[i];
        set<int> diff;
        for(auto x : pr)
            if(g[x].size() % 2 == 1)
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
        if(check(i))
        {
            res.push_back(-1);
            for(auto x : diff)
            {
                res.push_back(x);
                res.push_back(i);
            }
            printf("%d\n", res.size());
            for(auto x : res) printf("%d ", x);
            puts("");
            exit(0);
        }
        for(auto x : pr)
        {
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
            if(check(i))
            {
                res.push_back(-1);
                for(auto x : diff)
                {
                    res.push_back(x);
                    res.push_back(i);
                }
                printf("%d\n", res.size());
                for(auto x : res) printf("%d ", x);
                puts("");
                exit(0);
            }
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
        }
        for(auto x : diff)
        {
            g[i].insert(x);
            g[x].insert(i);
        }
    }
    puts("0");
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl;
  }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        var (n, k) = readLine()!!.split(' ').map { it.toInt() }
        k--
        val floor = n / 2
        println((k + (n % 2) * k / floor) % n + 1)
    }
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        if(n % 2 == 1)
        {
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    if(j - i <= n / 2)
                        cout << 1 << " ";
                    else
                        cout << -1 << " ";
            cout << endl;
        }
        else
        {
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    if(j - i < n / 2)
                        cout << 1 << " ";
                    else if(j - i == n / 2)
                        cout << 0 << " ";
                    else
                        cout << -1 << " ";
            cout << endl;
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 3; i * i <= 2 * n - 1; i += 2)
      ++ans;
    cout << ans << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;


int main()
{   
    vector<int> ns(4);
    for(int i = 0; i < 4; i++)
        scanf("%d", &ns[i]);
    vector<vector<int>> cs(4);
    for(int i = 0; i < 4; i++)
    {
        cs[i].resize(ns[i]);
        for(int j = 0; j < ns[i]; j++)
            scanf("%d", &cs[i][j]);
    }
    vector<vector<vector<int>>> bad(3);
    for(int i = 0; i < 3; i++)
    {
        bad[i].resize(ns[i + 1]);
        int m;
        scanf("%d", &m);
        for(int j = 0; j < m; j++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            x--;
            y--;
            bad[i][y].push_back(x);
        }
    }                   
    vector<vector<int>> dp(4);
    dp[0] = cs[0];
    for(int i = 0; i < 3; i++)
    {
        dp[i + 1].resize(ns[i + 1]);                
        multiset<int> s;
        for(int j = 0; j < ns[i]; j++)
            s.insert(dp[i][j]);
        for(int j = 0; j < ns[i + 1]; j++)
        {
            for(auto k : bad[i][j])
                s.erase(s.find(dp[i][k]));
            if(s.empty())
                dp[i + 1][j] = int(4e8 + 43);
            else
                dp[i + 1][j] = *s.begin() + cs[i + 1][j];
            for(auto k : bad[i][j])
                s.insert(dp[i][k]);       
        }
    }
    int ans = *min_element(dp[3].begin(), dp[3].end());
    if(ans > int(4e8))
        ans = -1;
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 250;
const int M = 28;
const int INF = 1e9;

int dp[2][M * 2 + 1][N][N];

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  s += "0";
  
  forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF;
  dp[0][M][N - 1][N - 1] = 0;
  
  forn(i, sz(s)) {
    forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF;
    forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) {
      if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]);
      if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]);
      int rcarry = carry - M;
      int val = rcarry + cp - cn;
      int digit = val % 10;
      if (digit < 0) digit += 10;
      int ncarry = val / 10;
      if (val < 0 && digit != 0) --ncarry;
      if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn);
    }
    swap(dp[0], dp[1]);
  }
  
  int ans = INF;
  forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]);
  cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 402;

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 c[26];
int dp[2][N][N][3][3];
int sumDp[N][N];
int p1[N][N];
int p2[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < 26; i++)
        cin >> c[i];
    for(int i = 0; i < 26; i++)
        for(int j = 0; j < 26; j++)
            for(int k = 0; k < 26; k++)
                if(i != k)
                {                                                                    
                    multiset<int> s = {i, j, k};
                    dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++;
                }
    for(int i = 4; i <= n; i++)
    {
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                for(int x = 0; x < 3; x++)
                    for(int y = 0; y < 3; y++)
                    {
                        dp[0][j][k][x][y] = dp[1][j][k][x][y];
                        dp[1][j][k][x][y] = 0;
                    }
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                for(int x = 0; x < 3; x++)
                    for(int y = 0; y < 3; y++)
                    {
                        int cur = dp[0][j][k][x][y];
                        if(cur == 0) continue;
                        for(int z = 0; z < 3; z++)
                        {                      
                            int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z];
                            nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0)));
                        }
                    }
    }
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < 3; k++)
                for(int l = 0; l < 3; l++)
                    sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]);
    for(int i = 0; i < N; i++)
    {
        p1[i][N - 1] = sumDp[i][N - 1];
        for(int j = N - 2; j >= 0; j--)
            p1[i][j] = add(sumDp[i][j], p1[i][j + 1]);
    }
    for(int j = 0; j < N; j++)
    {
        p2[N - 1][j] = p1[N - 1][j];
        for(int i = N - 2; i >= 0; i--)
            p2[i][j] = add(p1[i][j], p2[i + 1][j]);
    }
    int ans = p2[0][0]; 
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < N; j++)
            for(int k = c[i] + 1; k < N; k++)
                ans = sub(ans, sumDp[k][j]);
    }
    for(int i = 0; i < 26; i++)
        for(int j = 0; j < i; j++)
            ans = add(ans, p2[c[i] + 1][c[j] + 1]);
    cout << ans << endl;    
}

#include<bits/stdc++.h>

using namespace std;

int main() {
  int t; cin >> t;
  while(t--) {
    long long n, k;
    cin >> n >> k;
    
    long long cf = (n + k - 1) / k;
    k *= cf;
    
    cout << (k + n - 1) / n << endl;
  }
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int INF = int(1e9);

int main() {
  int t; cin >> t;
  while(t--) {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
      cin >> p[i];
    
    li x = 0;
    li pSum = p[0];
    for (int i = 1; i < n; i++) {
      x = max(x, (100ll * p[i] - k * pSum + k - 1) / k);
      pSum += p[i];
    }
    cout << x << endl;
  }
  return 0;
}

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

typedef long long li;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;
    vector<int> c(n), a(n), b(n);
    for (int i = 0; i < n; i++)
      cin >> c[i];
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> b[i];
    
    li ans = 0;
    li lstLen = 0;
    for (int i = 1; i < n; i++) {
      li curLen = c[i] + 1ll + abs(a[i] - b[i]);
      if (a[i] != b[i])
        curLen = max(curLen, c[i] + 1ll + lstLen - abs(a[i] - b[i]));
      ans = max(ans, curLen);
      lstLen = curLen;  
    }
    cout << ans << endl;
  }
  return 0;
};

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

char buf[300043];

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        scanf("%s", buf);
        string s = buf;
        vector<vector<int>> g(2 * n + 2);
        for(int i = 0; i < n; i++)
            if(s[i] == 'L')
            {
                g[(i + 1) * 2].push_back(i * 2 + 1);
                g[i * 2 + 1].push_back((i + 1) * 2);
            }
            else
            {
                g[i * 2].push_back((i + 1) * 2 + 1);
                g[(i + 1) * 2 + 1].push_back(i * 2);   
            }
        vector<int> comp(2 * n + 2, -1);
        vector<int> cnt;
        for(int i = 0; i < 2 * n + 2; i++)
        {
            if(comp[i] != -1) continue;
            int c = 1;
            int cc = cnt.size();
            queue<int> q;
            comp[i] = cc;
            q.push(i);
            while(!q.empty())
            {
                int k = q.front();
                q.pop();
                for(auto y : g[k])
                {
                    if(comp[y] == -1)
                    {
                        c++;
                        comp[y] = cc;
                        q.push(y);
                    }
                }
            }
            cnt.push_back(c);
        }
        for(int i = 0; i <= n; i++)
            printf("%d%c", cnt[comp[i * 2]], " \n"[i == n]);
    }
}

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    dpl = [i for i in range(n + 1)]
    dpr = [i for i in range(n + 1)]
    for i in range(n + 1):
        if i == 0 or s[i - 1] == 'R':
            dpl[i] = i
        elif i == 1 or s[i - 2] == 'L':
            dpl[i] = i - 1
        else:
            dpl[i] = dpl[i - 2]
    for i in range(n, -1, -1):
        if i == n or s[i] == 'L':
            dpr[i] = i
        elif i == n - 1 or s[i + 1] == 'R':
            dpr[i] = i + 1
        else:
            dpr[i] = dpr[i + 2]
    ans = [(dpr[i] - dpl[i]) + 1 for i in range(n + 1)]
    print(*ans)

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

int main() {
    cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  vector<pattern> p(n);
  g.assign(n, vector<int>());
  forn(i, n){
    cin >> p[i].s;
    p[i].i = i;
  }
  sort(p.begin(), p.end());
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    --mt;
    bool ok = false;
    forn(mask, 1 << k){
      forn(j, k)
        nw.s[j] = ((mask >> j) & 1 ? cur[j] : '_');
      auto it = lower_bound(p.begin(), p.end(), nw);
      if (it != p.end() && it->s == nw.s){
        if (it->i != mt)
          g[mt].push_back(it->i);
        else
          ok = true;
      }
    }
    if (!ok){
      puts("NO");
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

struct node{
  int nxt[28];
  int term;
  node(){
    memset(nxt, -1, sizeof(nxt));
    term = -1;
  }
};

vector<node> trie;

void add(const string &s, int i){
  int cur = 0;
  for (char c : s){
    int x = c - '_';
    if (trie[cur].nxt[x] == -1){
      trie[cur].nxt[x] = trie.size();
      trie.push_back(node());
    }
    cur = trie[cur].nxt[x];
  }
  trie[cur].term = i;
}

bool check(int i, int v, const string &s, int mt){
  if (i == int(s.size())){
    assert(trie[v].term != -1);
    if (trie[v].term != mt)
      g[mt].push_back(trie[v].term);
    else
      return true;
    return false;
  }
  bool res = false;
  if (trie[v].nxt[s[i] - '_'] != -1 && check(i + 1, trie[v].nxt[s[i] - '_'], s, mt))
    res = true;
  if (trie[v].nxt[0] != -1 && check(i + 1, trie[v].nxt[0], s, mt))
    res = true;
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  trie = vector<node>(1);
  int n, m, k;
  cin >> n >> m >> k;
  g.assign(n, vector<int>());
  forn(i, n){
    string cur;
    cin >> cur;
    add(cur, i);
  }
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    if (!check(0, 0, cur, mt - 1)){
      cout << "NO\n";
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

struct segTree
{
    int n;
    bool mx;
    vector<int> t;

    void fix(int v)
    {
        t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
    }

    void build(int v, int l, int r)
    {
        if(l == r - 1)
            t[v] = (mx ? -INF : INF);
        else
        {
            int m = (l + r) / 2;
            build(v * 2 + 1, l, m);
            build(v * 2 + 2, m, r);
            fix(v);
        }
    }

    void upd(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
            t[v] = (mx ? max(t[v], val) : min(t[v], val));
        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);
            fix(v);
        }
    }

    int get(int v, int l, int r, int L, int R)
    {
        if(L >= R)
            return (mx ? -INF : INF);
        if(l == L && r == R)
            return t[v];
        int m = (l + r) / 2;
        int lf = get(v * 2 + 1, l, m, L, min(R, m));
        int rg = get(v * 2 + 2, m, r, max(m, L), R);
        return (mx ? max(lf, rg) : min(lf, rg));
    }

    void upd(int pos, int val)
    {
        upd(0, 0, n, pos, val);
    }

    int get(int L, int R)
    {
        return get(0, 0, n, L, R);
    }

    void build()
    {
        return build(0, 0, n);
    }

    segTree() {};
    segTree(int n, bool mx) : n(n), mx(mx)
    {
        t.resize(4 * n);
    }
};

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        vector<int> p(n);
        for(int i = 0; i < n; i++)
            scanf("%d", &p[i]);
        vector<int> dp(n + 1, -INF);
        vector<int> par(n + 1, -2);
        dp[0] = 0;
        par[0] = -1;
        vector<int> lf(n), rg(n);
        for(int i = 0; i < n; i++)
        {
            lf[i] = max(1, i - p[i] + 1);
            rg[i] = min(n, i + p[i] + 1);
        }
        segTree sn(n + 1, false);        
        segTree sx(n, true);
        sn.build();
        sx.build();
        for(int i = 0; i < n; i++)
            sx.upd(i, rg[i]);
        sn.upd(0, 0);
        for(int i = 1; i <= n; i++)
        {
            int j = i - 1;
            int k = lf[j] - 1;
            
            int m = sn.get(k, n + 1);                 
            if(m != INF)
            {
                int nval = max(sx.get(m, i - 1), i - 1);
                if(nval > dp[i])
                {
                    dp[i] = nval;
                    par[i] = m;
                }
            }
            if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
            {
                dp[i] = max(dp[j], rg[j]);
                par[i] = -1;
            }
            if(dp[j] > dp[i])
            {
                dp[i] = dp[j];
                par[i] = -1;
            }
            sn.upd(dp[i], i);                
        }
        if(dp[n] != n)
            puts("NO");
        else
        {
            puts("YES");
            string ans;
            int cur = n;
            while(cur != 0)
            {
                if(par[cur] == -1)
                {
                    cur--;
                    ans += "R";
                }
                else
                {
                    int pcur = par[cur];
                    int diff = cur - pcur;
                    ans += "L";
                    for(int j = 0; j < diff - 1; j++)
                        ans += "R";
                    cur = pcur;    
                }
            }
            reverse(ans.begin(), ans.end());
            puts(ans.c_str());
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;
const int P = 2000;

struct query {
  int t, l, r, k, i;
};

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  forn(i, n) scanf("%d", &a[i]);
  
  vector<query> q;
  vector<array<int, 3>> upd;
  
  forn(i, m) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      q.push_back({sz(upd), l - 1, r - 1, k, sz(q)});
    } else {
      int p, x;
      scanf("%d%d", &p, &x); --p;
      upd.push_back({p, a[p], x});
      a[p] = x;
    }
  }
  
  sort(q.begin(), q.end(), [](const query &a, const query &b) {
    if (a.t / P != b.t / P)
      return a.t < b.t;
    if (a.l / P != b.l / P)
      return a.l < b.l;
    if ((a.l / P) & 1)
      return a.r < b.r;
    return a.r > b.r; 
  });
  
  for (int i = sz(upd) - 1; i >= 0; --i)
    a[upd[i][0]] = upd[i][1];
  
  vector<int> cnt(N), ord(N);
  vector<pt> bounds(N, {N, 0});
  bounds[0] = {0, N - 1};
  int L = 0, R = -1, T = 0;
  
  auto add = [&](int x) {
    int c = cnt[x];
    ++ord[bounds[c].x];
    bounds[c + 1].y = bounds[c].x;
    if (bounds[c + 1].x == N)
      bounds[c + 1].x = bounds[c].x;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N - 1;
    ++bounds[c].x;
    ++cnt[x];
  };
  
  auto rem = [&](int x) {
    int c = cnt[x];
    --ord[bounds[c].y];
    if (bounds[c - 1].x == N)
      bounds[c - 1].y = bounds[c].y;
    bounds[c - 1].x = bounds[c].y;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N;
    --bounds[c].y;
    --cnt[x];
  };
  
  auto apply = [&](int i, int fl) {
    int p = upd[i][0];
    int x = upd[i][fl + 1];
    if (L <= p && p <= R) {
      rem(a[p]);
      add(x);
    }
    a[p] = x;
  };
  
  vector<int> ans(sz(q));
  
  for (auto qr : q) {
    int t = qr.t, l = qr.l, r = qr.r, k = qr.k;
    while (T < t) apply(T++, 1);
    while (T > t) apply(--T, 0);
    while (R < r) add(a[++R]);
    while (L > l) add(a[--L]);
    while (R > r) rem(a[R--]);
    while (L < l) rem(a[L++]);
    
    int res = N;
    for (int i = 0, j = 0, sum = 0; i < N && ord[i] > 0; i = bounds[ord[i]].y + 1) {
      while (j < N && ord[j] > 0 && sum < k) {
        sum += bounds[ord[j]].y - bounds[ord[j]].x + 1;
        j = bounds[ord[j]].y + 1;
      }
      if (sum >= k) res = min(res, ord[i] - ord[j - 1]);
      sum -= bounds[ord[i]].y - bounds[ord[i]].x + 1;
    }
    if (res == N) res = -1;
    ans[qr.i] = res;
  }
  
  for (int x : ans) printf("%d\n", x);
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl;
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  auto mul = [](string s, int k) -> string {
    string res = "";
    while (k--) res += s;
    return res;
  };
  
  int tc;
  cin >> tc;
  while (tc--) {
    string s, t;
    cin >> s >> t;
    int n = s.length(), m = t.length();
    int g = __gcd(n, m);
    if (mul(s, m / g) == mul(t, n / g))
      cout << mul(s, m / g) << endl;
    else
      cout << "-1" << endl;
  }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }

        for (i in 1 until (k - (n - k)))
            print("$i ")
        for (i in k downTo (k - (n - k)))
            print("$i ")
        println("")
    }
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	forn(_, t){
		int n, m;
		string s;
		cin >> n >> m;
		cin >> s;
		vector<int> sul(1, 0), sur(1, 0);
		for (int i = n - 1; i >= 0; --i){
			int d = s[i] == '+' ? 1 : -1;
			sul.push_back(min(0, sul.back() + d));
			sur.push_back(max(0, sur.back() + d));
		}
		reverse(sul.begin(), sul.end());
		reverse(sur.begin(), sur.end());
		vector<int> prl(1, 0), prr(1, 0), pr(1, 0);
		forn(i, n){
			int d = s[i] == '+' ? 1 : -1;
			pr.push_back(pr.back() + d);
			prl.push_back(min(prl.back(), pr.back()));
			prr.push_back(max(prr.back(), pr.back()));
		}
		forn(i, m){
			int l, r;
			cin >> l >> r;
			--l;
			int l1 = prl[l], r1 = prr[l];
			int l2 = sul[r] + pr[l], r2 = sur[r] + pr[l];
			printf("%d\n", max(r1, r2) - min(l1, l2) + 1);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n, m;
vector<pair<int, int>> g[N];
long long d[N][2][2];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    --v; --u;
    g[v].emplace_back(u, w);
    g[u].emplace_back(v, w);
  }
  
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        d[i][j][k] = (long long)1e18;

  d[0][0][0] = 0;
  set<pair<long long, array<int, 3>>> q;
  q.insert({0, {0, 0, 0}});

  while (!q.empty()) {
    auto [v, mx, mn] = q.begin()->second;
    q.erase(q.begin());
    for (auto [u, w] : g[v]) {
      for (int i = 0; i <= 1 - mx; i++) {
        for (int j = 0; j <= 1 - mn; j++) {
          if (d[u][mx | i][mn | j] > d[v][mx][mn] + (1 - i + j) * w) {
            auto it = q.find({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
            if (it != q.end())
              q.erase(it);
            d[u][mx | i][mn | j] = d[v][mx][mn] + (1 - i + j) * w;
            q.insert({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
          }
        }
      }
    }
  }

  for (int i = 1; i < n; i++) {
    printf("%lld ", d[i][1][1]);
  }
  puts("");
}

#include<bits/stdc++.h>

using namespace std;

template<typename T>
struct dinic {
    struct edge {
        int u, rev;
        T cap, flow;
    };
    
    int n, s, t;
    T flow;
    vector<int> lst;
    vector<int> d;
    vector<vector<edge>> g;
    
    T scaling_lim;
    bool scaling;
    
    dinic() {}
    
    dinic(int n, int s, int t, bool scaling = false) : n(n), s(s), t(t), scaling(scaling) {
        g.resize(n);
        d.resize(n);
        lst.resize(n);
        flow = 0;
    }

    void add_edge(int v, int u, T cap, bool directed = true) {
        g[v].push_back({u, g[u].size(), cap, 0});
        g[u].push_back({v, int(g[v].size()) - 1, directed ? 0 : cap, 0});
    }

    T dfs(int v, T flow) {
        if (v == t)
            return flow;
        if (flow == 0)
            return 0;
        T result = 0;
        for (; lst[v] < g[v].size(); ++lst[v]) {
            edge& e = g[v][lst[v]];
            if (d[e.u] != d[v] + 1)
                continue;
            T add = dfs(e.u, min(flow, e.cap - e.flow));
            if (add > 0) {
                result += add;
                flow -= add;
                e.flow += add;
                g[e.u][e.rev].flow -= add;
            }
            if (flow == 0)
                break;
        }
        return result;
    }

    bool bfs() {
        fill(d.begin(), d.end(), -1);
        queue<int> q({s});
        d[s] = 0;
        while (!q.empty() && d[t] == -1) {
            int v = q.front(); q.pop();
            for (auto& e : g[v]) {
                if (d[e.u] == -1 && e.cap - e.flow >= scaling_lim) {
                    q.push(e.u);
                    d[e.u] = d[v] + 1;
                }
            }
        }
        return d[t] != -1;
    }

    T calc() {
        T max_lim = numeric_limits<T>::max() / 2 + 1;
        for (scaling_lim = scaling ? max_lim : 1; scaling_lim > 0; scaling_lim >>= 1) {
            while (bfs()) {
                fill(lst.begin(), lst.end(), 0);
                T add;
                while((add = dfs(s, numeric_limits<T>::max())) > 0)
                flow += add;
            }
        }   
        return flow;
    }
    
    vector<bool> min_cut() {
        vector<bool> res(n);
        for(int i = 0; i < n; i++) 
            res[i] = (d[i] != -1);
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    int s = n;
    int t = n + 1;
    dinic<int> d(n + 2, s, t, true);
    vector<int> last(101, -1);
    for(int i = 0; i < n; i++){
        if(b[i] > 0)
            d.add_edge(s, i, b[i]);
        if(b[i] < 0)
            d.add_edge(i, t, -b[i]);
        for(int k = 1; k <= 100; k++)
            if(last[k] != -1 && a[i] % k == 0)
                d.add_edge(i, last[k], int(1e9));
        last[a[i]] = i;    
    }   
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += max(0, b[i]);
    cout << sum - d.calc() << endl;
}

#include <bits/stdc++.h>

using namespace std;

#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)
#define sz(a) int((a).size())

template<const int &MOD>
struct _m_int {
  int val;
 
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(uint64_t v) {
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(int v) : _m_int(int64_t(v)) {}
  _m_int(unsigned v) : _m_int(uint64_t(v)) {}
 
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
 
    while (r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
 
    return x < 0 ? x + m : x;
  }
 
  explicit operator int() const { return val; }
  explicit operator unsigned() const { return val; }
  explicit operator int64_t() const { return val; }
  explicit operator uint64_t() const { return val; }
  explicit operator double() const { return val; }
  explicit operator long double() const { return val; }
 
  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return unsigned(x % m);
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
    unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }
 
  _m_int& operator*=(const _m_int &other) {
    val = fast_mod(uint64_t(val) * other.val);
    return *this;
  }
 
  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }
 
  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
 
  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
 
  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
 
  _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  _m_int operator--(int) { _m_int before = *this; --*this; return before; }
 
  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }
 
  friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
  friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
  friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
  friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
  friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
  friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
 
  _m_int inv() const {
    return inv_mod(val);
  }
 
  _m_int pow(int64_t p) const {
    if (p < 0)
      return inv().pow(-p);
 
    _m_int a = *this, result = 1;
 
    while (p > 0) {
      if (p & 1)
        result *= a;
      a *= a;
      p >>= 1;
    }
 
    return result;
  }
  
  friend string to_string(_m_int<MOD> x) {
    return to_string(x.val);
  }
 
  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

extern const int MOD = 998244353;
using Mint = _m_int<MOD>;

const int g = 3;
const int LOGN = 15;

vector<Mint> w[LOGN];
vector<int> rv[LOGN];

void prepare() {
  Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
  forn(st, LOGN - 1) {
    w[st].assign(1 << st, 1);
    Mint bw = wb.pow(1 << (LOGN - st - 1));
    Mint cw = 1;
    forn(k, 1 << st) {
      w[st][k] = cw;
      cw *= bw;
    }
  }
  forn(st, LOGN) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    int h = (1 << (st - 1));
    forn(k, 1 << st)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}

void ntt(vector<Mint> &a, bool inv) {
  int n = sz(a);
  int ln = __builtin_ctz(n);
  forn(i, n) {
    int ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  forn(st, ln) {
    int len = 1 << st;
    for (int k = 0; k < n; k += (len << 1)) {
      fore(pos, k, k + len){
        Mint l = a[pos];
        Mint r = a[pos + len] * w[st][pos - k];
        a[pos] = l + r;
        a[pos + len] = l - r;
      }
    }
  }
  if (inv) {
    Mint rn = Mint(n).inv();
    forn(i, n) a[i] *= rn;
    reverse(a.begin() + 1, a.end());
  }
}

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
  int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
  a.resize(cnt);
  b.resize(cnt);
  ntt(a, false);
  ntt(b, false);
  vector<Mint> c(cnt);
  forn(i, cnt) c[i] = a[i] * b[i];
  ntt(c, true);
  return c;
}

int main() {
  prepare();
  
  vector<Mint> fact(1, 1), ifact(1, 1);
  auto C = [&](int n, int k) -> Mint {
    if (k < 0 || k > n) return 0;
    while (sz(fact) <= n) {
      fact.push_back(fact.back() * sz(fact));
      ifact.push_back(fact.back().inv());
    }
    return fact[n] * ifact[k] * ifact[n - k];
  };
  
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  forn(i, n) cin >> a[i] >> b[i];
  
  vector<Mint> ans(1, 1);
  forn(i, n) {
    vector<Mint> Cs;
    for (int j = b[i] - sz(ans) + 1; j < sz(ans) + a[i]; ++j)
      Cs.push_back(C(a[i] + b[i], j));
    auto res = mul(ans, Cs);
    int cnt = sz(ans);
    ans.resize(cnt + a[i] - b[i]);
    forn(j, sz(ans)) ans[j] = res[cnt + j - 1];
  }
  
  cout << accumulate(ans.begin(), ans.end(), Mint(0)) << endl;
}

t = int(input())
for i in range(t):
    s = input()
    if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
        print('YES')
    else:
        print('NO')

t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    a = [s[i] for i in range(n)]
    cnt = n // 2 - 1
    for j in range(n):
        if a[j] == '?':
            if cnt > 0:
                cnt -= 1
                a[j] = '('
            else:
                a[j] = ')'
    bal = 0
    minbal = 0
    for j in range(n):
        if a[j] == '(':
            bal += 1
        else:
            bal -= 1
        minbal = min(bal, minbal)
    print('YES' if bal == 0 and minbal >= 0 else 'NO') 

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> r(n);
	for (int &x : r) cin >> x;
	int m;
	cin >> m;
	vector<int> b(m);
	for (int &x : b) cin >> x;
	partial_sum(r.begin(), r.end(), r.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
}

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

for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
	dp[0][0] = 0
	ans = 0
	for i in range(n + 1):
		for j in range(m + 1):
			if i < n:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
			if j < m:
				dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
			ans = max(ans, dp[i][j])
	print(ans)

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }
        val h = readLine()!!.split(' ').map { it.toInt() }

        var mn = h[0]
        var mx = h[0]
        var ok = true
        for (i in 1 until n) {
            mn = maxOf(mn - k + 1, h[i])
            mx = minOf(mx + k - 1, h[i] + k - 1)
            if (mn > mx) {
                ok = false
                break
            }
        }
        if (h[n - 1] !in mn..mx)
            ok = false
        println(if (ok) "YES" else "NO")
    }
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n;

inline bool read() {
	if(!(cin >> n))
		return false;
	return true;
}

void calc(int n, vector<pt> &ans) {
	if (n == 2)
		return;
	
	int y = max(1, (int)sqrt(n) - 1);
	while (y < (n + y - 1) / y)
		y++;
	
	fore (pos, y + 1, n)
		ans.emplace_back(pos, n);
	ans.emplace_back(n, y);
	ans.emplace_back(n, y);
	
	calc(y, ans);
}

inline void solve() {
	vector<pt> ans;
	calc(n, ans);
	
	cout << sz(ans) << endl;
	for(auto p : ans)
		cout << p.first << " " << p.second << '\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 tc; cin >> tc;
	while(tc--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;                 
int q;
char buf[N];
int n, k;

int ceilLog(int x)
{
    int y = 0;
    while((1 << y) < x)
        y++;
    return y;
}

int main()
{
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", buf);
        string s = buf;
        int m = min(k, ceilLog(n - k + 2));
        vector<int> used(1 << m, 0);
        vector<int> next0(n, int(1e9));
        if(s[n - 1] == '0')
            next0[n - 1] = n - 1;
        for(int j = n - 2; j >= 0; j--)
            if(s[j] == '0')
                next0[j] = j;
            else
                next0[j] = next0[j + 1];
        int d = k - m;
        for(int j = 0; j < n - k + 1; j++)
        {
            if(next0[j] - j < d)
                continue;
            int cur = 0;
            for(int x = j + d; x < j + k; x++)
                cur = cur * 2 + (s[x] - '0');
            used[((1 << m) - 1) ^ cur] = 1;    
        }
        int ans = -1;
        for(int j = 0; j < (1 << m); j++)
            if(used[j] == 0)
            {
                ans = j;
                break;    
            }
        if(ans == -1)
            puts("NO");
        else
        {
            puts("YES");
            string res(d, '0');
            string res2;
            for(int j = 0; j < m; j++)
            {
                res2.push_back('0' + (ans % 2));
                ans /= 2;
            }
            reverse(res2.begin(), res2.end());
            res += res2;
            puts(res.c_str());
        }
    }
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int n, k, nn;

vector<long long> t, ps;

void push(int v, int l, int r){
	if (l < r - 1){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v] * (r - l);
	ps[v] = 0;
}

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

long long get(int v, int l, int r, int L, int R){
	push(v, l, r);
	if (L >= R)
		return 0;
	if (l == L && r == R)
		return t[v];
	int m = (l + r) / 2;
	long long res = get(v * 2, l, m, L, min(m, R)) + get(v * 2 + 1, m, r, max(m, L), R);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int trav(int v, int l, int r, int cnt){
	push(v, l, r);
	if (l == r - 1)
		return l;
	int m = (l + r) / 2;
	push(v * 2, l, m);
	push(v * 2 + 1, m, r);
	int res = INF;
	if (t[v * 2] >= cnt)
		res = trav(v * 2, l, m, cnt);
	else if (t[v * 2 + 1] >= cnt - t[v * 2])
		res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int main() {
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	sort(a.begin(), a.end(), greater<int>());
	nn = a[0] + 500;
	t.resize(4 * nn);
	ps.resize(4 * nn);
	upd(1, 0, nn, 0, 1, 1);
	int fst = 0;
	int ans = INF;
	forn(i, n){
		while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
		upd(1, 0, nn, fst, fst + 1, -1);
		upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
		upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
		ans = min(ans, trav(1, 0, nn, k));
	}
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}

for i in range(int(input())):
	a, b, c = map(int, input().split())
	if (a + b + c) % 9 != 0:
		print("NO")
	else:
	    print("YES" if min(a, b, c) >= (a + b + c) // 9 else "NO")

for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	cur = [0, 0]
	for i in range(n):
		cur[i % 2] += a[i] - 1
	for j in range(2):
		if 2 * cur[j] > s:
			continue
		for i in range(n):
			if i % 2 == j:
				a[i] = 1
		break
	print(*a)

def inside(l, r, x):
	return min(l, r) <= x <= max(l, r)

def sg(x):
	return -1 if x < 0 else int(x > 0)

for _ in range(int(input())):
	n = int(input())
	qs = []
	for i in range(n):
		qs.append(list(map(int, input().split())))
	qs.append([4*10**9, 0])
	ans = 0
	pos, dr, lft = 0, 0, 0
	for i in range(n):
		t, x = qs[i]
		tn = qs[i + 1][0]
		if lft == 0:
			lft = abs(pos - x)
			dr = sg(x - pos)
		tmp = min(lft, tn - t)
		if inside(pos, pos + dr * tmp, x):
			ans += 1
		pos += dr * tmp
		lft -= tmp
	print(ans)

#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;
vector<int> b;

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

bool ok(const vector<int> &a, const vector<int> &b, int cnt) {
	fore (i, 0, cnt) {
		if (a[i] >= b[sz(b) - cnt + i])
			return false;
	}
	return true;
}

inline void solve() {
	vector<int> nb;
	fore (i, 1, 2 * n + 1) {
		if (!binary_search(b.begin(), b.end(), i))
			nb.push_back(i);
	}
	
	int mx[2] = {-1, -1};
	fore (k, 0, 2) {
		int lf = 0, rg = n + 1;
		while (rg - lf > 1) {
			int mid = (lf + rg) / 2;
			if (ok(b, nb, mid))
				lf = mid;
			else
				rg = mid;
		}
		mx[k] = lf;
		if (!ok(nb, b, n - lf)) {
			cout << 0 << endl;
			return;
		}
		swap(b, nb);
	}
	
	assert(n - mx[1] <= mx[0]);
	cout << mx[0] - (n - mx[1]) + 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;
}

#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;
vector<int> b;

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

int getMax(const vector<int> &a, const vector<int> &b) {
	int uk = 0;
	fore (i, 0, sz(a)) {
		while (uk < sz(b) && b[uk] < a[i])
			uk++;
		if (uk >= sz(b))
			return i;
		uk++;
	}
	return sz(a);
}

inline void solve() {
	vector<int> nb;
	fore (i, 1, 2 * n + 1) {
		if (!binary_search(b.begin(), b.end(), i))
			nb.push_back(i);
	}
	
	int mxX = getMax(b, nb);
	int mnX = n - getMax(nb, b);
	
	cout << mxX - mnX + 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;
}

#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>> g, h, ng;

vector<int> rk, p;

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

void unite(int a, int b){
	a = getp(a), b = getp(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	rk[a] += rk[b];
	p[b] = a;
}

vector<vector<int>> comp;

vector<int> ord;
vector<int> used;
bool fl;

void ts(int v, const vector<vector<int>> &g){
	used[v] = 1;
	for (int u : g[v]){
		if (used[u] == 0)
			ts(u, g);
		else if (used[u] == 1)
			fl = false;
		if (!fl) return;
	}
	ord.push_back(v);
	used[v] = 2;
}

bool topsort(const vector<vector<int>> &g){
	int n = g.size();
	used.assign(n, 0);
	ord.clear();
	fl = true;
	forn(i, n) if (!used[i]){
		ts(i, g);
		if (!fl) return false;
	}
	reverse(ord.begin(), ord.end());
	return true;
}

vector<int> pos;

bool dfs(int v){
	for (int u : g[v]){
		if (pos[u] < pos[v])
			return false;
		if (!dfs(u))
			return false;
	}
	return true;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	g.resize(n);
	h.resize(n);
	ng.resize(n);
	int rt = -1;
	forn(i, n){
		int p;
		scanf("%d", &p);
		--p;
		if (p == -1)
			rt = i;
		else
			g[p].push_back(i);
	}
	rk.assign(n, 1);
	p.resize(n);
	iota(p.begin(), p.end(), 0);
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		h[v].push_back(u);
		unite(v, u);
	}
	if (!topsort(h)){
		puts("0");
		return 0;
	}
	auto ord1 = ord;
	vector<int> pos1(n);
	forn(i, n) pos1[ord1[i]] = i;
	forn(v, n) for (int u : g[v]) if (getp(v) != getp(u))
		ng[getp(v)].push_back(getp(u));
	if (!topsort(ng)){
		puts("0");
		return 0;
	}
	comp.resize(n);
	forn(i, n) comp[getp(i)].push_back(i);
	vector<int> fin;
	for (int it : ord){
		sort(comp[it].begin(), comp[it].end(), [&](int v, int u){ return pos1[v] < pos1[u]; });
		for (int v : comp[it])
			fin.push_back(v);
	}
	pos.resize(n);
	forn(i, n) pos[fin[i]] = i;
	if (!dfs(rt)){
		puts("0");
		return 0;
	}
	for (int v : fin)
		printf("%d ", v + 1);
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 22;

int dp[2][1 << N];
int val[2 * N];

int main() {
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);
	
	int k = x + y;
	int m = max(x, y);
	int FULL = (1 << m) - 1;
	
	for (int i = 0; i < k; ++i)
		val[i] = n / k + (i < n % k);
	for (int mask = 0; mask < (1 << m); ++mask)
		dp[0][mask] = -INF;
	dp[0][0] = 0;
	
	for (int i = 0; i < k; ++i) {
		for (int mask = 0; mask < (1 << m); ++mask)
			dp[1][mask] = -INF;
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (dp[0][mask] == -INF)
				continue;
			int nmask = (mask << 1) & FULL;
			dp[1][nmask] = max(dp[1][nmask], dp[0][mask]);
			if (((mask >> (x - 1)) & 1) | ((mask >> (y - 1)) & 1))
				continue;
			nmask |= 1;
			dp[1][nmask] = max(dp[1][nmask], dp[0][mask] + val[i]);
		}
		swap(dp[0], dp[1]);
	}
	
	int ans = 0;
	for (int mask = 0; mask < (1 << m); ++mask) 
		ans = max(ans, dp[0][mask]);
	printf("%d\n", ans);
}