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

#include <bits/stdc++.h>

using namespace std;

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

void solve() {
	string s;
	cin >> s;
	vector<int> a;
	forn(i, sz(s)) if (s[i] == '1') {
		int j = i;
		while (j + 1 < sz(s) && s[j + 1] == '1')
			++j;
		a.push_back(j - i + 1);
		i = j;
	}
	sort(a.rbegin(), a.rend());
	int ans = 0;
	for (int i = 0; i < sz(a); i += 2)
		ans += a[i];
	cout << ans << endl;
}

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

for _ in range(int(input())):
    n = int(input())
    a = input()
    d = {0 : 1}
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        if x not in d:
            d[x] = 0
        d[x] += 1
        res += d[x] - 1
        
    print(res)

n = [int(x) for x in input().split()]
a = []
for i in range(3):
	a.append([int(x) for x in input().split()])
	a[i].sort(reverse=True)

dp = [[[0 for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)]
ans = 0
for i in range(n[0] + 1):
	for j in range(n[1] + 1):
		for k in range(n[2] + 1):
			if i < n[0] and j < n[1]:
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + a[0][i] * a[1][j])
			if i < n[0] and k < n[2]:
				dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + a[0][i] * a[2][k])
			if j < n[1] and k < n[2]:
				dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + a[1][j] * a[2][k])
			ans = max(ans, dp[i][j][k])

print(ans)

#include <bits/stdc++.h>

using namespace std;

const int N = int(1e5) + 9;

int n;
set <int> sDouble;
long long sum[2];
set <int> s[2];
int cntDouble[2];

// 0: 0 -> 1
// 1: 1 -> 0
void upd(int id) {
    assert(s[id].size() > 0);
    int x = *s[id].rbegin();
    if (id == 1) x = *s[id].begin();
    bool d = sDouble.count(x);
    
    sum[id] -= x, sum[!id] += x;
    s[id].erase(x), s[!id].insert(x);
    cntDouble[id] -= d, cntDouble[!id] += d;
}


int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int tp, x;
        cin >> tp >> x;// tp = 1 if double
        
        if (x > 0) {
            sum[0] += x;
            s[0].insert(x);
            cntDouble[0] += tp;
            if (tp) sDouble.insert(x);
        } else {
            x = -x;
            int id = 0;
            if (s[1].count(x)) id = 1;
            else assert(s[0].count(x));
            
            sum[id] -= x;
            s[id].erase(x);
            cntDouble[id] -= tp;
            if (tp) { 
                assert(sDouble.count(x));
                sDouble.erase(x);
            }
        }
        
        int sumDouble = cntDouble[0] + cntDouble[1];
        while (s[1].size() < sumDouble) upd(0);
        while (s[1].size() > sumDouble) upd(1);
        while (s[1].size() > 0 && s[0].size() > 0 && *s[0].rbegin() > *s[1].begin()) {
            upd(0);
            upd(1);
        }
        assert(s[1].size() == sumDouble);
        
        long long res = sum[0] + sum[1] * 2;
        if (cntDouble[1] == sumDouble && sumDouble > 0) {
            res -= *s[1].begin();
            if (s[0].size() > 0) res += *s[0].rbegin();
        }
        cout << res << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

int n;
string s;
vector <int> p[2][N];
int nxt[2][N];
int ptr[2];
char buf[N];

int main(){
    cin >> n >> s;
    
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] != '0') nxt[0][i] = 1 + nxt[0][i + 1];
        if (s[i] != '1') nxt[1][i] = 1 + nxt[1][i + 1];
    }
    
    for (int b = 0; b <= 1; ++b) {
        int l = 0;
        while (l < n) {
            if (s[l] == char('0' + b)) {
                ++l;
                continue;
            }
            int r = l + 1;
            while (r < n && s[r] != char('0' + b)) ++r;
            for (int len = 1; len <= r - l; ++len)
                p[b][len].push_back(l);
            l = r;
        }
    }

    for (int len = 1; len <= n; ++len) {
        int pos = 0, res = 0;
        ptr[0] = ptr[1] = 0;
        
        while (pos < n) {
            int npos = INF;
            for (int b = 0; b <= 1; ++b) {
                if (nxt[b][pos] >= len) 
                    npos = min(npos, pos + len);
                while (ptr[b] < p[b][len].size() && pos > p[b][len][ ptr[b] ]) 
                    ++ptr[b];
                if (ptr[b] < p[b][len].size()) 
                    npos = min(npos, p[b][len][ ptr[b] ] + len);
            }
            if (npos != INF) 
                ++res;
            pos = npos;
        }
        
        cout << res << ' ';
    }
    cout << endl;
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

const int LOGN = 20;
const int N = (1 << LOGN);
const int K = 200043;
const int M = 1000043;

typedef double ld;
typedef long long li;

const ld PI = acos(-1.0);

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

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

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

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

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

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

void precalc() 
{
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, comp());
        for(int k = 0; k < (1 << st); k++) 
        {
            double ang = PI / (1 << st) * k;
            w[st][k] = comp(cos(ang), sin(ang));
        }
        
        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(comp a[N], int n, int ln, bool inv) 
{
    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++) 
            {
                comp l = a[pos];
                comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
                
                a[pos] = l + r;
                a[pos + len] = l - r;
            }
        }
    }
    
    if(inv) for(int i = 0; i < n; i++)
        a[i] = a[i] / n;
}

comp aa[N];
comp bb[N];
comp cc[N];

inline void multiply(comp a[N], int sza, comp b[N], int szb, comp 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] : comp());
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : comp());
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = aa[i] * bb[i];
        
    fft(cc, n, ln, true);
    
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
}

comp a[N];
comp b[N];
comp c[N];
int used[M];
int dp[M];

int main()
{
    precalc();
    int n, x, y;
    for(int i = 0; i < M; i++)
        dp[i] = -1;
    scanf("%d %d %d", &n, &x, &y);
    vector<int> A(n + 1);
    for(int i = 0; i <= n; i++)
        scanf("%d", &A[i]);
    for(int i = 0; i <= n; i++)
    {
        a[A[i]] = comp(1.0, 0.0);
        b[K - A[i]] = comp(1.0, 0.0);
    }
    int s = 0;
    multiply(a, K + 1, b, K + 1, c, s);
    for(int i = K + 1; i < s; i++)
        if(c[i].x > 0.5)
            used[(i - K + y) * 2] = 1;
    for(int i = 1; i < M; i++)
    {
        if(!used[i]) continue;
        for(int j = i; j < M; j += i)
            dp[j] = max(dp[j], i);
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        int l;
        scanf("%d", &l);
        printf("%d ", dp[l]);
    }
}

t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    if l * 2 > r:
        print(-1, -1)
    else:
        print(l, l * 2)

for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for t in range(z + 1):
		pos = k - 2 * t
		if pos < 0:
			continue
		mx = 0
		s = 0
		for i in range(pos + 1):
			if i < n - 1:
				mx = max(mx, a[i] + a[i + 1])
			s += a[i]
		ans = max(ans, s + mx * t)
	print(ans)

for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for i in range(k + 1):
		if i < n - 1:
			mx = max(mx, a[i] + a[i + 1])
		s += a[i]
		if i % 2 == k % 2:
			tmp = (k - i) // 2
			if tmp <= z:
				ans = max(ans, s + mx * tmp)
	print(ans)

#include <bits/stdc++.h>

using namespace std;

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

int solve(const string& s, int x, int y) {
	int res = 0;
	for (auto c : s) if (c - '0' == x) {
		++res;
		swap(x, y);
	}
	if (x != y && res % 2 == 1)
		--res;
	return res;
}

void solve() {
	string s;
	cin >> s;
	int ans = 0;
	forn(x, 10) forn(y, 10)
		ans = max(ans, solve(s, x, y));
	cout << sz(s) - ans << endl;
}

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

import kotlin.math.*

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

        var ans = 1e18.toLong()
        if (max(l1, l2) <= min(r1, r2)) {
            val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2)))
            val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2))
            ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2
        } else {
            val invest = max(l1, l2) - min(r1, r2)
            for (cntInv in 1..n) {
                var curAns = invest * cntInv
                val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv
                curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2
                ans = min(ans, curAns)
            }
        }
        println(ans)
    }
}

fun gcd(a: Long, b: Long): Long {
	if (a == 0L) return b
	return gcd(b % a, a)
}

fun main() {
	repeat(readLine()!!.toInt()) {
		val (m, d, w) = readLine()!!.split(' ').map { it.toLong() }
		val w2 = w / gcd(d - 1, w)
		val mn = minOf(m, d)
		var cnt = mn / w2
		println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2)
	}
}

#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 forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int N = 200 * 1000;

int n;
int l[N], r[N], t[N];
set<pt> st[2];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i];
	
	vector<pair<int, pt>> ev;
	forn(i, n) {
		ev.pb(mp(l[i], mp(0, i)));
		ev.pb(mp(r[i], mp(1, i)));
	}

	sort(all(ev));
	
	int ans = 0;
	for (auto it : ev) {
		int i = it.y.y;
		if (it.y.x) {
			int j = t[i];
			int k = j ^ 1;
			if (st[j].count(mp(r[i], i)) && !st[k].empty()) {
				++ans;
				st[k].erase(st[k].begin());
			}
			if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i));
		} else {
			st[t[i]].insert(mp(r[i], i));
		}
	}
	
	printf("%d\n", n - ans);
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#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)

typedef pair<int, int> pt;

const int INF = 1e9;
const int N = 200 * 1000;

int n;
vector<pt> a[2];

struct segtree {
	int n;
	vector<int> t, ps;
	segtree(int n) : n(n) {
		t.resize(4 * n, -INF);
		ps.resize(4 * n, 0);
	}
	
	void push(int v, int l, int r) {
		if (l + 1 != r) {
			ps[v * 2 + 1] += ps[v];
			ps[v * 2 + 2] += ps[v];
		}
		t[v] += ps[v];
		ps[v] = 0;
	}
	
	void upd(int v, int l, int r, int pos, int val) {
		push(v, l, r);
		if (l + 1 == r) {
			t[v] = val;
			return;
		}
		int m = (l + r) >> 1;
		if (pos < m) upd(v * 2 + 1, l, m, pos, val);
		else upd(v * 2 + 2, m, r, pos, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void add(int v, int l, int r, int L, int R, int val) {
		push(v, l, r);
		if (L >= R) return;
		if (l == L && r == R) {
			ps[v] += val;
			push(v, l, r);
			return;
		}
		int m = (l + r) >> 1;
		add(v * 2 + 1, l, m, L, min(m, R), val);
		add(v * 2 + 2, m, r, max(m, L), R, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	int get(int v, int l, int r, int L, int R) {
		push(v, l, r);
		if (L >= R) return -INF;
		if (l == L && r == R) 
			return t[v];
		int m = (l + r) >> 1;
		int r1 = get(v * 2 + 1, l, m, L, min(m, R));
		int r2 = get(v * 2 + 2, m, r, max(m, L), R);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
		return max(r1, r2);
	}
	
	void upd(int pos, int val) {
		return upd(0, 0, n, pos, val);
	}
	
	void add(int l, int r, int val) {
		return add(0, 0, n, l, r, val);
	}
	
	int get(int l, int r) {
		return get(0, 0, n, l, r);
	}
};

int main() {
	scanf("%d", &n);
	forn(i, n) {
		int l, r, t;
		scanf("%d%d%d", &l, &r, &t);
		a[t - 1].pb(mp(r, l));
	}
	
	forn(i, 2) sort(all(a[i]), [](pt a, pt b) {
		if (a.x == b.x) return a.y > b.y;
		return a.x < b.x;
	});
	
	segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1);
	t1.upd(0, 0);
	t2.upd(0, 0);
		
	int ans = 0;
	for (int i = 0, j = 0; i + j < n; ) {
		if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) {
			int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1; 
			int cur = t2.get(0, pos) + 1;
			ans = max(ans, cur);
			t1.upd(i + 1, cur);
			t2.add(0, pos, 1);
			++i;
		} else {
			int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1; 
			int cur = t1.get(0, pos) + 1;
			ans = max(ans, cur);
			t2.upd(j + 1, cur);
			t1.add(0, pos, 1);
			++j;
		}
	}
	
	printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 300043;

bool is_bridge[N];
int w[N];
int c[N];
int v[N];
vector<pair<int, int> > g[N];

vector<pair<int, int> > g2[N];
int comp[N];
li sum[N];
li dp[N];
int cnt[N];
int fup[N];
int tin[N];
int T = 0;
li ans[N];
int v1[N], v2[N];

int n, m, k;

int dfs1(int x, int e)
{
	tin[x] = T++;
	fup[x] = tin[x];
	for(auto p : g[x])
	{
		int y = p.first;
		int i = p.second;
		if(i == e)
			continue;
		if(tin[y] != -1)
			fup[x] = min(fup[x], tin[y]);
		else
		{
			fup[x] = min(fup[x], dfs1(y, i));
			if(fup[y] > tin[x])
				is_bridge[i] = true;
		}
	}
	return fup[x];
}

void dfs2(int x, int cc)
{
	if(comp[x] != -1)
		return;
	comp[x] = cc;
	cnt[cc] += v[x];
	sum[cc] += c[x];
	for(auto y : g[x])
		if(!is_bridge[y.second])
			dfs2(y.first, cc);
}

void process_edge(int x, int y, int m, int weight)
{
	li add_dp = dp[y];
	if(cnt[y] > 0 && cnt[y] < k)
		add_dp = max(0ll, add_dp - weight);
	
	cnt[x] += m * cnt[y];
	dp[x] += m * add_dp;
}

void link(int x, int y, int weight)
{
	process_edge(x, y, 1, weight);
}

void cut(int x, int y, int weight)
{
	process_edge(x, y, -1, weight);
}

void dfs3(int x, int p)
{
    dp[x] = sum[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		dfs3(y, x);
		link(x, y, w[i]);
	}
}

void dfs4(int x, int p)
{
	ans[x] = dp[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		cut(x, y, w[i]);
		link(y, x, w[i]);
		dfs4(y, x);
		cut(y, x, w[i]);
		link(x, y, w[i]);
	}
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int  i = 0; i < k; i++)
	{
		int x;
		scanf("%d", &x);
		--x;
		v[x] = 1;
	}
	for(int i = 0; i < n; i++)
		scanf("%d", &c[i]);
	for(int i = 0; i < m; i++)
		scanf("%d", &w[i]);
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d", &v1[i], &v2[i]);
		--v1[i];
		--v2[i];
		g[v1[i]].push_back(make_pair(v2[i], i));
		g[v2[i]].push_back(make_pair(v1[i], i));
	}
	
	for(int i = 0; i < n; i++)
	{
		tin[i] = -1;
		comp[i] = -1;
	}
	dfs1(0, -1);
	int cc = 0;
	for(int i = 0; i < n; i++)
		if(comp[i] == -1)
			dfs2(i, cc++);
	for(int i = 0; i < m; i++)
		if(is_bridge[i])
		{
			g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
			g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
		}
	dfs3(0, 0);
	dfs4(0, 0);
	for(int i = 0; i < n; i++)
		printf("%lld ", ans[comp[i]]);
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n;
int a[N];

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
			cout << "YES" << endl;
			cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

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

fun main() {
    val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println("${winBy[maxCnt]}".repeat(s.length))
    }
}

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    res, cur = 0, 1
    for s in a:
        if s * cur >= x:
            res += 1
            cur = 0
        cur += 1
    print(res)
    

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
long long x, k, y;
int a[N];
int b[N];

bool upd(int l, int r, long long &res) {
    if (l > r) return true;
    bool canDel = false;
    int mx = *max_element(a + l, a + r + 1);
    int len = r - l + 1;
    if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
    if (r + 1 < n && a[r + 1] > mx) canDel = true;
    if (len < k && !canDel) return false;
    
    int need = len % k;
    res += need * y;
    len -= need;
    
    if (y * k >= x) {
        res += len / k * x;
    } else if(canDel) {
        res += len * y;
    } else {
        res += (len - k) * y + x;
    }
    
    return true;
}

int main(){
    scanf("%d %d", &n, &m);
    scanf("%lld %lld %lld", &x, &k, &y);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long res = 0;
    int lst = -1, posa = 0, posb = 0;
    while (posb < m) {
        while(posa < n && a[posa] != b[posb]) ++posa;
        if (posa == n) {
            puts("-1");
            return 0;
        }
        
        if (!upd(lst + 1, posa - 1, res)) {
            puts("-1");
            return 0;
        }
        
        lst = posa;
        ++posb;
    }
    
    if (!upd(lst + 1, n - 1, res)) {
        puts("-1");
        return 0;
    }
    
    printf("%lld\n", res);
    
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int L = 20;

vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;

void dfs(int x, int y)
{
	tin[x] = T++;
	p[x] = y;
	up[x][0] = y;
	for(int i = 1; i < L; i++)
		up[x][i] = up[up[x][i - 1]][i - 1];
	for(auto z : g[x])
		dfs(z, x);
	tout[x] = T++;
}

bool is_ancestor(int x, int y)
{
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
	if(is_ancestor(x, y))
		return x;
	for(int i = L - 1; i >= 0; i--)
		if(!is_ancestor(up[x][i], y))
			x = up[x][i];
	return p[x];
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &idx[i]);
		idx[i]--;
	}
	for(int i = 0; i < m; i++)
		cur[i] = i;
	for(int i = 0; i < m - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		int nidx = m + i;
		g[nidx].push_back(cur[x]);
		g[nidx].push_back(cur[y]);
		cur[x] = nidx;
	}
	int root = m * 2 - 2;
	dfs(root, root);
	for(int i = 0; i < n - 1; i++)
	{
		int t = lca(idx[i], idx[i + 1]);
		if(t < m)
			psum[0]++;
		else
			psum[t - m + 1]++;
	}
	for(int i = 0; i < m - 1; i++)
		psum[i + 1] += psum[i];
	for(int i = 0; i < m; i++)
		printf("%d\n", n - 1 - psum[i]);
}

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;

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

int main(){
	scanf("%d%d", &n, &m);
	p.resize(m);
	val.resize(m);
	who.resize(n);
	int ans = n - 1;
	forn(i, m)
		p[i] = i;
	forn(i, n){
		int x;
		scanf("%d", &x);
		--x;
		who[i] = x;
		ans -= (i && who[i] == who[i - 1]);
		val[who[i]].push_back(i);
	}
	printf("%d\n", ans);
	forn(i, m - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		v = getp(v - 1), u = getp(u - 1);
		if (val[v].size() < val[u].size())
			swap(v, u);
		for (int x : val[u]){
			if (x) ans -= who[x - 1] == v;
			if (x < n - 1) ans -= who[x + 1] == v;
		}
		for (int x : val[u]){
			val[v].push_back(x);
			who[x] = v;
		}
		p[u] = v;
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

string s;

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

struct node{
	int val[4], len;
};

node merge(const node &a, const node &b, int l, int r){
	node c;
	int na = a.len == 1 ? 0 : 1;
	int nb = b.len == 1 ? 0 : 2;
	c.len = a.len + b.len;
	c.val[0] = mul(a.val[na], b.val[nb]);
	c.val[1] = mul(a.val[na], b.val[3]);
	c.val[2] = mul(a.val[3], b.val[nb]);
	c.val[3] = mul(a.val[3], b.val[3]);
	if (l == 1){
		na = a.len == 1 ? 2 : 0;
		nb = b.len == 1 ? 1 : 0;
		c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
		c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
		c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
		c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
	}
	return c;
}

node t[4 * N];

void build(int v, int l, int r){
	t[v].len = r - l;
	if (l == r - 1){
		t[v].val[0] = 1;
		t[v].val[3] = s[l] + 1;
		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], s[m - 1], s[m]);
}

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

int main(){
	int n, m;

	scanf("%d%d", &n, &m);
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, n) s[i] -= '0';
	
	memset(t, 0, sizeof(t));
	build(1, 0, n);
	
	forn(i, m){
		int x, v;
		scanf("%d%d", &x, &v);
		--x;
		upd(1, 0, n, x, v);
		printf("%d\n", t[1].val[3]);
	}
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 9;
const int MOD = 998244353;

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

void add(int &a, int x) {
    a += x;
    a %= 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 inv(int a) {
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;

void updRes(int l, int r, int c) {
    assert(l <= r);
    if (c == 1) {
        assert(!lr.count(make_pair(l, r)));
        lr.insert(make_pair(l, r));
        res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
    } else {
        assert(lr.count(make_pair(l, r)));
        lr.erase(make_pair(l, r));
        res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
    }
}

void getLR(int &l, int &r, int pos) {
    l = r = -1;
    auto it = lr.lower_bound(make_pair(pos, n));
    if(it == lr.begin()) return;
    --it;
    if(!(it->first <= pos && pos <= it->second)) return;
    l = it->first, r = it->second;
}

char buf[N];
int main(){
    scanf("%d %d\n", &n, &m);
    scanf("%s", buf);
    s = string(buf);
    for (int i = 0; i <= 9; ++i) {
        dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
        dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
    }
    for (int i = 2; i < N; ++i)
        for (int j = 0; j <= 9; ++j) {
            dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
            //idp[i][j] = inv(dp[i][j]);
        }
    for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
    for (int l = 0; l < n; ) {
        int r = l;
        while(r < n && s[r] == '1') ++r;
        res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
        if (l != r) lr.insert(make_pair(l, r - 1));
        l = r + 1;
    }
    
    for (int i = 0; i < m; ++i) {
        int pos;
        char x;
        scanf("%d %c\n", &pos, &x);
        --pos;
        if (x == '1') {
            if (s[pos] != '1'){ 
                int l1, r1, l2, r2;
                getLR(l1, r1, pos - 1);
                getLR(l2, r2, pos + 1);
                
                int l = pos, r = pos;
                if (l1 != -1) {
                    assert(r1 == pos - 1);
                    updRes(l1, r1, -1);
                    l = l1;
                } else {
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                }
                
                if (l2 != -1) {
                    assert(l2 == pos + 1);
                    updRes(l2, r2, -1);
                    r = r2;
                } else {
                    if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
                }
                
                s[pos] = x;
                updRes(l, r, 1);
            }
        } else {
            if (s[pos] != '1') {
                if (pos - 1 >= 0 && s[pos - 1] == '1') {
                    int l, r;
                    getLR(l, r, pos - 1);
                    updRes(l, r, -1);
                    s[pos] = x;
                    updRes(l, r, 1);
                } else {
                    res = mul(res, dp[0][x - '0']);
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                    s[pos] = x;
                }
            } else {
                int l, r;
                getLR(l, r, pos);
                assert(l != -1 && r != -1);
                
                updRes(l, r, -1);
                s[pos] = x;
                if (l == r) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
                } else if (pos == l) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    updRes(l + 1, r, 1);
                } else if (pos == r) {
                    if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
                    updRes(l, r - 1, 1);
                } else {
                    updRes(l, pos - 1, 1);
                    updRes(pos + 1, r, 1);
                }
            }
            
        }
        printf("%d\n", res);
    }
}

Для начала, скажем, что математическое ожидание равно среднему значению дохода по всем позициям и равно сумме значений дохода по всем позициям, деленной на $$$n$$$. Поэтому перейдем к минимизации суммы.

Научимся решать для фиксированного $$$k$$$. Возьмем некоторую расстановку и повернем комнаты так, чтобы последняя комната содержала мимика. Тогда у нас стоят $$$cnt_1$$$ обычных сундуков, затем один мимик, $$$cnt_2$$$ обычных сундуков, один мимик, $$$\dots$$$, $$$cnt_k$$$ обычных сундуков, один мимик. Все $$$cnt_i \ge 0$$$ и $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.

Взглянем на один из таких интервалов длины $$$cnt_i$$$. Последний сундук на интервале взят из $$$cnt_i$$$ начальных позиций, второй с конца — $$$cnt_i - 1$$$ раз и так далее.

Найдем оптимальный способ выбрать $$$cnt_i$$$. Зафиксируем некоторые значения $$$cnt_i$$$. Взглянем на наименьшее из них и на наибольшее. Пусть их значения будут равны $$$x$$$ и $$$y$$$. Если они отличаются хотя бы на $$$2$$$ ($$$x \le y - 2$$$), то результат всегда можно сделать лучше, если подвинуть один обычный сундук из большего интервала в меньший.

Теперь все значения $$$cnt_i$$$ выставлены. Осталось только присвоить сундуки оптимальным способом. Выпишем объединение всех последовательностей коэффициентов интервалов $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ и отсортируем в неубывающем порядке. Легко показать, что сундуки должны быть отсортированы в невозрастающем порядке (очень стандартная штука, можно доказать опять же показав, что другая расстановка легко может быть улучшена).

Это позволяет нам написать решение за $$$O(n^2)$$$. Отсортируем все сундуки в самом начале, а затем для любого $$$k$$$ домножим значение $$$i$$$-го сундука на $$$\lfloor \frac{i}{k} \rfloor$$$ и сложим результаты.

Наконец, ускорим решение с помощью префиксных сумм. Заметим, что первые $$$k$$$ значений домножаются на $$$0$$$, вторые $$$k$$$ значений — на $$$1$$$ и так далее. Если $$$n$$$ не делится на $$$k$$$, то последний блок имеет длину меньше $$$k$$$. Тогда можно посчитать ответ для любого $$$k$$$ за $$$O(\frac{n}{k})$$$. А это равно $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.

Асимптотика решения: $$$O(n \log n)$$$.

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

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

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

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

vector<int> pr;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n);
	forn(i, n)
		scanf("%d", &c[i]);
	sort(c.begin(), c.end(), greater<int>());
	pr.push_back(0);
	forn(i, n)
		pr.push_back(add(pr.back(), c[i]));
	
	int invn = binpow(n, MOD - 2);
	for (int k = 1; k <= n; ++k){
		int ans = 0;
		for (int i = 0, j = 0; i < n; i += k, ++j)
			ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
		printf("%d ", mul(ans, invn));
	}
	puts("");
	
	return 0;
}

for tc in range(int(input())):
	a, b, c = map(int, input().split())
	print(1 if a < c else -1, end=" ")
	print(b if c < a * b else -1)

for _ in range(int(input())):
    s = input()
    print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET')

for _ in range(int(input())):
    s = input()
    cur, mn, res = 0, 0, len(s)
    for i in range(len(s)):
        cur += 1 if s[i] == '+' else -1
        if cur < mn:
            mn = cur
            res += i + 1
        
    print(res)

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<vector<long long>> dp(n + 1, vector<long long>(3));
		for (int i = 0; i < n; ++i) {
			dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + (i & 1 ? 0 : a[i]));
			if (i + 2 <= n) dp[i + 2][1] = max(dp[i + 2][1], max(dp[i][0], dp[i][1]) + (i & 1 ? a[i] : a[i + 1]));
			dp[i + 1][2] = max(dp[i + 1][2], max({dp[i][0], dp[i][1], dp[i][2]}) + (i & 1 ? 0 : a[i]));
		}
		cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int n, k;

bool decimalLess(const string& s, const string& t)
{
	if(s.size() != t.size())
		return s.size() < t.size();
	for(int i = 0; i < s.size(); i++)
		if(s[i] != t[i])
			return s[i] < t[i];
	return false;
}

void upd(string& ans, const string& cur)
{
	if(ans == "-1" || decimalLess(cur, ans))
		ans = cur;
}

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

void solve()
{
	string ans = "-1";
	for(int i = 0; i <= 9; i++)
	{
		int cnt9 = n / 9;
		if(i + k < 10)
			cnt9 = 0;
		for(int j = 0; j <= cnt9; j++)
		{
		    if(i + k >= 10 && j == 0)
		        continue;
			int curSum = (i + (i + k)) * (k + 1) / 2;
			if(j != 0)
			{
				int cntBefore = 10 - i;
				int cntAfter = k + 1 - cntBefore;
				curSum = (i + 9) * cntBefore / 2 + cntBefore * 9 * (j - 1) + (1 + cntAfter) * cntAfter / 2;
			}
			curSum = n - curSum;
			if(curSum < 0 || curSum % (k + 1) != 0)
				continue;
			string curNum = {char('0' + i)};
			for(int z = 0; z < j - 1; z++)
				curNum += "9";
			int maxNum = 9;
			if(i + k >= 10)
				maxNum = 8;
			curSum /= (k + 1);
			while(curSum != 0)
			{
				int d = min(curSum, maxNum);
				maxNum = 9;
				curSum -= d;
				curNum.push_back(char('0' + d));
			}
			reverse(curNum.begin(), curNum.end());
			upd(ans, curNum);
		}
	}
	cout << ans << endl;
}

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		read();
		solve();
	}
}

def get(s):
	return str(s % 9) + '9' * (s // 9)

for tc in range(int(input())):
	n, k = map(int, input().split())
	k += 1
	bst = 10**100
	for d in range(10):
		ends = 0
		for i in range(k):
			ends += (d + i) % 10
		if ends > n:
			continue
		if d + k > 10:
			for cnt in range(12):
				s = 9 * cnt * (10 - d)
				if s > n - ends:
					break
				for nd in range(9):
					ns = s + (10 - d) * nd + (k - (10 - d)) * (nd + 1)
					if ns > n - ends:
						break
					if (n - ends - ns) % k == 0:
						bst = min(bst, int(get((n - ends - ns) // k) + str(nd) + '9' * cnt + str(d)))
		elif (n - ends) % k == 0:
			bst = min(bst, int(get((n - ends) // k) + str(d)))
	print(-1 if bst == 10**100 else bst)

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n;
vector<int> a, b;

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

struct func {
	int minx, mink, maxk;
	func() : minx(0), mink(0), maxk(0) {}
	func(int minx, int mink, int maxk) : minx(minx), mink(mink), maxk(maxk) {}
};

func getFunc(int a, int b) {
	if (a <= b)
		return func(0, b - a, b);
	else
		return func(a - b, 0, b);
}

func merge(func a, func b) {
	if (a.minx == -1 || b.minx == -1)
		return func(-1, -1, -1);
	
	if (a.maxk < b.minx)
		return func(-1, -1, -1);
	if (a.mink >= b.minx)
		return func(a.minx, min(b.maxk, b.mink + (a.mink - b.minx)), min(b.maxk, b.mink + (a.maxk - b.minx)));
	else {
		int add = b.minx - a.mink;
		return func(a.minx + add, b.mink, min(b.maxk, b.mink + (a.maxk - b.minx)));
	}
}

inline void solve() {
	func total = getFunc(a[0], b[0]);
	fore(i, 1, n)
		total = merge(total, getFunc(a[i], b[i]));
	
	if (total.minx != -1 && total.minx <= total.mink)
		cout << "YES\n";
	else
		cout << "NO\n";
}

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

typedef long long li;
const int N = 1000 * 1000 + 13;

int n;
int a[N], b[N];
 
void solve() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
	for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
	
	li need = 0, add = 0, extra = 2e9;
	for (int i = n - 1; i >= 0; --i) {
		if (b[i] < need) {
			puts("NO");
			return;
		}
		
		li val = b[i] - a[i];
		li to_add = min(extra, max(0LL, val - need));
		add += to_add;
		extra = min(extra - to_add, b[i] - need - to_add);
		need = max(0LL, need - val);
	}
	
	puts(add >= need ? "YES" : "NO");
}
 
int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; ++i)
		solve();
}

#include <bits/stdc++.h>

using namespace std;

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

int n, k;
int m;
int t[8 * N];
int add[8 * N];
int cnt[2 * N];

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

void upd(int l, int r, int x) {
    upd(0, 0, n + n, l, r, x);
}

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

int get(int l, int r) {
    return get(0, 0, n + n, l, r);
}

int getAns(set <int> &smx) {
    if (smx.empty()) return 0;
    return max(0, get(0, *smx.rbegin() + 1) - n);
}

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

int main(){
    scanf("%d %d %d", &n, &k, &m);
    
    build(0, 0, n + n);
    set <pair<int, int> > s;
    set <int> smx;
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        int pos = abs(x - k) + y - 1;
        pair <int, int> p = make_pair(x, y);
        if (s.count(p)) {
            --cnt[pos];
            if (cnt[pos] == 0) smx.erase(pos);
            upd(0, pos + 1, -1);
            s.erase(p);
        } else {
            ++cnt[pos];
            if (cnt[pos] == 1) smx.insert(pos);
            upd(0, pos + 1, 1);
            s.insert(p);
        }
        
        printf("%d\n", getAns(smx));
    }
    return 0;
}

for _ in range(int(input())):
    l, r = map(int, input().split())
    print(min(l, r, (l + r) // 3))

for _ in range(int(input())):
    n, x, m = map(int, input().split())
    l, r = x, x
    for _ in range(m):
        L, R = map(int, input().split())
        if max(l, L) <= min(r, R):
            l = min(l, L)
            r = max(r, R)
            
    print(r - l + 1)

#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int> > a(n, vector<int>(m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	vector<vector<int> > cnt(n + m - 1, vector<int>(2));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cnt[i + j][a[i][j]]++;
	int ans = 0;
	for(int i = 0; i <= n + m - 2; i++)
	{
		int j = n + m - 2 - i;
		if(i <= j) continue;
		ans += min(cnt[i][0] + cnt[j][0], cnt[i][1] + cnt[j][1]);
	}
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

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

    val minDiv = IntArray(1e7.toInt() + 2) { it }
    for (i in 2 until minDiv.size) {
        if (minDiv[i] != i)
            continue
        for (j in i until minDiv.size step i)
            minDiv[j] = minOf(minDiv[j], i)
    }

    fun getPrimeDivisors(v: Int): ArrayList<Int> {
        val ans = ArrayList<Int>()
        var curVal = v
        while (curVal != 1) {
            if (ans.isEmpty() || ans.last() != minDiv[curVal])
                ans.add(minDiv[curVal])
            curVal /= minDiv[curVal]
        }
        return ans
    }

    val d1 = IntArray(n)
    val d2 = IntArray(n)
    for (id in a.indices) {
        val list = getPrimeDivisors(a[id])
        if (list.size < 2) {
            d1[id] = -1
            d2[id] = -1
        } else {
            d1[id] = list[0]
            list.removeAt(0)
            d2[id] = list.reduce { s, t -> s * t }
        }
    }
    println(d1.joinToString(" "))
    println(d2.joinToString(" "))
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int MOD = 998244353;

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

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

int main() {	
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    reverse(a, a + n);
    reverse(b, b + m);
    a[n] = -1;
    
    int mn = a[0];
    int pos = 0;
    while (pos < n && mn > b[0]) {
        ++pos;
        mn = min(mn, a[pos]);
    }
    
    if (pos == n || mn < b[0]) {
       puts("0");
       return 0;
    }
    
    assert(mn == b[0]);
    int res = 1;
    int ib = 0;
    while (true) {
        assert(mn == b[ib]);
        if (ib == m - 1){
            if(*min_element(a + pos, a + n) != b[ib]) {
               puts("0");
               return 0;
            }
            break;
        }
        
        bool f = true;
        int npos = pos;
        while (npos < n && mn != b[ib + 1]) {
            ++npos;
            mn = min(mn, a[npos]);
            
            if (f && mn < b[ib]){
                f = false;
                res = mul(res, npos - pos);
            }
        }
        
        if (npos == n || mn != b[ib + 1]) {
            puts("0");
            return 0;
        }
        
        ++ib;
        pos = npos;
    }
    
    printf("%d\n", res);
    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 = 1e18;
const int MOD = 1000'000'007;
const int inv2 = (MOD + 1) / 2;

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

struct frac{
	long long x, y;
	frac(long long a, long long b){
		if (b < 0) a = -a, b = -b;
		x = a, y = b;
	}
};

bool operator <=(const frac &a, const frac &b){
	return a.x * b.y <= a.y * b.x;
}

struct line{
	long long m, c;
	frac intersectX(const line &l) { return frac(c - l.c, l.m - m); }
};

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

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

int calc(int a1, int d, int n){
	assert(n >= 0);
	return mul(mul(n, inv2), add(mul(2, a1), mul(add(n, -1), d)));
}

int main() {
	int n, m;
	long long q;
	scanf("%d%d%lld", &n, &m, &q);
	vector<edge> e(m);
	vector<int> hv(n);
	forn(i, m){
		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
		--e[i].v, --e[i].u;
		hv[e[i].v] = max(hv[e[i].v], e[i].w);
		hv[e[i].u] = max(hv[e[i].u], e[i].w);
	}
	
	int ans = 0;
	vector<long long> d(n, -INF), nd(n);
	d[0] = 0;
	forn(val, m){
		long long mx = 0;
		forn(i, n)
			mx = max(mx, d[i]);
		if (val)
			ans = add(ans, mx % MOD);
		nd = d;
		forn(i, m){
			nd[e[i].v] = max(nd[e[i].v], d[e[i].u] + e[i].w);
			nd[e[i].u] = max(nd[e[i].u], d[e[i].v] + e[i].w);
		}
		d = nd;
	}
	
	vector<line> fin;
	forn(i, n) fin.push_back({hv[i], d[i]});
	sort(fin.begin(), fin.end(), [](const line &a, const line &b){
		if (a.m != b.m)
			return a.m < b.m;
		return a.c > b.c;
	});
	fin.resize(unique(fin.begin(), fin.end(), [](const line &a, const line &b){
		return a.m == b.m;
	}) - fin.begin());
	
	vector<line> ch;
	for (auto cur : fin){
		while (ch.size() >= 2 && cur.intersectX(ch.back()) <= ch.back().intersectX(ch[int(ch.size()) - 2]))
			ch.pop_back();
		ch.push_back(cur);
	}
	
	long long prv = 0;
	q -= m;
	forn(i, int(ch.size()) - 1){
		frac f = ch[i].intersectX(ch[i + 1]);
		if (f.x < 0) continue;
		long long lst = min(q, f.x / f.y);
		if (lst < prv) continue;
		ans = add(ans, calc((ch[i].c + ch[i].m * prv) % MOD, ch[i].m % MOD, lst - prv + 1));
		prv = lst + 1;
	}
	ans = add(ans, calc((ch.back().c + ch.back().m * prv) % MOD, ch.back().m % MOD, q - prv + 1));
	
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#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)

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

int n, m;
string s, t;
int dp[N][N];
int nxt[N];

int main() {
	cin >> s >> t;
	n = sz(s), m = sz(t);
	
	forn(i, n) if (s[i] != '.') {
		int bal = 0;
		nxt[i] = -1;
		fore(j, i, n) {
			if (s[j] == '.') --bal;
			else ++bal;
			if (bal == 0) {
				nxt[i] = j;
				break;
			}
		}
	}
	
	forn(i, n + 1) forn(j, m + 1)
		dp[i][j] = INF;
	dp[0][0] = 0;
	
	forn(i, n) forn(j, m + 1) {
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
		if (j < m && s[i] == t[j])
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
		if (s[i] != '.' && nxt[i] != -1)
			dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]);
	}
	
	cout << dp[n][m] << endl;
}

t = int(input())

for i in range(t):
    n, m, k = map(int, input().split())
    d = n // k
    a1 = min(m, d)
    a2 = (m - a1 + k - 2) // (k - 1)
    print(a1 - a2)

t = int(input())

for i in range(t):
    n, m, k = map(int, input().split())
    ans = 0
    d = n // k
    for a1 in range(m + 1):
        for a2 in range(a1 + 1):
            if(a1 > d):
                continue
            if(a1 + a2 > m):
                continue
            if(a1 + (k - 1) * a2 < m):
                continue
            ans = max(ans, a1 - a2)
    print(ans)

t = int(input())
for _ in range(t):
	n, m, x, y = map(int, input().split())
	ans = 0
	y = min(y, 2 * x)
	for __ in range(n):
		s = input()
		i = 0
		while i < m:
			if s[i] == '*':
				i += 1
				continue
			j = i
			while j + 1 < m and s[j + 1] == '.':
				j += 1
			l = j - i + 1
			ans += l % 2 * x + l // 2 * y
			i = j + 1
	print(ans)

Рассмотрим два типа остановок: $$$k$$$ горячих и $$$k$$$ холодных кружек и $$$(k + 1)$$$ горячая и $$$k$$$ холодных кружек.

Первый случай тривиален: температура всегда равна $$$\frac{h + c}{2}$$$. Во втором случае температура всегда строго выше, чем $$$\frac{h + c}{2}$$$. Поэтому, если $$$t \le \frac{h + c}{2}$$$, то ответ всегда $$$2$$$.

Покажем, что в противном случае ответ всегда достигается из второго случая:

Температура после $$$(k + 1)$$$ горячей кружки и $$$k$$$ холодных кружек $$$t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$$$. Утверждается, что $$$t_0 > t_1 > \dots$$$. Докажем это по индукции.

Также стоит показать, что этот ряд сходится к $$$\frac{h + c}{2}$$$:

Так что это утверждение показывает нам, что для любого $$$t$$$, больше чем $$$\frac{h + c}{2}$$$, ответ всегда достигается из второго случая.

Это позволяет нам найти такое $$$k$$$, что значение $$$t_k$$$ ровно $$$t$$$. Однако, $$$k$$$ не всегда оказывается целым числом. $$$\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} = t \leftrightarrow$$$ $$$\frac{k \cdot (h + c) + h}{2k + 1} = t \leftrightarrow$$$ $$$k \cdot (h + c) + h = 2kt + t \leftrightarrow$$$ $$$k \cdot (h + c - 2t) = t - h \leftrightarrow$$$ $$$k = \frac{t - h}{h + c - 2t}$$$.

Остается только понять, в какую сторону выгоднее округлять $$$k$$$. Кажется, что некоторые реализации с вещественными числами могут не работать из-за погрешностей вычислений. Однако, можно все целиком провести в целых числах.

Перепишем это выражение, чтобы знаменатель был всегда положительным $$$k = \frac{h - t}{2t - h - c}$$$. Теперь округлим это значение вниз и сравним $$$k$$$ и $$$k + 1$$$.

Оптимальное значение достигается при $$$k$$$, если $$$|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3} - t|$$$. Так что $$$|(k \cdot (h + c) + h) - t \cdot (2k + 1)| \cdot (2k + 3) \le |((k + 1) \cdot (h + c) + h) - t \cdot (2k + 3)| \cdot (2k + 1)$$$. Иначе ответ $$$k + 1$$$.

Оптимальное значение $$$k$$$ можно также найти бинарным поиском, но формулы получаются такие же, и все равно приходится опираться на монотонность. К тому же формулы помогают определить верхнюю границу на ответ.

Асимптотика решения: $$$O(1)$$$ или $$$O(\log h)$$$ на набор входных данных.

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		int h, c, t;
		scanf("%d%d%d", &h, &c, &t);
		if (h + c - 2 * t >= 0)
			puts("2");
		else{
			int a = h - t;
			int b = 2 * t - c - h;
			int k = 2 * (a / b) + 1;
			long long val1 = abs(k / 2 * 1ll * c + (k + 1) / 2 * 1ll * h - t * 1ll * k);
			long long val2 = abs((k + 2) / 2 * 1ll * c + (k + 3) / 2 * 1ll * h - t * 1ll * (k + 2));
			printf("%d\n", val1 * (k + 2) <= val2 * k ? k : k + 2);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	long long ans = 0;
	forn(mx, 31){
		long long cur = 0;
		long long best = 0;
		forn(i, n){
			int val = (a[i] > mx ? -INF : a[i]);
			cur += val;
			best = min(best, cur);
			ans = max(ans, (cur - best) - mx);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 500043;
const int MOD = 998244353;

int fact[N];

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 divide(int x, int y)
{
	return mul(x, inv(y));
}

void precalc()
{
	fact[0] = 1;
	for(int i = 1; i < N; i++)
		fact[i] = mul(i, fact[i - 1]);
}

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

int main()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	precalc();
	for(int i = 1; i <= n; i++)
	{
		int d = n / i;
		ans = add(ans, C(d - 1, k - 1));
	}
	cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

const double INF = 1e13;

struct line{
	int A, B, C;
	line(){}
	line(int x1, int y1, int x2, int y2){
		A = y1 - y2;
		B = x2 - x1;
		C = -A * x1 - B * y1;
		// A is guaranteed to be non-zero
		if (A < 0) A = -A, B = -B, C = -C;
		int g = __gcd(A, __gcd(abs(B), abs(C)));
		A /= g, B /= g, C /= g;
	}
};

bool operator ==(const line &a, const line &b){
	return a.A == b.A && a.B == b.B && a.C == b.C;
}

double x;

bool operator <(const line &a, const line &b){
	double val1 = (-a.A * x - a.C) / a.B;
	double val2 = (-b.A * x - b.C) / b.B;
	return val1 < val2;
}

struct car{
	int x, y, dx, dy, s;
	line l;
	double vx, vy;
};

int n;
vector<car> a(n);

long long det(int a, int b, int c, int d){
	return a * 1ll * d - b * 1ll * c;
}

bool inter(const line &a, const line &b, long long &D, long long &Dx, long long &Dy){
	D = det(a.A, a.B, b.A, b.B);
	if (D == 0) return false;
	Dx = -det(a.C, a.B, b.C, b.B);
	Dy = -det(a.A, a.C, b.A, b.C);
	return true;
}

int sg(int x){
	return x < 0 ? -1 : 1;
}

int sg(long long a, long long b, int c){
	// sign of a/b-c
	if (b < 0) a = -a, b = -b;
	return a - c * b < 0 ? -1 : (a - c * b > 0);
}

bool inter(int i, int j, double &len){
	if (i == -1 || j == -1)
		return false;
	long long D, Dx, Dy;
	if (!inter(a[i].l, a[j].l, D, Dx, Dy))
		return false;
	if (sg(Dx, D, a[i].x) != 0 && sg(a[i].dx) != sg(Dx, D, a[i].x))
		return false;
	if (sg(Dx, D, a[j].x) != 0 && sg(a[j].dx) != sg(Dx, D, a[j].x))
		return false;
	double x = Dx / double(D);
	double y = Dy / double(D);
	double di = (a[i].x - x) * (a[i].x - x) + (a[i].y - y) * (a[i].y - y);
	double dj = (a[j].x - x) * (a[j].x - x) + (a[j].y - y) * (a[j].y - y);
	return len * len >= di / a[i].s && len * len >= dj / a[j].s;
}

vector<set<pair<line, int>>::iterator> del;
set<pair<line, int>> q;

void get_neighbours(int i, int &l, int &r){
	l = r = -1;
	auto it = q.lower_bound({a[i].l, -1});
	if (it != q.end())
		r = it->y;
	if (!q.empty() && it != q.begin()){
		--it;
		l = it->y;
	}
}

bool check(double t){
	vector<pair<double, pair<int, int>>> cur;
	del.resize(n);
	forn(i, n){
		double x1 = a[i].x;
		double x2 = a[i].x + a[i].vx * t;
		if (x1 > x2) swap(x1, x2);
		cur.push_back({x1, {i, 0}});
		cur.push_back({x2, {i, 1}});
	}
	q.clear();
	
	sort(cur.begin(), cur.end());
	for (auto &qr : cur){		
		x = qr.x;
		int i = qr.y.x;
		int l, r;
		
		if (qr.y.y == 0){
			get_neighbours(i, l, r);
			
			if (r != -1 && a[i].l == a[r].l)
				return true;
			if (inter(i, l, t))
				return true;
			if (inter(i, r, t))
				return true;
			
			del[i] = q.insert({a[i].l, i}).x;
		}
		else{			
			q.erase(del[i]);
			get_neighbours(i, l, r);
			
			if (inter(l, r, t))
				return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	a.resize(n);
	forn(i, n){
		scanf("%d%d%d%d%d", &a[i].x, &a[i].y, &a[i].dx, &a[i].dy, &a[i].s);
		a[i].l = line(a[i].x, a[i].y, a[i].x + a[i].dx, a[i].y + a[i].dy);
		double d = sqrt(a[i].dx * a[i].dx + a[i].dy * a[i].dy);
		a[i].vx = a[i].dx / d * a[i].s;
		a[i].vy = a[i].dy / d * a[i].s;
		a[i].s *= a[i].s;
	}
	double l = 0, r = INF;
	bool ok = false;
	forn(_, 100){
		double m = (l + r) / 2;
		if (check(m)){
			ok = true;
			r = m;
		}
		else{
			l = m;
		}
	}
	if (!ok)
		puts("No show :(");
	else
		printf("%.15lf\n", l);
	return 0;
}

t = int(input())
for _ in range(t):
	a, b, c, d = map(int, input().split())
	if b >= a:
		print(b)
		continue
	if c <= d:
		print(-1)
		continue
	a -= b
	dif = c - d
	print(b + (a + dif - 1) // dif * c)

#include<bits/stdc++.h>

using namespace std;

char buf[200043];

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
		scanf("%s", buf);
		string s = buf;
		int ans = int(1e9);
		int n = s.size();
		vector<pair<char, int> > c;
		for(auto x : s)
		{
			if(c.empty() || c.back().first != x)
				c.push_back(make_pair(x, 1));
			else
				c.back().second++;
		}
		int m = c.size();
		for(int i = 1; i < m - 1; i++)
			if(c[i - 1].first != c[i + 1].first)
				ans = min(ans, c[i].second + 2);
		if(ans > n)
			ans = 0;
		printf("%d\n", ans);
	}
}

import kotlin.math.*

fun main() {
    val PI = acos(-1.0)
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val n = readLine()!!.toInt()
        var ans : Double
        if (n % 2 == 0) {
            ans = 1.0 / tan(PI / (2 * n))
        } else {
            ans = cos(PI / (4 * n)) / sin(PI / (2 * n))
        }
        println("%.9f".format(ans))
    }
}

#include<bits/stdc++.h>

using namespace std;

int n, q;
vector<int> a, k;

int count_le(int x)
{
	int cnt = 0;
	for(auto y : a)
		if(y <= x)
			cnt++;
	for(auto y : k)
	{
		if(y > 0 && y <= x)
			cnt++;
		if(y < 0 && abs(y) <= cnt)
			cnt--;
	}
	return cnt;
}

int main()
{
	scanf("%d %d", &n, &q);
	a.resize(n);
	k.resize(q);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < q; i++)
		scanf("%d", &k[i]);
	if(count_le(int(1e9)) == 0)
	{
		puts("0");
		return 0;
	}
	int lf = 0;
	int rg = int(1e6) + 1;
	while(rg - lf > 1)
	{
		int mid = (lf + rg) / 2;
		if(count_le(mid) > 0)
			rg = mid;
		else
			lf = mid;
	}
	printf("%d\n", rg);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}

template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

mt19937 rnd(time(NULL));

const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

const int N = 5000 + 7;

int n, m;
int a[3];
vector<int> g[N];

bool read () {
	if (scanf("%d%d", &n, &m) != 2)
		return false;
	forn(i, 3) scanf("%d", &a[i]);
	forn(i, n)
		g[i].clear();
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].pb(u);
		g[u].pb(v);
	}
	return true;
}

int tot0, tot1;
int clr[N];
vector<vector<int>> vts[2];
bool ok;

void dfs(int v){
	tot0 += clr[v] == 0;
	tot1 += clr[v] == 1;
	vts[clr[v]].back().pb(v);
	for (auto u : g[v]){
		if (clr[u] == -1){
			clr[u] = clr[v] ^ 1;
			dfs(u);
		}
		else if (clr[u] == clr[v]){
			ok = false;
		}
	}
}

int dp[N][N];
int res[N];

void solve() {
	vector<pt> siz;
	memset(clr, -1, sizeof(clr));
	vts[0].clear();
	vts[1].clear();
	forn(i, n) if (clr[i] == -1){
		tot0 = tot1 = 0;
		clr[i] = 0;
		ok = true;
		vts[0].pb(vector<int>());
		vts[1].pb(vector<int>());
		dfs(i);
		if (!ok){
			puts("NO");
			return;
		}
		siz.pb(mp(tot0, tot1));
	}
	
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	forn(i, sz(siz)) forn(j, N) if (dp[i][j] != -1){
		dp[i + 1][j + siz[i].x] = 0;
		dp[i + 1][j + siz[i].y] = 1;
	}
	
	if (dp[sz(siz)][a[1]] == -1){
		puts("NO");
		return;
	}
	
	puts("YES");
	memset(res, -1, sizeof(res));
	int cur = a[1];
	for (int i = sz(siz); i > 0; --i){
		for (auto it : vts[dp[i][cur]][i - 1])
			res[it] = 2;
		cur -= sz(vts[dp[i][cur]][i - 1]);
	}
	
	forn(i, n) if (res[i] == -1){
		if (a[0] > 0){
			res[i] = 1;
			--a[0];
		}
		else{
			res[i] = 3;
			--a[2];
		}
	}
	
	forn(i, n) printf("%d", res[i]);
	puts("");
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;

	while(read()) {	
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif

	}
}

#include<bits/stdc++.h>

using namespace std;

const int N = 243;

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

int s, t, V;
vector<int> g[N];
vector<edge> e;

void add(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 rem(int num)
{
    return e[num].c - e[num].f;
}   

int p[N];
int d[N];
int pe[N];
int inq[N];

bool enlarge()
{
    for(int i = 0; i < V; i++)
    {
        d[i] = int(1e9);
        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 z : g[k])
        {
            if(!rem(z)) continue;
            if(d[e[z].y] > d[k] + e[z].cost)
            {
                p[e[z].y] = k;
                pe[e[z].y] = z;
                d[e[z].y] = d[k] + e[z].cost;
                if(!inq[e[z].y])
                {
                    q.push(e[z].y);
                    inq[e[z].y] = 1;
                }
            }
        }
    }
    if(p[t] == -1)
        return false;
    int cur = t;
    while(cur != s)
    {
        e[pe[cur]].f++;
        e[pe[cur] ^ 1].f--;
        cur = p[cur];
    }
    return true;
}

void process_test()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
	}
	s = 2 * n;
	t = 2 * n + 1;
	V = 2 * n + 2;
	for(int i = 0; i < n; i++)
	{
		add(s, i, 1, 0);
		add(i + n, t, 1, 0);
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		{
			if(j < k - 1)
				add(i, j + n, 1, -(a[i] + b[i] * j));
			else if(j == n - 1)
				add(i, j + n, 1, -(a[i] + b[i] * (k - 1)));
			else
				add(i, j + n, 1, -(b[i] * (k - 1)));
		}
	for(int i = 0; i < n; i++)
		enlarge();
	vector<int> order(n);
	for(int i = 0; i < n; i++)
		for(auto x : g[i])
		{
			int to = e[x].y;
			if(to >= n && to < 2 * n && e[x].f == 1)
				order[to - n] = i;
		}
	cout << k + (n - k) * 2 << endl;
	for(int i = 0; i < n; i++)
	{
		cout << order[i] + 1 << " ";
		if(i >= k - 1 && i < n - 1)
			cout << -(order[i] + 1) << " ";
	}
	cout << endl;
	e.clear();
	for(int i = 0; i < V; i++)
		g[i].clear();
}

int main()
{                       
    int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		process_test();
}

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void output_vector(const vector<T> &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());

    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}

const int64_t INF64 = int64_t(2e18) + 5;

vector<int> assignment;

template<typename T>
int64_t hungarian(vector<vector<T>> costs) {
    int n = int(costs.size());
    int m = costs.empty() ? 0 : int(costs[0].size());

    if (n > m) {
        vector<vector<T>> new_costs(m, vector<T>(n));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                new_costs[j][i] = costs[i][j];

        swap(costs, new_costs);
        swap(n, m);
    }

    vector<int64_t> u(n + 1), v(m + 1);
    vector<int> p(m + 1), way(m + 1);

    for (int i = 1; i <= n; i++) {
        vector<int64_t> min_v(m + 1, INF64);
        vector<bool> used(m + 1, false);
        p[0] = i;
        int j0 = 0;

        do {
            used[j0] = true;
            int i0 = p[j0], j1 = 0;
            int64_t delta = INF64;

            for (int j = 1; j <= m; j++)
                if (!used[j]) {
                    int64_t cur = costs[i0 - 1][j - 1] - u[i0] - v[j];

                    if (cur < min_v[j]) {
                        min_v[j] = cur;
                        way[j] = j0;
                    }

                    if (min_v[j] < delta) {
                        delta = min_v[j];
                        j1 = j;
                    }
                }

            for (int j = 0; j <= m; j++)
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    min_v[j] -= delta;
                }

            j0 = j1;
        } while (p[j0] != 0);

        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }

    // Note that p[j] is the row assignment of column j (both 1-based). If p[j] = 0, the column is unassigned.
    assignment = p;
    return -v[0];
}


void run_case() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N), B(N);

    for (int i = 0; i < N; i++)
        cin >> A[i] >> B[i];

    vector<vector<int>> costs(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++)
        for (int position = 0; position < N; position++)
            if (position < K)
                costs[i][position] = -(A[i] + position * B[i]);
            else
                costs[i][position] = -((K - 1) * B[i]);

    int64_t score = -hungarian(costs);
    dbg(score);
    vector<int> solution;

    for (int k = 1; k < K; k++)
        solution.push_back(assignment[k]);

    for (int k = K + 1; k <= N; k++) {
        solution.push_back(assignment[k]);
        solution.push_back(-assignment[k]);
    }

    solution.push_back(assignment[K]);
    assert(int(solution.size()) == 2 * N - K);
    cout << solution.size() << '\n';
    output_vector(solution);
}

int main() {
    ios::sync_with_stdio(false);
#ifndef NEAL_DEBUG
    cin.tie(nullptr);
#endif

    int tests;
    cin >> tests;

    while (tests-- > 0)
        run_case();
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define x first
#define y second
#define mp make_pair
#define pb push_back
#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;
typedef pair<int, int> pt;
 
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << "(" << a.x << ", " << a.y << ")";
}
 
template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}
 
mt19937 rnd(time(NULL));
 
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
 
const int N = 100;
 
int n, k;
pair<pt, int> a[N];
 
bool read () {
	if (scanf("%d%d", &n, &k) != 2)
		return false;
	forn(i, n){
		scanf("%d%d", &a[i].x.x, &a[i].x.y);
		a[i].y = i;
	}
	return true;
}
 
int dp[N][N];
int p[N][N];
 
void solve() {
	sort(a, a + n, [](const pair<pt, int> &a, const pair<pt, int> &b){
		if (a.x.y != b.x.y)
			return a.x.y < b.x.y;
		return a.x.x < b.x.x;
	});
	
	forn(i, N) forn(j, N)
		dp[i][j] = -INF;
	dp[0][0] = 0;
	forn(i, n) forn(j, N) if (dp[i][j] >= 0){
		if (dp[i + 1][j] < dp[i][j] + a[i].x.y * (k - 1)){
			dp[i + 1][j] = dp[i][j] + a[i].x.y * (k - 1);
			p[i + 1][j] = j;
		}
		if (dp[i + 1][j + 1] < dp[i][j] + a[i].x.y * j + a[i].x.x){
			dp[i + 1][j + 1] = dp[i][j] + a[i].x.y * j + a[i].x.x;
			p[i + 1][j + 1] = j;
		}
	}
	
	vector<int> ans1, ans2;
	int cur = k;
	for (int i = n; i > 0; --i){
		if (p[i][cur] == cur)
			ans2.pb(a[i - 1].y + 1);
		else
			ans1.pb(a[i - 1].y + 1);
		cur = p[i][cur];
	}
	
	reverse(all(ans1));
	reverse(all(ans2));
	printf("%d\n", sz(ans1) + sz(ans2) * 2);
	forn(i, sz(ans1) - 1)
		printf("%d ", ans1[i]);
	for (auto it : ans2)
		printf("%d %d ", it, -it);
	printf("%d\n", ans1.back());
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int tt = clock();
	
#endif
	
	cerr.precision(15);
	cout.precision(15);
	cerr << fixed;
	cout << fixed;
 
	int tc;
	scanf("%d", &tc);
	while(tc--) {	
		read();
		solve();
		
#ifdef _DEBUG
	cerr << "TIME = " << clock() - tt << endl;
	tt = clock();
#endif
 
	}
}

#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 MAG = 30;
int lst;

int n, k;

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

int ask(int l1, int r1, int l2, int r2) {
	assert(l1 < r1 && l2 < r2);
	assert(r1 <= l2 || r2 <= l1);
	
	cout << "? " << r1 - l1 << " " << r2 - l2 << endl;
	fore(i, l1, r1) {
		if (i > l1) cout << " ";
		cout << i + 1;
	}
	cout << endl;
	fore(i, l2, r2) {
		if (i > l2) cout << " ";
		cout << i + 1;
	}
	cout << endl;
	cout.flush();
	
	string resp;
	cin >> resp;
	
	if (resp == "FIRST")
		return -1;
	if (resp == "SECOND")
		return 1;
	if (resp == "EQUAL")
		return 0;
	
	exit(0);
}

inline void solve() {
	//check first position
	mt19937 rnd(lst ^ (n * 1024 + k));
	for(int q = 0; q < MAG; q++) {
		int cur = 1 + rnd() % (n - 1);
		
		int resp = ask(0, 1, cur, cur + 1);
		if (resp == 1) {
			cout << "! 1" << endl;
			cout.flush();
			return;
		}
	}
	
	int len = 1;
	while(true) {
		int cnt = min(len, n - len);
		int resp = ask(0, cnt, len, len + cnt);
		if (resp != 0) {
			assert(resp == -1);
			break;
		}
		len <<= 1;
	}
	
	int lf = len, rg = min(2 * len, n);
	while(rg - lf > 1) {
		int mid = (lf + rg) >> 1;
		int resp = ask(0, mid - lf, lf, mid);
		assert(resp != 1);
		
		if (resp == 0)
			lf = mid;
		else
			rg = mid;
	}
	cout << "! " << lf + 1 << endl;
	cout.flush();
	
	lst = lf + 1;
}

int main() {
	int tc;
	cin >> tc;
	
	lst = tc;
	while(tc--) {
		assert(read());
		solve();
	}
	return 0;
}

for _ in range(int(input())):
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    b = min(b, a + a)
    if x < y:
        x, y= y, x
    print(y * b + (x - y) * a)

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val t = readLine()!!

        val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
        println(s)
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 40043;

int len;
int p[N];

void build(int a, int b)
{
	len = a * b;
	p[0] = 0;
	for(int i = 1; i <= len; i++)
	{
		p[i] = p[i - 1];
		if((i % a) % b != (i % b) % a)
			p[i]++;
	}
}

long long query(long long l)
{
	long long cnt = l / len;
	int rem = l % len;
	return p[len] * 1ll * cnt + p[rem]; 
}

long long query(long long l, long long r)
{
	return query(r) - query(l - 1);
}

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int a, b, q;
		cin >> a >> b >> q;
		build(a, b);
		long long l, r;
		for(int j = 0; j < q; j++)
		{
			cin >> l >> r;
			cout << query(l, r) << " ";
		}
		cout << endl;
	}
}

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> c(k + 1);
	forn(i, k) scanf("%d", &c[i + 1]);
	
	sort(a.begin(), a.end(), greater<int>());
	int ans = 0;
	for (int i = k, g = 0; i >= 1; --i){
		while (g < n && a[g] == i) ++g;
		ans = max(ans, (g + c[i] - 1) / c[i]);
	}
	vector<vector<int>> res(ans);
	forn(i, n) res[i % ans].push_back(a[i]);
	
	printf("%d\n", ans);
	forn(i, ans){
		printf("%d", int(res[i].size()));
		for (auto it : res[i])
			printf(" %d", it);
		puts("");
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 200043;

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

int sub(int x, int y)
{
	return add(x, MOD - y);
}

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

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

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

int fact[N];

int C(int n, int k)
{
	return mul(fact[n], inv(mul(fact[k], fact[n - k])));
}

int main()
{
	int n, k;
	cin >> n >> k;
	
	if(k > n - 1)
	{
		cout << 0 << endl;
		return 0;
	}
	
	fact[0] = 1;
	for(int i = 1; i <= n; i++)
		fact[i] = mul(i, fact[i - 1]);
	int ans = 0;
	int c = n - k;
	for(int i = c; i >= 0; i--)
		if(i % 2 == c % 2)
			ans = add(ans, mul(binpow(i, n), C(c, i)));
		else
			ans = sub(ans, mul(binpow(i, n), C(c, i)));
	ans = mul(ans, C(n, c));
	if(k > 0)
		ans = mul(ans, 2);
	cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#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 INF = 1e9;
const int N = 15;

int n;
int a[N];
int sum[1 << N];
int dp[N + 1][1 << N][N + 1];
pt p[N + 1][1 << N][N + 1];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	
	forn(mask, 1 << n) {
		sum[mask] = 0;
		forn(i, n) if (mask & (1 << i))
			sum[mask] += a[i];
	}	
	
	forn(cnt, n + 1) forn(mask, 1 << n) forn(pos, n + 1)
		dp[cnt][mask][pos] = INF;
	
	dp[0][0][0] = 0;
	forn(cnt, n) forn(mask, 1 << n) forn(pos, n) if (dp[cnt][mask][pos] < INF) {
		int rmask = mask ^ ((1 << n) - 1);
		for (int nmask = rmask; nmask; nmask = (nmask - 1) & rmask) {
			if (sum[nmask] <= dp[cnt][mask][pos])
				continue;
			if ((nmask >> pos) == 0)
				continue;
			int npos = pos + __builtin_ctz(nmask >> pos) + 1;
			if (dp[cnt + 1][mask | nmask][npos] > sum[nmask]) {
				dp[cnt + 1][mask | nmask][npos] = sum[nmask];
				p[cnt + 1][mask | nmask][npos] = mp(mask, pos);
			}
		}
	}
	
	int acnt = 0, apos = 0;
	forn(cnt, n + 1) forn(pos, n + 1) if (dp[cnt][(1 << n) - 1][pos] < INF)
		acnt = cnt, apos = pos;
		
	vector<pt> ans;
	
	int mask = (1 << n) - 1, pos = apos;
	for (int cnt = acnt; cnt > 0; --cnt) {
		int nmask = p[cnt][mask][pos].x;
		int npos = p[cnt][mask][pos].y;
		forn(i, n) if ((nmask ^ mask) & (1 << i))
			if (i != pos - 1) ans.pb(mp(i, pos - 1));
		mask = nmask, pos = npos;
	}
	
	
	printf("%d\n", sz(ans));
	forn(i, sz(ans)) {
		int from = ans[i].x;
		forn(j, i) from -= ans[j].x < ans[i].x;
		int to = ans[i].y;
		forn(j, i) to -= ans[j].x < ans[i].y;
		printf("%d %d\n", from + 1, to + 1);
	}
}	

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

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int n;
		scanf("%d", &n);
		int p = 0, c = 0;
		bool fl = true;
		forn(i, n){
			int x, y;
			scanf("%d%d", &x, &y);
			if (x < p || y < c || y - c > x - p)
				fl = false;
			p = x, c = y;
		}
		puts(fl ? "YES" : "NO");
	}
	return 0;
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, x) = readLine()!!.split(' ').map { it.toInt() }
        val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()

        var cnt = 0
        var sum = 0L
        while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) {
            sum += a[cnt]
            cnt++
        }
        println(cnt)
    }
}

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

int n;
li a[N], b[N];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%lld%lld", &a[i], &b[i]);
	
	li ans = 0, mn = 1e18;
	forn(i, n) {
		int ni = (i + 1) % n;
		li val = min(a[ni], b[i]);
		ans += a[ni] - val;
		mn = min(mn, val);
	}
	ans += mn;
	printf("%lld\n", ans);
}

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

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

int n;
li l, r;

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

bool intersect(li l1, li r1, li l2, li r2) {
	return min(r1, r2) > max(l1, l2);
}

vector<int> ans;

void calc(int lf, int rg, li &id) {
	if(lf == rg) return;
	
	if(intersect(l, r, id, id + 2 * (rg - lf))) {
		fore(to, lf + 1, rg + 1) {
			if(l <= id && id < r)
				ans.push_back(lf);
			id++;
			
			if(l <= id && id < r)
				ans.push_back(to);
			id++;
		}
	} else
		id += 2 * (rg - lf);
	
	calc(lf + 1, rg, id);
	
	if(lf == 0) {
		if(l <= id && id < r)
			ans.push_back(lf);
		id++;
	}
}

inline void solve() {
	ans.clear();
	li id = 0;
	l--;
	calc(0, n - 1, id);
	
	assert(sz(ans) == r - l);
	assert(id == n * li(n - 1) + 1);
	
	for(int v : ans)
		cout << v + 1 << " ";
	cout << 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>

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

using namespace std;

const int MOD = 998244353;

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

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

int 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() {
	long long d;
	scanf("%lld", &d);
	int q;
	scanf("%d", &q);
	
	vector<long long> primes;
	for (long long i = 2; i * i <= d; ++i) if (d % i == 0){
		primes.push_back(i);
		while (d % i == 0) d /= i;
	}
	if (d > 1){
		primes.push_back(d);
	}
	
	vector<int> fact(100), rfact(100);
	fact[0] = 1;
	for (int i = 1; i < 100; ++i)
		fact[i] = mul(fact[i - 1], i);
	rfact[99] = binpow(fact[99], MOD - 2);
	for (int i = 98; i >= 0; --i)
		rfact[i] = mul(rfact[i + 1], i + 1);
	
	forn(i, q){
		long long x, y;
		scanf("%lld%lld", &x, &y);
		vector<int> up, dw;
		for (auto p : primes){
			int cnt = 0;
			while (x % p == 0){
				--cnt;
				x /= p;
			}
			while (y % p == 0){
				++cnt;
				y /= p;
			}
			if (cnt < 0) dw.push_back(-cnt);
			else if (cnt > 0) up.push_back(cnt);
		}
		int ans = 1;
		ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]);
		for (auto it : up) ans = mul(ans, rfact[it]);
		ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]);
		for (auto it : dw) ans = mul(ans, rfact[it]);
		printf("%d\n", ans);
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;
const li INF64 = li(1e18);
const int N = 500043;

li f[N];

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

void inc(int x, li d)
{
    for (; x < N; x = (x | (x + 1)))
        f[x] += d;    
}

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

li dp[N];
int a[N], b[N], p[N];
int n, m;

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

    for(int i = 0; i < n; i++)
        dp[i] = -INF64;
    map<int, vector<int> > pos;
    for(int i = 0; i < n; i++)
        pos[a[i]].push_back(i);
    set<pair<int, int> > q;
    for(int i = 0; i < n; i++)
        q.insert(make_pair(a[i], i));
    
    for(auto x : pos[b[0]])
        dp[x] = p[x];
    while(!q.empty() && q.begin()->first <= b[0])
    {
        int k = q.begin()->second;
        q.erase(q.begin());
        if(p[k] > 0)
            inc(k, p[k]);
    }  

    for(int i = 1; i < m; i++)
    {
        int i1 = b[i - 1], i2 = b[i];
        vector<int> both_pos;
        for(auto x : pos[i1])
            both_pos.push_back(x);
        for(auto x : pos[i2])
            both_pos.push_back(x);
        li best = -INF64;
        int last = -1;
        sort(both_pos.begin(), both_pos.end());
        for(auto x : both_pos)
        {
            best += get(last + 1, x);
            last = x;
            if(a[x] == i1)
                best = max(best, dp[x]);
            else
                dp[x] = best + p[x];
        }
        while(!q.empty() && q.begin()->first <= i2)
        {
            int k = q.begin()->second;
            q.erase(q.begin());
            if(p[k] > 0)
                inc(k, p[k]);
        }
    }

    li best_dp = -INF64;
    for(int i = 0; i < n; i++)
        if(a[i] == b[m - 1])
            best_dp = max(best_dp, dp[i] + get(i + 1, n - 1));
    li ans = 0;
    for(int i = 0; i < n; i++)
        ans += p[i];
    ans -= best_dp;
    if(ans > li(1e15))
        puts("NO");
    else     
        printf("YES\n%lld\n", ans);
    
}

#include<bits/stdc++.h>

using namespace std;

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

const int LOGN = 20;
const int N = (1 << LOGN);

typedef long double ld;
typedef long long li;

const ld PI = acos(-1.0);

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

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

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

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

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

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

void precalc() 
{
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, comp());
        for(int k = 0; k < (1 << st); k++) 
        {
            double ang = PI / (1 << st) * k;
            w[st][k] = comp(cos(ang), sin(ang));
        }
        
        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(comp a[N], int n, int ln, bool inv) 
{
    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++) 
            {
                comp l = a[pos];
                comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
                
                a[pos] = l + r;
                a[pos + len] = l - r;
            }
        }
    }
    
    if(inv) for(int i = 0; i < n; i++)
        a[i] = a[i] / n;
}

comp aa[N];
comp bb[N];
comp cc[N];

inline void multiply(comp a[N], int sza, comp b[N], int szb, comp 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] : comp());
    for(int i = 0; i < n; i++)
        bb[i] = (i < szb ? b[i] : comp());
        
    fft(aa, n, ln, false);
    fft(bb, n, ln, false);
    
    for(int i = 0; i < n; i++)
        cc[i] = aa[i] * bb[i];
        
    fft(cc, n, ln, true);
    
    szc = n;
    for(int i = 0; i < n; i++)
        c[i] = cc[i];
}

comp a[N];
comp b[N];
comp c[N];

vector<int> p_function(const vector<int>& v)
{
    int n = v.size();
    vector<int> p(n);
    for(int i = 1; i < n; i++)
    {
        int j = p[i - 1];
        while(j > 0 && v[j] != v[i])
            j = p[j - 1];
        if(v[j] == v[i])
            j++;
        p[i] = j;   
    }
    return p;
}

int p[26];
char buf[N];
string s, t;

int main()
{
    precalc();                  
    for(int i = 0; i < 26; i++)
    {
        scanf("%d", &p[i]);
        p[i]--;
    }
    scanf("%s", buf);
    s = buf;
    scanf("%s", buf);
    t = buf;

    int n = s.size();
    int m = t.size();
    vector<int> color(26, 0);
    vector<vector<int> > cycles;
    for(int i = 0; i < 26; i++)
    {
        if(color[i])
            continue;
        vector<int> cycle;
        int cc = cycles.size() + 1;
        int cur = i;
        while(color[cur] == 0)
        {
            cycle.push_back(cur);
            color[cur] = cc;
            cur = p[cur];
        }
        cycles.push_back(cycle);
    }

    vector<int> ans(m - n + 1);
    vector<int> s1, t1;
    for(int i = 0; i < n; i++)
        s1.push_back(color[int(s[i] - 'a')]);
    for(int i = 0; i < m; i++)
        t1.push_back(color[int(t[i] - 'a')]);
    vector<int> st = s1;
    st.push_back(0);
    for(auto x : t1)
        st.push_back(x);
    vector<int> pf = p_function(st);
    for(int i = 0; i < m - n + 1; i++)
        if(pf[2 * n + i] == n)
            ans[i] = 1;
    map<char, comp> m1, m2;
    for(auto cur : cycles)
    {
        int k = cur.size();
        for(int i = 0; i < k; i++)
        {
            ld ang1 = 2 * PI * i / k;
            ld ang2 = (PI - 2 * PI * i) / k;
            m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1));
            m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2));
        }
    }

    ld ideal = 0;
    for(int i = 0; i < n; i++)
        ideal += (m1[s[i]] * m2[s[i]]).x;
    reverse(s.begin(), s.end());
    for(int i = 0; i < n; i++)                  
        a[i] = m1[s[i]];                
    for(int i = 0; i < m; i++)
        b[i] = m2[t[i]];
    int szc;
    multiply(a, n, b, m, c, szc);
    for(int i = 0; i < m - n + 1; i++)
        if(fabsl(c[i + n - 1].x - ideal) > 0.01)
            ans[i] = 0;
    

    for(int i = 0; i < m - n + 1; i++)
        printf("%d", ans[i]);
    return 0;
}

for i in range(int(input())):
    n, k = map(int, input().split())
    print('YES' if k * k <= n and n % 2 == k % 2 else 'NO')

from sys import stdin, stdout

t = int(stdin.readline())
for _ in range(t):
    n = int(stdin.readline())
    used = [False for i in range(n)]
    v = -1
    for i in range(n):
        l = [int(x) - 1 for x in stdin.readline().split()][1:]
        for j in l:
            if not used[j]:
                used[j] = True
                break
        else:
            v = i
    if v == -1:
        stdout.write("OPTIMAL\n")
    else:
        u = used.index(False)
        stdout.write("IMPROVE\n" + str(v + 1) + " " + str(u + 1) + "\n")

n, m, _ = map(int, input().split())

print(2 * (n - 1) + (n + 1) * (m - 1))
print("U" * (n - 1) + "L" * (m - 1), end="")
for i in range(n):
    if i != 0:
        print("D", end="")
    if i % 2 == 0:
        print("R" * (m - 1), end="")
    else:
        print("L" * (m - 1), end="")

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n;
vector<int> p, c;

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

inline void solve() {
    vector<int> used(n, 0);
    
    int ans = INF;
    fore(st, 0, n) {
        if(used[st])
            continue;
        
        vector<int> cycle;
        int v = st;
        while(!used[v]) {
            used[v] = 1;
            cycle.push_back(v);
            v = p[v];
        }
        
        fore(step, 1, sz(cycle) + 1) {
            if(sz(cycle) % step != 0)
                continue;
            
            fore(s, 0, step) {
                bool eq = true;
                for(int pos = s; pos + step < sz(cycle); pos += step) {
                    if(c[cycle[pos]] != c[cycle[pos + step]])
                        eq = false;
                }
                if(eq) {
                    ans = min(ans, step);
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

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

MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
    p[i] = (p[i - 1] * 10) % MOD

n = int(input())
for i in range(1, n):
    res = 2 * 10 * 9 * p[n - i - 1]
    res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
    print(res % MOD, end = ' ')
print(10)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#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)

typedef pair<int, int> pt;

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

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

int ones[N];
int mx[N], sum[N];

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

int calc(int t) {
    memset(ones, 0, sizeof(ones));
    memset(mx, -1, sizeof(mx));
    
    forn(i, m) {
        int l = q[i].x.x, r = q[i].x.y;
        if (q[i].y & (1 << t)) {
            ones[l]++;
            ones[r + 1]--;
        } else {
            mx[r] = max(mx[r], l);
        }
    }
    
    int j = -1;
    forn(i, n) {
        int cur = 0;
        if (!ones[i]) {
            cur = sum[i];
            if (j == -1) cur = add(cur, 1);
            else cur = add(cur, -sum[j]);
        }
        
        sum[i + 1] = add(sum[i], cur);
        ones[i + 1] += ones[i];
        j = max(j, mx[i]);
    }
    
    return add(sum[n], j != -1 ? -sum[j] : 1);
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    forn(i, m) {
        scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
        --q[i].x.x; --q[i].x.y;
    }
    
    int ans = 1;
    forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
    printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 8000043;
const int K = 15;
const int M = 1043;

int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;

map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];

int get_nxt(int x, char c)
{
    if(!nxt[x].count(c))
    {
        p[ts] = x;
        pchar[ts] = c;
        nxt[x][c] = ts++;
    }
    return nxt[x][c];
}

void add_string(int i)
{
    int cur = 0;
    for(auto x : t[i])
    {
        cur = get_nxt(cur, x);
    }
    term[cur] += c[i];
}

int get_go(int x, char c);

int get_lnk(int x)
{
    if(lnk[x] != -1)
        return lnk[x];
    if(x == 0 || p[x] == 0)
        return lnk[x] = 0;
    return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}

int get_dp(int x)
{
    if(dp[x] != -1)
        return dp[x];
    dp[x] = term[x];
    if(get_lnk(x) != x)
        dp[x] += get_dp(get_lnk(x));
    return dp[x];
}

int get_go(int x, char c)
{
    if(go[x].count(c))
        return go[x][c];
    if(nxt[x].count(c))
        return go[x][c] = nxt[x][c];
    if(x == 0)
        return go[x][c] = 0;
    return go[x][c] = get_go(get_lnk(x), c);
}

void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{                     
    sA = vector<int>(ts);
    for(int i = 0; i < ts; i++)
        sA[i] = i;
    sF = vector<long long>(ts);
    for(auto c : s)
    {
        int ci = int(c - 'a');
        for(int i = 0; i < ts; i++)
        {
            sF[i] += F[sA[i]][ci];
            sA[i] = A[sA[i]][ci];
        }
    }
}

long long solve(const string& s)
{
    long long BAD = (long long)(-1e18);

    vector<int> pos;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == '?')
            pos.push_back(i);
    int cntQ = pos.size();
    vector<vector<int> > skip_A(cntQ + 1);
    vector<vector<long long> > skip_F(cntQ + 1);
    build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
    for(int i = 1; i < cntQ; i++)
        build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
    build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);

    vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
    vector<int> used(1 << K);
    dp[0][skip_A[0][0]] = skip_F[0][0];
    queue<int> q;
    q.push(0);
    used[0] = 1;
    long long ans = BAD;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        int step = __builtin_popcount(k);
        if(step == cntQ)
        {
            for(int i = 0; i < ts; i++)
                ans = max(ans, dp[k][i]);
            continue;
        }
        for(int i = 0; i < K - 1; i++)
        {
            if(k & (1 << i)) continue;
            int nk = (k ^ (1 << i));
            if(used[nk] == 0)
            {
                used[nk] = 1;
                q.push(nk);
            }
            for(int j = 0; j < ts; j++)
            {
                if(dp[k][j] == BAD)
                    continue;
                int nj = get_go(j, char('a' + i));
                int newSt = skip_A[step + 1][nj];
                long long add = get_dp(nj) + skip_F[step + 1][nj];
                dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
            }
        }
    }
    return ans;
}

int main()
{
    scanf("%d", &k);
    t.resize(k);
    c.resize(k);
    for(int i = 0; i < k; i++)
    {
        scanf("%s %d", buf2, &c[i]);
        t[i] = buf2;
    }    
    scanf("%s", buf);
    s = buf;

    for(int i = 0; i < k; i++)
        add_string(i);
    for(int i = 0; i < ts; i++)
    {
        lnk[i] = -1;
        dp[i] = -1;
    }
    for(int i = 0; i < ts; i++)
    {
        get_lnk(i);
        for(char c = 'a'; c <= 'o'; c++)
            get_go(i, c);
    }
    for(int i = 0; i < ts; i++)
        get_dp(i);                               
    for(int i = 0; i < ts; i++)
    {
        for(int j = 0; j < K; j++)
        {
            A[i][j] = get_go(i, char('a' + j));
            F[i][j] = dp[A[i][j]];
        }
    }   
    int n = s.size();
    vector<int> leftQ(n, -1);
    vector<int> rightQ(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(i != 0)
            leftQ[i] = leftQ[i - 1];
        if(s[i] == '?')
            leftQ[i] = i;
    }
    for(int i = n - 1; i >= 0; i--)
    {
        if(i != n - 1)
            rightQ[i] = rightQ[i + 1];
        if(s[i] == '?')
            rightQ[i] = i;
    }
    vector<int> bad(n, 0);
    
    if(leftQ.back() == -1)
        bad = vector<int>(n, 1);

    long long ans = 0;
    int curSt = 0;
    string news = "";
    for(int i = 0; i < n; i++)
    {
        int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
        if(bad[i])
            ans += F[curSt][ci];
        curSt = A[curSt][ci];
        if(!bad[i])
            news.push_back(s[i]);
        else if(i != 0 && !bad[i - 1])
            news.push_back('o');
    }                    
    if(!news.empty())
        ans += solve(news);
    printf("%lld\n", ans);
}

for i in range(int(input())):
    n, m = map(int, input().split())
    print('YES' if n % m == 0 else 'NO')

for t in range(int(input())):
    n = input()
    print(*sorted(map(int, input().split()))[::-1])

fun main() {
    val T = readLine()!!.toInt()
    testCases@for (tc in 1..T) {
        val (_, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray()

        var maxPower = 1L
        while (maxPower < 1e16.toLong())
            maxPower *= k

        while (maxPower > 0) {
            val positions = a.withIndex().filter { it.value >= maxPower }.map { it.index }
            if (positions.isNotEmpty()) {
                if (positions.size > 1) {
                    println("NO")
                    continue@testCases
                }
                a[positions[0]] -= maxPower
            }
            maxPower /= k
        }
        if (a.max()!! > 0L) {
            println("NO")
            continue@testCases
        }
        println("YES")
    }
}

fun getMask(a: Long, k: Long): Long? {
    var (tmp, res) = listOf(a, 0L)
    var cnt = 0
    while (tmp > 0) {
        if (tmp % k > 1)
            return null
        res = res or ((tmp % k) shl cnt)
        tmp /= k
        cnt++
    }
    return res
}

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
        val b = a.filterNotNull()
        if (b.size < n) {
            println("NO")
            continue
        } else {
            val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
            println(if (res < 0) "NO" else "YES")
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int MOD = 998244353;

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

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

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

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

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

int fact[N];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

int C(int n, int k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main() 
{
    precalc();
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if(n > 2)
        ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
    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 long double ld;
typedef pair<int, int> pt;

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

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

const int N = 555;
int n, a[N];

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

int dp[N][N];

int calcDP(int l, int r) {
    assert(l < r);
    if(l + 1 == r)
        return dp[l][r] = a[l];
    if(dp[l][r] != 0)
        return dp[l][r];
    
    dp[l][r] = -1;
    fore(mid, l + 1, r) {
        int lf = calcDP(l, mid);
        int rg = calcDP(mid, r);
        if(lf > 0 && lf == rg)
            return dp[l][r] = lf + 1;
    }
    return dp[l][r];
}

int dp2[N];

inline void solve() {
    fore(i, 0, N)
        dp2[i] = INF;
    
    dp2[0] = 0;
    fore(i, 0, n) {
        fore(j, i + 1, n + 1) {
            if(calcDP(i, j) > 0)
                dp2[j] = min(dp2[j], dp2[i] + 1);
        }
    }
    cout << dp2[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;

const int N = 300043;
const int K = 5;

int x, y, z, n;
long long a[N];

typedef vector<vector<int> > state;
map<state, int> d;
int cnt;
int p;
vector<vector<int> > state_log;

int mex(const vector<int>& a)
{
    for(int i = 0; i < a.size(); i++)
    {
        bool f = false;
        for(auto x : a)
            if(x == i)
                f = true;
        if(!f)
            return i;
    }
    return a.size();
}

state go(state s)
{
    int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
    int f2 = mex({s[0][K - x], s[2][K - z]});
    int f3 = mex({s[0][K - x], s[1][K - y]});
    state nw = s;
    nw[0].push_back(f1);
    nw[1].push_back(f2);
    nw[2].push_back(f3);
    for(int i = 0; i < 3; i++)
        nw[i].erase(nw[i].begin());
    return nw;
}

void precalc()
{
    d.clear();
    state cur(3, vector<int>(K, 0));
    cnt = 0;
    state_log.clear();
    while(!d.count(cur))
    {
        d[cur] = cnt;
        state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
        cur = go(cur);
        cnt++;
    }                   
    p = cnt - d[cur];
}

int get_grundy(long long x, int t)
{
    if(x < cnt)
        return state_log[x][t];
    else
    {
        int pp = cnt - p;
        x -= pp;
        return state_log[pp + (x % p)][t];
    }
}

void read()
{
    scanf("%d %d %d %d", &n, &x, &y, &z);
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
}                    

int check(int x, int y)
{
    return x == y ? 1 : 0;
}

void solve()
{
    precalc();
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans ^= get_grundy(a[i], 0);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        ans ^= get_grundy(a[i], 0);
        res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
        res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
        res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
        ans ^= get_grundy(a[i], 0);
    }
    printf("%d\n", res);
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;

map<char, int> nxt[N];
bool term[N];
int n, k;
char buf[3];
int dp[N];
int dict[N];

int T[4 * N];
int f[4 * N];

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

int getVal(int v)
{
    return T[v] + f[v];
}

void push(int v, int l, int r)
{
    T[v] += f[v];
    if(l != r - 1)
    {
        f[v * 2 + 1] += f[v];
        f[v * 2 + 2] += f[v];
    }
    f[v] = 0;
}

void upd(int v, int l, int r)
{
    if(l != r - 1)
    {
        T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
    }
}

int get(int v, int l, int r, int L, int R)
{
    if(L >= R)
        return int(1e9);
    if(l == L && r == R)
        return getVal(v);
    push(v, l, r);
    int m = (l + r) / 2;
    int ans = min(get(v * 2 + 1, l, m, L, min(m, R)), get(v * 2 + 2, m, r, max(L, m), R));
    upd(v, l, r);
    return ans;
}

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

void setVal(int v, int l, int r, int pos, int val)
{
    if(l == r - 1)
    {
        f[v] = 0;
        T[v] = val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    if(pos < m)
        setVal(v * 2 + 1, l, m, pos, val);
    else
        setVal(v * 2 + 2, m, r, pos, val);
    upd(v, l, r);
}

void dfs(int v, int d, int last)
{
    dp[v] = last + 1;
    if(term[v])
        dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
    setVal(0, 0, n + 1, d, dp[v] + 1);
    if(term[v])
        add(0, 0, n + 1, 0, d + 1, 1);
    for(auto x : nxt[v])
        dfs(x.second, d + 1, dp[v]);
    setVal(0, 0, n + 1, d, int(1e9));
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        int p;
        scanf("%d %s", &p, buf);
        char c = buf[0];
        nxt[p][c] = i + 1;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d", &dict[i]);
        term[dict[i]] = true;
    }

    build(0, 0, n + 1);
    dfs(0, 0, -1);
    for(int i = 0; i < k; i++)
        printf("%d ", dp[dict[i]]);
    puts("");
}

for t in range(int(input())):
    print(input().strip('0').count('0'))

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
        
        val needG = (n + 1) / 2
        var totalG = needG / g * (b + g)
        totalG += if (needG % g == 0L) -b else needG % g
        println(maxOf(n, totalG))
    }
}

#include <bits/stdc++.h>

using namespace std;

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

void solve() {
    string s;
    cin >> s;

    vector<bool> used(26);
    used[s[0] - 'a'] = true;
    string t(1, s[0]);
        
    int pos = 0;
    for (int i = 1; i < sz(s); i++) {
        if (used[s[i] - 'a']) {
            if (pos > 0 && t[pos - 1] == s[i]) {
                pos--;
            } else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        } else {
            if (pos == 0) {
                t = s[i] + t;
            } else if (pos == sz(t) - 1) {
                t += s[i];
                pos++;
            } else {
                cout << "NO" << endl;
                return;
            }
        }
        used[s[i] - 'a'] = true;
    }
        
    forn(i, 26) if (!used[i])
        t += char(i + 'a');
    cout << "YES" << endl << t << endl;
}

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

from math import log2

for t in range(int(input())):
    n, m = map(int, input().split())
    c = [0] * 61
    s = 0
    for x in map(int, input().split()):
        c[int(log2(x))] += 1
        s += x

    if s < n:
        print(-1)
        continue

    i, res = 0, 0
    while i < 60:
        if (1<<i)&n != 0:
            if c[i] > 0:
                c[i] -= 1
            else:
                while i < 60 and c[i] == 0:
                    i += 1
                    res += 1
                c[i] -= 1
                continue
        c[i + 1] += c[i] // 2
        i += 1

    print(res)

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

string s, t;

inline bool read() {
    if(!(cin >> s >> t))
        return false;
    for(auto &c : s)
        c -= 'a';
    for(auto &c : t)
        c -= 'a';
    return true;
}

vector< vector<int> > nxt;

bool calc(const string &a, const string &b) {
    vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
    dp[0][0] = 0;
    fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
        if(dp[i][j] > sz(s))
            continue;
        
        int len = dp[i][j];
        if(i < sz(a) && nxt[len][a[i]] < INF) {
            dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
        }
        if(j < sz(b) && nxt[len][b[j]] < INF) {
            dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
        }
    }
    return dp[sz(a)][sz(b)] < INF;
}

inline void solve() {
    nxt.assign(sz(s) + 1, vector<int>(26, INF));
    for(int i = sz(s) - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i]] = i;
    }
    
    for(int i = 0; i < sz(t); i++) {
        if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << 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;

#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)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)

typedef pair<int, int> pt;

const int M = 310;
const int N = 2000 * 1000 + 13;

int n, m, q;
int a[M][M];

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

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

int p[M * M], rk[M * M];

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

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

int dif[N];
vector<pt> add[N], del[N];

void recalc(const vector<pt>& ev, int coeff)  {
    forn(i, n) forn(j, m) a[i][j] = 0;
    forn(i, n * m) p[i] = i, rk[i] = 1;
        
    for (auto it : ev) {
        int cur = 1;
        int x = it.x / m, y = it.x % m;
        a[x][y] = 1;
        
        forn(k, 4) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (in(nx, ny) && a[nx][ny] == 1)
                cur -= unite(nx * m + ny, x * m + y);
        }
        
        dif[it.y] += cur * coeff;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    int clrs = 1;
    forn(i, q) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        --x; --y;
        if (a[x][y] == c) continue;
        clrs = c + 1;
        add[c].pb(mp(x * m + y, i));
        del[a[x][y]].pb(mp(x * m + y, i));
        a[x][y] = c;
    }
    
    forn(x, n) forn(y, m)
        del[a[x][y]].pb(mp(x * m + y, q));
    
    forn(i, clrs) reverse(all(del[i]));
    
    forn(i, clrs) recalc(add[i], +1);
    forn(i, clrs) recalc(del[i], -1);
    
    int cur = 1;
    forn(i, q) {
        cur += dif[i];
        printf("%d\n", cur);
    }
}

#include<bits/stdc++.h>

using namespace std;

const int N = 150043;

typedef pair<long long, long long> func;

func T[4 * N];
bool usedT[4 * N];

void clear(int v, int l, int r)
{
    if(!usedT[v]) return;
    usedT[v] = false;
    T[v] = make_pair(0ll, 0ll);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        clear(v * 2 + 1, l, m);
        clear(v * 2 + 2, m, r);
    }
}

long long eval(func f, int x)
{
    return f.first * x + f.second;
}

long long get(int v, int l, int r, int x)
{
    long long ans = eval(T[v], x);
    if(l < r - 1)
    {
        int m = (l + r) / 2;
        if(m > x)
            ans = max(ans, get(v * 2 + 1, l, m, x));
        else
            ans = max(ans, get(v * 2 + 2, m, r, x));
    }
    return ans;
}

void upd(int v, int l, int r, func f)
{
    usedT[v] = true;
    int m = (l + r) / 2;
    bool need_swap = eval(f, m) > eval(T[v], m);
    if(need_swap)
        swap(T[v], f);
    if(l == r - 1)
        return;
    if(eval(f, l) > eval(T[v], l))
        upd(v * 2 + 1, l, m, f);
    else
        upd(v * 2 + 2, m, r, f);
}

long long ans = 0;

void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
    int n = heads.size();
    for(int i = 0; i < n; i++)
    {
        for(auto x : heads[i])
            ans = max(ans, get(0, 0, N, x.first) + x.second);
        for(auto x : tails[i])
            upd(0, 0, N, x);
    }
    clear(0, 0, N);
}

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

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

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

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

void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += curadd;
    sink.push_back(make_pair(cnt, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_heads(to, v, cnt, cursum, curadd, sink);
}

void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
    if(used[v])
        return;
    cnt++;
    curadd += a[v];
    cursum += a[v] * 1ll * cnt;
    sink.push_back(make_pair(curadd, cursum));
    for(auto to : g[v])
        if(to != p)
            dfs_tails(to, v, cnt, cursum, curadd, sink);
}

void centroid(int v)
{
    if(used[v]) return;
    dfs1(v);
    S = siz[v];
    c = make_pair(int(1e9), -1);
    find_centroid(v);
    int C = c.second;
    used[C] = 1;
    vector<vector<func> > heads, tails;
    for(auto to : g[C])
        if(!used[to])
        {
            heads.push_back(vector<func>());
            dfs_heads(to, C, 1, a[C], a[C], heads.back());
            tails.push_back(vector<func>());
            dfs_tails(to, C, 0, 0, 0, tails.back());
        }
    heads.push_back(vector<func>({{1, a[C]}}));
    tails.push_back(vector<func>({{0, 0}}));
    update_ans(heads, tails);
    reverse(heads.begin(), heads.end());
    reverse(tails.begin(), tails.end());
    update_ans(heads, tails);
    for(auto to : g[C])
        centroid(to);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);    
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    centroid(0);
    printf("%lld\n", ans);
}

t = int(input())
for i in range(t):
    n = int(input())
    if(n % 2 == 1):
        print(7, end='')
        n -= 3
    while(n > 0):
        print(1, end='')
        n -= 2
    print()

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

int n, x;
string s;

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

inline void solve() {
	int ans = 0;
	bool infAns = false;
	
	int cntZeros = (int)count(s.begin(), s.end(), '0');
	int total = cntZeros - (n - cntZeros);
	
	int bal = 0;
	for(int i = 0; i < n; i++) {
		if(total == 0) {
			if(bal == x)
				infAns = true;
		}
		else if(abs(x - bal) % abs(total) == 0) {
			if((x - bal) / total >= 0)
				ans++;
		}
		
		if(s[i] == '0')
			bal++;
		else
			bal--;
	}
	
	if(infAns) 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--) {
		read();
		solve();
	}
	
	return 0;
}

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

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

int tc;
string s, t;
int nxt[N][26];

int main() {
    cin >> tc;
    while(tc--){
        cin >> s >> t;
        for(int i = 0; i < s.size() + 5; ++i)
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = INF;
    	
        for(int i = int(s.size()) - 1; i >= 0; --i){
            for(int j = 0; j < 26; ++j)
                nxt[i][j] = nxt[i + 1][j];
            nxt[i][s[i] - 'a'] = i;
        }    
    
        int res = 1, pos = 0;
        for(int i = 0; i < t.size(); ++i){
            if(pos == s.size()){
                pos = 0;
                ++res;
            }
            if(nxt[pos][t[i] - 'a'] == INF){
                pos = 0; 
                ++res;
    		}
    		if(nxt[pos][t[i] - 'a'] == INF && pos == 0){
                res = INF;
                break;
            }    
            pos = nxt[pos][t[i] - 'a'] + 1;
            
        }
    
        if(res >= INF) cout << -1 << endl;
        else cout << res << endl;
    }
    return 0;
}

fun gcd(a : Long, b : Long) : Long {
    return if (a == 0L) b else gcd(b % a, a)
}
fun phi(a : Long) : Long {
    var (tmp, ans) = listOf(a, a)
    var d = 2L
    while (d * d <= tmp) {
        var cnt = 0
        while (tmp % d == 0L) {
            tmp /= d
            cnt++
        }
        if (cnt > 0) ans -= ans / d
        d++
    }
    if (tmp > 1L) ans -= ans / tmp
    return ans
}

fun main() {
    val t = readLine()!!.toInt()
    for (tc in 1..t) {
        val (a, m) = readLine()!!.split(' ').map { it.toLong() }
        println(phi(m / gcd(a, m)))
    }
}

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

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

int n;
int p[N];
int rp[N];
int a[N];

long long b[N];
long long t[4 * N];
long long add[4 * N];

void build(int v, int l, int r){
	if(r - l == 1){
		t[v] = b[l];
		return;
	}

	int mid = (l + r) / 2;	
	build(v * 2 + 1, l, mid);
	build(v * 2 + 2, mid, r);
	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]); 
}

void push(int v, int l, int r){
	if(add[v] != 0){
		if(r - l > 1)
			for(int i = v+v+1; i < v+v+3; ++i){
				add[i] += add[v];
				t[i] += add[v];
			}
		add[v] = 0;
	}
}

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

	t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

void upd(int l, int r, int x){
	upd(0, 0, n, l, r, x);
}

long long get(int v, int l, int r, int L, int R){
	if(L >= R) return 1e18;

	push(v, l, r);
	if(l == L && r == R)
		return t[v];

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

long long get(int l, int r){
	return get(0, 0, n, l, r);
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", p + i);
        --p[i];
        rp[p[i]] = i;
	}
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);
	
	b[0] = a[0];
	for(int i = 1; i < n; ++i)
		b[i] = a[i] + b[i - 1];
	build(0, 0, n);
	
	long long res = get(0, n - 1);
	//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	for(int i = 0; i < n; ++i){
	    int pos = rp[i];
		upd(pos, n, -a[pos]);
		upd(0, pos, a[pos]);
		res = min(res, get(0, n - 1));
		//for(int i = 0; i < n; ++i) cout << get(i, i+1) << ' ';cout << endl;
	}
	
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

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

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

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

typedef vector<int> poly;

void norm(poly& p)
{
    while(p.size() > 0 && p.back() == 0)
        p.pop_back();
}

poly operator +(const poly& a, const poly& b)
{
    poly c = a;
    while(c.size() < b.size()) c.push_back(0);
    for(int i = 0; i < b.size(); i++) c[i] = add(c[i], b[i]);
    norm(c);
    return c;
}

poly operator +(const poly& a, int b)
{
    return a + poly(1, b);
}

poly operator +(int a, const poly& b)
{
    return b + a;
}

poly operator *(const poly& a, int b)
{
    poly c = a;                               
    for(int i = 0; i < c.size(); i++) c[i] = mul(c[i], b);
    norm(c);
    return c;
}

poly operator /(const poly& a, int b)
{   
    return a * inv(b);
}

poly operator *(const poly& a, const poly& b)
{
    poly c(a.size() + b.size() - 1);
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
            c[i + j] = add(c[i + j], mul(a[i], b[j]));

    norm(c);
    return c;
}

poly interpolate(const vector<int>& x, const vector<int>& y)
{
    int n = int(x.size()) - 1;
    vector<vector<int> > f(n + 1);
    f[0] = y;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n - i; j++)
            f[i].push_back(divide(add(f[i - 1][j + 1], -f[i - 1][j]), add(x[i + j], -x[j])));
    
    poly cur = poly(1, 1);
    poly res;
    for(int i = 0; i <= n; i++)
    {
        res = res + cur * f[i][0];
        cur = cur * poly({add(0, -x[i]), 1});
    }

    return res;
}

int eval(const poly& a, int x)
{
    int res = 0;
    for(int i = int(a.size()) - 1; i >= 0; i--)
        res = add(mul(res, x), a[i]);
    return res;
}

poly sumFromL(const poly& a, int L, int n)
{
    vector<int> x;
    for(int i = 0; i <= n; i++)
        x.push_back(L + i);
    vector<int> y;
    int cur = 0;
    for(int i = 0; i <= n; i++)
    {
        cur = add(cur, eval(a, x[i]));
        y.push_back(cur);
    }
    return interpolate(x, y);
}

int sumOverSegment(const poly& a, int L, int R)
{
    return eval(sumFromL(a, L, a.size()), R - 1);
}

int main() {
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    for(int i = 0; i < n; i++)
    {
        cin >> L[i] >> R[i];
        R[i]++;
    }
    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    vector<int> coord = {0, MOD - 2};
    for(int i = 0; i < n; i++)
    {
        coord.push_back(L[i]);
        coord.push_back(R[i]);
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    vector<int> cL = coord, cR = coord;
    cL.pop_back();
    cR.erase(cR.begin());
    int cnt = coord.size() - 1;
    vector<poly> cur(cnt);
    for(int i = 0; i < cnt; i++)
        if(cL[i] >= L[0] && cR[i] <= R[0])
            cur[i] = poly(1, inv(R[0] - L[0]));
    for(int i = 1; i < n; i++)
    {
        vector<poly> nxt(cnt);        
        int curSum = 0;
        for(int j = 0; j < cnt; j++)
        {
            nxt[j] = sumFromL(cur[j], cL[j], i) + curSum;
            curSum = add(curSum, sumOverSegment(cur[j], cL[j], cR[j]));    
        }
        for(int j = 0; j < cnt; j++)
            nxt[j] = nxt[j] * (cL[j] >= L[i] && cR[j] <= R[i] ? inv(R[i] - L[i]) : 0);
        cur = nxt;
    }
    int ans = 0;
    for(int i = 0; i < cnt; i++)
        ans = add(ans, sumOverSegment(cur[i], cL[i], cR[i]));

    cout << ans << endl;
}