for t in range(int(input())):
	a = sorted(list(map(int, input().split())))
	print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No')

for t in range(int(input())):
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    id = 0
    for i in range(n):
        if a[i] > a[id]:
            id = i
        t -= a[i]
        if t < 0:
            break

    if t >= 0:
        id = -1 
    print(id + 1)

for t in range(int(input())):
	n, m = map(int, input().split())
	a = [x - 1 for x in list(map(int, input().split()))]
	b = [x - 1 for x in list(map(int, input().split()))]
	pos = a[:]
	for i in range(n):
		pos[a[i]] = i
	
	lst = -1
	res = m
	for i in range(m):
		if pos[b[i]] > lst:
			res += 2 * (pos[b[i]] - i)
			lst = pos[b[i]]
	
	print(res)

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;
const int N = 1e6 + 7;

int n;
vector<int> a[N];
int cnt[N];
int inv[N];

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

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

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

int main() {
	scanf("%d", &n);
	forn(i, n) {
		int k;
		scanf("%d", &k);
		a[i].resize(k);
		forn(j, k) scanf("%d", &a[i][j]);
		forn(j, k) cnt[a[i][j]]++;
	}
	
	forn(i, N) inv[i] = binpow(i, MOD - 2);
	
	int ans = 0;
	forn(i, n) for (auto x : a[i])
		ans = add(ans, mul(mul(inv[n], inv[sz(a[i])]), mul(cnt[x], inv[n])));
			
	printf("%d\n", ans);
}

#include <bits/stdc++.h>

using namespace std;

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

typedef long long li;
typedef long double ld;

const int N = 55;
const li INF = 2e18;

int n;
li k;

li cycl[N], cnt[N];
bool used[N];
int ans[N];

li add(li x, li y) {
	return min(INF, x + y);
}

li mul(li x, li y) {
	ld t = ld(x) + y;
	if (t > INF) return INF;
	return x * y;
}

void solve() {
	cin >> n >> k;
	--k;

	cycl[0] = cycl[1] = 1;
	fore(i, 2, n + 1) 
		cycl[i] = mul(cycl[i - 1], i - 1);
		
	cnt[n] = 1;
	for (int i = n - 1; i >= 0; i--) {
		cnt[i] = 0;
		fore(val, i, n) {
			int len = (val - i) + 1;
			cnt[i] = add(cnt[i], mul(cnt[i + len], cycl[len - 1]));
		}
	}
	
	if (cnt[0] <= k) {
		cout << -1 << endl;
		return;
	}
	
	memset(used, 0, sizeof(used));
	memset(ans, -1, sizeof(ans));
	
	forn(i, n) {
		fore(val, i, n) {
			int len = (val - i) + 1;
			li cur = mul(cnt[i + len], cycl[len - 1]); 
			
			if (cur <= k)  {
				k -= cur;
				continue;	
			}
			
			ans[i] = val;
			used[val] = true;
			
			for (int j = i + 1; j < i + len; j++) {
				int lft = len - (j - i) - 1;
				fore(nval, i, val) if (!used[nval] && j != nval) {
					if (j != i + len - 1) {
						int tmp = ans[nval];
						while (tmp != -1 && tmp != j) 
							tmp = ans[tmp];
						if (tmp == j) continue;
					}
					
					li cur = mul(cnt[i + len], cycl[lft]); 
					if (cur <= k) {
						k -= cur;
						continue;	
					}
					
					ans[j] = nval;
					used[nval] = true;		
					break;
				}
			}
				
			i += len - 1;
			break;
		}
	}

	forn(i, n) cout << ans[i] + 1 << ' ';
	cout << endl;
}

int main() {
	int tc;
	cin >> tc;
	forn(i, tc) solve();
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 * 1000 + 11;
const int INF = 1e9;

int n, k, l;
string s;
int a[N];
pair<int, int> dp[N];

int calc(int mid) {
	for (int i = 0; i <= n; ++i) {
		dp[i] = make_pair(INF, INF);
	}
	dp[0] = make_pair(0, 0);
	for (int i = 0; i < n; ++i) {
		if (dp[i + 1] > make_pair(dp[i].first + a[i], dp[i].second)) {
			dp[i + 1] = make_pair(dp[i].first + a[i], dp[i].second);
		}
		if (dp[min(n, i + l)] > make_pair(dp[i].first + mid, dp[i].second + 1)) {
			dp[min(n, i + l)] = make_pair(dp[i].first + mid, dp[i].second + 1);
		}
	}
	return dp[n].second;
}

int solve() {
	int l = 0, r = n;
	int res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (calc(mid) > k) {
			l = mid + 1;
			res = mid;
		} else {
			r = mid - 1;
		}
	}
	if (calc(res) <= k) return 0;
	calc(res + 1);
	return dp[n].first - (res + 1) * 1ll * k;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k >> l >> s;
	for (int i = 0; i < n; ++i) {
		a[i] = islower(s[i]) > 0;
	}
	int ans = INF;
	ans = min(ans, solve());
	for (int i = 0; i < n; ++i) {
		a[i] = isupper(s[i]) > 0;
	}
	ans = min(ans, solve());
	cout << ans << endl;
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	int n = h.size();
	vector<int> cntp(26);
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, n){
		vector<int> cnth(26);
		for (int j = i; j < n; ++j){
			++cnth[h[j] - 'a'];
			if (cntp == cnth){
				puts("YES");
				return;
			}
		}
	}
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;
string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	vector<int> cntp(AL), cnt(AL);
	vector<bool> eq(AL);
	int sum = 0;
	
	auto chg = [&cntp, &cnt, &eq, &sum](int c, int val){
		sum -= eq[c];
		cnt[c] += val;
		eq[c] = (cntp[c] == cnt[c]);
		sum += eq[c];
	};
	
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, AL){
		eq[i] = (cnt[i] == cntp[i]);
		sum += eq[i];
	}
	
	int m = p.size();
	int n = h.size();
	forn(i, n){
		chg(h[i] - 'a', 1);
		if (i >= m) chg(h[i - m] - 'a', -1);
		if (sum == AL){
			puts("YES");
			return;
		}
	}
	
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t, a, b;

bool ok(int res, int d){
	long long sum = res * 1LL * (res + 1) / 2;
	if(sum < d) return false;
	return sum % 2 == d % 2;
}	

int main() {		
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b;
		int d = abs(a - b);
		if(d == 0){ 
			cout << "0\n";
			continue;
		}

		int res = 1;
		while(!ok(res, d)) ++res;
		cout << res << endl;
		
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<int> a;

bool read(){
	if (scanf("%d", &n) != 1)
		return false;
	a.resize(2 * n);
	forn(i, 2 * n)
		scanf("%d", &a[i]);
	return true;
}

void solve(){
	int cur = 0;
	map<int, int> difr;
	
	difr[0] = 0;
	cur = 0;
	for (int i = n; i < 2 * n; ++i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (!difr.count(cur))
			difr[cur] = i - (n - 1);
	}
	
	int ans = 2 * n;
	int dif = count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 2);
	
	cur = 0;
	for (int i = n - 1; i >= 0; --i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (difr.count(dif - cur))
			ans = min(ans, n - i + difr[dif - cur]);
	}
	if (difr.count(dif)){
		ans = min(ans, difr[dif]);
	}
	
	printf("%d\n", ans);
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	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 forn(i, n) for (int i = 0; i < int(n); i++)

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

const int N = 500010;

int n;
pt a[N];
vector<int> g[N];
bool used[N];

void dfs(int v, int p = -1) {
	used[v] = true;
	for (auto to : g[v]) if (to != p) {
		if (!used[to])
			dfs(to, v);
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
	
	vector<pt> evs;
	forn(i, n) {
		evs.pb(mp(a[i].x, i));
		evs.pb(mp(a[i].y, i));
	}
	
	sort(all(evs));
	
	int cnt = 0;
	set<pt> cur;
	for (auto it : evs) {
		if (cnt >= n) break;
		if (cur.count(it)) {
			cur.erase(it);
		} else {
			int i = it.y;
			int r = a[i].y;
			for (auto jt : cur) {
				if (jt.x > r) break;
				int j = jt.y;
				g[i].pb(j);
				g[j].pb(i);
				cnt++;
				if (cnt >= n) break;
			}
			cur.insert(mp(a[i].y, i));
		}
	}
	
	dfs(0);
	puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO");
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#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 pair<int, int> pt;

const int N = 500 * 1000 + 13;

int n;
vector<int> g[N], vs[N];
pt segs[N];

void dfs(int v, int p = -1) {
	int sum = 0;
	int bst = -1;
	for (auto to : g[v]) if (to != p) {
		dfs(to, v);
		sum += 2 * sz(vs[to]);
		if (bst == -1 || sz(vs[to]) > sz(vs[bst]))
			bst = to;
	}
	
	if (bst == -1) {
		vs[v].pb(v);
		segs[v] = mp(1, 2);
		return;
	}
	
	swap(vs[v], vs[bst]);
	int lst = segs[bst].y;
	
	sum -= 2 * sz(vs[v]);
	sum += 1;
	segs[bst].y += sum;
	
	for (auto to : g[v]) if (to != p && to != bst) {
		int add = lst - 1;
		for (auto u : vs[to]) {
			segs[u].x += add;
			segs[u].y += add;
			vs[v].pb(u);
		}
		lst = segs[to].y;
		sum -= 2 * sz(vs[to]);
		segs[to].y += sum;
		vs[to].clear();
	}
	
	vs[v].pb(v);
	segs[v] = mp(lst, segs[bst].y + 1);
}	

int main() {
	scanf("%d", &n);
	forn(i, n - 1) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		g[x].pb(y);
		g[y].pb(x);
	}
	
	dfs(0);
	
	for (int i = 0; i < n; i++)
		printf("%d %d\n", segs[i].x, segs[i].y);
	
	return 0;
}

1278F - Cards

Во-первых, я бы хотел поблагодарить Errichto за его прекрасную лекцию по математическому ожиданию: часть 1, часть 2. Эта задача была придумана после того, как я узнал идею подсчета квадрата математического ожидания через ожидаемое количество пар — и в разборе будет использована похожая идея.

Окей, теперь сам разбор. Назовем число $$$a$$$ хорошим, если $$$1 \le a \le n$$$, и $$$a$$$-е перемешивание колоды привело к тому, что на вершине колоды оказался джокер. $$$x$$$ из нашей задачи — это количество таких хороших чисел $$$a$$$. Мы можем представить $$$x^2$$$ как количество таких пар $$$(a_1, a_2)$$$, что каждый элемент пары — хорошее число; $$$x^3$$$ как количество подобных троек, и так далее — $$$x^k$$$ представим как количество кортежей из $$$k$$$ элементов $$$(a_1, a_2, \dots, a_k)$$$, в которых каждый элемент является хорошим числом.

Теперь представим математическое ожидание $$$x^k$$$ как ожидаемое количество таких кортежей, или же как сумму $$$P(t)$$$ по всем кортежам $$$t$$$, где $$$P(t)$$$ — вероятность того, что кортеж $$$t$$$ состоит только из хороших чисел. Как посчитать эту вероятность для $$$t$$$? Так как после каждого перемешивания джокер будет на вершине колоды с вероятностью $$$\frac{1}{m}$$$, $$$P(t)$$$ должно быть равно $$$\frac{1}{m^k}$$$ — но это верно только в том случае, когда все элементы в $$$t$$$ различны. Как обработать повторяющиеся элементы? Так как все вхождения одного и того же числа являются либо хорошими, либо плохими (и вероятность того, что они все хорошие, равна $$$\frac{1}{m}$$$), точной формулой для вычисления $$$P(t)$$$ будет $$$P(t) = \frac{1}{m^d}$$$, где $$$d$$$ — количество различных элементов в кортеже.

Теперь для каждого $$$d \in [1, k]$$$ надо посчитать количество кортежей из $$$k$$$ элементов, в которых ровно $$$d$$$ различных элементов. Сделаем это при помощи динамического программирования: $$$dp_{i, j}$$$ — количество кортежей размера $$$i$$$, в которых ровно $$$j$$$ различных элементов. Каждый переход в этой динамике — это добавление нового элемента; чтобы обработать переходы из $$$dp_{i, j}$$$, мы либо добавляем новый элемент в кортеж (его можно выбрать $$$n - j$$$ способами, и мы переходим в состояние $$$dp_{i + 1, j + 1}$$$), либо добавляем уже ранее встреченный элемент (его можно выбрать $$$j$$$ способами, и мы переходим в состояние $$$dp_{i + 1, j}$$$).

Сложность решения — $$$O(k^2 \log MOD)$$$ или $$$O(k^2 + \log MOD)$$$, в зависимости от реализации.

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5043;

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

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

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

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

int n, m, k;

int dp[N][N];

int main()
{
	cin >> n >> m >> k;
	dp[0][0] = 1;
	for(int i = 0; i < k; i++)
		for(int j = 0; j < k; j++)
		{
			dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
			dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], n - j));
		}
	int ans = 0;
	for(int i = 1; i <= k; i++)
		ans = add(ans, mul(dp[k][i], binpow(inv(m), i)));
	cout << ans << endl;
}

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

int c, sum;

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

inline void solve() {
	int d = sum / c;
	int rem = sum % c;
	cout << rem * (d + 1) * (d + 1) + (c - rem) * d * d << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	int n; cin >> n;
	while(n--) {
		read();
		solve();
	}
	return 0;
}

for t in range(int(input())):
	a, b = map(int, input().split())
	if a > b:
		a, b = b, a
	print ('YES' if ( ((a + b) % 3) == 0 and a * 2 >= b) else 'NO')

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

li a, b, k;

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

inline void solve() {
	li g = __gcd(a, b);
	a /= g;
	b /= g;
	if(a > b)
		swap(a, b);
	if((k - 1) * a + 1 < b)
		cout << "REBEL";
	else
		cout << "OBEY";
	cout << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
	}
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

typedef pair<int, int> pt;

#define x first
#define y second


int m, n, k, t;
vector<int> l, r, d, a;

bool can(int x)
{
	int mn = int(1e9);
	for (int i = 0; i < x; i++)
		mn = min(mn, a[i]);
	vector<pt> segm;
	for (int i = 0; i < k; i++)
		if (d[i] > mn)
			segm.push_back(make_pair(l[i], r[i]));
	int req_time = 0;
	sort(segm.begin(), segm.end());
	int lastr = 0;
	for (auto s : segm)
	{
		if (s.x <= lastr)
		{
			req_time += max(0, s.y - lastr);
			lastr = max(s.y, lastr);
		}
		else
		{
			req_time += s.y - s.x + 1;
			lastr = s.y;
		}
	}
	req_time = 2 * req_time + n + 1;
	return req_time <= t;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d %d %d %d", &m, &n, &k, &t);
	a.resize(m);
	for (int i = 0; i < m; i++)
		scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	l.resize(k);
	r.resize(k);
	d.resize(k);
	for (int i = 0; i < k; i++)
		scanf("%d %d %d", &l[i], &r[i], &d[i]);

	int lf = 0;
	int rg = m + 1;
	while (rg - lf > 1)
	{
		int mid = (lf + rg) / 2;
		if (can(mid))
			lf = mid;
		else
			rg = mid;
	}
	printf("%d\n", lf);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int LOGN = 20;
const int N = (1 << LOGN) + 99;
const long long INF = 1e18;

int n;
int a[N];
long long dp[LOGN+2][N];
int sum[100];

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

	if(a[pos] == -1) return res = 0;
	int rem = sum[cnt] - pos;

	res = INF;
	if(cnt < LOGN)
		res = calc(cnt + 1, pos + 1) + a[pos];
	if(rem > 0)		
		res = min(res, calc(cnt, pos + 1));

	return res;
}

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

	for(int i = 1, x = n / 2; i < 100; ++i, x /= 2)
		sum[i] = sum[i - 1] + x;
	
	reverse(a, a + n);
	memset(dp, -1, sizeof dp);
	printf("%lld", calc(0, 0));	
	return 0;
}                             	

#include<bits/stdc++.h>
using namespace std;
int n ;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7 ;
vector<int> E[maxn];
vector<int> in[maxn] , out[maxn];
int cm = 0;
int l[maxn] , dfn = 0 , dep[maxn];
int g[maxn];
int siz[maxn] , top[maxn] , h[maxn] , f[maxn];
///-----segment tree
struct seg
{
    int l , r;
    int sum , add ;
}Node[maxn * 4];

void build(int u,int l,int r)
{
    Node[u].l = l , Node[u].r = r;
    Node[u].sum = Node[u].add = 0;
    if(l == r) return ;
    build(u<<1 , l , (l + r >> 1));
    build(u<<1|1 , (l + r >>1) + 1 , r);
    return ;
}
void pd(int u)
{
    Node[u].sum = (1LL*Node[u].add*(Node[u].r - Node[u].l + 1) + Node[u].sum) % mod ;
    if(Node[u].l == Node[u].r) {
        Node[u].add = 0 ;return ;
    }
    (Node[u<<1].add += Node[u].add ) %= mod;
    (Node[u<<1|1].add += Node[u].add ) %= mod;
    Node[u].add = 0 ; return ;
}
void modify(int u,int l,int r,int v)
{
    if(Node[u].l == l && Node[u].r == r) {
        (Node[u].add += v ) %= mod;
        pd(u) ; return ;
        return ;
    }
    pd(u) ;
    if(Node[u<<1].r >= r) {modify(u<<1 , l , r , v) ; pd(u<<1|1);}
    else if(Node[u<<1|1].l <= l) {modify(u<<1|1 , l , r , v) ; pd(u<<1) ;}
    else {
        modify(u<<1 , l , Node[u<<1].r , v) ;
        modify(u<<1|1 , Node[u<<1|1].l , r , v);
    }
    Node[u].sum = (Node[u<<1].sum + Node[u<<1|1].sum) % mod;
    return ;
}
int query(int u,int l,int r)
{
    pd(u) ;
    if(Node[u].l == l && Node[u].r == r) return Node[u].sum ;
    if(Node[u<<1].r >= r) return query(u<<1 , l , r) ;
    else if(Node[u<<1|1].l <= l) return query(u<<1|1 , l , r);
    else return (query(u<<1 , l , Node[u<<1].r) + query(u<<1|1 , Node[u<<1|1].l , r)) % mod;
}
///---segment tree end
void dfs(int fa,int u,int d)
{
    f[u] = fa;
    dep[u] = d;siz[u] = 1;h[u] = -1;
    for(int i = 0;i < E[u].size();i++) {
        if(E[u][i] != fa) {
            dfs(u , E[u][i] , d + 1) ;siz[u] += siz[E[u][i]];
            if(h[u] == -1 || siz[E[u][i]] > siz[E[u][h[u]]]) h[u] = i;
        }
    }
    return ;
}
void dfs2(int fa,int u)
{
    l[u] = ++dfn;
    if(h[u] != -1) {
        top[E[u][h[u]]] = top[u] ;
        dfs2(u , E[u][h[u]]);
    }
    for(int i = 0;i < E[u].size();i++) {
        if(E[u][i] != fa && i != h[u]) {
            top[E[u][i]] = E[u][i] ;
            dfs2(u , E[u][i]) ;
        }
    }
    return ;
}
int fpow(int a,int b)
{
    int ans = 1;
    while(b) {
        if(b & 1) ans = (1LL * ans * a) % mod;
        a = (1LL * a * a) % mod ;b >>= 1;
    }
    return ans;
}
void add(int u,int v)
{
    while(u) {
        modify(1 , l[top[u]] , l[u] , v) ;
        u = f[top[u]] ;
    }
    return ;
}
int cal(int u)
{
    int ans = mod - query(1 , 1 , 1);
    while(u) {
        ans = (ans + query(1 , l[top[u]] , l[u])) % mod;
        u = f[top[u]] ;
    }
    return ans;
}
int main()
{
    scanf("%d",&n) ;
    int P = 1;
    for(int i = 1;i <= n;i++) {
        int l , r;scanf("%d%d",&l,&r) ;
        in[l].push_back(i) ;
        out[r + 1].push_back(i) ; cm = max(cm , r);
        g[i] = fpow(r - l + 1 , mod - 2) ;
        P = 1LL * P * (r - l + 1) % mod;
    }
    for(int i = 1;i < n;i++) {
        int u , v;scanf("%d%d",&u,&v) ;
        E[u].push_back(v) ; E[v].push_back(u) ;
    }
    dfs(0 , 1 , 0) ; top[1] = 1;
    dfs2(0 , 1) ;
    build(1 , 1 , n) ;
    int ans = 0 , cur = 0;
    int d1 = 0 , d2 = 0 , u , d3 = 0;
    for(int i = 1;i <= cm;i++) {
        for(int j = 0;j < out[i].size();j++) {
            u = out[i][j] ;
            d1 = (d1 - 1LL * dep[u] * g[u] % mod + mod) % mod;
            d2 = (d2 - g[u] + mod) % mod ;
            d3 = (d3 - 1LL*dep[u]*g[u] % mod * g[u] % mod + mod) % mod;
            add(u , mod - g[u]) ;
            cur = (cur - 1LL * g[u] * cal(u) % mod + mod) % mod;
        }
        for(int j = 0;j < in[i].size();j++) {
            u = in[i][j] ;
            d1 = (d1 + 1LL * dep[u] * g[u]) % mod;
            d2 = (d2 + g[u]) % mod;
            d3 = (d3 + 1LL*dep[u]*g[u]%mod*g[u]) % mod;
            cur = (cur + 1LL * g[u] * cal(u)) % mod;
            add(u , g[u]) ;
        }
        ans = (ans + 1LL * d1 * d2%mod - 2LL*cur - d3) % mod;
        ans = (ans + mod) % mod;
    }
    ans = 1LL * ans * P % mod;
    printf("%d\n",ans);
    return 0;
}

import kotlin.math.abs
fun main() {
    val q = readLine()!!.toInt()
    for (ct in 1..q) {
        val (n, x, a, b) = readLine()!!.split(' ').map { it.toInt() }
        println(minOf(n - 1, abs(a - b) + x))
    }
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int x, y;
	cin >> x >> y;
	
	if (x > 3) puts("YES");
	else if (x == 1) puts(y == 1 ? "YES" : "NO");
	else puts(y <= 3 ? "YES" : "NO");
}

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

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

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

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];
	return true;
}

inline void solve() {
	int ans = n + 5;
	vector<int> lst(n + 1, -1);
	for(int i = 0; i < n; i++) {
		if(lst[a[i]] != -1)
			ans = min(ans, i - lst[a[i]] + 1);
		lst[a[i]] = i;
	}
	if(ans > n)
		ans = -1;
	cout << ans << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

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

int t;
int n;
int a[N];
int m;
int p[N], s[N];
int bst[N];

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i <= n; ++i) bst[i] = 0;
		for(int i = 0; i < n; ++i)
			scanf("%d", a + i);
		scanf("%d", &m);
		for(int i = 0; i < m; ++i){
			scanf("%d %d", p + i, s + i);
			bst[s[i]] = max(bst[s[i]], p[i]);
		}
		for(int i = n - 1; i >= 0; --i)
			bst[i] = max(bst[i], bst[i + 1]);	
		

		int pos = 0;
		int res = 0;
		bool ok = true;
		while(pos < n){
			++res;
			int npos = pos;
			int mx = 0;
			while(true){
				mx = max(mx, a[npos]);
				if(mx > bst[npos - pos + 1]) break;
				++npos;
			}
	
			if(pos == npos){
				ok = false;
				break;
			}
			pos = npos;
		}

		if(!ok) res = -1;
		printf("%d\n", res);
	}

	return 0;
}                             	            	

#include <bits/stdc++.h>

using namespace std;

int main() 
{
	int k1, k2, k3;
	scanf("%d %d %d", &k1, &k2, &k3);
	int n = k1 + k2 + k3;
	vector<int> a(n);
	for(int i = 0; i < k1; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 0;
	}
	for(int i = 0; i < k2; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 1;
	}
	for(int i = 0; i < k3; i++)
	{
		int x;
		scanf("%d", &x);
		a[x - 1] = 2;
	}
	
	int ans = 0;
	int bestp = 0;
	for(int i = 0; i < n; i++)
		if(a[i] != 2)
			ans++;
	vector<int> cntl(3);
	vector<int> cntr(3);
	for(int i = 0; i < n; i++)
		cntr[a[i]]++;
	for(int i = 0; i < n; i++)
	{
		cntl[a[i]]++;
		cntr[a[i]]--;
		bestp = max(bestp, cntl[0] - cntl[1]);
		int curans = cntr[0] + cntr[1] + cntl[2] + cntl[0] - bestp;
		ans = min(ans, curans);
	}
	
	cout << ans << endl;
}                    	

#include<bits/stdc++.h>

using namespace std;

typedef long long li;
const int N = 143;
const int K = 15;
const int V = 5000000;

int n;
li a[N];
int lst[V];
map<int, int> nxt[V];
int t = 1;
li a1[N];
li a2[N];

int get_nxt(int v, int x)
{
	if(!nxt[v].count(x))
		nxt[v][x] = t++;
	return nxt[v][x];
}

void add(vector<int> diff, int x)
{
	int v = 0;
	for(auto i : diff)
		v = get_nxt(v, i);
	lst[v] = x;
}

int try_find(vector<int> diff)
{
	int v = 0;
	for(auto i : diff)
	{
		if(!nxt[v].count(i))
			return -1;
		v = nxt[v][i];
	}
	return lst[v];
}

vector<int> get_diff(li arr[N], int x)
{
	vector<int> cnt(n);
	for(int i = 0; i < n; i++)
		cnt[i] = __builtin_popcountll(arr[i] ^ x);
	vector<int> diff(n - 1);
	for(int i = 0; i + 1 < n; i++)
		diff[i] = cnt[i + 1] - cnt[0];
	return diff;
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	for(int i = 0; i < n; i++)
	{
		a1[i] = (a[i] >> K);
		a2[i] = a[i] ^ (a1[i] << K);
	}
	for(int i = 0; i < (1 << K); i++)
	{
		vector<int> d = get_diff(a1, i);
		add(d, i);
	}
	for(int i = 0; i < (1 << K); i++)
	{
		vector<int> d = get_diff(a2, i);
		for(int j = 0; j + 1 < n; j++)
			d[j] *= -1;
		int x = try_find(d);
		if(x != -1)
		{
			li res = (li(x) << K) ^ i;
			cout << res << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

const int LOGN = 18;
const int MOD = 998244353;
int g = 3;

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

vector<int> w[LOGN], rv;
bool precalced = false;

void precalc() {
	if(precalced)
		return;
	precalced = true;
	
    int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    fore(st, 0, LOGN) {
        w[st].assign(1 << st, 1);

        int bw = binPow(wb, 1 << (LOGN - st - 1));
        int cw = 1;

        fore(k, 0, (1 << st)) {
            w[st][k] = cw;
            cw = mul(cw, bw);
        }
    }
    
    rv.assign(1 << LOGN, 0);
    fore(i, 1, sz(rv))
		rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}

const int MX = (1 << LOGN) + 3;

inline void fft(int a[MX], int n, bool inverse) {
	precalc();
	
    int ln = __builtin_ctz(n);
    assert((1 << ln) < MX);
    assert((1 << ln) == n);

    fore(i, 0, n) {
        int ni = rv[i] >> (LOGN - ln);
        if(i < ni) swap(a[i], a[ni]);
    }

    for(int st = 0; (1 << st) < n; st++) {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) {
        	fore(pos, k, k + len) {
                int l = a[pos];
                int r = mul(a[pos + len], w[st][pos - k]);

                a[pos] = norm(l + r);
                a[pos + len] = norm(l - r);
            }
        }
    }
    
    if(inverse) {
        int in = inv(n);
        fore(i, 0, n)
            a[i] = mul(a[i], in);
        reverse(a + 1, a + n);
    }
}

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

vector<int> multiply(const vector<int> &a, const vector<int> &b) {
	int ln = 1;
	while(ln < (sz(a) + sz(b)))
		ln <<= 1;
	
	fore(i, 0, ln)
		aa[i] = (i < sz(a) ? a[i] : 0);
	fore(i, 0, ln)
		bb[i] = (i < sz(b) ? b[i] : 0);
		
	fft(aa, ln, false);
	fft(bb, ln, false);
	
	fore(i, 0, ln)
		cc[i] = mul(aa[i], bb[i]);
	fft(cc, ln, true);
	
	vector<int> ans(cc, cc + ln);
	while(ans.back() == 0)
		ans.pop_back();
	return ans;
}

int n;
vector<int> ps;

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

struct cmp {
	bool operator ()(const vector<int> &a, const vector<int> &b) {
		return sz(a) < sz(b);
	}
};

inline void solve() {
	map<int, int> cnt;
	fore (i, 0, n)
		cnt[ps[i]]++;
	
	multiset< vector<int>, cmp > polys;
	for (auto p : cnt)
		polys.emplace(p.second + 1, 1);
	
	while (sz(polys) > 1) {
		auto it2 = polys.begin();
		auto it1 = it2++;
		polys.insert(multiply(*it1, *it2));
		
		polys.erase(it1);
		polys.erase(it2);
	}

	auto poly = *polys.begin();
//	cerr << '[';
//	fore(i, 0, sz(poly)) {
//		if(i) cerr << ", ";
//		cerr << poly[i];
//	}
//	cerr << ']' << endl;

	cout << poly[n / 2] << 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;

bool ans[26];

void solve() {
	string s;
	cin >> s;
	
	memset(ans, 0, sizeof(ans));
	
	for (int i = 0; i < s.size(); i++) {
		int j = i;
		while (j + 1 < s.size() && s[j + 1] == s[i])
			j++;
		if ((j - i) % 2 == 0)
			ans[s[i] - 'a'] = true;
		i = j;
	}
	
	for (int i = 0; i < 26; i++) if (ans[i])
		cout << char('a' + i);
	cout << endl;
}

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

fun main() {
    val q = readLine()!!.toInt()
    for (ct in 1..q) {
        val n = readLine()!!.toInt()
        var (odd, evenGood, evenBad) = listOf(0, 0, 0)
        for (i in 1..n) {
            val s = readLine()!!
            when {
                s.length % 2 == 1 -> odd++
                s.count { it == '0' } % 2 == 0 -> evenGood++
                else -> evenBad++
            }
        }
        println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0)
    }
}

#include <bits/stdc++.h>

using namespace std;

int t;
string a;

int main() {	
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a;
		string s[2];
		for(auto x : a)
			s[int(x - '0') & 1] += x;
		
		reverse(s[0].begin(), s[0].end());
		reverse(s[1].begin(), s[1].end());

		string res = "";
		while(!(s[0].empty() && s[1].empty())){
			if(s[0].empty()){
				res += s[1].back();
				s[1].pop_back();
				continue;
			}
			if(s[1].empty()){
				res += s[0].back();
				s[0].pop_back();
				continue;
			}

			if(s[0].back() < s[1].back()){
				res += s[0].back();
				s[0].pop_back();
			}
			else{
				res += s[1].back();
				s[1].pop_back();
			}
		}

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

#include <bits/stdc++.h>

using namespace std;

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

int t;
int n;
long long s;
pair<int, int> p[N];

bool ok(int mid){
	long long sum = 0;
	int cnt = 0;
	vector <int> v;
	for(int i = 0; i < n; ++i){
		if(p[i].second < mid)
			sum += p[i].first;
		else if(p[i].first >= mid){
			sum += p[i].first;
			++cnt;
		}
		else
			v.push_back(p[i].first);
	}

	assert(is_sorted(v.begin(), v.end()));
	
	int need = max(0, (n + 1) / 2 - cnt);
	if(need > v.size()) return false;
	for(int i = 0; i < v.size(); ++i){
		if(i < v.size() - need)
			sum += v[i];
		else
			sum += mid;
	}

	return sum <= s;
}

int main() {	
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d %lld", &n, &s);
		for(int i = 0; i < n; ++i)
			scanf("%d %d", &p[i].first, &p[i].second);
		
		sort(p, p + n);
		int lf = 1, rg = INF; ///WA -> 10^9
		while(rg - lf > 1){
			int mid = (lf + rg) / 2;
			if(ok(mid)) lf = mid;
			else rg = mid;
		}
		
		printf("%d\n", lf);
	}
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

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

int t, n;
vector <int> v[N];

int main() {	
	int t;
	scanf("%d", &t);
	for(int tc = 0; tc < t; ++tc){
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
			v[i].clear();
		for(int i = 0; i < n; ++i){
			int x, s;
			scanf("%d %d", &x, &s);
			v[x].push_back(s);
		}		
		
		multiset <int > q;
		long long res = 0;
		int pref = n;
		int cnt = 0;
		for(int i = n - 1; i >= 0; --i){
			pref -= v[i].size();
			int need = i - pref;
			for(auto x : v[i]) q.insert(x);

			while(cnt < need){
				++cnt;
				res += *q.begin();				
				q.erase(q.begin());
			}
		}		

        	printf("%lld\n", res);
        }
	return 0;
}                             	

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

inline int binPow(int a, int k) 
{
	int ans = 1;
	while(k > 0) 
	{
		if(k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

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

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

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

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

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

inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 
{
	int n = 1, ln = 0;
	while(n < (sza + szb))
		n <<= 1, ln++;
	for(int i = 0; i < n; i++)
		aa[i] = (i < sza ? a[i] : 0);
	for(int i = 0; i < n; i++)
		bb[i] = (i < szb ? b[i] : 0);
		
	fft(aa, n, ln, false);
	fft(bb, n, ln, false);
	
	for(int i = 0; i < n; i++)
		cc[i] = mul(aa[i], bb[i]);
		
	fft(cc, n, ln, true);
	
	szc = n;
	for(int i = 0; i < n; i++)
		c[i] = cc[i];
}

vector<int> T[N];

int a[N];
int b[N];
int n, k;
int ans[N];
int Q[N];
int fact[N];
int rfact[N];

int auxa[N];
int auxb[N];
int auxc[N];

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

vector<int> newtonExp(int a, int b, int p)
{
	vector<int> res(p + 1);
	for(int i = 0; i <= p; i++)
		res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i)));
	return res;
}

int main()
{
	precalc();
	fact[0] = 1;
	for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
	for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]);
	
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	for(int i = 0; i < k; i++) scanf("%d", &b[i]);
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++) scanf("%d", &Q[i]);
	
	map<int, int> cnt;
	for(int i = 0; i < n; i++)
		cnt[a[i]]++;
	
	for(int i = 0; i < k; i++)
	{
		int redL = b[i];
		int cnt1 = 0;
		int cnt2 = 0;
		for(auto x : cnt)
		{
			if(x.first >= redL) 
				break;
			if(x.second == 1)
				cnt1++;
			else
				cnt2++;
		}
		memset(auxa, 0, sizeof auxa);
		memset(auxb, 0, sizeof auxb);
		memset(auxc, 0, sizeof auxc);
		vector<int> p1 = newtonExp(2, 1, cnt1);
		vector<int> p2 = newtonExp(1, 1, cnt2 * 2);
		int sa = p1.size();
		int sb = p2.size();
		int sc;
		for(int j = 0; j < sa; j++)
			auxa[j] = p1[j];
		for(int j = 0; j < sb; j++)
			auxb[j] = p2[j];
		multiply(auxa, sa, auxb, sb, auxc, sc);
		for(int j = 0; j < q; j++)
		{
			int cntW = Q[j] / 2 - redL - 1;
			if(cntW >= 0 && cntW < sc)
				ans[j] = norm(ans[j] + auxc[cntW]);
		}
	}
	
	for(int i = 0; i < q; i++)
		printf("%d\n", ans[i]);
}

t = int(input())

for i in range(t):
	x, y = map(int, input().split())
	if(x - y > 1):
		print('YES')
	else:
		print('NO')

#include <bits/stdc++.h>

using namespace std;

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

const int N = 100 * 1000 + 13;

int n, r;
int a[N];

void solve() {
	scanf("%d%d", &n, &r);
	forn(i, n) scanf("%d", &a[i]);
	
	sort(a, a + n);
	n = unique(a, a + n) - a;
	
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) 
		ans += (a[i] - ans * r > 0);

	printf("%d\n", ans);
}

int main() {
	int q;
	scanf("%d", &q);
	forn(i, q) solve();
}

#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

const int INF = int(1e9);

int h, n;
vector<int> p;

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

inline void solve() {
	int ans = 0;
	
	int lf = 0;
	fore(i, 0, n) {
		if (i > 0 && p[i - 1] > p[i] + 1) {
			if (lf > 0)
				ans += (i - lf) & 1;
			else
				ans += 1 - ((i - lf) & 1);
			lf = i;
		}
	}
	if (p[n - 1] > 1) {
		if (lf != 0)
			ans += (n - lf) & 1;
		else
			ans += 1 - ((n - lf) & 1);
	}
	
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#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();
	}
	return 0;
}

n = int(input())
s = input()
res = n * (n - 1) // 2

for x in range(2):
	cur = 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			cur += 1
		else:
			res -= cur - x
			cur = 1
	s = s[::-1]

print(res) 

#include <bits/stdc++.h>

using namespace std;

void upd(int &a, int b){
	a = min(a, b);
}

const int N = 20;
const int M = (1 << N) + 55;
const int INF = int(1e9) + 100;

int a, n;
string s;
int cnt[N][N];
int d[M][N];
int dp[M];
int cntBit[M];
int minBit[M];

int main() {	
	cin >> n >> a >> s;
	
	int B = (1 << a) - 1;
	for(int i = 1; i < s.size(); ++i){
		++cnt[s[i] - 'a'][s[i - 1] - 'a'];
		++cnt[s[i - 1] - 'a'][s[i] - 'a'];
	}
	for(int i = 0; i < M; ++i)
		dp[i] = INF;
	dp[0] = 0;
	for(int msk = 1; msk < M; ++msk){
		cntBit[msk] = 1 + cntBit[msk & (msk - 1)];
		for(int i = 0; i < N; ++i) if((msk >> i) & 1){
			minBit[msk] = i;
			break;
		}
	}
	for(int msk = 1; msk < M; ++msk)
		for(int i = 0; i < a; ++i){
			int b = minBit[msk];
			d[msk][i] = d[msk ^ (1 << b)][i] + cnt[i][b];		
		}

	for(int msk = 0; msk < (1 << a); ++msk){
		for(int i = 0; i < a; ++i){
			if((msk >> i) & 1) continue;
			//i -> x
			int pos = cntBit[msk];
			int nmsk = msk | (1 << i);
			upd(dp[nmsk], dp[msk] + pos * (d[msk][i] - d[B ^ nmsk][i]));
		}
	}	

	cout << dp[B] << endl;
	return 0;
} 

#include <bits/stdc++.h>

using namespace std;

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

int n;
vector <int> g[N];
int d[N];
int dp[N][2];

void dfs(int v, int p){
	vector <int> d1;
	dp[v][1] = d[v] - 1;
	for(auto to : g[v]){
		if(to == p) continue;
		dfs(to, v);
		dp[v][0] = max(dp[v][0], dp[to][0]);
		if(g[to].size() > 1){
			d1.push_back(dp[to][1]);
			dp[v][1] = max(dp[v][1], d[v] + dp[to][1] - 1);	
		}
	}

	sort(d1.rbegin(), d1.rend());
	int x = d[v] + 1;
	for(int i = 0; i < 2; ++i)
		if(i < d1.size())
			x += d1[i];
    dp[v][0] = max(dp[v][0], x);
}

int main() {	
    int q;
    scanf("%d", &q);
    for(int qc = 0; qc < q; ++qc){
    	scanf("%d", &n);
    	for(int i = 0; i < n; ++i){
    	    g[i].clear();
    	    d[i] = 0;
    	    dp[i][0] = dp[i][1] = 0;
    	}
    	for(int i = 0; i < n - 1; ++i){
    		int u, v;
    		scanf("%d %d", &u, &v);
    		--u, --v;
    		g[u].push_back(v), g[v].push_back(u);
    	}
    
        if(n <= 2){
            printf("%d\n", n);
            continue;
        }
        
    	for(int v = 0; v < n; ++v){
    		//d[v] = 1;
    		//for(auto to : g[v])	
    		//	d[v] += g[to].size() == 1;
    		d[v] = g[v].size();
    	}
        
        int r = -1;
        for(int v = 0; v < n; ++v)
            if(g[v].size() != 1)
                r = v;
                
    	dfs(r, r);
    	printf("%d\n", dp[r][0]);
    }
	return 0;
}                             	

#include <bits/stdc++.h>

using namespace std;

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

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

const int N = 500 * 1000 + 13;

int n, m, c, c0;
pair<int, pt> a[N];

li solve() {
	scanf("%d%d%d%d", &n, &m, &c, &c0);
	forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].y.x, &a[i].y.y);
	a[n++] = mp(m, mp(0, 0));
	sort(a, a + n);

	int sum = c0;
	map<int, int> q;
	q[0] = c0;
	
	li ans = 0;
	forn(i, n) {
		int x = a[i].x;
		int cnt = a[i].y.x;
		int cost = a[i].y.y;
	
		int dist = x - (i ? a[i - 1].x : 0);
		while (!q.empty() && dist > 0) {
			int can = min(q.begin()->y, dist);
			ans += q.begin()->x * 1ll * can;
			sum -= can;
			dist -= can;
			q.begin()->y -= can;
			if (q.begin()->y == 0) q.erase(q.begin());
		}
		
		if (dist > 0) 
			return -1;
		
		int add = min(c - sum, cnt);
		sum += add;
		
		while (add < cnt && !q.empty() && q.rbegin()->x > cost) {
			if (cnt - add >= q.rbegin()->y) {
				add += q.rbegin()->y;
				q.erase(--q.end());
			} else {
				q.rbegin()->y -= cnt - add;
				add = cnt;
			}
		}
		
		q[cost] += add;
	}
	
	return ans;
}

int main() {
	int q;
	scanf("%d", &q);
	forn(i, q) printf("%lld\n", solve());
}

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

// awoo~

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

// awoo~

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