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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

using li = long long;

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

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

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

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

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

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

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

int ans;

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

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

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

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

using li = long long;

const int MAXLEN = 5;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

using li = long long;

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

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

const int MOD = 998244353;

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

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

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

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

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

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

import java.util.*

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

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

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

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

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

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

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

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

vector<int> d;

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

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

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

typedef unsigned long long uli;

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n;
li m1, m2;

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

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

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

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

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

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

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

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

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

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

	int cnt = 0;
	int xorSum = 0;
	fore (i, 0, sz(ans)) {
		cnt += ans[i] > 0;
		xorSum ^= ans[i];
	}
	
//	cout << sz(ans) << endl;
//	cout << ans << endl;
	cout << cnt << " " << xorSum << endl;
}

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

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

int varMul(int x)
{
    return x;
}

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

const int ZERO = 100000;

int dp[2][ZERO * 2];

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

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

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

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

#include <bits/stdc++.h>

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

using namespace std;


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

#include<bits/stdc++.h>

using namespace std;

const int N = 5043;

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

vector<int> ans;

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

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

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

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

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

	fore (i, 0, m)
		cout << ans[i] << '\n';
}

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

vector<int> ans;

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

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

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

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

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

	fore (i, 0, m)
		cout << ans[i] << '\n';
}

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

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

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

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

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

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

const int N = 143;
int n;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

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

using namespace std;


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

#include <bits/stdc++.h>

#define f first
#define s second

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

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

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

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

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


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

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

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

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

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

    tout[v] = T;
}

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

    Query() {};
};

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

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

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

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

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

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

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

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

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

        v--;
        u--;

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

    dfs1(0, -1, 0);

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

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

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

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

        leaf[cur] = v;

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

        cur++;
    }

    dfs2(0);

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

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

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

    int q;
    cin >> q;

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

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

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

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

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

    sort(queries, queries + q, cmp);

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

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

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

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

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

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

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

mt19937 rnd(1);

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

    solve();
}

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

typedef long long li;

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

int mind[N];

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

int x, y;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

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

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

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

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

#include <bits/stdc++.h>     

using namespace std;

const int N = 243;

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

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

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

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

int n, m, s, t, v;

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

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

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

for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        input()
    print("NO" if n == m else "YES")

#include <bits/stdc++.h>

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

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, int>> a(m);
        forn(i, m){
            scanf("%d%d", &a[i].first, &a[i].second);
            --a[i].first, --a[i].second;
        }
        bool ans = false;
        forn(i, m) forn(x, n) forn(y, n) if ((x == a[i].first) ^ (y == a[i].second)){
            bool ok = true;
            forn(j, m) if (i != j){
                ok &= x != a[j].first && y != a[j].second;
            }
            ans |= ok;
        }
        puts(ans ? "YES" : "NO");
    }
}

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

        println(a.sum() + b.sum() - b.maxOrNull()!!)
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int ans = 0;
    for (int k = 1; k <= n; ++k) {
      multiset<int> s(a.begin(), a.end());
      for (int i = 0; i < k; ++i) {
        auto it = s.upper_bound(k - i);
        if (it == s.begin()) break;
        s.erase(--it);
        if (!s.empty()) {
          int x = *s.begin();
          s.erase(s.begin());
          s.insert(x + k - i);
        }
      }
      if (s.size() + k == n) ans = k;
    }
    cout << ans << '\n';
  }
}

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

const int MOD = 998244353;

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

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

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

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

bool prime(int x)
{
    for(int i = 2; i * 1ll * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;    
}

int main()
{
    int n;
    long long m;
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = add(ans, binpow(m % MOD, i));
    long long cur = 1;
    int cnt = 1;
    for(int i = 1; i <= n; i++)
    {
        if(cur > m) continue;
        if(prime(i)) cur *= i;
        cnt = mul(cnt, (m / cur) % MOD);
        ans = sub(ans, cnt);
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

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

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (auto &it : s) cin >> it;
    
    auto in = [&](int x, int y) {
      return 0 <= x && x < n && 0 <= y && y < m;
    };
    
    auto can = [&](int x, int y) {
      if (!in(x, y)) return false;
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == '#')
          return false;
      }
      return true;
    };
    
    vector<vector<int>> d(n, vector<int>(m, INF)), p(n, vector<int>(m));
    deque<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        if (s[i][0] == '#') {
          d[i][0] = 0;
          q.push_front({i, 0});
        } else if (can(i, 0)) {
          d[i][0] = 1;
          q.push_back({i, 0});
        }
    }
    
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop_front();
      for (int i = 4; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (!can(nx, ny)) continue;
        int w = (s[nx][ny] != '#');
        if (d[nx][ny] > d[x][y] + w) {
          d[nx][ny] = d[x][y] + w;
          p[nx][ny] = i;
          if (w) q.push_back({nx, ny});
          else q.push_front({nx, ny});
        }
      }
    }
    
    int x = 0, y = m - 1;
    for (int i = 0; i < n; ++i) if (d[x][y] > d[i][y])
      x = i;
    if (d[x][y] == INF) {
      cout << "NO\n";
      continue;
    }
    while (true) {
      s[x][y] = '#';
      int i = p[x][y];
      if (!i) break;
      x -= dx[i];
      y -= dy[i];
    }
    cout << "YES\n";
    for (auto it : s) cout << it << '\n';
  }
}

#include<bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

void build(int v, int pr) {
    tin[v] = T++;
    p[0][v] = pr;
    fore (pw, 1, LOG)
        p[pw][v] = p[pw - 1][p[pw - 1][v]];
    
    for (int to : g[v]) {
        if (to == pr)
            continue;
        build(to, v);
    }
    tout[v] = T;
}

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

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

const int D = 21;
struct Fenwick {
    int n;
    vector<int> F;
    void init(int nn) {
        n = nn;
        F.assign(n, 0);
    }
    
    void add(int pos, int val) {
        for (; pos < n; pos |= pos + 1)
            F[pos] += val;
    }
    int sum(int pos) {
        int ans = 0;
        for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
            ans += F[pos];
        return ans;
    }
    int getSum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
};

struct DS {
    Fenwick f;
    void init(int n) {
        f.init(n);
    }
    
    void addPath(int v, int l, int k) {
        f.add(tin[v], +k);
        f.add(tin[l], -k);
    }
    int getVertex(int v) {
        return f.getSum(tin[v], tout[v]);
    }
    
    void addVertex(int v, int k) {
        f.add(tin[v], +k);
        if (p[0][v] != v)
            f.add(tin[p[0][v]], -k);
    }
};

DS t[D];

inline void solve() {
    fore (i, 0, D) {
        g[n - 1 + i].push_back(n + i);
        g[n + i].push_back(n - 1 + i);
    }
    int root = n + D - 1;
    
    build(root, root);
    fore (i, 0, D)
        t[i].init(root + 1);
    
    int m; cin >> m;
    fore(_, 0, m) {
        int tp; cin >> tp;
        if (tp == 1) {
            int v; cin >> v;
            v--;
            
            int ans = 0;
            for (int i = 0, cur = v; i < D; i++, cur = p[0][cur])
                ans += t[i].getVertex(cur);
            cout << ans << endl;
        } 
        else {
            assert(tp == 2);

            int u, v, k, d;
            cin >> u >> v >> k >> d;
            u--, v--;
            
            int l = lca(u, v);
            
            if (u != l)
                t[d].addPath(u, l, k);
            if (v != l)
                t[d].addPath(v, l, k);
            
            for (int i = 0; i <= d; i++, l = p[0][l]) {
                t[d - i].addVertex(l, k);
                if (d - i > 0)
                    t[d - i - 1].addVertex(l, k);
            }
        }
    }
}

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

for _ in range(int(input())):
	n = int(input())
	a = set(map(int, input().split()))
	ans = 0
	for i in range(10000):
		num = str(i)
		num = (4 - len(num)) * '0' + num
		used = set(num)
		if len(used) != 2:
			continue
		d1 = int(used.pop())
		d2 = int(used.pop())
		if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2:
			ans += 1
	print(ans)

#include <bits/stdc++.h>

using namespace std;

int n;

inline void read() {	
    cin >> n;
    int x;
    for (int i = 0; i < n; ++i)
        cin >> x;
}

inline int fac(int n) {
    int res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

inline int c(int n, int k) {
    return fac(n) / fac(k) / fac(n - k);
}

inline void solve() {
    cout << c(10 - n, 2) * c(4, 2) << endl;
}

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

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

void solve() 
{
    int n;
    cin >> n;
    cout << 1;
    for(int i = n; i >= 2; i--)
        cout << " " << i;
    cout << endl;
}

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

for _ in range(int(input())):
	n = int(input())
	s = '0' + input()
	a = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i <= n:
		mn = a[i]
		sm = a[i]
		j = i + 1
		while j <= n and s[j] == '1':
			mn = min(mn, a[j])
			sm += a[j]
			j += 1
		ans += sm - mn
		i = j
	print(ans)

#include<bits/stdc++.h>

using namespace std;

char buf[1000043];

string normalize(const string& v)
{
    int cnt = 0;
    while(cnt < v.size() && v[cnt] == '0') cnt++;
    if(cnt == v.size()) return "0";
    return v.substr(cnt, int(v.size()) - cnt);
}

string operator |(const string& a, const string& b)
{
    int sz = max(a.size(), b.size());
    string ans(sz, '0');
    for(int i = 0; i < a.size(); i++)
        if(a[i] == '1') ans[i + sz - int(a.size())] = '1';
    for(int i = 0; i < b.size(); i++)
        if(b[i] == '1') ans[i + sz - int(b.size())] = '1';    
    return normalize(ans);
}

bool better(const string& a, const string& b)
{
    if(a.size() != b.size()) return a.size() > b.size();
    return a > b;
}

int main()
{
    int n;
    scanf("%d", &n);
    string s;
    scanf("%s", buf);
    s = buf;
    string ans = s | s;
    int pos1 = s.find("1");
    if(pos1 != string::npos)
    {
        int pos2 = s.find("0", pos1);
        if(pos2 != string::npos)
        {
            int cur = pos1;
            int not_needed = 0;
            while(true)
            {                
                if(cur == n || (s[cur] == '1' && cur > pos2)) break;
                string nw = s | s.substr(pos1, n - pos1 - not_needed);
                if(better(nw, ans)) ans = nw;
                cur++;
                not_needed++;
            }
        }
    }
    puts(ans.c_str());
}

#include <bits/stdc++.h>

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

using namespace std;

const long long INF64 = 1e18;

int main() {
	vector<int> ps(2);
	vector<long long> ts(2);
	int h, s;
	forn(i, 2) scanf("%d%lld", &ps[i], &ts[i]);
	scanf("%d%d", &h, &s);
	long long ans = INF64;
	vector<long long> dp(h + 1, INF64);
	dp[0] = 0;
	forn(i, h) for (int j = 1; j <= h - i; ++j) forn(k, 2){
		int ni = min((long long)h, i + j * (ps[k] - s) + j * ts[k] / ts[k ^ 1] * (ps[k ^ 1] - s));
		if (ni == h)
			ans = min(ans, dp[i] + j * ts[k]);
		if (j * ts[k] >= ts[k ^ 1]){
			ni = min((long long)h, i + (j - 1) * (ps[k] - s) + (j * ts[k] / ts[k ^ 1] - 1) * (ps[k ^ 1] - s) + (ps[0] + ps[1] - s));
			dp[ni] = min(dp[ni], dp[i] + j * ts[k]);
		}
	}
	ans = min(ans, dp[h]);
	printf("%lld\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;

typedef array<int, 2> vec;
typedef array<vec, 2> mat;

const int MOD = 998244353;

mat operator*(const mat& a, const mat& b)
{
    mat c;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            c[i][j] = 0;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                c[i][k] = (a[i][j] * 1ll * b[j][k] + c[i][k]) % MOD;
    return c;
}

mat ZERO = {vec({3, 0}), vec({1, 2})};
mat ONE = {vec({1, 2}), vec({1, 2})};

mat t[4 * N];

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

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

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> v(N);
    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        v[l].push_back(make_pair(1, i));
        v[r + 1].push_back(make_pair(0, i));
    }    
    build(0, 0, n - 1);
    int cur = 0;
    int ans = 0;
    for(int i = 0; i <= 300000; i++)
    {
        for(auto x : v[i])
        {
            if(x.second == 0) cur = x.first;
            else upd(0, 0, n - 1, x.second - 1, x.first);
        }
        ans = (ans + t[0][cur][1]) % MOD;
    }
    cout << ans << endl;
}

#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 sub(int x, int y)
{
    return add(x, MOD - y);
}

int expected(int mask)
{
    if(mask & 2) return 0;
    return 1;
}

int last_bit(int x)
{
    if(x == 0) return -1;
    return x - (x & (x - 1));
}

bool go(int& a, int x)
{
    if(expected(a) != x)
    {
        a = 1 << x;
        return false;    
    }
    a ^= (1 << x);
    while(true)
    {
        int b = last_bit(a);
        int c = last_bit(a - b);
        if(c == 2 * b) a += b;
        else break;
    }
    return true;
}

bool is_fib(int a)
{
    return a == last_bit(a);
}

vector<pair<int, int>> go(const vector<pair<int, int>>& a, int x)
{
    vector<pair<int, int>> nw;
    for(auto b : a)
    {
        int cost = b.first;
        int seqn = b.second;
        if(go(seqn, x)) nw.push_back(make_pair(cost, seqn));
    }
    return nw;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int last = 1, sum = 1;
    vector<pair<int, int>> w;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(auto x : s)
        {
            int c = x - '0';
            int ndp = sub(sum, last);
            w = go(w, c);
            for(int j = 0; j < w.size(); j++)
            {
                if(is_fib(w[j].second))
                    ndp = sub(ndp, w[j].first);
            }
            if(c == 1) w.push_back(make_pair(last, 2));
            sum = add(sum, ndp);
            last = ndp;
            assert(w.size() <= 60);
        }
        cout << last << endl;
    }
}

for _ in range(int(input())):
	n, m = map(int, input().split())
	print(n // 2 + 1, m // 2 + 1)

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n, m;
		scanf("%d%d", &n, &m);
		int svx = 1, svy = 1;
		for (int x = 1; x <= n; ++x){
			for (int y = 1; y <= m; ++y){
				bool ok = true;
				for (int dx : {-2, -1, 1, 2}){
					for (int dy : {-2, -1, 1, 2}){
						if (abs(dx * dy) != 2) continue;
						if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m)
							ok = false;
					}
				}
				if (ok){
					svx = x;
					svy = y;
				}
			}
		}
		printf("%d %d\n", svx, svy);
	}
}

for _ in range(int(input())):
	n = int(input())
	ans = [0]
	for x in map(int, input().split()):
		if x != 0 and ans[-1] - x >= 0:
			print(-1)
			break
		else:
			ans.append(ans[-1] + x)
	else:
		print(*ans[1:])

#include<bits/stdc++.h>

using namespace std;

long long dp[65][65][3];

void solve(int n)
{
    memset(dp, 0, sizeof dp);
    int k = n / 2;
    dp[0][0][2] = 1;
    for(int i = 0; i <= k; i++)
        for(int j = 0; j <= k; j++)
            for(int t = 0; t <= 2; t++)
            {
                int turn = (i + j) % 4;
                if (turn == 0 || turn == 3)
                {
                    if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t] += dp[i][j][t];
                }
                else
                {
                    if(i < k) dp[i + 1][j][t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t];
                }
            }
    for(int i = 0; i < 3; i++)
        cout << dp[k][k][i] % 998244353 << " ";
    cout << endl;
}

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

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

def choose(n, k):
    return fact(n) // fact(k) // fact(n - k)

def calc(n):
    if n == 2:
        return [1, 0, 1]
    else:
        a = calc(n - 2)
        return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]

t = int(input())
for i in range(t):
    mod = 998244353
    n = int(input())
    a = calc(n)
    a = list(map(lambda x: x % mod, a))
    print(*a)

#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<vector<int>> g;

vector<int> st;
vector<int> pd;

void init(int v, int d){
	st.push_back(v);
	if (int(st.size()) - d >= 0)
		pd[v] = st[st.size() - d];
	for (int u : g[v])
		init(u, d);
	st.pop_back();
}

vector<char> used;

void dfs(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		dfs(u);
}

int get(int d){
	pd.assign(n, -1);
	init(0, d);
	
	vector<int> ord, h(n);
	queue<int> q;
	q.push(0);
	while (!q.empty()){
		int v = q.front();
		q.pop();
		ord.push_back(v);
		for (int u : g[v]){
			q.push(u);
			h[u] = h[v] + 1;
		}
	}
	reverse(ord.begin(), ord.end());
	
	used.assign(n, 0);
	int res = 0;
	for (int v : ord) if (!used[v] && h[v] > d){
		++res;
		dfs(pd[v]);
	}
	
	return res;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int k;
		scanf("%d%d", &n, &k);
		g.assign(n, vector<int>());
		for (int i = 1; i < n; ++i){
			int p;
			scanf("%d", &p);
			--p;
			g[p].push_back(i);
		}
		int l = 1, r = n - 1;
		int ans = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (get(m) <= k){
				ans = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		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 INF = 1e9;

int main(){
	int n;
	cin >> n;
	vector<string> s(2);
	forn(i, 2) cin >> s[i];
	vector<array<array<int, 2>, 2>> dp(n + 1);
	forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF;
	dp[0][0][s[1][0] == '1'] = s[1][0] == '1';
	dp[0][0][0] = 0;
	forn(i, n - 1) forn(j, 2){
		int nxtj = s[j][i + 1] == '1';
		int nxtj1 = s[j ^ 1][i + 1] == '1';
		dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1);
		dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj);
		dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj);
	}
	cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n';
}

#include<bits/stdc++.h>

using namespace std;

const int N = 10043;
const int K = 12;

int tsz = 0;
int trie[N][K];
int aut[N][K];
int lnk[N];
int p[N];
int pchar[N];
int cost[N];
int ncost[N];

int newNode()
{
    lnk[tsz] = -1;
    ncost[tsz] = -1;
    cost[tsz] = 0;
    for(int i = 0; i < K; i++)
    {
        trie[tsz][i] = aut[tsz][i] = -1;
    }
    return tsz++;
}

int nxt(int x, int y)
{                                 
    if(trie[x][y] == -1) 
    {
        trie[x][y] = newNode();
        pchar[trie[x][y]] = y;
        p[trie[x][y]] = x;
    }
    return trie[x][y];
}

int go(int x, int y);

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

int go(int x, int y)
{
    if(aut[x][y] != -1) return aut[x][y];
    int& d = aut[x][y];
    if(trie[x][y] != -1) return d = trie[x][y];
    if(x == 0) return d = 0;
    return d = go(get_lnk(x), y);
}

void add(string s, int c)
{
    int cur = 0;
    for(auto x : s) cur = nxt(cur, x - 'a');
    cost[cur] += c;     
} 

int calc(int x)
{
    if(ncost[x] != -1) return ncost[x];
    ncost[x] = cost[x];
    int y = get_lnk(x);
    if(y != x) ncost[x] += calc(y);
    return ncost[x];
}

int main()
{
    int root = newNode();
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        int x;
        cin >> x >> s;
        map<char, set<char>> adj;
        for(int j = 0; j + 1 < s.size(); j++)
        {
            adj[s[j]].insert(s[j + 1]);
            adj[s[j + 1]].insert(s[j]);
        }
        bool bad = false;
        string res = "";
        char c;
        for(c = 'a'; c <= 'l'; c++)
        {
            if(!adj.count(c)) continue;
            if(adj[c].size() >= 3)
                bad = true;
            if(adj[c].size() == 1)
                break;
        }
        if(c == 'm' || bad) continue;
        res.push_back(c);
        while(adj[c].size() > 0)
        {
            char d = *adj[c].begin();
            adj[c].erase(d);
            adj[d].erase(c);
            c = d;
            res.push_back(c);  
        }
        bad |= adj.size() != res.size();
        map<char, int> pos;
        for(int i = 0; i < res.size(); i++)
            pos[res[i]] = i;
        for(int i = 0; i + 1 < s.size(); i++)
            bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1;
        if(bad) continue;
        add(res, x);
        reverse(res.begin(), res.end());
        add(res, x);
    }  
    int INF = 1e9;
    int K = 12;
    vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF));
    vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1));
    dp[0][0] = 0;
    for(int i = 0; i < (1 << K); i++)
        for(int j = 0; j <= tsz; j++)
        {
            for(int z = 0; z < K; z++)
            {
                if(i & (1 << z)) continue;
                int nstate = go(j, z);
                int add = calc(nstate);
                int nmask = i | (1 << z);
                if(dp[nmask][nstate] < dp[i][j] + add)
                {
                    dp[nmask][nstate] = dp[i][j] + add;
                    pdp[nmask][nstate] = {z, j};
                }
            }
        }
    string ans = "";
    int curmask = (1 << K) - 1;
    int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin();
    while(curmask != 0)
    {
        int cc = pdp[curmask][curstate].first;
        int ns = pdp[curmask][curstate].second;
        ans.push_back(char('a' + cc));
        curmask ^= (1 << cc);
        curstate = ns;
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]);
    for (int &x : p) cout << x << ' ';
    cout << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n;
		scanf("%d", &n);
		vector<int> a(n), b(n);
		forn(i, n) scanf("%d", &a[i]);
		forn(i, n) scanf("%d", &b[i]);
		priority_queue<int> qa(a.begin(), a.end());
		priority_queue<int> qb(b.begin(), b.end());
		int ans = 0;
		while (!qa.empty()){
			if (qa.top() == qb.top()){
				qa.pop();
				qb.pop();
				continue;
			}
			++ans;
			if (qa.top() > qb.top()){
				qa.push(to_string(qa.top()).size());
				qa.pop();
			}
			else{
				qb.push(to_string(qb.top()).size());
				qb.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

int comp(char c, char d){
	return c < d ? -1 : (c > d ? 1 : 0);
}

int main() {
	int t;
	cin >> t;
	forn(_, t){
		string s;
		cin >> s;
		int n = s.size();
		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
		for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){
			int r = l + len;
			dp[l][r] = 1;
			{
				int res = -1;
				if (dp[l + 1][r - 1] != 0)
					res = max(res, dp[l + 1][r - 1]);
				else
					res = max(res, comp(s[l], s[r - 1]));
				if (dp[l + 2][r] != 0)
					res = max(res, dp[l + 2][r]);
				else
					res = max(res, comp(s[l], s[l + 1]));
				dp[l][r] = min(dp[l][r], res);
			}
			{
				int res = -1;
				if (dp[l + 1][r - 1] != 0)
					res = max(res, dp[l + 1][r - 1]);
				else
					res = max(res, comp(s[r - 1], s[l]));
				if (dp[l][r - 2] != 0)
					res = max(res, dp[l][r - 2]);
				else
					res = max(res, comp(s[r - 1], s[r - 2]));
				dp[l][r] = min(dp[l][r], res);
			}
		}
		if (dp[0][n] == -1)
			cout << "Alice\n";
		else if (dp[0][n] == 0)
			cout << "Draw\n";
		else
			cout << "Bob\n";
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

long long gcd(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long x1, y1;
	long long d = gcd(b, a % b, x1, y1);
	x = y1;
	y = x1 - y1 * (a / b);
	return d;
}

bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) {
	g = gcd(abs(a), abs(b), x0, y0);
	if (c % g) {
		return false;
	}
	x0 *= c / g;
	y0 *= c / g;
	if (a < 0) x0 = -x0;
	if (b < 0) y0 = -y0;
	return true;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n), b(n);
	forn(i, n) scanf("%d%d", &a[i], &b[i]);
	long long cur = accumulate(b.begin(), b.end(), 0ll);
	vector<int> difs(n);
	forn(i, n) difs[i] = a[i] - b[i];
	sort(difs.begin(), difs.end(), greater<int>());
	vector<long long> bst(n + 1);
	forn(i, n + 1){
		bst[i] = cur;
		if (i < n)
			cur += difs[i];
	}
	int mx = max_element(bst.begin(), bst.end()) - bst.begin();
	int m;
	scanf("%d", &m);
	forn(_, m){
		int x, y;
		scanf("%d%d", &x, &y);
		long long x0, y0, g;
		if (!find_any_solution(x, y, n, x0, y0, g)){
			puts("-1");
			continue;
		}
		long long l = x * 1ll * y / g;
		long long red = x0 * 1ll * x;
		red = red + (max(0ll, mx - red) + l - 1) / l * l;
		red = red - max(0ll, red - mx) / l * l;
		long long ans = -1;
		if (red <= n) ans = max(ans, bst[red]);
		red -= l;
		if (red >= 0) ans = max(ans, bst[red]);
		printf("%lld\n", ans);
	}
	return 0;
}

#include <bits/stdc++.h>     

using namespace std;

const int N = 1003;

int n;
int a[N];
vector<int> g[N * N];
int mt[N];
bool used[N * N];
vector<int> val;

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

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= n; j++)
            val.push_back(a[i] * j);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    int v = val.size();
    long long ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= n; j++)
        {
            int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin();
            g[k].push_back(i);
        }
    for(int i = 0; i < n; i++) mt[i] = -1;
    for(int i = 0; i < v; i++)
    {
        if(kuhn(i))
        {
            ans += val[i];
            for(int j = 0; j < v; j++) used[j] = false;
        }
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

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() {
	int D, n, m;
	
	scanf("%d%d%d", &D, &n, &m);
	
	vector<int> inv(D + 1);
	forn(i, D + 1) inv[i] = binpow(i, MOD - 2);
	
	vector<int> b(n);
	forn(i, n) scanf("%d", &b[i]);
	
	vector<int> a(m);
	forn(i, m) scanf("%d", &a[i]);
	sort(a.begin(), a.end());
	
	int fl = (1 << m) - 1;
	vector<int> ways(1 << m, 1);
	forn(i, m) forn(j, n){
		int d = abs(b[j] - a[i]);
		int mask;
		if (b[j] > a[i]){
			int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
			mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
		}
		else{
			int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
			mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
		}
		ways[mask] = mul(ways[mask], d);
		mask ^= (1 << i);
		ways[mask] = mul(ways[mask], inv[d]);
	}
	
	forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){
		ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]);
	}
	
	ways[0] = binpow(D + 1, n);
	forn(mask, 1 << m){
		ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1);
	}
	forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){
		ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]);
	}
	
	int q;
	scanf("%d", &q);
	forn(_, q){
		int x;
		scanf("%d", &x);
		int ans = binpow(D + 1, n + 1);
		forn(i, m){
			int d = abs(x - a[i]);
			int mask;
			if (x > a[i]){
				int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
				mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
			}
			else{
				int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
				mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
			}
			ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d));
		}
		printf("%d\n", ans);
	}
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        string s1, s2;
        cin >> s1 >> s2;
        s1 += s2;
        cout << set<char>(s1.begin(), s1.end()).size() - 1 << endl;
    }
}

for _ in range(int(input())):
	n, m, sx, sy, d = map(int, input().split())
	if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d:
	    print(-1)
	else:
	    print(n + m - 2)

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

        val indices = (0 until n).sortedBy { a[it] }
        val mn = Array(n) { 0 }
        val mx = Array(n) { 0 }

        var lst = n
        for (i in n - 1 downTo 0) {
            val pos = indices[i]
            mn[pos] = lowerBound(b, a[pos])
            mx[pos] = lst - 1;
            if (i == mn[pos])
                lst = i

            mn[pos] = b[mn[pos]] - a[pos]
            mx[pos] = b[mx[pos]] - a[pos]
        }
        println(mn.joinToString(" "))
        println(mx.joinToString(" "))
    }
}

fun lowerBound(a: List<Int>, v: Int): Int {
    var l = -1; var r = a.size
    while (r - l > 1) {
        val m = (l + r) / 2
        if (a[m] < v)
            l = m
        else
            r = m
    }
    return r
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    
    auto check = [&](int ans) {
      map<int, int> cnt;
      for (int x : a) ++cnt[x & ans];
      for (int x : b) --cnt[~x & ans];
      bool ok = true;
      for (auto it : cnt) ok &= it.second == 0;
      return ok;
    };
    
    int ans = 0;
    for (int bit = 29; bit >= 0; --bit) 
      if (check(ans | (1 << bit)))
        ans |= 1 << bit;
    
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;

vector<int> prefix_function(const string &s){
	int n = s.size();
	vector<int> p(n);
	for (int i = 1; i < n; ++i){
		int k = p[i - 1];
		while (k > 0 && s[i] != s[k])
			k = p[k - 1];
		k += (s[i] == s[k]);
		p[i] = k;
	}
	return p;
}

int main() {
	cin.tie(0);
	iostream::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	auto p = prefix_function(s);
	vector<vector<int>> A(n, vector<int>(AL));
	forn(i, n) forn(j, AL){
		if (i > 0 && j != s[i] - 'a')
			A[i][j] = A[p[i - 1]][j];
		else
			A[i][j] = i + (j == s[i] - 'a');
	}
	int q;
	cin >> q;
	vector<vector<int>> ans(q);
	forn(z, q){
		string t;
		cin >> t;
		int m = t.size();
		s += t;
		for (int i = n; i < n + m; ++i){
		    A.push_back(vector<int>(AL));
			forn(j, AL){
				if (j != s[i] - 'a')
					A[i][j] = A[p[i - 1]][j];
				else
					A[i][j] = i + (j == s[i] - 'a');
			}
			p.push_back(A[p[i - 1]][s[i] - 'a']);
			ans[z].push_back(p[i]);
		}
		forn(_, m){
			p.pop_back();
			s.pop_back();
			A.pop_back();
		}
	}
	for (auto &it : ans){
		for (int x : it)
			cout << x << ' ';
		cout << '\n';
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

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

vector<edge> e;
vector<int> g[N];
int S, T, V;
int d[N], lst[N];
int n1, n2, m, q;
map<pair<int, int>, int> es;

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

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

bool bfs()
{
    for (int i = 0; i < V; i++)
        d[i] = INF;
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty())
    {
        int k = q.front();
        q.pop();
        for (auto y : g[k])
        {
            if (rem(y) == 0)
                continue;
            int to = e[y].y;
            if (d[to] > d[k] + 1)
            {
                q.push(to);
                d[to] = d[k] + 1;
            }
        }
    }
    return d[T] < INF;
}

int dfs(int x, int mx)
{
    if (x == T || mx == 0)
        return mx;
    int sum = 0;
    for (; lst[x] < g[x].size(); lst[x]++)
    {
        int num = g[x][lst[x]];
        int r = rem(num);
        if (r == 0)
            continue;
        int to = e[num].y;
        if (d[to] != d[x] + 1)
            continue;
        int pushed = dfs(to, min(r, mx));
        if (pushed > 0)
        {
            e[num].f += pushed;
            e[num ^ 1].f -= pushed;
            sum += pushed;
            mx -= pushed;
            if (mx == 0)
                return sum;
        }
    }
    return sum;
}

int Dinic()
{
    int ans = 0;
    while (bfs())
    {
        for (int i = 0; i < V; i++)
            lst[i] = 0;
        int f = 0;
        do
        {
            f = dfs(S, INF);
            ans += f;
        } while (f > 0);
    }
    return ans;
}

int main()
{
    scanf("%d %d %d %d", &n1, &n2, &m, &q);
    S = n1 + n2;
    T = S + 1;
    V = T + 1;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        es[make_pair(x, y)] = i + 1;
        add_edge(x, n1 + y, 1);
    }
    for (int i = 0; i < n1; i++)
        add_edge(S, i, 1);
    for (int i = 0; i < n2; i++)
        add_edge(i + n1, T, 1);
    Dinic();
    bfs();
    vector<int> vertex_cover;
    map<int, int> index;
    set<int> matched;
    long long sum = 0;
    for (int i = 0; i < n1; i++)
        if (d[i] == INF)
        {
            vertex_cover.push_back(i + 1);
            for (auto ei : g[i])
                if (e[ei].f == 1)
                {
                    int idx = es[make_pair(i, e[ei].y - n1)];
                    index[i + 1] = idx;
                    sum += idx;
                    matched.insert(idx);
                }
        }
    for (int i = 0; i < n2; i++)
        if (d[i + n1] != INF)
        {
            vertex_cover.push_back(-(i + 1));
            for (auto ei : g[i + n1])
                if (e[ei].f == -1)
                {
                    int idx = es[make_pair(e[ei].y, i)];
                    index[-(i + 1)] = idx;
                    sum += idx;    
                    matched.insert(idx);
                }
        }
    for (int i = 0; i < q; i++)
    {
        int s;
        scanf("%d", &s);
        if (s == 1)
        {
            puts("1");
            int v = vertex_cover.back();
            vertex_cover.pop_back();
            printf("%d\n", v);
            sum -= index[v];
            matched.erase(index[v]);
            printf("%lld\n", sum);
        }
        else
        {
            printf("%d\n", (int)matched.size());
            for(auto x : matched) printf("%d ", x);
            puts("");
        }   
        fflush(stdout);
    }
}