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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

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

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

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

    return 0;
}

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

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

#include <bits/stdc++.h>

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

using namespace std;

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

#include <bits/stdc++.h>

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

using namespace std;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

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

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

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

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

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

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

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

vector<node> f;

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

using pt = pair<int, int>;

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

import kotlin.math.sqrt

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

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

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

#include <bits/stdc++.h>

using namespace std;

const long long pw10 = 1e12;

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

#include <bits/stdc++.h>

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

using namespace std;

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

const int MOD = 998244353;

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

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

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

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

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

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

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

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

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

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

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

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

int main()
{
    string fb;
    int cur = 1;
    while(fb.size() < 100)
    {
        if(cur % 3 == 0) fb += "F";
        if(cur % 5 == 0) fb += "B";
        cur++;
    }
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int k;
        cin >> k;
        string s;
        cin >> s;
        cout << (fb.find(s) != string::npos ? "YES" : "NO") << endl;
    }
}

for _ in range(int(input())):
    a = input()
    b = input()
    if a[0] == b[0]:
        print("YES")
        print(a[0] + "*")
        continue
    if a[-1] == b[-1]:
        print("YES")
        print("*" + a[-1])
        continue
    for i in range(len(b) - 1):
        if (b[i] + b[i + 1]) in a:
            print("YES")
            print("*" + b[i] + b[i + 1] + "*")
            break
    else:
        print("NO")

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

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int l, r;
        cin >> l >> r;
        int max_size = 1;
        while((l << max_size) <= r)
            max_size++;
        int ans2 = (r / (1 << (max_size - 1)) - l + 1);
        if(max_size > 1)
            ans2 += (max_size - 1) * max(0, (r / (1 << (max_size - 2)) / 3 - l + 1));
        cout << max_size << " " << ans2 << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

const int N = 222222;
const int K = 22;
const li INF = 1e18;

int n, k, x;
int a[N];
li dp[N][K][3];

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int tc;
  cin >> tc;
  while (tc--) {
    cin >> n >> k >> x;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) { 
        for (int t = 0; t < 3; ++t) {
          dp[i][j][t] = -INF;
        }
      }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= k; ++j) {
        for (int t = 0; t < 3; ++t) {
          if (dp[i][j][t] == -INF) continue;
          for (int jj = j; jj <= min(k, j + 1); ++jj) {
            li add = a[i] + (j == jj ? -x : x);
            for (int tt = t; tt < 3; ++tt) {
              dp[i + 1][jj][tt] = max(dp[i + 1][jj][tt], dp[i][j][t] + (tt == 1 ? add : 0));
            }
          }
        }
      }
    }
    cout << max(dp[n][k][1], dp[n][k][2]) << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

vector<vector<int>> g;
vector<multiset<int>> len;
multiset<int> all;

int getlen(int v){
    return len[v].empty() ? 1 : *len[v].begin() + 1;
}

void init(int v, int p = -1){
    for (int u : g[v]) if (u != p){
        init(u, v);
        len[v].insert(getlen(u));
    }
    if (int(len[v].size()) > 1){
        all.insert(*(++len[v].begin()));
    }
}

int ans;

void dfs(int v, int p = -1){
    ans = max(ans, min(*len[v].begin() + 1, *all.begin()));
    
    for (int u : g[v]) if (u != p){
        if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
        len[v].erase(len[v].find(getlen(u)));
        if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
        
        if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
        len[u].insert(getlen(v));
        if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
        
        dfs(u, v);
        
        if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
        len[u].erase(len[u].find(getlen(v)));
        if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
        
        if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
        len[v].insert(getlen(u));
        if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
    }
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        g.assign(n, {});
        forn(i, n - 1){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        len.assign(n, {});
        all.clear();
        all.insert(n);
        init(0);
        ans = 0;
        dfs(0);
        printf("%d\n", ans);
    }
}

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

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

using li = long long;

const int MAXLEN = 5;

vector<int> divs(int x) {
  vector<int> res;
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      res.push_back(i);
      if (i * i != x)
        res.push_back(x / i);
    }
  }
  return res;
}

int main() {
  int A, B, N;
  cin >> A >> B >> N;

  vector<int> pw(10);
  pw[0] = 1;
  for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10;
  
  int PW = pw[MAXLEN];
  set<array<int, 3>> used;
  
  vector<int> len(PW);
  for (int i = 0; i < PW; ++i)
    len[i] = sz(to_string(i));
  
  for (int lenn = 1; lenn <= 9; ++lenn) {
    int x = pw[lenn] - 1;
    for (int k2 : divs(x)) {
      int r = x / k2;
      for (int d = 1; d < PW; ++d) {
        for (int lenb = len[d]; lenb <= MAXLEN; ++lenb) {
          int bg = pw[lenb] - d * li(r) % pw[lenb];
          int dd = d / __gcd(d, bg);
          int lb = (pw[lenb - 1] + bg - 1) / bg;
          int rb = (pw[lenb] - 1) / bg;
          for (int g = (lb + dd - 1) / dd * dd; g <= rb; g += dd) {
            int b = bg * g;
            assert(b % d == 0);
            if (b >= B || __gcd(b / d, r) != 1) continue;
            int ag = (d * li(r) + bg) / pw[lenb];
            li n = b / d * li(k2) * ag;
            if (n < N && ag * g < A && __gcd(ag, bg) == 1 && sz(to_string(n)) == lenn) 
              used.insert({ag * g, b, n});
          }
        }
      }
    }
  }
  
  int res = 0;
  for (auto it : used) {
    li a = it[0], b = it[1], n = it[2];
    int lenn = sz(to_string(n));
    int lenb = sz(to_string(b));
    res += a * b * pw[lenn] + n * b == a * n * pw[lenb] + a * b;
  }
  
  cout << res << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  auto ok = [](string s) {
    for (int i = 1; i < (int)s.size(); ++i)
      if (s[i - 1] == s[i]) return false;
    return true;    
  };
  
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    bool f = false;
    for (int x = 0; x < 2; ++x) {
      string cs = s, ct = t;
      for (int i = 0; i < n; ++i) {
        f |= ok(cs) && ok(ct);
        ct.push_back(cs.back());
        cs.pop_back();
      }
      swap(n, m);
      swap(s, t);   
    }
    cout << (f ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    reverse(t.begin(), t.end());
    s += t;
    int cnt = 0;
    for (int i = 1; i < n + m; ++i) cnt += s[i - 1] == s[i];
    cout << (cnt <= 1 ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    int L = 0, R = 55;
    while (n--) {
      int l, r;
      cin >> l >> r;
      if (l <= k && k <= r)
        L = max(L, l), R = min(R, r);
    }
    cout << (L == R ? "YES\n" : "NO\n");
  }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<li> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<li> sum(n + 1);
    for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + b[i];
    vector<li> cnt(n + 1), add(n + 1);
    for (int i = 0; i < n; ++i) {
      int j = upper_bound(sum.begin(), sum.end(), a[i] + sum[i]) - sum.begin() - 1;
      cnt[i] += 1;
      cnt[j] -= 1;
      add[j] += a[i] - sum[j] + sum[i];
    }
    for (int i = 0; i < n; ++i) {
      cout << cnt[i] * b[i] + add[i] << ' ';
      cnt[i + 1] += cnt[i];   
    }
    cout << '\n';
  }
}

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

const int MOD = 998244353;

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

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

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

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

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

int main()
{
    int n;
    cin >> n;
    int ans = 1;
    for(int i = 1; i <= n / 6; i++)
        ans = mul(ans, divide(i + n / 6, i));
    for(int i = 0; i < n / 3; i++)
    {
        vector<int> a(3);
        for(int j = 0; j < 3; j++)
            cin >> a[j];
        int mn = *min_element(a.begin(), a.end());
        int cnt_min = count(a.begin(), a.end(), mn);
        ans = mul(ans, cnt_min);
    }
    cout << ans << endl;
}

import java.util.*

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

        val d = Array(2) { LongArray(n) { 0 } }
        for (tp in 0..1) {
            val s = Stack<Pair<Int, Int>>()

            for (i in h.indices) {
                while (s.isNotEmpty() && s.peek().first > h[i] - i)
                    s.pop()
                var j = maxOf(-1, i - h[i])
                if (s.isNotEmpty())
                    j = maxOf(j, s.peek().second)

                val len = (i - j).toLong()
                d[tp][i] = len * h[i] - len * (len - 1) / 2
                if (j >= 0 && len < h[i])
                    d[tp][i] += d[tp][j]

                s.push(Pair(h[i] - i, i))
            }
            h = h.reversed()
        }
        d[1] = d[1].reversedArray()

        var ans = 1e18.toLong()
        val sum = h.fold(0L) { total, it -> total + it }
        for (i in h.indices) {
            val cur = sum - d[0][i] - d[1][i] + 2 * h[i]
            ans = minOf(ans, cur)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

vector<vector<int>> g;
vector<int> req;
vector<char> used;

vector<int> d;

bool dfs(int v, int p = -1){
    d[v] = 0;
    for (int u : g[v]) if (u != p){
        if (!dfs(u, v)) return false;
        if (!used[u]) d[v] = max(d[v], d[u] + 1);
    }
    if (req[v] == 0 || d[v] >= req[v]) return true;
    if (p == -1 || used[p]) return false;
    used[p] = true;
    req[p] = req[v] - 1;
    return true;
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        g.assign(n, {});
        d.resize(n);
        forn(i, n - 1){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        int k;
        scanf("%d", &k);
        vector<int> a(k);
        forn(i, k){
            scanf("%d", &a[i]);
            --a[i];
        }
        int l = 1, r = n;
        int res = 0;
        while (l <= r){
            int m = (l + r) / 2;
            used.assign(n, 0);
            req.assign(n, 0);
            forn(i, k){
                used[a[i]] = true;
                req[a[i]] = m / k + (i < m % k);
            }
            if (dfs(0)){
                res = m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        printf("%d\n", res);
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

typedef unsigned long long uli;

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(n);
        forn(i, n) scanf("%d", &a[i]);
        vector<vector<int>> g(n);
        forn(i, m){
            int v, u;
            scanf("%d%d", &v, &u);
            --v, --u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        vector<char> rem(n);
        vector<int> d(n);
        forn(i, n) d[i] = g[i].size();
        queue<int> q;
        forn(i, n) if (a[i] == d[i]) q.push(i);
        vector<pair<int, int>> ord;
        while (!q.empty()){
            int v = q.front();
            q.pop();
            rem[v] = true;
            for (int u : g[v]) if (!rem[u]){
                --d[u];
                ord.push_back({v, u});
                if (d[u] == a[u])
                    q.push(u);
            }
        }
        reverse(ord.begin(), ord.end());
        vector<uli> mask(n);
        long long ans = n * 1ll * (n + 1) / 2;
        for (int l = 0; l < n; l += 64){
            int r = min(n, l + 64);
            for (int i = l; i < r; ++i)
                mask[i] = 1ull << (i - l);
            for (const pair<int, int> &it : ord)
                mask[it.first] |= mask[it.second];
            forn(i, n){
                ans -= __builtin_popcountll(mask[i]);
                mask[i] = 0;
            }
        }
        printf("%lld\n", ans);
    }
}

#include <bits/stdc++.h>

using namespace std;

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

for _ in range(int(input())):
    a1, a2, a3, a4 = map(int, input().split())
    if a1 == 0:
        print(1)
    else:
        print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) {
      int x;
      cin >> x;
      pos[x] = i;
    }
    int l = (n + 1) / 2, r = (n + 2) / 2;
    while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) {
      --l;
      ++r;
    }
    cout << (n - r + l + 1) / 2 << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 

int get(const vector<int> &a, const vector<int> &b){
	int res = 0;
	while (res < int(a.size()) && a[res] == b[res])
		++res;
	return res;
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		int n, m;
		scanf("%d%d", &n, &m);
		vector<vector<int>> a(n, vector<int>(m));
		forn(i, n) forn(j, m){
			scanf("%d", &a[i][j]);
			--a[i][j];
		}
		vector<vector<int>> b(n, vector<int>(m));
		forn(i, n) forn(j, m) b[i][a[i][j]] = j;
		sort(b.begin(), b.end());
		forn(i, n){
			int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
			int ans = 0;
			if (j > 0) ans = max(ans, get(a[i], b[j - 1]));
			if (j < n) ans = max(ans, get(a[i], b[j]));
			printf("%d ", ans);
		}
		puts("");
	}
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n;
li m1, m2;

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

vector<pt> mFact;
vector<li> divs;

void factM(li m1, li m2) {
	mFact.clear();

	for (int d = 2; d * d <= m1 || d * d <= m2; d++) {
		int cnt = 0;
		while (m1 % d == 0) {
			m1 /= d;
			cnt++;
		}
		while (m2 % d == 0) {
			m2 /= d;
			cnt++;
		}
		if (cnt > 0)
			mFact.push_back({d, cnt});
	}
	if (m1 > m2)
		swap(m1, m2);
	if (m1 > 1)
		mFact.push_back({m1, 1});
	if (m2 > 1) {
		if (m2 == m1)
			mFact.back().y++;
		else
			mFact.push_back({m2, 1});
	}
}

void genDivisors(int pos, li val) {
	if (pos >= sz(mFact)) {
		divs.push_back(val);
		return;
	}
	li cur = val;
	fore (pw, 0, mFact[pos].y + 1) {
		genDivisors(pos + 1, cur);
		if (pw < mFact[pos].y)
			cur *= mFact[pos].x;
	}
}

inline void solve() {
	factM(m1, m2);

	divs.clear();
	genDivisors(0, 1);
	sort(divs.begin(), divs.end());

	vector<int> ans(sz(divs), 0);

	vector<li> dp(sz(divs), -1);
	fore (id, 0, sz(divs)) {
		if (divs[id] <= n)
			dp[id] = divs[id];
		for (auto [p, pw] : mFact) {
			if (divs[id] % p != 0)
				continue;
			
			int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin());
			dp[id] = max(dp[id], dp[pos]);
		}

		if (divs[id] / dp[id] <= n)
			ans[id] = divs[id] / dp[id];
	}

	int cnt = 0;
	int xorSum = 0;
	fore (i, 0, sz(ans)) {
		cnt += ans[i] > 0;
		xorSum ^= ans[i];
	}
	
//	cout << sz(ans) << endl;
//	cout << ans << endl;
	cout << cnt << " " << xorSum << 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 varMul(int x)
{
    return x;
}

template<typename... Args>
int varMul(int x, Args... args)
{
    return mul(x, varMul(args...));
}

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

vector<int> fact, rfact;
vector<int> dp;
int n;

void precalc()
{
    fact.resize(n + 1);
    rfact.resize(n + 1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = mul(i, fact[i - 1]);
    for(int i = 0; i <= n; i++)
        rfact[i] = binpow(fact[i], MOD - 2);
    dp.resize(n + 1, -1);
}

int C(int n, int k)
{
    if(n < 0 || n < k || k < 0) return 0;
    return varMul(fact[n], rfact[k], rfact[n - k]);
}

int calc(int x)
{
    if(dp[x] != -1) return dp[x];
    if(x == 1) return dp[x] = 1;
    if(x == 2) return dp[x] = 1;
    dp[x] = 0;
    int& d = dp[x];
    for(int i = 1; i < x; i++)
    {
        d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1)));
    }   
    return d;
}

int main()
{
    cin >> n;
    precalc();
    cout << add(mul(calc(n), 2), -2) << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int LOGN = 18;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;

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

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

inline int norm(int a) 
{
    while(a >= MOD)
        a -= MOD;
    while(a < 0)
        a += MOD;
    return a;
}

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

inline int inv(int a) 
{
    return binPow(a, MOD - 2);
}

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

void precalc() 
{
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, 1);
        iw[st].assign(1 << st, 1);
        
        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int ibw = inv(bw);
        
        int cw = 1;
        int icw = 1;
        
        for(int k = 0; k < (1 << st); k++) 
        {
            w[st][k] = cw;
            iw[st][k] = icw;
            
            cw = mul(cw, bw);
            icw = mul(icw, ibw);
        }
        
        rv[st].assign(1 << st, 0);
        
        if(st == 0) 
        {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(int a[N], int n, int ln, bool inverse) 
{   
    for(int i = 0; i < n; i++) 
    {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }
    
    for(int st = 0; (1 << st) < n; st++) 
    {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) 
        {
            for(int pos = k; pos < k + len; pos++) 
            {
                int l = a[pos];
                int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
                
                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) 
    {
        int in = inv(n);
        for(int i = 0; i < n; i++)
            a[i] = mul(a[i], in);
    }
}

int aa[N], bb[N], cc[N];

vector<int> multiply(vector<int> a, vector<int> b) 
{
    int sza = a.size();
    int szb = b.size();
    int n = 1, ln = 0;
    while(n < (sza + szb))
        n <<= 1, ln++;
    for(int i = 0; i < n; i++)
        aa[i] = (i < sza ? a[i] : 0);
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : 0);
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = mul(aa[i], bb[i]);
        
    fft(cc, n, ln, true);
    
    int szc = n;
    vector<int> c(szc);
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
    return c;
}                    

int main()
{
    int n;
    cin >> n;
    vector<int> fact(n + 1);
    fact[0] = 1;
    for(int i = 0; i < n; i++)
        fact[i + 1] = mul(fact[i], i + 1);
    precalc();
    vector<int> A = {0, 1, 2};
    vector<int> B = {0, 1, 1};
    vector<int> C = {0, 1, 1};
    vector<int> D = {0, 1, 1};
    vector<int> conv;
    const int K = 2000;
    int last_conv = -1e9;
    while(A.size() <= n)
    {
        int cur = A.size();
        if(cur - last_conv >= K)
        {
            last_conv = cur - 1;
            conv = multiply(C, D);
        }
        /*for(auto x : conv) cerr << x << " ";
        cerr << endl;*/
        int val_A;
        if(last_conv * 2 >= cur)
        {
            val_A = conv[cur];
            // [cur - last_conv, last_conv] are already used
            for(int i = 1; i < (cur - last_conv); i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
            for(int i = last_conv + 1; i < cur; i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
        }
        else
        {
            val_A = 0;
            for(int i = 1; i <= cur - 1; i++)
            {
                val_A = norm(val_A + mul(C[i], D[cur - i]));
            }
        }
        val_A = mul(val_A, fact[cur - 1]);
        val_A = mul(val_A, 2);
        A.push_back(val_A);
        B.push_back(mul(val_A, inv(2)));
        C.push_back(mul(val_A, inv(fact[cur])));
        D.push_back(mul(B.back(), inv(fact[cur - 1])));
    }
    cout << norm(A[n] - 2) << endl;
}

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if a[0] == a[n - 1]:
        print('NO')
    else:
        print('YES')
        print(a[n - 1], end = ' ')
        print(*(a[0:n-1]))

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    int l = 1, r = n * n, t = 0;
    forn(i, n) {
      forn(j, n) {
        if (t) a[i][j] = l++;
        else a[i][j] = r--;
        t ^= 1;
      }
      if (i & 1) reverse(a[i].begin(), a[i].end());
    }
    forn(i, n) forn(j, n) cout << a[i][j] << " \n"[j == n - 1];
  }
}

#include <bits/stdc++.h>

using namespace std;

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

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

const int ZERO = 100000;

int dp[2][ZERO * 2];

void recalc(int x)
{
    for(int i = 0; i < ZERO * 2; i++)
        dp[1][i] = 0;

    for(int i = 0; i < ZERO * 2; i++)
    {
        if(dp[0][i] == 0) continue;
        int nx = x + i;
        dp[1][nx] = add(dp[1][nx], dp[0][i]);
        if(nx != ZERO)
            dp[1][2 * ZERO - nx] = add(dp[1][2 * ZERO - nx], dp[0][i]);
    }

    for(int i = 0; i < ZERO * 2; i++)
        dp[0][i] = dp[1][i];
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    dp[0][ZERO] = 1;
    for(int i = 1; i + 1 < n; i++)
        recalc(a[i]);
    int ans = 0;
    for(int i = 0; i < ZERO * 2; i++)
        ans = add(ans, dp[0][i]);
    cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> a(n), b(n);
		forn(i, n) scanf("%d", &a[i]);
		forn(i, n) scanf("%d", &b[i]);
		vector<int> dx(n + 1);
		forn(i, n) if (b[i] < a[i]){
			++dx[b[i]];
			--dx[a[i]];
		}
		forn(i, n) dx[i + 1] += dx[i];
		vector<int> ans;
		for (int k = 1; k <= n; ++k){
			bool ok = true;
			for (int nk = k; nk <= n; nk += k)
				ok &= dx[nk] == 0;
			if (ok)
				ans.push_back(k);
		}
		printf("%d\n", int(ans.size()));
		for (int k : ans) printf("%d ", k);
		puts("");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 5043;

vector<int> g[N];
int mt[N];
int u[N];
vector<vector<int>> cycle[2];
vector<int> a[2];
int n;
int vs[2];
vector<vector<int>> inter;

bool kuhn(int x)
{
    if(u[x]) return false;
    u[x] = true;
    for(auto y : g[x])
    {
        if(mt[y] == x) continue;
        if(mt[y] == -1 || kuhn(mt[y]))
        {
            mt[y] = x;
            return true;
        }
    }
    return false;
}

int find_intersection(const vector<int>& x, const vector<int>& y)
{
    for(auto i : x)
        for(auto j : y)
            if(i == j)
                return i;
    return -1;
}

int main()
{
    scanf("%d", &n);
    for(int k = 0; k < 2; k++)
    {
        a[k].resize(n);
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &a[k][j]);
            a[k][j]--;
        }    
    }

    for(int k = 0; k < 2; k++)
    {
        vector<bool> used(n);
        for(int i = 0; i < n; i++)
        {
            if(used[i]) continue;
            vector<int> cur;
            int j = i;
            while(!used[j])
            {
                cur.push_back(j);
                used[j] = true;
                j = a[k][j];            
            }
            cycle[k].push_back(cur);
        }
        vs[k] = cycle[k].size();
    }

    inter.resize(vs[0], vector<int>(vs[1]));

    for(int i = 0; i < vs[0]; i++)
        for(int j = 0; j < vs[1]; j++)
        {
            inter[i][j] = find_intersection(cycle[0][i], cycle[1][j]);
            if(inter[i][j] != -1)
                g[i].push_back(j);
        }

    for(int i = 0; i < vs[1]; i++)
        mt[i] = -1;
    for(int i = 0; i < vs[0]; i++)
    {
        for(int j = 0; j < vs[0]; j++)
            u[j] = false;
        kuhn(i);
    }
    
    set<int> res;
    for(int i = 0; i < n; i++) res.insert(i);
    for(int i = 0; i < vs[1]; i++)
        if(mt[i] != -1)
            res.erase(inter[mt[i]][i]);

    printf("%d\n", res.size());
    for(auto x : res) printf("%d ", x + 1);
    puts("");
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

const int LOG = 18;
const int N = int(2e5) + 55;

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

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

int p[LOG][N];
int h[N], tin[N], tout[N], T = 0;

void precalcLca(int v, int pr) {
	tin[v] = T++;
	h[v] = 0;
	if (pr != v)
		h[v] = h[pr] + 1;
	p[0][v] = pr;
	fore (pw, 0, LOG - 1)
		p[pw + 1][v] = p[pw][p[pw][v]];

	for (int to : g[v]) {
		if (to == pr)
			continue;
		precalcLca(to, v);
	}
	tout[v] = T;
}

bool isParent(int l, int v) {
	return tin[l] <= tin[v] && tout[v] <= tout[l];
}

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

int getFarthest(int s) {
	vector<int> used(n, 0);
	queue<int> q;

	used[s] = 1;
	q.push(s);
	int v;
	while (!q.empty()) {
		v = q.front(); 
		q.pop();
		for (int to : g[v]) {
			if (used[to])
				continue;
			used[to] = 1;
			q.push(to);
		}
	}
	return v;
}

int getDist(int u, int v) {
	return h[u] + h[v] - 2 * h[lca(u, v)];
}

const int M = int(2e5);
vector<pt> ops[4 * M];

void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
	if (l >= r || lf >= rg) return;
	if (l == lf && r == rg) {
		ops[v].push_back(op);
		return;
	}
	int mid = (l + r) / 2;
	if (lf < mid)
		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
	if (rg > mid)
		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}

void updDiam(int &s, int &t, int &curD, const pt &op) {
	int v = op.x;
	a[v] = op.y;

	int ns = s, nt = t, nD = curD;

	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
	for (auto &c : cds) {
		int d1 = getDist(c.x, c.y);
		if (nD < a[c.x] + d1 + a[c.y]) {
			nD = a[c.x] + d1 + a[c.y];
			ns = c.x, nt = c.y;
		}
	}
	s = ns;
	t = nt;
	curD = nD;
}

vector<int> ans;

void calcDiams(int v, int l, int r, int s, int t, int curD) {
	for (auto &op : ops[v])
		updDiam(s, t, curD, op);
	if (r - l > 1) {
		int mid = (l + r) / 2;
		calcDiams(2 * v + 1, l, mid, s, t, curD);
		calcDiams(2 * v + 2, mid, r, s, t, curD);
	}
	else
		ans[l] = (curD + 1) / 2;
	
	for (auto &op : ops[v])
		a[op.first] = 0;
}

inline void solve() {
	precalcLca(0, 0);
	int s = getFarthest(0);
	int t = getFarthest(s);

	int m;
	cin >> m;
	vector<int> lst(n, 0);
	fore (i, 0, m) {
		int v, x;
		cin >> v >> x;
		v--;

		setOp(0, 0, m, lst[v], i, {v, a[v]});
		lst[v] = i;
		a[v] = x;
	}
	fore (v, 0, n)
		setOp(0, 0, m, lst[v], m, {v, a[v]});

	ans.resize(m, -1);
	a.assign(n, 0);
	calcDiams(0, 0, m, s, t, getDist(s, t));

	fore (i, 0, m)
		cout << ans[i] << '\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;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

const int LOG = 18;
const int N = int(2e5) + 55;

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

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

struct Lca {
	vector<int> log2, tin;
	vector< vector<int> > hs;
	int T = 0;

	void dfs(int v, int p, int cdepth) {
		tin[v] = T++;
		hs[0][tin[v]] = cdepth;
		for (int to : g[v]) {
			if (to == p)
				continue;
			dfs(to, v, cdepth + 1);
			hs[0][T++] = cdepth;
		}
	}

	void init() {
		log2.assign(2 * n, 0);
		fore (i, 2, sz(log2))
			log2[i] = log2[i / 2] + 1;
		hs.assign(log2.back() + 1, vector<int>(2 * n, INF));

		tin.assign(n, 0);
		T = 0;

		dfs(0, -1, 0);
		assert(T < 2 * n);

		fore (pw, 0, sz(hs) - 1) {
			fore (i, 0, T - (1 << pw))
				hs[pw + 1][i] = min(hs[pw][i], hs[pw][i + (1 << pw)]);
		}
	}

	int getMin(int u, int v) {
		if (tin[u] > tin[v])
			swap(u, v);
		int len = log2[tin[v] + 1 - tin[u]];
		int d = min(hs[len][tin[u]], hs[len][tin[v] + 1 - (1 << len)]);
//		cerr << u << " " << v << ": " << d << endl;
		return d;
	}
	inline int getH(int v) {
		return hs[0][tin[v]];
	}
} lcaST;

int getFarthest(int s) {
	vector<int> used(n, 0);
	queue<int> q;

	used[s] = 1;
	q.push(s);
	int v;
	while (!q.empty()) {
		v = q.front(); 
		q.pop();
		for (int to : g[v]) {
			if (used[to])
				continue;
			used[to] = 1;
			q.push(to);
		}
	}
	return v;
}

int getDist(int u, int v) {
	return lcaST.getH(u) + lcaST.getH(v) - 2 * lcaST.getMin(u, v);
}

const int M = int(2e5);
vector<pt> ops[4 * M];

void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
	if (l >= r || lf >= rg) return;
	if (l == lf && r == rg) {
		ops[v].push_back(op);
		return;
	}
	int mid = (l + r) / 2;
	if (lf < mid)
		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
	if (rg > mid)
		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}

void updDiam(int &s, int &t, int &curD, const pt &op) {
	int v = op.x;
	a[v] = op.y;

	int ns = s, nt = t, nD = curD;

	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
	for (auto &c : cds) {
		int d1 = getDist(c.x, c.y);
		if (nD < a[c.x] + d1 + a[c.y]) {
			nD = a[c.x] + d1 + a[c.y];
			ns = c.x, nt = c.y;
		}
	}
	s = ns;
	t = nt;
	curD = nD;
}

vector<int> ans;

void calcDiams(int v, int l, int r, int s, int t, int curD) {
	for (auto &op : ops[v])
		updDiam(s, t, curD, op);
	if (r - l > 1) {
		int mid = (l + r) / 2;
		calcDiams(2 * v + 1, l, mid, s, t, curD);
		calcDiams(2 * v + 2, mid, r, s, t, curD);
	}
	else
		ans[l] = (curD + 1) / 2;
	
	for (auto &op : ops[v])
		a[op.first] = 0;
}

inline void solve() {
	lcaST.init();
	int s = getFarthest(0);
	int t = getFarthest(s);

	int m;
	cin >> m;
	vector<int> lst(n, 0);
	fore (i, 0, m) {
		int v, x;
		cin >> v >> x;
		v--;

		setOp(0, 0, m, lst[v], i, {v, a[v]});
		lst[v] = i;
		a[v] = x;
	}
	fore (v, 0, n)
		setOp(0, 0, m, lst[v], m, {v, a[v]});

	ans.resize(m, -1);
	a.assign(n, 0);
	calcDiams(0, 0, m, s, t, getDist(s, t));

	fore (i, 0, m)
		cout << ans[i] << '\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;
}

Я не профессиональный веб-разработчик, даже не назвал бы себя опытным. С помощью друзей из kbr дискорд сервера я пофиксил серьезные баги, но если вы что-то найдете, то пишите мне в личные сообщения. Я постараюсь исправить все как можно скорее.

• Performance считается как $$$\mathit{oldRating} + 4 \cdot \mathit{delta}$$$.
• Последний рейтинговый AC показывает время до конца контеста. Чем меньше значение, тем ближе к концу.

t = int(input())
for i in range(t):
    print(eval(input()))

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int _ = 0; _ < t; _++)
    {
        vector<int> a(4);
        for(int i = 0; i < 4; i++)
            cin >> a[i];
        int maxpos = max_element(a.begin(), a.end()) - a.begin();
        int minpos = min_element(a.begin(), a.end()) - a.begin();
        if(maxpos + minpos == 3)
            puts("YES");
        else
            puts("NO");
    }
}

def construct(f, k):
    return [(i + 2 if i < f - 1 else 1) for i in range(k)]

t = int(input())
for i in range(t):
    k, n = map(int, input().split())
    ans = 1
    for f in range(1, k):
        d = construct(f, k - 1)
        if sum(d) <= n - 1:
            ans = f
    res = [1]
    d = construct(ans, k - 1)
    for x in d:
        res.append(res[-1] + x)
    print(*res)

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

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int j = 0; j < n; j++)
            cin >> a[j];
        int mn = 0, mx = int(1e9);
        for(int j = 0; j + 1 < n; j++)
        {
            int x = a[j];
            int y = a[j + 1];
            int midL = (x + y) / 2;
            int midR = (x + y + 1) / 2;
            if(x < y)
                mx = min(mx, midL);
            if(x > y)
                mn = max(mn, midR);
        }
        if(mn <= mx) cout << mn << endl;
        else cout << -1 << endl;
    }
}

for tc in range(int(input())):
  n = int(input())
  p = list(map(int, input().split()))
  a, b, c = 0, 0, 0
  for i in range(n):
    if p[i] != i + 1 and p[i] != n - i:
      c += 1
    elif p[i] != i + 1:
      a += 1
    elif p[i] != n - i:
      b += 1
  if a + c <= b:
    print("First")
  elif b + c < a:
    print("Second")
  else:
    print("Tie")

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++)

struct op{
    int t, x, y, i;
};

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<string>> a(k + 1, vector<string>(n));
    forn(z, k + 1) forn(i, n)
        cin >> a[z][i];
    
    vector<int> cnt(k + 1);
    forn(z, k + 1){
        for (int i = 1; i < n - 1; ++i){
            for (int j = 1; j < m - 1; ++j){
                bool ok = true;
                forn(t, 4)
                    ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]];
                cnt[z] += ok;
            }
        }
    }
    
    vector<int> ord(k + 1);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&cnt](int x, int y){
        return cnt[x] > cnt[y];
    });
    
    vector<op> ops;
    forn(z, k){
        forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){
            a[ord[z]][i][j] ^= '0' ^ '1';
            ops.push_back({1, i + 1, j + 1, -1});
        }
        ops.push_back({2, -1, -1, ord[z + 1] + 1});
    }
    
    cout << ord[0] + 1 << '\n';
    cout << ops.size() << '\n';
    for (auto it : ops){
        cout << it.t << " ";
        if (it.t == 1)
            cout << it.x << " " << it.y << '\n';
        else
            cout << it.i << '\n';
    }
}

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

int n;
li x, y;
vector<li> a;

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

li ceil(li a, li b) {
    assert(a >= 0 && b >= 0);
    return (a + b - 1) / b;
}

inline void solve() {
    sort(a.begin(), a.end());
    
    vector<li> t(n), b(n);
    fore (i, 0, n) {
        if (i > 0 && b[i - 1] >= a[i]) {
            t[i] = t[i - 1];
            b[i] = b[i - 1] + 1;
        } else {
            t[i] = a[i] - i;
            b[i] = a[i] + 1;
        }
    }
    
    li ans = 0;
    while (x < y) {
        int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
        
        li p = pos, m = n - pos;
        if (x + p >= y) {
            cout << ans + (y - x) << endl;
            return;
        }
        if (p <= m) {
            cout << -1 << endl;
            return;
        }
        
        //1. x + k(p - m) + p >= y
        li k = ceil(y - x - p, p - m);
        if (pos < n) {
            //2. x + k(p - m) >= t[pos]
            k = min(k, ceil(t[pos] - x, p - m));
        }
        ans += k * n;
        //x + k(p - m) < y, since 1. and p >= p - m
        x += k * (p - m);
    }
    assert(false);
}

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

t = int(input())
for i in range(t):
    input()
    xs = []
    ys = []
    for j in range(3):
        x, y = map(int, input().split())
        xs.append(x)
        ys.append(y)
    print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO')

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    x = a[0]
    a = sorted(a[1:])
    for y in a:
        if y > x:
            x += (y - x + 1) // 2
    print(x)

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

const int N = 143;
int n;

int a[N][N];
int dp[N][N];

bool check(int cnt, int last)
{
    for(int i = 0; i < cnt; i++)
    {
        if(a[i][cnt - 1] == 0) continue;
        if(a[i][cnt - 1] == 1 && last > i) return false;
        if(a[i][cnt - 1] == 2 && last <= i) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
            cin >> a[i][j];
    }
    if(a[0][0] != 2) dp[1][0] = 2;
    for(int i = 1; i < n; i++)
        for(int j = 0; j < i; j++)
            for(int k : vector<int>({j, i}))
                if(check(i + 1, k))
                    dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]);
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = add(ans, dp[n][i]);
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int k = count(s.begin(), s.end(), '1');
  for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x)
    cout << x << ' ';
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> c(n);
    forn(i, n){
        scanf("%d", &c[i]);
        --c[i];
    }
    vector<int> x(m);
    forn(i, m) scanf("%d", &x[i]);
    
    vector<long long> g(m);
    forn(i, n - 1){
        g[c[i]] |= 1ll << c[i + 1];
        g[c[i + 1]] |= 1ll << c[i];
    }
    g[c[0]] |= 1ll << c[0];
    g[c[n - 1]] |= 1ll << c[n - 1];
    
    int mid = m / 2;
    vector<int> dp(1 << mid, 1e9);
    forn(mask, 1 << (m - mid)){
        long long chk = 0;
        int tot = 0;
        forn(i, m - mid){
            if ((mask >> i) & 1)
                tot += x[i + mid];
            else
                chk |= g[i + mid];
        }
        if (((chk >> mid) | mask) != mask)
            continue;
        chk &= (1ll << mid) - 1;
        dp[chk] = min(dp[chk], tot);
    }
    forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){
        dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]);
    }
    int ans = 1e9;
    forn(mask, 1 << mid){
        long long chk = 0;
        int tot = 0;
        forn(i, mid){
            if ((mask >> i) & 1)
                tot += x[i];
            else
                chk |= g[i];
        }
        chk &= (1ll << mid) - 1;
        if ((chk | mask) != mask)
            continue;
        ans = min(ans, dp[mask] + tot);
    }
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;
using li = long long;
using ld = long double;
using pii = pair<int, int>;

const int INF = 2e9 + 13;
const li INF64 = 2e18 + 13;
const int M = 998244353;
const int A = 2e5 + 13;

const int N = 2e5 + 13;
const int B = 2000;
const int SQRTA = 500;
const int K = N / B + 113;

int val[N];
vector<int> g[N];
int sz[N];
int gr[N];
int leaf[N], group_root[N];
int par[N];
bool heavy[N];

int tin[N], tout[N], T = 0, mid[N];
int et[N];
int valet[N];


void dfs1(int v, int pr, int depth) {
    par[v] = pr;
    sz[v] = 1;

    int mx = -1;
    for(int i = 0; i < g[v].size(); i++) {
        int u = g[v][i];
        if(u != pr) {
            dfs1(u, v, depth + 1);
            sz[v] += sz[u];
            if(mx == -1 || sz[g[v][mx]] < sz[u])
                mx = i;
        }
    }

    if(mx != -1)
        swap(g[v][mx], g[v][0]);
}

void dfs2(int v) {
    et[T] = v;
    tin[v] = T++;

    for(int u : g[v]) {
        if(u != par[v])
            dfs2(u);
    }

    tout[v] = T;
}

struct Query {
    int ind;
    int v, u;
    int lv, rv, lu, ru;
    int b;

    Query() {};
};

bool cmp(const Query& a, const Query& b) {
    if(a.b != b.b)
        return a.b < b.b;
    else
        return a.lu < b.lu;
}

int cnt[A];
int block_index[A];
int block_mx[A];
int block_cnt_of_cnt[A / SQRTA + 13][A];

inline void insert(int i) {
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    cnt[valet[i]]++;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
    if(cnt[valet[i]] > block_mx[block_index[valet[i]]])
        block_mx[block_index[valet[i]]]++;
}

inline void erase(int i) {
    if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1)
        block_mx[block_index[valet[i]]]--;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
    cnt[valet[i]]--;
    block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
}

int get_mode() {
    int mx = 0;
    for(int i = 0; i < A / SQRTA + 1; i++)
        mx = max(mx, block_mx[i]);
    for(int i = 0; ; i++) {
        if(block_mx[i] == mx) {
            for(int j = i * SQRTA; ; j++) {
                if(cnt[j] == mx)
                    return j;
            }
        }
    }
}

Query queries[N];
int ans[N];

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

    for(int i = 0; i < n; i++)
        cin >> val[i];

    for(int i = 1; i < n; i++) {
        int v, u;
        cin >> v >> u;

        v--;
        u--;

        g[v].push_back(u);
        g[u].push_back(v);
    }

    dfs1(0, -1, 0);

    vector<pii> ord(n);
    for(int i = 0; i < n; i++) {
        ord[i] = {sz[i], i};
        gr[i] = -1;
    }

    sort(ord.begin(), ord.end());

    for(int i = 0; i < n; i++) {
        if(sz[i] >= B)
            heavy[i] = true;
    }

    int cur = 0;
    for(int i = 0; i < n; i++) {
        int v = ord[i].s;
        if(sz[v] < B || gr[v] != -1)
            continue;

        leaf[cur] = v;

        int u = v;
        while(gr[u] == -1 && sz[u] - sz[v] < B) {
            gr[u] = cur;
            group_root[cur] = u;
            u = par[u];
        }

        cur++;
    }

    dfs2(0);

    for(int i = 0; i < n; i++) {
        if(sz[i] < B) {
            gr[i] = cur + tin[i] / B;
        }
    }

    for(int i = 0; i < n; i++)
        valet[i] = val[et[i]];

    for(int i = 0; i < A; i++) {
        block_index[i] = i / SQRTA;
    }

    int q;
    cin >> q;

    for(int i = 0; i < q; i++) {
        queries[i].ind = i;
        cin >> queries[i].v >> queries[i].u;

        queries[i].v--;
        queries[i].u--;

        queries[i].lv = tin[queries[i].v];
        queries[i].rv = tout[queries[i].v];
        queries[i].lu = tin[queries[i].u];
        queries[i].ru = tout[queries[i].u];

        if(queries[i].lv > queries[i].lu) {
            swap(queries[i].v, queries[i].u);
            swap(queries[i].lv, queries[i].lu);
            swap(queries[i].rv, queries[i].ru);
        }

        queries[i].b = gr[queries[i].v];
    }

    sort(queries, queries + q, cmp);

    int lv = 0, rv = 0, lu = 0, ru = 0;
    li fir = 0, sec = 0;

    int hs = 0;
    for(int i = 0; i < q; i++) {
        int qlv = queries[i].lv;
        int qrv = queries[i].rv;
        int qlu = queries[i].lu;
        int qru = queries[i].ru;

        fir += abs(lv - qlv) + abs(rv - qrv);
        sec += abs(lu - qlu) + abs(ru - qru);

        if(queries[i].b < cur) {
            while(rv < qrv)
                insert(rv++);
            while(lv > qlv)
                insert(--lv);
            while(rv > qrv)
                erase(--rv);
            while(lv < qlv)
                erase(lv++);
        } else {
            while(rv > lv)
                erase(--rv);
            lv = qlv;
            rv = lv;
            while(rv < qrv)
                insert(rv++);
        }

        while(ru < qru)
                insert(ru++);
            while(lu > qlu)
                insert(--lu);
            while(ru > qru)
                erase(--ru);
            while(lu < qlu)
                erase(lu++);

        ans[queries[i].ind] = get_mode();
    }

    for(int i = 0; i < q; i++)
        cout << ans[i] << endl;
}

mt19937 rnd(1);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);

    solve();
}

def check(x):
    s = str(x)
    cnt = 0
    for c in s:
        if c != '0':
            cnt += 1
    return cnt == 1

a = []
for i in range(1, 1000000):
    if check(i):
        a.append(i)
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    for x in a:
        if x <= n:
            ans += 1
    print(ans)

for _ in range(int(input())):
	n = int(input())
	s = input()
	cur = {}
	for i in range(n - 1):
		t = s[i:i+2]
		if t in cur:
			if cur[t] < i - 1:
				print("YES")
				break
		else:
			cur[t] = i
	else:
		print("NO")

for _ in range(int(input())):
	n = int(input())
	s = [input() for i in range(2)]
	pos = -1
	for i in range(n):
		if s[0][i] != s[1][i]:
			pos = i
	if pos == -1:
		print("YES")
		continue
	ok = True
	cur = 0 if s[0][pos] == 'B' else 1
	for i in range(pos + 1, n):
		if s[cur][i] == 'W':
			ok = False
		if s[cur ^ 1][i] == 'B':
			cur ^= 1
	cur = 0 if s[0][pos] == 'B' else 1
	for i in range(pos - 1, -1, -1):
		if s[cur][i] == 'W':
			ok = False
		if s[cur ^ 1][i] == 'B':
			cur ^= 1
	print("YES" if ok 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())

typedef long long li;

const int INF = int(1e9);
const int N = int(1e7) + 5;

int mind[N];

void precalc() {
	fore (i, 0, N)
		mind[i] = i;
	
	for (int p = 2; p < N; p++) {
		if (mind[p] != p)
			continue;
		for (int d = 2 * p; d < N; d += p)
			mind[d] = min(mind[d], p);
	}
}

int x, y;

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

vector<int> getPrimes(int v) {
	vector<int> ps;
	while (v > 1) {
		if (ps.empty() || ps.back() != mind[v])
			ps.push_back(mind[v]);
		v /= mind[v];
	}
	return ps;
}

inline void solve() {
	int d = y - x;
	if (d == 1) {
		cout << -1 << '\n';
		return;
	}
	
	int r = INF;
	for (int p : getPrimes(d))
		r = min(r, ((x + p - 1) / p) * p);
	cout << r - x << '\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);
	
	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>

using namespace std;

const int N = 300043;

int n;
int v[N];
map<vector<int>, long long> dp[N];

pair<int, vector<int>> go(vector<int> a, int x)
{
    if(x == 0)
        return {1, a};
    else
    {
        bool f = false;
        for(int i = 0; i < a.size() && !f; i++)
            if((a[i] & x) > 0)
            {
                f = true;
                a[i] = x;
            }
        int c = 0;
        if(!f)
        {
            c = 1;
            a.push_back(x);
        }
        return {c, a};
    }
}

long long calc(int i, vector<int> a)
{
    if(i == n) return 0ll;
    if(dp[i].count(a)) return dp[i][a];
    auto p = go(a, v[i]);
    return (dp[i][a] = p.first * 1ll * (n - i) + calc(i + 1, p.second));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &v[i]);
    long long ans = 0;
    for(int i = 0; i < n; i++)
        ans += calc(i, vector<int>(0));
    printf("%lld\n", ans);    
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 243;

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

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

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

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

int n, m, s, t, v;

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

void no_answer()
{
    cout << "Impossible" << endl;
    exit(0);
}

int main()
{                              
    cin >> n >> m;
    vector<int> excess_flow(n, 0);
    vector<int> orc(m);
    for(int i = 0; i < m; i++)
    {
        int x, y, c, w;
        cin >> x >> y >> c >> w;
        orc[i] = c;
        --x;
        --y;
        add_edge(x, y, c / 2, w);
        if(c % 2 == 1)
        {
            excess_flow[x]--;
            excess_flow[y]++;
        }
    }
    s = n;
    t = n + 1;
    v = n + 2;
    int total_excess = 0;
    if(excess_flow[0] % 2 == -1)
    {
        excess_flow[0]--;
        excess_flow[n - 1]++;
    }
    for(int i = 0; i < n; i++)
    {
        if(excess_flow[i] % 2 != 0)
            no_answer();
        int val = abs(excess_flow[i]) / 2;
        if(excess_flow[i] > 0)
        {
            total_excess += val;
            add_edge(s, i, val, -int(1e9));
        }
        if(excess_flow[i] < 0)
        {
            add_edge(i, t, val, -int(1e9));
        }
    }
    add_edge(s, 0, 100000, 0);
    add_edge(n - 1, t, 100000, 0);
    auto ans = MCMF();
    bool good_answer = true;
    for(int x = 0; x < e.size(); x++)
        if(e[x].w == -int(1e9) && rem(x) != 0)
            good_answer = false;
    if(!good_answer)
        no_answer();
    cout << "Possible" << endl;
    for(int i = 0; i < 2 * m; i += 2)
    {
        if(i) cout << " ";
        cout << e[i].f * 2 + orc[i / 2] % 2;
    }
    cout << endl;
}