for t in range(int(input())):
	n = input()
	l = filter(lambda x : x <= 2048,  map(int, input().split()) )
	print('YES' if sum(l) >= 2048 else 'NO')

n = int(input())
for i in range(n):
	print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))

t = int(input())
for i in range(t):
	c, m, x = map(int, input().split())
	d = max(c, m) - min(c, m)
	x += d
	if(c > m):
		c -= d
	else:
		m -= d
	ans = min(c, m, x)
	c -= ans
	m -= ans
	x -= ans
	ans += (c + m) // 3
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int main(){
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i){
		int c, m, x;
		cin >> c >> m >> x;
		int l = 0, r = min(c, m);
		int ans = 0;
		while (l <= r){
			int mid = (l + r) / 2;
			if (c + m + x - 2 * mid >= mid){
				l = mid + 1;
				ans = mid;
			}
			else{
				r = mid - 1;
			}
		}
		cout << ans << "\n";
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const long long INF64 = (long long)(1e18) + 100;

int t;
int n;
int a[N];
int b[N];
long long dp[3][N];

long long calc(int add, int pos){
	long long &res = dp[add][pos];
	if(res != -1) return res;

	res = INF64;
	if(pos == n) return res = 0;
	for(long long x = 0; x <= 2; ++x)
		if(pos == 0 || a[pos] + x != a[pos - 1] + add)
			res = min(res, calc(x, pos + 1) + x * b[pos]);
		
	return res;
}

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

		for(int i = 0; i <= n; ++i) 
			dp[0][i] = dp[1][i] = dp[2][i] = -1;				
		printf("%lld\n", calc(0, 0));
	}
	return 0;
} 

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 99;

int t;
int a, b;
string s;

int main() {
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b >> s;
		vector <int> v;
		int l = 0;
		while(l < s.size()){
			if(s[l] == 'X'){
				++l;
				continue;
			}

			int r = l + 1;
			while(r < s.size() && s[r] == '.') ++r;
			v.push_back(r - l);
			l = r;
		}
		
		bool ok = true;
		int id = -1;
		int cnt = 0;
		for(int i = 0; i < v.size(); ++i){
			if(b <= v[i] && v[i] < a) ok = false;
			if(b + b <= v[i]){
				if(id == -1) id = i;
				else ok = false;
			}
			if(a <= v[i] && v[i] < b + b) ++cnt; 
		}

		if(!ok){
			cout << "NO" << endl;			
			continue;
		}

		if(id == -1){
			if(cnt & 1) cout << "YES" << endl;
			else cout << "NO" << endl;
			continue;
		}

		ok = false;
		int sz = v[id];
		assert(sz >= a);
		for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
			int rem2 = sz - a - rem1;
			int ncnt = cnt;
			if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
			if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;

			if(rem1 >= a) ++ncnt;
			if(rem2 >= a) ++ncnt;
			if(ncnt % 2 == 0) ok = true;
		}
		
		if(ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

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

const int N = 1000 * 1000 + 13;

int n;
pair<pt, int> a[N];
vector<int> vals;
vector<pt> ev[N];
pair<li, int> t[4 * N];
li add[4 * N];

void build(int v, int l, int r) {
	if (l == r) {
		t[v] = mp(-vals[l], l);
		add[v] = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(v * 2 + 1, l, m);
	build(v * 2 + 2, m + 1, r);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

void push(int v, int l, int r) {
	if (add[v] == 0) return;
	t[v].x += add[v];
	if (l != r) {
		add[v * 2 + 1] += add[v];
		add[v * 2 + 2] += add[v];
	}
	add[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) {
		add[v] += val;
		push(v, l, r);
		return;
	}
	int m = (l + r) >> 1;
	upd(v * 2 + 1, l, m, L, min(m, R), val);
	upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}

pair<li, int> get(int v, int l, int r, int L, int R) {
	push(v, l, r);
	if (L > R) return mp(-li(1e18), 0);
	if (l == L && r == R) return t[v];
	int m = (l + r) >> 1;
	auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
	auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
	return max(r1, r2);
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
	
	forn(i, n) {
		vals.pb(a[i].x.x);
		vals.pb(a[i].x.y);
	}
	
	vals.pb(0);
	sort(all(vals));
	vals.pb(vals.back() + 1);
	
	vals.resize(unique(all(vals)) - vals.begin());
	
	forn(i, n) {
		int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
		int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
		ev[min(x, y)].pb(mp(max(x, y), a[i].y));
	}
	
	n = sz(vals);
	
	build(0, 0, n - 1);
	
	li ans = -1;
	int ansl = -1, ansr = -1;
	
	for (int i = sz(vals) - 1; i >= 0; i--) {
		for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
		auto cur = get(0, 0, n - 1, i, n - 1);
		if (cur.x + vals[i] > ans) {
			ans = cur.x + vals[i];
			ansl = vals[i]; ansr = vals[cur.y]; 
		}
	}
	
	printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
	
}

#include <bits/stdc++.h>

using namespace std;

const int N = 40;
const int M = 20;

long long incident_mask[N];
vector<int> g[N];
int n, m;
long long ans = 0;
long long cntmask[1 << M];

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

int used[N];

void dfs(int x, int c)
{
	if(used[x])
		return;
	used[x] = c;
	for(auto y : g[x])
		dfs(y, 3 - c);
}

long long countIsolated()
{
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(g[i].empty())
			ans++;
	return ans;
}

long long countComponents()
{
	memset(used, 0, sizeof used);
	long long ans = 0;
	for(int i = 0; i < n; i++)
		if(!used[i])
		{
			ans++;
			dfs(i, 1);
		}
	return ans;
}

bool bipartite()
{
	memset(used, 0, sizeof used);
	for(int i = 0; i < n; i++)
		if(!used[i])
			dfs(i, 1);
	for(int i = 0; i < n; i++)
		for(auto j : g[i])
			if(used[i] == used[j])
				return false;
	return true;
}

long long countIndependentSets()
{
	int m1 = min(n, 20);
	int m2 = n - m1;
	//cerr << m1 << " " << m2 << endl;
	memset(cntmask, 0, sizeof cntmask);
	for(int i = 0; i < (1 << m1); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = 0; j < m1; j++)
		{
			if((i & (1 << j)) == 0)
				continue;
			if(curmask & (1 << j))
				good = false;
			curmask |= ((1 << j) | incident_mask[j]);
		}
		if(good)
		{
			cntmask[curmask >> m1]++;
		}
	}	
	for(int i = 0; i < m2; i++)
		for(int j = 0; j < (1 << m2); j++)
			if(j & (1 << i))
				cntmask[j] += cntmask[j ^ (1 << i)];
	long long ans = 0;
	for(int i = 0; i < (1 << m2); i++)
	{
		long long curmask = 0;
		bool good = true;
		for(int j = m1; j < n; j++)
		{
			if((i & (1 << (j - m1))) == 0)
				continue;
			if(curmask & (1ll << j))
				good = false;
			curmask |= (1ll << j) | incident_mask[j];
		}
		if(good)
		{
			//cerr << i << endl;
			ans += cntmask[(i ^ ((1 << m2) - 1))];
		}
	}
	return ans;
}

long long calc(int mask)
{
	if(mask == 0)
		return binpow(2, n);
	if(mask == 1 || mask == 4)
		return countIndependentSets();
	if(mask == 2)
		return binpow(2, countComponents());
	if(mask == 3 || mask == 6)
		return binpow(2, countIsolated());
	if(mask == 5)
		return (bipartite() ? binpow(2, countComponents()) : 0);
	if(mask == 7)
		return (m == 0 ? binpow(2, n) : 0);
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
		incident_mask[x] ^= (1ll << y);
		incident_mask[y] ^= (1ll << x);
	}
	for(int i = 0; i < 8; i++)
	{
		//cerr << i << " " << calc(i) << endl;
		if(__builtin_popcount(i) % 2 == 0)
			ans += calc(i);
		else
			ans -= calc(i);
	}
	cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
#include "testlib.h"

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

using namespace std;

int n;
string w[143];

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

bool good(int x, int y)
{
	return (x >= 0 && x < n && y >= 0 && y < n);
}

int readAndCheckAnswer(InStream& in) {
	for(int i = 0; i < n; i++)
		w[i] = in.readLine(format("[BW]{%d}", n).c_str(), "s");
	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
			if(w[i][j] == 'B') continue;
			for(int k = 0; k < 8; k++)
			{
				int x = dx[k] + i;
				int y = dy[k] + j;
				if(good(x, y) && w[x][y] == 'B')
					ans++;
			}
		}
	return ans;
}

int main(int argc, char* argv[]) {
	registerTestlibCmd(argc, argv);
	
	n = inf.readInt();
	
	bool ja = readAndCheckAnswer(ans);
	bool pa = readAndCheckAnswer(ouf);

	if(ja > pa)
		quitf(_wa, "jury has better answer");
	if(pa > ja)
		quitf(_fail, "participant has better answer");
	
	quitf(_ok, "ok");
}

fun main() {
    val t = readLine()!!.toInt()
    for (ct in 1..t) {
        val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() }
        val minAddStr = maxOf(0, (exp + int - str + 2) / 2)
        println(maxOf(exp - minAddStr + 1, 0))
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int t;
int n, m;
int d[N], h[N];

int main() {
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> n >> m;
		int maxDH = -2e9;
		for(int i = 0; i < n; ++i){
			cin >> d[i] >> h[i];
			maxDH = max(maxDH, d[i] - h[i]);
		}

		int res = 1;	
		int maxD = *max_element(d, d + n);
		m -= maxD;
		if(m > 0){
			if(maxDH <= 0) res = -1;
			else res += (m + maxDH - 1) / maxDH; 	
		}	
		cout << res << endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int t;
string s;
int nxt[N];

int main() {
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> s;
		for(int i = 0; i < s.size(); ++i)
			if(s[i] == '1') nxt[i] = i;
			else nxt[i] = (i == 0? -1 : nxt[i - 1]);		
		int res = 0;
		for(int r = 0; r < s.size(); ++r){
			int sum = 0;
			for(int l = r; l >= 0 && r - l < 20; --l){
				if(s[l] == '0') continue;
				sum += 1 << (r - l);
				if(sum <= r - (l == 0? -1 : nxt[l - 1]))
					++res;
			}
		}
		cout << res << endl;
	}	

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = int(1e6) + 55;

int n, m;
vector <pair<int, int> > g[N];
int col[N];
bool cyc;
int res[N];

void dfs(int v){
	col[v] = 1;
	for(auto p : g[v]){
		int to = p.first, id = p.second;
		if(col[to] == 0){
			dfs(to);
			res[id] = 1;
		}
		else if(col[to] == 2)
			res[id] = 1;
		else{
			res[id] = 2;
			cyc = true;
		}
	}
	col[v] = 2;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(make_pair(v, i));
	}
	
	for(int i = 0; i < n; ++i)
			if(col[i] == 0)
				dfs(i);
			
	cout << (cyc? 2 : 1) << endl;
	for(int i = 0; i < m; ++i) cout << res[i] << ' ';
	cout << endl;
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int N = 200 * 1000 + 13;
const int INF = 2e9;
const int LOGN = 9;

struct node{
	int best;
	int mn[LOGN];
	node(){
		best = INF;
		forn(i, LOGN)
			mn[i] = INF;
	}
	int& operator [](int x){
		return mn[x];
	}
};

int a[N];
node t[4 * N];

void upd(node &t, int val){
	int x = val;
	forn(i, LOGN){
		if (x % 10 != 0)
			t[i] = min(t[i], val);
		x /= 10;
	}
}

node merge(node &a, node &b){
	node c;
	c.best = min(a.best, b.best);
	forn(i, LOGN){
		c[i] = min(a[i], b[i]);
		if (a[i] < INF && b[i] < INF)
			c.best = min(c.best, a[i] + b[i]);
	}
	return c;
}

void build(int v, int l, int r){
	if (l == r - 1){
		t[v] = node();
		upd(t[v], a[l]);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

void upd(int v, int l, int r, int pos, int val){
	if (l == r - 1){
		t[v] = node();
		upd(t[v], val);
		return;
	}
	int m = (l + r) / 2;
	if (pos < m)
		upd(v * 2, l, m, pos, val);
	else
		upd(v * 2 + 1, m, r, pos, val);
	t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

node get(int v, int l, int r, int L, int R){
	if (l == L && r == R)
		return t[v];
	int m = (l + r) / 2;
	if (R <= m)
		return get(v * 2, l, m, L, R);
	if (L >= m)
		return get(v * 2 + 1, m, r, L, R);
	node ln = get(v * 2, l, m, L, m);
	node rn = get(v * 2 + 1, m, r, m, R);
	return merge(ln, rn);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d", &a[i]);
	build(1, 0, n);
	forn(i, m){
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		--x;
		if (t == 1)
			upd(1, 0, n, x, y);
		else{
			node res = get(1, 0, n, x, y);
			printf("%d\n", res.best == INF ? -1 : res.best);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int BUF = 10 * 1000 * 1000 + 13;
const int N = 300 * 1000 + 13;
const int M = 300 * 1000 + 13;
const int P = 400;

struct query{
	int t, x, y;
	int e0, e1;
};

int n, m;
query q[M];

int p[N], rk[N];

int cnt;
int* where[BUF];
int val[BUF];

void rollback(){
	while (cnt > 0){
		*where[cnt - 1] = val[cnt - 1];
		--cnt;
	}
}

int getp(int a){
	return (a == p[a] ? 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);
	where[cnt] = &rk[a];
	val[cnt++] = rk[a];
	where[cnt] = &p[b];
	val[cnt++] = p[b];
	assert(cnt <= BUF);
	rk[a] += rk[b];
	p[b] = a;
}

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

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

struct edge{
	int v, u;
};

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

edge edges[2 * M];
map<edge, int> rev;

bool used[2 * M];
bool state[2 * M];
int ans[M];
vector<int> cur;

void rebuild(int l){
	int r = min(m, l + P);
	forn(i, n) p[i] = i, rk[i] = 1;
	memset(used, 0, sizeof(used));
	memset(state, 0, sizeof(state));

	forn(i, l) if (q[i].t == 1){
		int e = (ans[i] ? q[i].e1 : q[i].e0);
		used[e] = true;
		state[e] ^= 1;
	}
	
	for (int i = l; i < r; ++i) if (q[i].t == 1)
		used[q[i].e0] = used[q[i].e1] = false;
	
	cur.clear();
	cnt = 0;
	forn(i, l) if (q[i].t == 1){
		int e = (ans[i] ? q[i].e1 : q[i].e0);
		if (used[e] && state[e]){
			state[e] = false;
			uniteFast(edges[e].v, edges[e].u);
		}
		else if (!used[e] && state[e]){
			state[e] = false;
			cur.push_back(e);
		}
	}
}

int get_edge(edge e){
	if (!rev.count(e)){
		int k = rev.size();
		edges[k] = e;
		rev[e] = k;
	}
	return rev[e];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, m){
		scanf("%d%d%d", &q[i].t, &q[i].x, &q[i].y);
		--q[i].x, --q[i].y;
		if (q[i].t == 1){
			edge e({q[i].x, q[i].y});
			if (e.v > e.u) swap(e.v, e.u);
			q[i].e0 = get_edge(e);
			e.v = (e.v + 1) % n, e.u = (e.u + 1) % n;
			if (e.v > e.u) swap(e.v, e.u);
			q[i].e1 = get_edge(e);
		}
	}
	
	string res = "";
	ans[0] = 0;
	forn(i, m){
		if (i % P == 0)
			rebuild(i);
		
		int x = (q[i].x + ans[i]) % n;
		int y = (q[i].y + ans[i]) % n;
		if (x > y) swap(x, y);
		
		if (q[i].t == 1){
			rollback();
			int e = get_edge({x, y});
			auto it = find(cur.begin(), cur.end(), e);
			if (it == cur.end())
				cur.push_back(e);
			else
				cur.erase(it);
			ans[i + 1] = ans[i];
		}
		else{
			for (auto e : cur)
				unite(edges[e].v, edges[e].u);
			bool rc = (getp(x) == getp(y));
			ans[i + 1] = rc;
			res += ('0' + rc);
		}
	}
	
	puts(res.c_str());
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t;
int b, p, f;
int h, c;

int main() {
    cin >> t;
    for(int tc = 0; tc < t; ++tc){
        cin >> b >> p >> f;
        cin >> h >> c;

        b /= 2;
        if(h < c){
            swap(h, c);
            swap(p, f);
        }

        int res = 0;

        int cnt = min(b, p);
        b -= cnt, p -= cnt;
        res += h * cnt; 
        
        cnt = min(b, f);
        b -= cnt, f -= cnt;
        res += c * cnt; 
            
        cout << res << endl;
    }
    return 0;
}                               

n, m = map(int, input().split())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int, input().split()))

ans = []
for i in range(n - 1):
    for j in range(m - 1):
        if(a[i][j] * a[i][j + 1] * a[i + 1][j] * a[i + 1][j + 1] > 0):
            a[i][j] = 2
            a[i + 1][j] = 2
            a[i][j + 1] = 2
            a[i + 1][j + 1] = 2
            ans.append([i, j])

cnt1 = 0
for i in range(n):
    for j in range(m):
        if(a[i][j] == 1):
            cnt1 += 1

if(cnt1 != 0):
    print(-1)
else:
    print(len(ans))
    for x in ans:
        print(x[0] + 1, x[1] + 1)

const val INF64 = 1e18.toLong()

fun main(args: Array<String>) {
    val tc = readLine()!!.toInt()
    for (t in 1..tc) {
        val (n, a, b) = readLine()!!.split(' ').map { it.toInt() }
        val s = readLine()!!

        val d = Array(n + 1) { arrayOf(INF64, INF64) }
        d[0][0] = b.toLong()

        for (pos in 0 until n) {
            if (s[pos] == '0') {
                d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][0] + a + b)
                d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][0] + 2 * (a + b))

                d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
                d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][1] + 2 * a + b)
            } else {
                d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
            }
        }
        println(d[n][0])
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const int MOD = 998244353;

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


int sum(int a, int b){
    return (a + b) % MOD;
}

int n;
pair<int, int> a[N];
int f[N];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].first, &a[i].second);

    f[0] = 1;
    for(int i = 1; i < N; ++i)
        f[i] = mul(i, f[i - 1]);

    int res = f[n];
    for(int c = 0; c < 2; ++c){
        int d = 1;
        sort(a, a + n);
        int l = 0;
        while(l < n){
            int r = l + 1;
            while(r < n && a[l].first == a[r].first) ++r;
            d = mul(d, f[r - l]);
            l = r;
        }
        res = sum(res, MOD - d);
        for(int i = 0; i < n; ++i) 
            swap(a[i].first, a[i].second);
    }       

    sort(a, a + n);
    int l = 0;
    int d = 1;
    while(l < n){
        int r = l + 1;
        while(r < n && a[l].first == a[r].first) ++r;
        map<int, int> m;
        for(int i = l; i < r; ++i) ++m[a[i].second];
        for(auto p : m) d = mul(d, f[p.second]);
        l = r;
    }
    for(int i = 1; i < n; ++i) 
        if(a[i - 1].second > a[i].second) d = 0;

    res = sum(res, d);
    printf("%d\n", res);
    return 0;
}                               

#include<bits/stdc++.h>

using namespace std;

int main()
{
    cout << "?";
    for(int i = 1; i <= 100; i++)
        cout << " " << i;
    cout << endl;
    cout.flush();
    int res1;
    cin >> res1;
    cout << "?";
    for(int i = 1; i <= 100; i++)
        cout << " " << (i << 7);
    cout << endl;
    cout.flush();
    int res2;
    cin >> res2;
    int x = 0;
    x |= (res1 & (((1 << 7) - 1) << 7));
    x |= (res2 & ((1 << 7) - 1));
    cout << "! " << x << endl;
    cout.flush();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 500043;
const int K = 750;

int a[N];
int sum[K][K];

int main()
{
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);
        if(t == 1)
        {
            a[x] += y;
            for(int i = 1; i < K; i++)
                sum[i][x % i] += y;
        }
        else
        {
            if(x >= K)
            {
                int ans = 0;
                for(int i = y; i <= 500000; i += x)
                    ans += a[i];
                printf("%d\n", ans);
            }
            else
                printf("%d\n", sum[x][y]);
        }
    }
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;
const int N = 400 * 1000 + 13;

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

struct node_at{
    int nxt[AL];
    int p;
    char pch;
    int link;
    int go[AL];
    node_at(){
        memset(nxt, -1, sizeof(nxt));
        memset(go, -1, sizeof(go));
        link = p = -1;
    }
    int& operator [](int x){
        return nxt[x];
    }
};

int cntnm;
node trienm[N];

int cntqr;
node_at trieqr[N];

int add_string(string s){
    int v = 0;
    for (auto it : s){
        int c = it - 'a';
        if (trieqr[v][c] == -1){
            trieqr[cntqr] = node_at();
            trieqr[cntqr].p = v;
            trieqr[cntqr].pch = c;
            trieqr[v][c] = cntqr;
            ++cntqr;
        }
        v = trieqr[v][c];
    }
    return v;
}

int go(int v, int c);
 
int get_link(int v){
    if (trieqr[v].link == -1){
        if (v == 0 || trieqr[v].p == 0)
            trieqr[v].link = 0;
        else
            trieqr[v].link = go(get_link(trieqr[v].p), trieqr[v].pch);
    }
    return trieqr[v].link;
}
 
int go(int v, int c) {
    if (trieqr[v].go[c] == -1){
        if (trieqr[v][c] != -1)
            trieqr[v].go[c] = trieqr[v][c];
        else
            trieqr[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
    }
    return trieqr[v].go[c];
}

int add_letter(int v, int c){
    if (trienm[v][c] == -1){
        trienm[cntnm] = node();
        trienm[v][c] = cntnm;
        ++cntnm;
    }
    return trienm[v][c];
}

vector<int> g[N];
int tin[N], tout[N], T;

void dfs_init(int v){
    tin[v] = T++;
    for (auto u : g[v])
        dfs_init(u);
    tout[v] = T;
}

int f[N];

void upd(int v, int val){
    for (int i = tin[v]; i < N; i |= i + 1)
        f[i] += val;
}

int get(int x){
    int sum = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        sum += f[i];
    return sum;
}

int sum(int v){
    return get(tout[v] - 1) - get(tin[v] - 1);
}

int n, m;
int nm[N], qr[N];
vector<int> nms[N];
vector<int> reqs[N];
int ans[N];

void dfs(int v, int cur){
    upd(cur, 1);
    for (auto it : nms[v])
        for (auto q : reqs[it])
            ans[q] = sum(qr[q]);
    forn(i, AL) if (trienm[v][i] != -1)
        dfs(trienm[v][i], go(cur, i));
    upd(cur, -1);
}

int main(){
    cntqr = 0;
    trieqr[cntqr++] = node_at();
    
    cntnm = 0;
    trienm[cntnm++] = node();
    
    char buf[N];
    scanf("%d", &n);
    forn(i, n){
        int t;
        scanf("%d", &t);
        if (t == 1){
            scanf("%s", buf);
            nm[i] = add_letter(0, buf[0] - 'a');
        }
        else{
            int j;
            scanf("%d%s", &j, buf);
            --j;
            nm[i] = add_letter(nm[j], buf[0] - 'a');
        }
        nms[nm[i]].push_back(i);
    }
    
    scanf("%d", &m);
    forn(i, m){
        int j;
        scanf("%d%s", &j, buf);
        --j;
        reqs[j].push_back(i);
        qr[i] = add_string(buf);
    }
    
    for (int v = 1; v < cntqr; ++v)
        g[get_link(v)].push_back(v);
    
    T = 0;
    dfs_init(0);
    dfs(0, 0);
    
    forn(i, m)
        printf("%d\n", ans[i]);
}

fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val x = readLine()!!.reversed()
        val y = readLine()!!.reversed()

        val posY = y.indexOf('1')
        val posX = x.indexOf('1', posY)
        println(posX - posY)
    }
}

const val INF = 1e9.toInt()

fun main(args: Array<String>) {
    val s = readLine()!!.map { it - '0' }
    val cf = Array(10) {Array(10) {0}}
    for (i in 1 until s.size)
        cf[s[i - 1]][s[i]]++

    for (x in 0..9) {
        for (y in 0..9) {
            val ds = Array(10) {Array(10) {INF + 7}}

            for (v in 0..9) {
                for (cx in 0..9) {
                    for (cy in 0..9) {
                        if (cx + cy == 0)
                            continue

                        val to = (v + cx * x + cy * y) % 10
                        ds[v][to] = minOf(ds[v][to], cx + cy)
                    }
                }
            }

            var res = 0
            for (v in 0..9) {
                for (to in 0..9) {
                    if (ds[v][to] > INF && cf[v][to] > 0) {
                        res = -1
                        break
                    }
                    res += (ds[v][to] - 1) * cf[v][to]
                }
                if (res == -1)
                    break
            }

            print("$res ")
        }
        println()
    }
}

const val INF = 1e9.toInt()

fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val s = readLine()!!
        val alp = arrayOf("WS", "AD")
        val aDir = arrayOf(
                s.filter { alp[0].indexOf(it) != -1 },
                s.filter { alp[1].indexOf(it) != -1 }
        )

        val baseW = arrayOf(INF, INF)
        val bestW = arrayOf(INF, INF)

        for (k in 0..1) {
            val pSum = arrayListOf(0)
            for (c in aDir[k]) {
                val add = if (c == alp[k][0]) +1 else -1
                pSum.add(pSum.last() + add)
            }

            for (tp in 0..1) {
                val firstMin = pSum.withIndex().minBy { it.value }!!.index
                val lastMax = pSum.withIndex().reversed().maxBy { it.value }!!.index

                val curBase = pSum[lastMax] - pSum[firstMin] + 1
                var curBest = curBase
                if (curBase > 2 && lastMax < firstMin)
                    --curBest

                baseW[k] = minOf(baseW[k], curBase)
                bestW[k] = minOf(bestW[k], curBest)

                for (i in pSum.indices)
                    pSum[i] = -pSum[i]
            }
        }

        println("${minOf(baseW[0] * 1L * bestW[1], baseW[1] * 1L * bestW[0] )}")
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    for(int tc = 0; tc < t; ++tc){
    	int n;
    	cin >> n;
    	int len = 2;
    	while(len * (len + 1) / 2 <= n)
    		++len;
    
    	n -= len * (len - 1) / 2;
    	assert(n >= 0);
    	assert(n <= 45000);
    	
    	string s = "133";
    	while(n > 0){
    		--n;
    		s += "7";
    	}
    
    	len -= 2;
    	while(len > 0){
    		--len;
    		s += "3";
    	}
    	s += "7";
    	cout << s << endl;
    }
	return 0;
} 

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

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

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

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

const int N = 500005;
const int A = 27;
const int MAG = 500;

struct node {
    node *to[A];
    int cnt;
} nodes[N];
int szn = 0;

typedef node* vt;

vt getNode() {
    assert(szn < N);
    fore(i, 0, A)
        nodes[szn].to[i] = NULL;
    nodes[szn].cnt = 0;
    return &nodes[szn++];
}

void addWord(vt v, const string &s) {
    fore(i, 0, sz(s)) {
        int c = s[i] - 'a';
        if (!v->to[c])
            v->to[c] = getNode();
        v = v->to[c];
    }
    v->cnt++;
}

int calcCnt(vt v, const string &s, int pos) {
    assert(v->cnt == 0);
    int ans = 0;
    while(pos < sz(s)) {
        int c = s[pos] - 'a';
        if (!v->to[c])
            break;
        v = v->to[c];
        ans += v->cnt;
        pos++;
    }
    return ans;
}

vector<int> zf(string s) {
    vector<int> z(sz(s), 0);
    for (int i = 1, l = 0, r = 0; i < sz(s); ++i) {
        if(i < r)
            z[i] = min(r - i, z[i - l]);
        while (i + z[i] < sz(s) && s[i + z[i]] == s[z[i]])
            z[i]++;

        if(i + z[i] > r)
            l = i, r = i + z[i];
    }
    return z;
}

string t;
int n;
vector<string> s;

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

inline void solve() {
    vector<int> cnt[2];
    fore(k, 0, 2) {
        cnt[k].assign(sz(t) + 1, 0);
        szn = 0;
        vt root = getNode();

        forn(i, n) {
            if (sz(s[i]) > MAG) {
                auto z = zf(s[i] + t);
                fore(j, 0, sz(t))
                    cnt[k][j] += (z[sz(s[i]) + j] >= sz(s[i]));
            } else {
                addWord(root, s[i]);
            }
        }

        fore(i, 0, sz(t))
            cnt[k][i] += calcCnt(root, t, i);

        reverse(all(t));
        fore(i, 0, n)
            reverse(all(s[i]));
    }

    li ans = 0;
    fore(i, 0, sz(t) + 1)
        ans += cnt[0][i] * 1ll * cnt[1][sz(t) - i];
    cout << ans << endl;
}

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

    if(read()) {
        solve();

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

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	
	int n = a + b;
	int ans = 0;
	int l = 1;
	while (l <= n){
		int g = n / l;
		
		if (a < g || b < g){
			l = n / g + 1;
			continue;
		}
		
		int r = n / g;
		
		int a_low = (a + g) / (g + 1);
		int a_high = a / g;
		int b_low = (b + g) / (g + 1);
		int b_high = b / g;
		
		if (a_low <= a_high && b_low <= b_high)
			ans += max(0, min(r, a_high + b_high) - max(l, a_low + b_low) + 1);
		l = r + 1;
	}
	
	printf("%d\n", ans);
}

fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()
        println(minOf(a[1] - 1, n - 2))
    }
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	
	int pos = max_element(a.begin(), a.end()) - a.begin();
	bool res = true;
	for(int i = 0; i < pos; i++)
		res &= (a[i] < a[i + 1]);
	for(int i = pos; i < n - 1; i++)
		res &= (a[i] > a[i + 1]);

	if(res)
		puts("YES");
	else
		puts("NO");
}

#include<bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int n, k;
int a[N];

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	
	vector <int> v;
	for(int i = 1; i < n; ++i) v.push_back(a[i - 1] - a[i]);
	
	sort(v.begin(), v.end());
	
	int res = a[n - 1] - a[0];
	for(int i = 0; i < k - 1; ++i) res += v[i];
	
	cout << res << endl;
 	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int n, m, k;
int a[N];
long long bst[N];
long long psum[N];

long long sum(int l, int r){
    l = max(l, 0);
	return psum[r] - (l == 0? 0 : psum[l - 1]);
}

int main() {
	cin >> n >> m >> k;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		psum[i] = a[i] + (i == 0? 0 : psum[i - 1]);
	}

	long long res = 0;
	for(int len = 1; len <= m && len <= n; ++len)
			res = max(res, sum(0, len - 1) - k);
	for(int i = 0; i < n; ++i){
		if(i + 1 >= m){
			long long nbst = sum(i - m + 1, i) - k;
			if(i - m >= 0) nbst += bst[i - m];
			bst[i] = max(bst[i], + nbst);
		}

		for(int len = 0; len < m && i + len < n; ++len)
			res = max(res, bst[i] + sum(i + 1, i + len) - k * (len > 0));
	}	

	cout << res << endl;
	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;

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

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

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

pt combine(const pt &a, const pt &b) {
	if(a.x < b.x)
		return a;
	if(a.x > b.x)
		return b;
	return {a.x, norm(a.y + b.y)};
}

int n;
vector<pt> p;

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

vector<pt> T;

void setVal(int pos, const pt &val) {
	T[pos += n] = val;
	for(pos >>= 1; pos > 0; pos >>= 1)
		T[pos] = combine(T[2 * pos], T[2 * pos + 1]);
}

pt getMin(int l, int r) {
	pt ans = {INF, 0};
	for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if(l & 1)
			ans = combine(T[l++], ans);
		if(r & 1)
			ans = combine(T[--r], ans);
	}
	return ans;
}

inline void solve() {
	auto comp = [](const pt &a, const pt &b) {
		if(a.y != b.y)
			return a.y < b.y;
		return a.x < b.x;
	};
	
	sort(p.begin(), p.end(), comp);
	
	T.assign(2 * n, {INF, 0});
	for (int i = n - 1; i >= 0; i--) {
		int pos = int(lower_bound(p.begin(), p.end(), pt(0, p[i].x), comp) - p.begin());
		
		if(pos >= n) {
			setVal(i, {p[i].y, 1});
			continue;
		}
		pt bst = getMin(pos, n);
		setVal(i, {bst.x - (p[i].x - p[i].y), bst.y});
	}
	
	cout << getMin(0, n).y << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

typedef vector<int> vec;
typedef vector<vec> mat;

vec mul(const mat& a, const vec& b)
{
	int n = a.size();
	int m = b.size();
	vector<int> c(m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			c[i] = add(c[i], mul(b[j], a[i][j]));
	return c;
}

mat add(const mat& a, const mat& b)
{
	int n = a.size();
	int m = a[0].size();
	mat c(n, vec(m, 0));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			c[i][j] = add(a[i][j], b[i][j]);
	return c;
}

mat mul(const mat& a, const mat& b)
{
	int x = a.size();
	int y = b.size();
	int z = b[0].size();
	mat c(x, vec(z, 0));
	for(int i = 0; i < x; i++)
		for(int j = 0; j < y; j++)
			for(int k = 0; k < z; k++)
				c[i][k] = add(c[i][k], mul(a[i][j], b[j][k]));
	return c;
}

mat binpow(mat a, int d)
{
	int n = a.size();
	mat c = mat(n, vec(n, 0));
	for(int i = 0; i < n; i++) c[i][i] = 1;
	while(d > 0)
	{
		if(d % 2 == 1) c = mul(c, a);
		a = mul(a, a);
		d /= 2;
	}
	return c;
}

int f[3][3];

int extend(int color, vector<int> last_numbers)
{
	vector<int> used(4, 0);
	for(int i = 0; i < 3; i++)
		if(f[color][i])
			used[last_numbers[i]] = 1;
	for(int i = 0; i <= 3; i++)
		if(used[i] == 0)
			return i;
	return 3;
}

vector<int> extend_state(int color, vector<int> last_numbers)
{
	int z = extend(color, last_numbers);
	last_numbers.insert(last_numbers.begin(), z);
	last_numbers.pop_back();
	return last_numbers;
}

vector<int> int2state(int x)
{
	vector<int> res;
	for(int i = 0; i < 3; i++)
	{
		res.push_back(x % 4);
		x /= 4;
	}
	return res;
}

int state2int(const vector<int>& x)
{
	int res = 0;
	int deg = 1;
	for(auto y : x)
	{
		res += deg * y;
		deg *= 4;
	}
	return res;
}

mat form_matrix(int color)
{
	mat res(64, vec(64, 0));
	for(int i = 0; i < 64; i++)
	{
		int j = state2int(extend_state(color, int2state(i)));
		res[j][i] = add(res[j][i], 1);
	}
	return res;
}

mat color_matrices[3];
mat full_matrix;

vector<pair<int, int> > colored[1043];
int len[1043];
int dp[1043][4];

mat full_pows[31];

void precalc_pows()
{
	full_pows[0] = full_matrix;
	for(int i = 0; i <= 30; i++)
		full_pows[i + 1] = mul(full_pows[i], full_pows[i]);
}

vec powmul(int d, vec b)
{
	for(int i = 0; i <= 30; i++)
	{
		if(d % 2 == 1) 
			b = mul(full_pows[i], b);
		d /= 2;
	}
	return b;
}

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> len[i];
	int m;
	cin >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		--x;
		--y;
		--c;
		colored[x].push_back(make_pair(y, c));
	}
	for(int i = 0; i < n; i++)
		sort(colored[i].begin(), colored[i].end());
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin >> f[i][j];
	
	for(int i = 0; i < 3; i++)
		color_matrices[i] = form_matrix(i);
	full_matrix = color_matrices[0];
	for(int i = 1; i < 3; i++)
		full_matrix = add(full_matrix, color_matrices[i]);
	precalc_pows();
		
	dp[0][0] = 1;
	for(int i = 0; i < n; i++)
	{
		vec cur(64);
		cur[state2int({3, 3, 3})] = 1;
		int last = 0;
		for(auto x : colored[i])
		{
			cur = powmul(x.first - last, cur);
			cur = mul(color_matrices[x.second], cur);
			last = x.first + 1;
		}
		cur = powmul(len[i] - last, cur);
		for(int j = 0; j < 4; j++)
			for(int k = 0; k < 64; k++)
			{
				vector<int> s = int2state(k);
				dp[i + 1][j ^ s[0]] = add(dp[i + 1][j ^ s[0]], mul(dp[i][j], cur[k]));
			}
	}
	cout << dp[n][0] << endl;
}

fun main(args: Array<String>) {
    val T = readLine()!!.toInt()
    for (t in 1..T) {
        val (n, x) = readLine()!!.split(' ').map { it.toLong() }
        println(x * 2)
    }
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int q;
	cin >> q;
	forn(_, q){
		int n, m;
		cin >> n >> m;
		vector<string> s(n);
		forn(i, n)
			cin >> s[i];
		vector<int> cntn(n), cntm(m);
		forn(i, n) forn(j, m){
			cntn[i] += (s[i][j] == '.');
			cntm[j] += (s[i][j] == '.');
		}
		int ans = n + m;
		forn(i, n) forn(j, m){
			ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
		}
		cout << ans << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int q;
string s, t, p;
int cnt[30];

int main() {
	cin >> q;
	for(int iq = 0; iq < q; ++iq){
		cin >> s >> t >> p;
		memset(cnt, 0, sizeof cnt);
		for(auto x : p)
			++cnt[x - 'a'];

		bool ok = true;
		int is = 0, it = 0;
		while(is < s.size()){
			if(it == t.size()){
				ok = false;
				break;
			}
			
			if(s[is] == t[it]){
				++is, ++it;
				continue;
			}
			
			--cnt[t[it] - 'a'];
			++it;
		}
        while(it < t.size()){
            --cnt[t[it] - 'a'];
			++it;
        }
        
		if(*min_element(cnt, cnt + 30) < 0)
			ok = false;

		if(ok) cout << "YES\n";
		else cout << "NO\n";
	}		
	return 0;
}                             	



}                             	

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

int n, k;

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

void solve() {
	bool win = true;
	if(k % 3 == 0) {
		int np = n % (k + 1);
		if(np % 3 == 0 && np != k)
			win = false;
	} else {
		int np = n % 3;
		if(np == 0)
			win = false;
	}
	
	puts(win ? "Alice" : "Bob");
}

int main(){
	int T; cin >> T;
	while(T--) {
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair

const int N = 10009;
const int INF = 1000000009;
 
int n;
vector <pair<int, int> > vs[N], hs[N];
int f[N];
vector <int> d[N];

void upd(int pos, int x){
	for(; pos < N; pos |= pos + 1)
		f[pos] += x;
}

int get(int pos){
	int res = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += f[pos];
	return res;
}

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

const int D = 5000;

int main() {
	cin >> n;
	for(int i = 0; i < n; ++i){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1 += D, y1 += D, x2 += D, y2 += D; 
		if(y1 == y2) 
			hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) );	
		else 
			vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) );	
	}

	long long res = 0;
	for(int y = 0; y < N; ++y) for(auto s : hs[y]){
		for(int i = 0; i < N; ++i) d[i].clear();
		memset(f, 0, sizeof f);

		int l = s.first, r = s.second;
		for(int x = l; x <= r; ++x) for(auto s2 : vs[x])
			if(s2.first <= y && s2.second > y) {
				d[s2.second].push_back(x);
				upd(x, 1);
			}

		for(int y2 = y + 1; y2 < N; ++y2){
			for(auto s2 : hs[y2]){			
				int cur = get(s2.first, s2.second);
				res += cur * (cur - 1) / 2;
			}
			for(auto x : d[y2]) upd(x, -1);
		}
	}

	cout << res << endl;
	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 MOD = int(1e9) + 7;

inline int norm(int a) {
    if(a >= MOD) a -= MOD;
    if(a < 0) a += MOD;
    return a;
}
inline int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}
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);
}

int n;
li T;
vector<li> t;

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

vector<int> f, inf;

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

inline void solve() {
    f.resize(n + 5);
    inf.resize(n + 5);
    f[0] = inf[0] = 1;
    fore(i, 1, sz(f)) {
        f[i] = mul(i, f[i - 1]);
        inf[i] = mul(inf[i - 1], inv(i));
    }

    int sumC = 1;
    li bd = T;
    int pw2 = 1, i2 = (MOD + 1) / 2;

    vector<int> p(n + 1, 0);
    fore(i, 0, n) {
        pw2 = mul(pw2, i2);

        sumC = norm(mul(2, sumC) - C(i, bd));
        li need = t[i];
        if(bd > i + 1) {
            li sub = min(bd - i - 1, need);
            bd -= sub, need -= sub;
        }
        li rem = min(bd + 1, need);
        fore(k, 0, rem)
            sumC = norm(sumC - C(i + 1, bd - k));
        bd -= rem;

        p[i] = mul(sumC, pw2);
    }

    int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD);
    cout << ans << endl;
//    cerr << mul(ans, binPow(2, n)) << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    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;

const int N = 105;

int a[N];
int n;
int numPos[10], denPos[10];
int num, den;
const int MOD = 998244353;

struct halfState
{
	int carry;
	int mask;
	bool comp;
	
	halfState() {};
	halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {};
};

bool operator <(const halfState& x, const halfState& y)
{
	if(x.carry != y.carry) return x.carry < y.carry;
	if(x.mask != y.mask) return x.mask < y.mask;
	return x.comp < y.comp;
}

bool operator ==(const halfState& x, const halfState& y)
{
	return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp;
}

bool operator !=(const halfState& x, const halfState& y)
{
	return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp;
}

halfState go(const halfState& s, int pos, int digit, bool isNum)
{
	int newDigit = digit * (isNum ? num : den) + s.carry;
	int newCarry = newDigit / 10;
	newDigit %= 10;
	int newMask = s.mask;
	int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]);
	if(maskPos != -1) newMask |= (1 << maskPos);
	bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp);
	return halfState(newCarry, newMask, newComp);
}

struct state
{
	halfState numState;
	halfState denState;
	
	state() {};
	state(halfState numState, halfState denState) : numState(numState), denState(denState) {};
	
	void norm()
	{
		if(numState.mask & denState.mask)
			numState.mask = denState.mask = 1;
	};
	
	bool valid()
	{
		return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0);
	};
};

bool operator <(const state& x, const state& y)
{
	if(x.numState != y.numState) return x.numState < y.numState;
	return x.denState < y.denState;
}

state go(const state& s, int pos, int digit)
{
	halfState newNum = go(s.numState, pos, digit, true);
	halfState denNum = go(s.denState, pos, digit, false);
	state res(newNum, denNum);
	res.norm();
	return res;
}

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

int ans = 0;

void calcFixed(int x, int y)
{
	num = x;
	den = y;
	for(int i = 0; i <= 9; i++)
		numPos[i] = denPos[i] = -1;
	int cnt = 0;
	for(int i = 1; i <= 9; i++)
		for(int j = 1; j <= 9; j++)
			if(i * y == j * x)
			{
				numPos[i] = denPos[j] = cnt++;
			}
	vector<map<state, int> > dp(102);
	dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1;
	for(int i = 0; i <= 100; i++)
		for(auto x : dp[i])
		{
			state curState = x.first;
			int curCount = x.second;
			for(int j = 0; j <= 9; j++)
			{
				state newState = go(curState, i, j);
				dp[i + 1][newState] = add(dp[i + 1][newState], curCount);
			}
		}
	for(auto x : dp[101])
	{
		state curState = x.first;
		int curCount = x.second;
		if(curState.valid())
			ans = add(ans, curCount);
	}
}

int main()
{
	string s;
	cin >> s;
	int len = s.size();
	reverse(s.begin(), s.end());
	for(int i = 0; i < len; i++)
	{
		a[i] = s[i] - '0';
 	}
 	for(int i = 1; i <= 9; i++)
 		for(int j = 1; j <= 9; j++)
 			if(__gcd(i, j) == 1)
 				calcFixed(i, j);
 	cout << ans << endl;
}

fun main(args: Array<String>) {
    val tc = readLine()!!.toInt()
    for (i in 1..tc) {
        val (n, s, t) = readLine()!!.split(' ').map { it.toInt() }
        println(maxOf(n - s, n - t) + 1)
    }
}

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
string s, t;
vector<int> pos[26];

int main() {
	cin >> n >> s;
	forn(i, n)
		pos[s[i] - 'a'].push_back(i + 1);
	
	cin >> m;
	forn(i, m){
		cin >> t;
		vector<int> cnt(26);
		for (auto &c : t)
			++cnt[c - 'a'];
		int ans = -1;
		forn(j, 26) if (cnt[j] > 0)
			ans = max(ans, pos[j][cnt[j] - 1]);
		cout << ans << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;

int n, m;
int l[N], r[N], s[N];
int d[N];
int dx[N];
int res[N];
int nxt[N];

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; ++i){
		scanf("%d %d %d", s + i, l + i, r + i);
		--l[i], --r[i];
		if(s[i] == 1)
			++d[l[i]], --d[r[i]];
	}

	memset(dx, -1, sizeof dx);
	int sum = 0;
	for(int i = 0; i < n - 1; ++i){
		sum += d[i];
		if(sum > 0)	
			dx[i] = 0;
	}		

	res[0] = n;
	for(int i = 1; i < n; ++i)
		res[i] = res[i - 1] + dx[i - 1];	

	nxt[n - 1] = n - 1;
	for(int i = n - 2; i >= 0; --i){
		if(res[i] <= res[i + 1])
			nxt[i] = nxt[i + 1];
		else 
			nxt[i] = i;
	}			

	for(int i = 0; i < m; ++i){
		if(s[i] != (nxt[l[i]] >= r[i])){
			puts("NO");
			return 0;		
		}
	}	

	puts("YES");
	for(int i = 0; i < n; ++i)
		printf("%d ", res[i]);
	puts("");

	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;

int t, n;
int a[N], b[N];
vector <int> p[N];
int st[4 * N + 55];

int getMin(int v, int l, int r, int L, int R){
	if(L >= R) return INF;
	if(l == L && r == R)
		return st[v];

	int mid = (l + r) / 2;
	return min(getMin(v * 2 + 1, l, mid, L, min(R, mid)),
		getMin(v * 2 + 2, mid, r, max(mid, L), R));	
}

void upd(int v, int l, int r, int pos, int x){
	if(r - l == 1){
		st[v] = x;
		return;
	}

	int mid = (l + r) / 2;
	if(pos < mid) upd(v * 2 + 1, l, mid, pos, x);
	else upd(v * 2 + 2, mid, r, pos, x);
		
	st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

int main() {
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			p[i].clear();					
		for(int i = 0; i < n; ++i){
			scanf("%d", a + i);
			--a[i];
			p[a[i]].push_back(i);	
		}	
		for(int i = 0; i < n; ++i){
			scanf("%d", b + i);	
			--b[i];		
		}

		for(int i = 0; i < 4 * n; ++i) st[i] = INF;
		for(int i = 0; i < n; ++i){
			reverse(p[i].begin(), p[i].end());
			if(!p[i].empty()) upd(0, 0, n, i, p[i].back());
		}

		bool ok = true;
		for(int i = 0; i < n; ++i){
			if(p[b[i]].empty()){
				ok = false;
				break;
			}

			int pos = p[b[i]].back();
			if(getMin(0, 0, n, 0, b[i]) < pos){
				ok = false;
				break;
			}

			p[b[i]].pop_back();
			upd(0, 0, n, b[i], p[b[i]].empty()? INF : p[b[i]].back());			
		}

		if(ok) puts("YES");
		else puts("NO");
	}	
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n;
long long ans;
vector<int> siz;
vector<long long> dp;
vector<vector<int>> g;

int calcsize(int v, int p = -1) {
	siz[v] = 1;
	for (auto to : g[v]) {
		if (to == p) continue;
		siz[v] += calcsize(to, v);
	}
	return siz[v];
}

long long calcdp(int v, int p = -1) {
	dp[v] = siz[v];
	for (auto to : g[v]) {
		if (to == p) continue;
		dp[v] += calcdp(to, v);
	}
	return dp[v];
}

void dfs(int v, int p = -1) {
	ans = max(ans, dp[v]);
	for (auto to : g[v]) {
		if (to == p) continue;
		
		dp[v] -= dp[to];
		dp[v] -= siz[to];
		siz[v] -= siz[to];
		siz[to] += siz[v];
		dp[to] += siz[v];
		dp[to] += dp[v];
		
		dfs(to, v);
		
		dp[to] -= dp[v];
		dp[to] -= siz[v];
		siz[to] -= siz[v];
		siz[v] += siz[to];
		dp[v] += siz[to];
		dp[v] += dp[to];
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	g = vector<vector<int>>(n);
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	ans = 0;
	siz = vector<int>(n);
	dp = vector<long long>(n);
	
	calcsize(0);
	calcdp(0);
	dfs(0);
	
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

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

typedef long long li;

using namespace std;

const int N = 200 * 1000 + 13;

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

int siz[N];
li sum[N];

void init(int v, int p = -1){
	siz[v] = 1;
	sum[v] = 0;
	for (auto u : g[v]) if (u != p){
		init(u, v);
		siz[v] += siz[u];
		sum[v] += sum[u];
	}
	sum[v] += (siz[v] - 1);
}

li dp[N];

void dfs(int v, int p = -1){
	dp[v] = 0;
	li tot = 0;
	for (auto u : g[v]) if (u != p)
		tot += sum[u];
	for (auto u : g[v]) if (u != p){
		dfs(u, v);
		dp[v] = max(dp[v], (n - siz[u] - 1) + dp[u] + (tot - sum[u]));
	}
	if (g[v].size() == 1){
		dp[v] = n - 1;
	}
}

int main() {
	scanf("%d", &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);
	}
	
	if (n == 2) {
		cout << 3 << endl;
		return 0;
	}
	
	forn(i, n) if (int(g[i].size()) > 1){
		init(i);
		dfs(i);
		printf("%lld\n", dp[i] + n);
		break;
	}
	
	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;

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;
	for(; k > 0; k >>= 1) {
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
	}
	return ans;
}
int inv(int a) {
	int b = binPow(a, MOD - 2);
	assert(mul(a, b) == 1);
	return b;
}

int n;
vector<int> l, r;

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

vector<int> p;

int calcEq(int i0) { 
	int i1 = i0 + 1;
	int pSame = 0;
	if(i0 > 0) {
		int cnt = max(0, min({r[i0 - 1], r[i0], r[i1]}) - max({l[i0 - 1], l[i0], l[i1]}));
		pSame = mul(cnt, inv(mul(mul(r[i0 - 1] - l[i0 - 1], r[i0] - l[i0]), r[i1] - l[i1])));
	}
	return norm(1 - norm(2 - p[i0] - p[i1]) + pSame);
}

inline void solve() {
	p.assign(n, 0);
	p[0] = 1;
	fore(i, 1, n) {
		int cnt = max(0, min(r[i - 1], r[i]) - max(l[i - 1], l[i]));
		p[i] = norm(1 - mul(cnt, inv(mul(r[i - 1] - l[i - 1], r[i] - l[i]))));
	}
	
	int sum = 0;
	fore(i, 0, n)
		sum = norm(sum + p[i]);
	
	int ans = 0;
	fore(i, 0, n) {
		int curS = sum;
		for(int j = max(0, i - 1); j < min(n, i + 2); j++)
			curS = norm(curS - p[j]);
		
		ans = norm(ans + mul(p[i], curS));
		
		if(i > 0)
			ans = norm(ans + calcEq(i - 1));
		ans = norm(ans + p[i]);
		if(i + 1 < n)
			ans = norm(ans + calcEq(i));
	}
	
	cout << ans << endl;
}

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

#include<bits/stdc++.h>

using namespace std;

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

vector<edge> e;

const int N = 14043;
vector<int> g[N];

long long ans = 0;
long long d[N];
int p[N];
int pe[N];
int inq[N];

const long long INF64 = (long long)(1e18);

int s = N - 2;
int t = N - 1;

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

void push_flow()
{
	for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0;
	d[s] = 0;
	queue<int> q;
	q.push(s);
	inq[s] = 1;
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		inq[k] = 0;
		for(auto x : g[k])
		{
			if(!rem(x)) continue;
			int c = e[x].cost;
			int y = e[x].y;
			if(d[y] > d[k] + c)
			{
				d[y] = d[k] + c;
				p[y] = k;
				pe[y] = x;
				if(inq[y] == 0)
				{
					inq[y] = 1;
					q.push(y);
				}
			}
		}
	}
	int cur = t;
//	vector<int> zz(1, cur);
	while(cur != s)
	{
		e[pe[cur]].f++;
		e[pe[cur] ^ 1].f--;
		cur = p[cur];
//		zz.push_back(cur);
	}
//	reverse(zz.begin(), zz.end());
//	for(auto x : zz) cerr << x << " ";
//	cerr << endl;
	ans += d[t];
}

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

int main()
{
	int n, m, k, c, d;
	cin >> n >> m >> k >> c >> d;
	for(int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		--x;
		add_edge(s, x, 1, 0);
	}
	int tt = 101;
	for(int i = 0; i < tt; i++)
		add_edge(0 + i * n, t, k, i * c);
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		for(int i = 0; i < tt - 1; i++)
			for(int j = 0; j < k; j++)
				add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1));
		for(int i = 0; i < tt - 1; i++)
			for(int j = 0; j < k; j++)
				add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1));
 	}
 	for(int i = 0; i < n; i++)
 		for(int j = 0; j < tt - 1; j++)
 			add_edge(i + j * n, i + j * n + n, k, 0);
 	for(int i = 0; i < k; i++)
 		push_flow();
 	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

long long n, k;

int main(){
    int tc;
    cin >> tc;
    for(int i = 0; i < tc; ++i){
    	cin >> n >> k;
    	long long res = 0;
    	while(n > 0){
    	    if(n % k == 0){
    	        n /= k;
    	        ++res;
    	    }
    	    else{
    	        long long rem = n % k;
    	        res += rem;
    	        n -= rem;
    	    }
    	}
    	
    	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 long long INF = 1ll << 32;

int main(){
	int l;
	cin >> l;
	
	stack<long long> cur;
	cur.push(1);
	
	long long res = 0;
	forn(_, l){
		string t;
		cin >> t;
		if (t == "for"){
			int x;
			cin >> x;
			cur.push(min(INF, cur.top() * x));
		}
		else if (t == "end"){
			cur.pop();
		}
		else{
			res += cur.top();
		}
	}
	
	if (res >= INF)
		cout << "OVERFLOW!!!" << endl;
	else
		cout << res << endl;
}

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

int n, k;
vector<int> a;

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

inline void solve() {
	pair<int, int> ans = {int(1e9) + 7, -1};
	fore(i, 0, n - k) {
		int dist = a[i + k] - a[i];
		ans = min(ans, make_pair(dist, a[i] + dist / 2));
	}
	
	cout << ans.second << 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 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 = 300009;

int n, k;
int a[N];

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i)
		cin >> a[i];
	
	long long sum = 0;
	vector <long long> v;
	for(int i = n - 1; i >= 0; --i){
	    sum += a[i];
	    if(i > 0) v.push_back(sum);
	}
	
	long long res = sum;
	
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	
	
	for(int i = 0; i < k - 1; ++i)
	    res += v[i];
	    
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;
const int LOGN = 18;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int up[LOGN][N];

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	forn(i, n)
		up[0][i] = nxt[a[i].y];
	for (int j = 1; j < LOGN; ++j) forn(i, n){
		if (up[j - 1][i] == -1)
			up[j][i] = -1;
		else
			up[j][i] = up[j - 1][up[j - 1][i]];
	}
	
	forn(i, m){
		int x = nxt[q[i].x];
		
		if (x == -1){
			puts("-1");
			continue;
		}
		
		int res = 1;
		for (int j = LOGN - 1; j >= 0; --j){
			int y = up[j][x];
			if (y == -1)
				continue;
			if (a[y].y < q[i].y){
				res += (1 << j);
				x = y;
			}
		}
		
		if (a[x].y >= q[i].y)
			printf("%d\n", res);
		else if (up[0][x] == -1)
			puts("-1");
		else
			printf("%d\n", res + 1);
	}
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;

int n, m;
pair<int, int> a[N], q[N];

int nxt[N];
int ans[N];

pair<int, int> p[N];

pair<int, int> get(int x, int r){
	if (x == -1)
		return make_pair(-1, -1);
	if (a[x].y >= r)
		return make_pair(x, 0);
	auto res = get(p[x].x, r);
	if (res.x == -1)
		p[x] = make_pair(-1, -1);
	else
		p[x] = make_pair(res.x, p[x].y + res.y);
	return p[x];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n)
		scanf("%d%d", &a[i].x, &a[i].y);
	forn(i, m)
		scanf("%d%d", &q[i].x, &q[i].y);
	sort(a, a + n);
	
	int lst = 0;
	pair<int, int> mx(0, -1);
	forn(i, N){
		while (lst < n && a[lst].x == i){
			mx = max(mx, make_pair(a[lst].y, lst));
			++lst;
		}
		nxt[i] = (mx.x <= i ? -1 : mx.y);
	}
	
	vector<int> perm(m);
	iota(perm.begin(), perm.end(), 0);
	sort(perm.begin(), perm.end(), [](int a, int b){
		return q[a].y < q[b].y;
	});
	
	forn(i, n)
		p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1);
	
	for (auto i : perm){
		int x = nxt[q[i].x];
		auto res = get(x, q[i].y).y;
		ans[i] = (res == -1 ? -1 : res + 1);
	}
	
	forn(i, m)
		printf("%d\n", ans[i]);
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> pt;

const int N = int(3e5) + 99;
const pt zero = make_pair(0, 0);

int n;
int a[N];
pt hsh[N], sumHsh[N];

void upd(pt &a, pt b){
    a.first ^= b.first;
    a.second ^= b.second;
}

int calc(int pos){
	set <int> sl, sr;
	set<pt> s;
	int r = pos + 1, l = pos - 1;
	pt curr = hsh[0], curl = zero;
	s.insert(zero);
	sr.insert(0), sl.insert(0);
	
	int res = 0;	
	while(r < n && !sr.count(a[r])){
		sr.insert(a[r]);
		upd(curr, hsh[a[r]]);
		++r;

		while(l >= 0 && !sl.count(a[l]) && a[l] < *sr.rbegin()){
			sl.insert(a[l]);
			upd(curl, hsh[a[l]]);
			s.insert(curl);
			--l;	
		}

		pt need = sumHsh[*sr.rbegin()];
		upd(need, curr);
		if(s.count(need)) ++res;
	}	

	return res;
}	

int main() {
    long long x = 0;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		--a[i];	
		x ^= a[i];
	}
	
	
	mt19937_64 rnd(time(NULL));
	for(int i = 0; i < N; ++i){
		hsh[i].first = rnd() ^ x;
		hsh[i].second = rnd() ^ x;
		sumHsh[i] = hsh[i];
		if(i > 0) upd(sumHsh[i], sumHsh[i - 1]);
	}
	
	int res = 0;
		
	for(int tc = 0; tc < 2; ++tc){
		for(int i = 0; i < n; ++i)
			if(a[i] == 0)
				res += calc(i) + (tc == 0);
		reverse(a, a + n);
	}
	cout << res << endl;

	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<li, li> pt;

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

pt operator -(const pt &a, const pt &b) {
    return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
    return a.x * b.x + a.y * b.y;
}
li operator %(const pt &a, const pt &b) {
    return a.x * b.y - a.y * b.x;
}
pt rotate(const pt &p) {
    return {-p.y, p.x};
}

struct LinearHull {
    deque<pt> pts, vecs;

    void addRight(const pt &l) {
        while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) {
            vecs.pop_back();
            pts.pop_back();
        }
        if(!pts.empty())
            vecs.push_back(rotate(l - pts.back()));
        pts.push_back(l);
    }
    void addLeft(const pt &l) {
        while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) {
            vecs.pop_front();
            pts.pop_front();
        }
        if(!pts.empty())
            vecs.push_front(rotate(pts.front() - l));
        pts.push_front(l);
    }

    li getMin(const pt &x) {
        auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) {
            return a % b > 0;
        });
        return x * pts[it - vecs.begin()];
    }
};

typedef unique_ptr<LinearHull> pHull;

void mergeHulls(pHull &a, pHull &b) {
    if(sz(b->pts) >= sz(a->pts)) {
        for(auto &p : a->pts)
            b->addRight(p);
    } else {
        for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++)
            a->addLeft(*it);
        swap(a, b);
    }
}

const int M = 1000 * 1000 + 555;
int szn = 0;
struct node {
    pt line;
    node *l, *r;

    node() : line(), l(nullptr), r(nullptr) {}
    node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {}
} nodes[M];

typedef node* tree;

tree getNode(const pt &line, tree l, tree r) {
    assert(szn < M);
    nodes[szn] = node(line, l, r);
    return &nodes[szn++];
}
tree copy(tree v) {
    if(v == nullptr) return v;
    return getNode(v->line, v->l, v->r);
}

li f(const pt &line, int x) {
    return line * pt{x, 1};
}

tree addLine(tree v, int l, int r, pt line) {
    if(!v)
        return getNode(line, nullptr, nullptr);
    int mid = (l + r) >> 1;
    bool lf = f(line, l) < f(v->line, l);
    bool md = f(line, mid) < f(v->line, mid);

    if(md)
        swap(v->line, line);

    if(l + 1 == r)
        return v;
    else if(lf != md)
        v->l = addLine(copy(v->l), l, mid, line);
    else
        v->r = addLine(copy(v->r), mid, r, line);
    return v;
}

li getMin(tree v, int l, int r, int x) {
    if(!v) return INF64;
    if(l + 1 == r)
        return f(v->line, x);
    int mid = (l + r) >> 1;

    if(x < mid)
        return min(f(v->line, x), getMin(v->l, l, mid, x));
    else
        return min(f(v->line, x), getMin(v->r, mid, r, x));
}

int n, k;
vector<li> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);

    fore(i, 0, n)
        cin >> a[i];
    return true;
}

struct state {
    int pos;
    pHull hull;
    tree v;

    state() : pos(-1), hull(nullptr), v(nullptr) {}
};

vector<li> d[2];

inline void solve() {
    int maxn = (int)*max_element(a.begin(), a.end()) + 3;
    fore(k, 0, 2)
        d[k].resize(n + 1, INF64);

    d[0][0] = 0;
    fore(_k, 1, k + 1) {
        szn = 0;

        int ck = _k & 1;
        int nk = ck ^ 1;

        vector< state > st;

        fore(i, 0, sz(d[ck])) {
            d[ck][i] = INF64;
            if(!st.empty())
                d[ck][i] = getMin(st.back().v, 0, maxn, i);

            if(i >= sz(a))
                continue;

            state curVal;
            curVal.pos = i;
            curVal.hull = make_unique<LinearHull>();
            curVal.hull->addRight({-i, d[nk][i]});
            curVal.v = nullptr;

            while(!st.empty() && a[st.back().pos] < a[i]) {
                mergeHulls(st.back().hull, curVal.hull);
                st.pop_back();
            }
            if(!st.empty())
                curVal.v = st.back().v;

            li val = curVal.hull->getMin({a[i], 1});
            curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val});

            st.push_back(move(curVal));
        }
    }
    cout << d[k & 1][n] << endl;
}

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

    if(read()) {
        solve();

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

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    int tc;
    cin >> tc;
    for(int t = 0; t < tc; ++t){
        cin >> n >> s;
        int pos = n;
        for(int i = 0; i < n; ++i)
            if(s[i] == '8'){
                pos = i;
                break;
            }
            
        if(n - pos >= 11)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

vector<int> p = {4, 8, 15, 16, 23, 42};
int ans[4];

int main()
{
	for(int i = 0; i < 4; i++)
	{
		cout << "? " << i + 1 << " " << i + 2 << endl;
		cout.flush();
		cin >> ans[i];
	}
	do
	{
		bool good = true;
		for(int i = 0; i < 4; i++)
			good &= (p[i] * p[i + 1] == ans[i]);
		if(good) break;
	}
	while(next_permutation(p.begin(), p.end()));
	cout << "!";
	for(int i = 0; i < 6; i++)
		cout << " " << p[i];
	cout << endl;
	cout.flush();
	return 0;
}

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

const int N = 1000043;
vector<int> g[N];

int color[N];
int siz[N];
int n, m;
int cc = 0;

int dfs(int x)
{
	if(color[x])
		return 0;
	color[x] = cc;
	int ans = (x < n ? 1 : 0);
	for(auto y : g[x])
		ans += dfs(y);
	return ans; 
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++)
	{
		int k;
		scanf("%d", &k);
		for(int j = 0; j < k; j++)
		{
			int x;
			scanf("%d", &x);
			--x;
			g[x].push_back(i + n);
			g[i + n].push_back(x);
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(!color[i])
		{
			cc++;
			siz[cc] = dfs(i);
		}
		printf("%d ", siz[color[i]]);
	}
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;

int n, m;
int rk[N], p[N];

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);
	p[b] = a;
	rk[a] += rk[b];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n) p[i] = i, rk[i] = 1;
	
	forn(i, m){
		int k;
		scanf("%d", &k);
		int lst = -1;
		forn(j, k){
			int x;
			scanf("%d", &x);
			--x;
			if (lst != -1)
				unite(x, lst);
			lst = x;
		}
	}
	
	forn(i, n)
		printf("%d ", rk[getP(i)]);
	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())

int n;
string s;

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

inline void solve() {
	string t(n, '0');
	
	int bal = 0;
	fore(i, 0, n) {
		if(s[i] == ')')
			bal--;
		
		t[i] = char('0' + (bal & 1));
		
		if(s[i] == '(')
			bal++;
	}
	
	cout << t << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e6) + 99;
int n, x;
int a[N];
vector <int> pos[N];
int prefMax[N];

int main() {
	scanf("%d %d", &n, &x);
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		pos[a[i]].push_back(i);	
		prefMax[i] = max(a[i], (i > 0 ? prefMax[i - 1] : a[i]));
	}
	
	int p = 1;
	int lst = n + 5;
	for(int i = x; i >= 1; --i){
		if(pos[i].empty()){
		    p = i;
		    continue;
		}
		if(pos[i].back() > lst) break;
		p = i;
		lst = pos[i][0];
	}	

	long long res = 0;
	lst = -1;
	for(int l = 1; l <= x; ++l){
		int r = max(l, p - 1);
		if(lst != -1) r = max(r, prefMax[lst]);
		res += x - r + 1;
		if(!pos[l].empty()){
    		if(pos[l][0] < lst) break;
    		lst = pos[l].back();
		}
	}	

	cout << res << endl;
	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())

typedef long long li;

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

int add(int a, int b) {
	a += b;
	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 n;
vector<int> a;

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

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

vector<int> S[2];

inline void solve() {
	fore(k, 0, 2) {
		S[k].assign(n, 0);
		f.assign(n, 0);
		
		vector<int> dx(a.begin(), a.end());
		sort(dx.begin(), dx.end());
		
		fore(i, 0, n) {
			int pos = int(lower_bound(dx.begin(), dx.end(), a[i]) - dx.begin());
			S[k][i] = int(sum(pos) % MOD);
			inc(pos, i + 1);
		}
		reverse(a.begin(), a.end());
	}
	
	reverse(S[1].begin(), S[1].end());
	int ans = 0;
	fore(i, 0, n) 
		ans = add(ans, mul(a[i], add(mul(i + 1, n - i), add(mul(S[0][i], n - i), mul(S[1][i], i + 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);
	
	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;

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

const int N = 200 * 1000 + 555;
const int D = 7077;

int n, d, m;
int a[N], qs[N];

inline bool read() {
	if(scanf("%d%d", &n, &d) != 2)
		return false;
	fore(i, 0, n)
		scanf("%d", &a[i]);
	
	assert(scanf("%d", &m) == 1);
	fore(i, 0, m)
		scanf("%d", &qs[i]);
	return true;
}

bitset<D> L, R, cur;
int dist[N];
set<int> has;

void shiftL(int s, int t, int &uk) {
	L <<= t - s;
	for(; uk < n && a[uk] < t; uk++) {
		if(t - a[uk] - 1 < D)
			L[t - a[uk] - 1] = 1;
		if(t - a[uk] < D)
			L[t - a[uk]] = 1;
	}
}

void shiftR(int s, int t, int &uk) {
	R >>= t - s;
	if(!has.count(t))
		R[0] = 0;
	
	for(; uk < n && a[uk] < t + D; uk++) {
		if(a[uk] - t >= 0) {
			R[a[uk] - t] = 1;
			if(a[uk] - t + 1 >= 0)
				R[a[uk] - t + 1] = 1;
		}
	}
}

inline void solve() {
	fore(i, 0, m) {
		dist[i] = INF;
		int pos = int(lower_bound(a, a + n, qs[i]) - a);
		if(pos > 0)
			dist[i] = qs[i] - a[pos - 1] - 1;
		if(pos < n)
			dist[i] = min(dist[i], a[pos] - qs[i]);
	}
	has = set<int>(a, a + n);
	
	int uL = 0, uR = 0;
	L.reset();
	R.reset();
	fore(i, 0, m) {
		shiftL(i > 0 ? qs[i - 1] : -D, qs[i], uL);
		shiftR(i > 0 ? qs[i - 1] : -D, qs[i], uR);
		
		double ans = atan2(1, dist[i]);

		cur = L & R;
		int pos = (int)cur._Find_first();
		if(pos < D) {
			int ds = pos;
			ans = max(ans, 2 * atan2(1, ds));
		}
		printf("%.15f\n", ans);
	}
}

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

#include <bits/stdc++.h>

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

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	int sum = 0;
	int lst = 1;
	vector<int> figs;
	forn(i, n){
		int x;
		scanf("%d", &x);
		if (lst != 1 && x != 1){
			puts("Infinite");
			return 0;
		}
		if (x != 1){
			figs.push_back(x);
			sum += x + 1;
			if (i != 0 && i != n - 1)
				sum += x + 1;
		}
		lst = x;
	}
	forn(i, int(figs.size()) - 1) if (figs[i] == 3 && figs[i + 1] == 2)
		--sum;
	printf("Finite\n%d\n", sum);
}

#include <bits/stdc++.h>

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

using namespace std;

bool check(string s){
	bool ok = true;
	forn(i, int(s.size()) - 1)
		ok &= (abs(s[i] - s[i + 1]) != 1);
	return ok;
}

int main() {
	int T;
	scanf("%d", &T);
	static char buf[120];
	forn(_, T){
		scanf("%s", buf);
		string s = buf;
		string odd = "", even = "";
		forn(i, s.size()){
			if (s[i] % 2 == 0)
				odd += s[i];
			else
				even += s[i];
		}
		sort(odd.begin(), odd.end());
		sort(even.begin(), even.end());
		if (check(odd + even))
			printf("%s\n", (odd + even).c_str());
		else if (check(even + odd))
			printf("%s\n", (even + odd).c_str());
		else
			puts("No answer");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int n, z;
int a[N];

int main()
{
	scanf("%d", &n);
	scanf("%d", &z);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int l = 0;
	int r = n / 2 + 1;
	while(r - l > 1)
	{
		int m = (l + r) / 2;
		bool good = true;
		for(int i = 0; i < m; i++)
			good &= (a[n - m + i] - a[i] >= z);
		if(good)
			l = m;
		else
			r = m;
	}
	cout << l << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int p[2][N];
int siz[2][N];

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

void merge(int x, int y, int c)
{
	x = get(x, c);
	y = get(y, c);
	if(siz[c][x] < siz[c][y])
		swap(x, y);
	p[c][y] = x;
	siz[c][x] += siz[c][y];
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		p[0][i] = p[1][i] = i;
		siz[0][i] = siz[1][i] = 1;
	}
	for(int i = 0; i < n - 1; i++)
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		--x;
		--y;
		merge(x, y, c);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(p[0][i] == i)
			ans += siz[0][i] * 1ll * (siz[0][i] - 1);
		if(p[1][i] == i)
			ans += siz[1][i] * 1ll * (siz[1][i] - 1);
		ans += (siz[0][get(i, 0)] - 1) * 1ll * (siz[1][get(i, 1)] - 1);
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int lf[N];
int rg[N];
int n;
int ans = 0;
int p[N];
int q[N];

void update(int l, int r, int l2, int r2, int sum)
{
	for(int i = l; i <= r; i++)
	{
		int o = sum - p[i];
		if(o >= 1 && o <= n && l2 <= q[o] && q[o] <= r2)
			ans++;
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &p[i]);
		q[p[i]] = i;
	}
	stack<pair<int, int> > s;
	s.push(make_pair(n + 1, -1));
	for(int i = 0; i < n; i++)
	{
		while(s.top().first < p[i])
			s.pop();
		lf[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	while(!s.empty())
		s.pop();
	s.push(make_pair(n + 1, n));
	for(int i = n - 1; i >= 0; i--)
	{
		while(s.top().first < p[i])
			s.pop();
		rg[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	for(int i = 0; i < n; i++)
	{
	//	cerr << i << " " << lf[i] << " " << rg[i] << endl;
		int lenl = i - lf[i] - 1;
		int lenr = rg[i] - i - 1;
		if(lenl == 0 || lenr == 0)
			continue;
		if(lenl < lenr)
			update(lf[i] + 1, i - 1, i + 1, rg[i] - 1, p[i]);
		else
			update(i + 1, rg[i] - 1, lf[i] + 1, i - 1, p[i]);
	}
	cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5005;

void upd(int &a, int b){
    a += b;
    a %= MOD;
}

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

int bp(int a, int n){
    int res = 1;
    for(; n > 0; n >>= 1){
        if(n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int getInv(int a){
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n;
int cnt[N];
int suf[N];
int dp[N][N];
int sum[N][N];
int inv[N];

int main(){
    for(int i = 1; i < N; ++i)
        inv[i] = getInv(i);
        
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        ++cnt[x];
    }
    cnt[0] = 1;
    for(int i = N - 2; i >= 0; --i)
        suf[i] = suf[i + 1] + cnt[i];
        
    for(int x = n; x >= 0; --x)
        for(int y = n; y >= 0; --y){
            if(cnt[x] == 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            int s = n - y;
            if(s <= 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            
            upd(dp[x][y], mul(cnt[x] - 1, inv[s]));
            upd(dp[x][y], mul(sum[x + 1][y + 1], inv[s]));
            
            upd(sum[x][y], sum[x + 1][y]);
            upd(sum[x][y], mul(cnt[x], dp[x][y]));
        }
    
    cout << dp[0][0] << endl;
	return 0;
}

Solution described in a tutorial.

Jury's solution:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;


struct expr {
	string t; // variable name or operation
	expr * l, * r; // only if operation
	long long hash;
	
	expr (string var)
		: t(var), l(0), r(0), hash(0)
		{ }
	expr (char op, expr * l, expr * r)
		: t(1,op), l(l), r(r), hash(0)
		{ }

	long long calc_hash() {
		if (!hash)
			if (!l) {
				long long pw = 257;
				for (size_t i=0; i<t.length(); ++i,  pw*=97)
					hash += t[i] * pw;
			}
			else
				hash += l->calc_hash() * t[0] + r->calc_hash() * 31;
		return hash;
	}
};

map<string,expr*> var;

void inc_var_name (string & cur) {
	for (size_t i=cur.length()-1; ; --i)
		if (cur[i] < 'z') {
			++cur[i];
			break;
		}
		else
			cur[i] = 'a';
}

string generate_var() {
	static string cur = "aaaa";
	while (var.count(cur))
		inc_var_name (cur);
	string res = cur;
	inc_var_name (cur);
	return res;
}

vector<string> ans;
map<long long,string> calced;

string restore (expr * e, string name = "") {
	if (!e->l)  return e->t;
	long long h = e->calc_hash();
	if (calced.count(h))  return calced[h];
	string l = restore (e->l),  r = restore (e->r);
	string my = name.empty() ? generate_var() : name;
	calced[h] = my;
	ans.push_back (my + "=" + l + e->t + r);
	return my;
}

int main() {
	int n;
	scanf ("%d\n", &n);
	for (int i=0; i<n; ++i) {
		static char buf[100];
		gets (buf);
		string s = buf;

		size_t pos1 = s.find ('='),  pos2 = s.find_first_of ("&^$#");
		string lname = s.substr (0, pos1);
		string r1name = s.substr (pos1 + 1, pos2 - pos1 - 1);
		if (!var.count(r1name))
			var[r1name] = new expr (r1name);
		if (pos2 != -1) {
			string r2name = s.substr (pos2 + 1);
			if (!var.count(r2name))
				var[r2name] = new expr (r2name);
			var[lname] = new expr (s [ s.find_first_of ("&^$#") ], var[r1name], var[r2name]);
		}
		else
			var[lname] = var[r1name];
	}

	if (!var.count("res")) {
		cout << 0;
		return 0;
	}

	string name = restore (var["res"], "res");
	if (name != "res")
		ans.push_back ("res=" + name);

	cout << ans.size() << endl;
	for (size_t i=0; i<ans.size(); ++i)
		puts (ans[i].c_str());

}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	string s;
	cin >> n >> s;
	
	for (int i = 1; i < int(s.size()); ++i) {
		if (s[i] < s[i - 1]) {
			cout << "YES" << endl;
			cout << i << " " << i + 1 << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n;
string s;

int main(){
    cin >> n >> s;
    int cnt1 = (n - 11) / 2;
    int cnt2 = cnt1;
    string res = "";
    for(int i = 0; i < n; ++i){
        if(s[i] == '8'){
            if(cnt1 > 0) --cnt1;
            else res += s[i];
        }
        else{
            if(cnt2 > 0) --cnt2;
            else res += s[i];
        }
    }
    
    if(res[0] == '8') cout << "YES\n";
    else cout << "NO\n";
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	vector<long long> x(n), p(m);
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> p[i];
	}
	
	long long g = x[1] - x[0];
	for (int i = 2; i < n; ++i) {
		g = __gcd(g, x[i] - x[i - 1]);
	}
	
	for (int i = 0; i < m; ++i) {
		if (g % p[i] == 0) {
			cout << "YES" << endl;
			cout << x[0] << " " << i + 1 << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

typedef long long li;

const int N = 300 * 1000 + 13;
const li INF64 = 1e18;

int n, x;
int a[N];

li dp[N][3][3];

int main() {
	scanf("%d%d", &n, &x);
	forn(i, n) scanf("%d", &a[i]);
	
	forn(i, n + 1) forn(j, 3) forn(k, 3)
		dp[i][j][k] = -INF64;
	
	dp[0][0][0] = 0;
	forn(i, n + 1) forn(j, 3) forn(k, 3){
		if (k < 2)
			dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]);
		if (j < 2)
			dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
		if (i < n)
			dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1));
	}
	
	printf("%lld\n", dp[n][2][2]);
}

#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 MOD = 1000 * 1000 + 3;

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;
}
int inv(int a) {
	return binPow(a, MOD - 2);
}

int k = 10;
vector<int> f;

int main() {
	f.resize(k + 1);
	fore(i, 0, sz(f)) {
		cout << "? " << i << endl;
		cout.flush();
		cin >> f[i];
	}
	
	vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1));
	fore(i, 0, sz(mat)) {
		mat[i][0] = 1;
		mat[i][sz(f)] = f[i];
		
		fore(j, 1, sz(mat[i]) - 1)
			mat[i][j] = mul(mat[i][j - 1], i);
	}
	
	/*
	fore(i, 0, sz(mat)) {
		fore(j, 0, sz(mat[i]))
			cerr << mat[i][j] << " ";
		cerr << endl;
	}
	*/
	
	fore(j, 0, sz(mat)) {
		int nid = -1;
		fore(i, j, sz(mat)) {
			if(mat[i][j] != 0) {
				nid = i;
				break;
			}
		}
		if(nid == -1)
			continue;
		
		swap(mat[j], mat[nid]);
		fore(i, 0, sz(mat)) {
			if(i == j) continue;
			int cf = mul(mat[i][j], inv(mat[j][j]));
			
			fore(cj, j, sz(mat[i]))
				mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj]));
		}
	}
	
	vector<int> a(sz(f), 0);
	fore(i, 0, sz(a)) {
		if(mat[i][i] == 0)
			continue;
		a[i] = mul(mat[i][sz(a)], inv(mat[i][i]));
	}
	
	fore(x0, 0, MOD) {
		int val = 0;
		for(int i = sz(a) - 1; i >= 0; i--)
			val = norm(mul(val, x0) + a[i]);
			
		if(val == 0) {
			cout << "! " << x0 << endl;
			return 0;
		}
	}
	
	cout << "! -1" << endl;
	return 0;
}

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

const int N = 14;
const int INF = int(1e9);

int dp[1 << N];
int par[1 << N];
int last[1 << N];
pair<int, int> last_pair[1 << N];
int dp2[N][N][1 << N];
int lastv[N][N][1 << N];
vector<int> bits[1 << N];

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

int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i = 0; i < (1 << n); i++)
		dp[i] = INF;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int z = 0; z < (1 << n); z++)
				dp2[i][j][z] = INF;
	for(int i = 0; i < n; i++)
		for(auto x : g[i])
		{
			dp2[i][x][0] = 1;
			lastv[i][x][0] = i;
		}
	for(int mask = 0; mask < (1 << n); mask++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
			{
				if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF))
					continue;
				for(auto z : g[j])
				{
					if(mask & (1 << z)) continue;
					if(z == lastv[i][j][mask]) continue;
					int nmask = mask ^ (1 << j);
					if(dp2[i][z][nmask] == INF)
					{
						dp2[i][z][nmask] = 1;
						lastv[i][z][nmask] = j;
					}
				}
			}
	for(int mask = 0; mask < (1 << n); mask++)
		for(int j = 0; j < n; j++)
			if(mask & (1 << j))
				bits[mask].push_back(j);
	dp[1] = 0;
	for(int mask = 0; mask < (1 << n); mask++)
		for(int addmask = mask; addmask; addmask = (addmask - 1) & mask)
		{
			int lastmask = mask ^ addmask;
			int cnt = __builtin_popcount(addmask) + 1;
			if(dp[lastmask] + cnt >= dp[mask])
				continue;
			bool f = false;
			for(auto x : bits[lastmask])
			{
				for(auto y : bits[lastmask])
				{
					if(dp2[x][y][addmask] == 1)
					{
						dp[mask] = dp[lastmask] + cnt;
						last_pair[mask] = make_pair(x, y);
						last[mask] = addmask;
					}
					if(f) break;
				}
				if(f) break;
			}
		}
	if(dp[(1 << n) - 1] == INF)
		cout << -1 << endl;
	else
	{
		cout << dp[(1 << n) - 1] << endl;
		int cur = (1 << n) - 1;
		while(cur != 1)
		{
			int lst = last[cur];
			int x = last_pair[cur].first;
			int y = last_pair[cur].second;
			cur ^= lst;
			while(lst)
			{
				int ny = lastv[x][y][lst];
				cout << y + 1 << " " << ny + 1 << endl;
				lst ^= (1 << ny);
				y = ny;
			}
			cout << x + 1 << " " << y + 1 << endl;
		}
	}
}

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

int n;
vector<int> a;

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

inline void solve() {
	int cnt = 0, pos = 0;
	while(pos < n) {
		cnt++;
		int mx = pos;
		while(pos < n && pos <= mx) {
			mx = max(mx, a[pos]);
			pos++;
		}
	}
	cout << cnt << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif	
	if(read()) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t, n;
string s;

int main(){
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> n >> s;
		int res = n - 1;
		for(int i = 0; i < n; ++i)
			if(s[i] == '>' || s[n - 1 - i] == '<')
				res = min(res, i);
		
		cout << res << endl;
	}

	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

int n, k;
pair<int, int> a[N];

int main() {
	cin >> n >> k;
	
	for(int i = 0; i < n; ++i)
		cin >> a[i].second >> a[i].first;

	sort(a, a + n);
	long long res = 0;
	long long sum = 0;
	set<pair<int, int> > s;
	for(int i = n - 1; i >= 0; --i){
		s.insert(make_pair(a[i].second, i));
		sum += a[i].second;
		while(s.size() > k){
			auto it = s.begin();
			sum -= it->first;
			s.erase(it);
		}

		res = max(res, sum * a[i].first);
	}

	cout << res << endl;
	return 0;
}

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

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

	long long ans = 0;
	for(int id = 2; id < n; id++)
		ans += 1ll * id * (id + 1);
	
	cout << ans << endl;
}

#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 MOD = 998244353;
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 n, k;
vector<int> a;

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

pair<int, int> calc(int len) {
    if(len == 0) return {0, 1};
    if(len & 1) {
        auto res = calc(len >> 1);
        return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
                norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    }
    auto res = calc(len - 1);
    return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}

vector<int> curArray;

int calcSeg(int l, int r) {
    if(r >= sz(curArray)) {
        int len = r - l - 1, cf = 1;
        if(l < 0)
            len--, cf = k;
        if(len == 0) return cf;

        auto res = calc(len - 1);
        return mul(cf, norm(res.x + mul(k - 1, res.y)));
    }
    if(l < 0) {
        if(r - l == 1) return 1;
        auto res = calc(r - l - 2);
        return norm(res.x + mul(k - 1, res.y));
    }
    auto res = calc(r - l - 1);
    return curArray[l] == curArray[r] ? res.x : res.y;
}

inline void solve() {
    int ans = 1;
    fore(k, 0, 2) {
        curArray.clear();
        for(int i = 0; 2 * i + k < n; i++)
            curArray.push_back(a[2 * i + k]);

        int lst = -1;
        fore(i, 0, sz(curArray)){
            if(curArray[i] == -1) continue;
            ans = mul(ans, calcSeg(lst, i));
            lst = i;
        }
        ans = mul(ans, calcSeg(lst, sz(curArray)));
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    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;

typedef long long li;

#define x first
#define y second

const int N = 300043;
const int K = 300000;

int p[2 * N];
int s1[2 * N];
int s2[2 * N];
li ans = 0;

int* where[80 * N];
int val[80 * N];
int cur = 0;

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

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

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

void merge(int x, int y)
{
	x = get(x);
	y = get(y);
	if(x == y) return;
	ans -= s1[x] * 1ll * s2[x];
	ans -= s1[y] * 1ll * s2[y];
	if(s1[x] + s2[x] < s1[y] + s2[y])
		swap(x, y);
	change(p[y], x);
	change(s1[x], s1[x] + s1[y]);
	change(s2[x], s2[x] + s2[y]);
	ans += s1[x] * 1ll * s2[x];
}

void init()
{
	for(int i = 0; i < K; i++)
	{
		p[i] = i;
		p[i + K] = i + K;
		s1[i] = 1;
		s2[i + K] = 1;
	}
}

vector<pair<int, int> > T[4 * N];

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

li res[N];

void dfs(int v, int l, int r)
{
	li last_ans = ans;
	int state = cur;
	for(auto x : T[v])
		merge(x.x, x.y + K);
	if(l == r - 1)
		res[l] = ans;
	else
	{
		int m = (l + r) / 2;
		dfs(v * 2 + 1, l, m);
		dfs(v * 2 + 2, m, r);
	}
	while(cur != state) rollback();
	ans = last_ans;
}

int main()
{
	int q;
	scanf("%d", &q);
	map<pair<int, int>, int> last;
	for(int i = 0; i < q; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		pair<int, int> p = make_pair(x, y);
		if(last.count(p))
		{
			add(0, 0, q, last[p], i, p);
			last.erase(p);
		}
		else
			last[p] = i;
	}
	for(auto x : last)
		add(0, 0, q, x.y, q, x.x);
	init();
	dfs(0, 0, q);
	for(int i = 0; i < q; i++)
		printf("%I64d ", res[i]);
}

#include <bits/stdc++.h>

using namespace std;

typedef long long li;

#define x first
#define y second

const int N = 600043;

li d1[N];
li d2[N][2];
li dist_temp[N][2];
vector<pair<int, int> > g[N];
vector<int> qs[N];
int qq[N][2];
li ans[N];
int n;
int used[N];
int cnt[N];
int last[N];
int cc = 1;

void preprocess()
{
	set<pair<li, int> > q;
	for(int i = 0; i < n; i++)
		q.insert(make_pair(d1[i], i));
	while(!q.empty())
	{
		int k = q.begin()->second;
		q.erase(q.begin());
		for(auto e : g[k])
		{
			int to = e.first;
			li w = d2[e.second][0] + d2[e.second][1];
			if(d1[to] > w + d1[k])
			{
				q.erase(make_pair(d1[to], to));
				d1[to] = w + d1[k];
				q.insert(make_pair(d1[to], to));
			}
		}
	}
}

void dfs1(int x, int p = -1)
{
	if(used[x]) return;
	cnt[x] = 1;
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
		{
			dfs1(to, x);
			cnt[x] += cnt[to];
		}
	}
}

vector<int> cur_queries;
pair<int, int> c;
int S = 0;

void find_centroid(int x, int p = -1)
{
	if(used[x])	return;
	int mx = 0;
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
		{
			find_centroid(to, x);
			mx = max(mx, cnt[to]);
		}
	}
	if(p != -1)
		mx = max(mx, S - cnt[x]);
	c = min(c, make_pair(mx, x));
}	

void dfs2(int x, int p = -1, int e = -1)
{
	if(used[x]) return;
	if(p == -1)
	{
		dist_temp[x * 2][0] = dist_temp[x * 2 + 1][1] = 0ll;
		dist_temp[x * 2][1] = dist_temp[x * 2 + 1][0] = d1[x];
	}
	else
	{
		for(int k = 0; k < 2; k++)
		{
			li& D0 = dist_temp[x * 2][k];
			li& D1 = dist_temp[x * 2 + 1][k];
			D0 = dist_temp[p * 2][k] + d2[e][0];
			D1 = dist_temp[p * 2 + 1][k] + d2[e][1];
			D0 = min(D0, D1 + d1[x]);
			D1 = min(D1, D0 + d1[x]); 
		}
	}
	for(auto y : qs[x])
	{
		if(ans[y] != -1) continue;
		if(last[y] == cc)
			cur_queries.push_back(y);
		else
			last[y] = cc;
	}
	for(auto y : g[x])
	{
		int to = y.first;
		if(!used[to] && to != p)
			dfs2(to, x, y.second);
	}
}

void centroid(int v)
{
	if(used[v]) return;
	dfs1(v);
	S = cnt[v];
	c = make_pair(int(1e9), -1);
	find_centroid(v);
	int C = c.second;
	used[C] = 1;
	for(auto y : g[C])
		centroid(y.first);
	cc++;
	cur_queries.clear();
	used[C] = 0;
	dfs2(C);
	for(auto x : cur_queries)
	{
		int u = qq[x][0];
		int v = qq[x][1];
		ans[x] = min(dist_temp[u][0] + dist_temp[v][0], dist_temp[u][1] + dist_temp[v][1]);
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%I64d", &d1[i]);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		li w1, w2;
		scanf("%d %d %I64d %I64d", &x, &y, &w1, &w2);
		--x;
		--y;
		d2[i][0] = w1;
		d2[i][1] = w2;
		g[x].push_back(make_pair(y, i));
		g[y].push_back(make_pair(x, i));
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		scanf("%d", &qq[i][0]);
		scanf("%d", &qq[i][1]);
		--qq[i][0];
		--qq[i][1];
		qs[qq[i][0] / 2].push_back(i);
		qs[qq[i][1] / 2].push_back(i);
	}
	preprocess();
	for(int i = 0; i < q; i++)
		ans[i] = -1;
	centroid(0);
	for(int i = 0; i < q; i++)
		cout << ans[i] << endl;
}