#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    vector<int> l(3);
    for (int i = 0; i < 3; ++i)
      cin >> l[i];
    bool ok = false;
    for (int i = 0; i < 3; ++i)
      ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3];
    for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0)
      ok |= l[(i + 1) % 3] == l[(i + 2) % 3];
    cout << (ok ? "YES\n" : "NO\n");
  }
} 

for _ in range(int(input())):
	n = int(input())
	p = [int(x) for x in input().split()]
	s = input()
	l = sorted([[s[i], p[i], i] for i in range(n)])
	q = [-1 for i in range(n)]
	for i in range(n):
		q[l[i][2]] = i + 1
	print(*q)

#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 li INF64 = li(1e18);

int n;
li k;
vector<int> a;

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

li accurateFloor(li a, li b) {
	li val = a / b;
	while (val * b > a)
		val--;
	return val;
}

inline void solve() {
	sort(a.begin(), a.end());
	vector<li> pSum(n + 1, 0);
	fore (i, 0, n)
		pSum[i + 1] = pSum[i] + a[i];
	
	li ans = 1e18;
	fore (y, 0, n) {
		//(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k
		//a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1)
		//x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1)
		
		li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1);
		ans = min(ans, y + max(0LL, x));
	}
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while (t--) {
		read();
		solve();
	}
	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 main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    string s;
    cin >> s;
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0');
    vector<vector<int>> C(n + 1);
    for(int i = 0; i <= n; i++)
    {
        C[i].resize(i + 1);
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++)
            C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
    int ans = 1;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
        {
            int cnt = j + 1 - i;
            int cnt1 = p[j + 1] - p[i];
            if(cnt1 > k || p[n] < k) continue;
            cnt -= 2;
            if(s[i] == '0') cnt1--;
            if(s[j] == '0') cnt1--;
            if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0)
                ans = add(ans, C[cnt][cnt1]);
        }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> x(n);
    forn(i, n) scanf("%d", &x[i]);
    vector<vector<int>> a(n, vector<int>(m));
    forn(i, n) forn(j, m) scanf("%1d", &a[i][j]);
    
    int ans = -1;
    vector<int> best;
    forn(mask, 1 << n) {
      vector<int> val(m);
      forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1;
      int res = 0;
      forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i];
      vector<int> p(m);
      iota(p.begin(), p.end(), 0);
      sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; });
      forn(i, m) res += val[p[i]] * (i + 1);
      if (res > ans) ans = res, best = p;
    }
    
    vector<int> ansPerm(m);
    forn(i, m) ansPerm[best[i]] = i;
    forn(i, m) printf("%d ", ansPerm[i] + 1);
    puts("");
  }
} 

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 * 1000 + 13;

using li = unsigned long long;

int pr[N];
li hs[N], f[N];
unordered_map<li, int> rf;

int main() {
  int n;
  scanf("%d", &n);
  
  mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  iota(pr, pr + N, 0);
  for (int i = 2; i <= n; ++i) if (pr[i] == i) {
    for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i);
    hs[i] = rnd();
  }
  for (int i = 2; i <= n; ++i) {
    f[i] = f[i - 1];
    int x = i;
    while (x != 1) {
      f[i] ^= hs[pr[x]];
      x /= pr[x];
    }
    rf[f[i]] = i;
  }
  
  auto solve = [&] (int n) -> vector<int> {
    li fp = 0;
    for (int i = 2; i <= n; ++i) fp ^= f[i];
    if (fp == 0) return {};
    if (rf.count(fp)) return {rf[fp]};
    for (int i = 2; i <= n; ++i) {
        li x = f[i] ^ fp;
        if (rf.count(x) && rf[x] != i) return {rf[x], i};
    }
    return {2, n / 2, n};
  };
  
  auto ans = solve(n);
  printf("%d\n", n - (int)ans.size());
  for (int i = 1; i <= n; ++i)
    if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i);
  puts("");
} 

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n");
  }
} 

for _ in range(int(input())):
  w, h = map(int, input().split())
  ans = 0
  for i in range(4):
    a = [int(x) for x in input().split()][1:]
    ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w))
  print(ans)

for _ in range(int(input())):
  n, k, x = map(int, input().split())
  x -= 1
  s = input()[::-1]
  res = []
  i = 0
  while i < n:
    if s[i] == 'a':
      res.append(s[i])
    else:
      j = i
      while j + 1 < n and s[j + 1] == s[i]:
        j += 1
      cur = (j - i + 1) * k + 1
      res.append('b' * (x % cur))
      x //= cur
      i = j
    i += 1
  print(''.join(res[::-1]))

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

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

int n;
vector<int> a;

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

bool p(int val, int c1, int c2, int c3) {
  fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) {
    if (cur1 + 2 * cur2 > val)
      continue;
    if ((val - cur1 - 2 * cur2) % 3 != 0)
      continue;
    if ((val - cur1 - 2 * cur2) / 3 <= c3)
      return true;
  }
  return false;
}

bool possible(int c1, int c2, int c3) {
  for (int v : a) {
    if (!p(v, c1, c2, c3))
      return false;
  }
  return true;
}

inline void solve() {
  int m = *max_element(a.begin(), a.end());
  int ans = int(1e9);
  
  const int MAG = 3;
  fore (c1, 0, MAG) fore (c2, 0, MAG) {
    int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3);
    assert(c1 + 2 * c2 + 3 * c3 >= m);
    
    if (possible(c1, c2, c3))
      ans = min(ans, c1 + c2 + c3);
  }
  cout << ans << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

const int N = 500 * 1000 + 13;

int main() {
  int q;
  scanf("%d", &q);
  vector<int> t(q), x(q), y(q);
  for (int i = 0; i < q; ++i) {
    scanf("%d%d", &t[i], &x[i]);
    if (t[i] == 2) scanf("%d", &y[i]);
  }
  vector<int> p(N);
  iota(p.begin(), p.end(), 0);
  vector<int> ans;
  for (int i = q - 1; i >= 0; --i) {
    if (t[i] == 1) {
      ans.push_back(p[x[i]]);
    } else {
      p[x[i]] = p[y[i]];
    }
  }
  reverse(ans.begin(), ans.end());
  for (int &x : ans) printf("%d ", x);
} 

#include <bits/stdc++.h>

using namespace std;

const int N = 500 * 1000 + 13;

int n, q;
vector<int> pos[N];

int main() {
  scanf("%d", &q);
  while (q--) {
    int t, x, y;
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d", &x);
      pos[x].push_back(n++);
    } else {
      scanf("%d%d", &x, &y);
      if (x != y) {
        if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]);
        for (int &i : pos[x]) pos[y].push_back(i);
        pos[x].clear();
      }
    }
  }
  vector<int> ans(n);
  for (int x = 0; x < N; ++x)
    for (int &i : pos[x]) 
      ans[i] = x;
  for (int &x : ans) printf("%d ", x);
} 

#include <bits/stdc++.h>

using namespace std;

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

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

int n;
int p[N], a[N];
int dp[N][2][2];
pair<int, int> pr[N][2][2];

void solve() {
  scanf("%d", &n);
  forn(i, n) scanf("%d", &p[i]);
  forn(i, n) forn(pos, 2) forn(sg, 2)
    dp[i][pos][sg] = INF;
  dp[0][0][0] = dp[0][0][1] = -INF;
  
  forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {
    forn(nsg, 2) {
      int x = sg ? -p[i] : p[i];
      int y = dp[i][pos][sg];
      if (pos) swap(x, y);
      int z = nsg ? -p[i + 1] : p[i + 1];
      if (z > x) {
        if (dp[i + 1][0][nsg] > y) {
          dp[i + 1][0][nsg] = y;
          pr[i + 1][0][nsg] = make_pair(pos, sg);
        }
      } else if (z > y)  {
        if (dp[i + 1][1][nsg] > x) {
          dp[i + 1][1][nsg] = x;
          pr[i + 1][1][nsg] = make_pair(pos, sg);
        }
      }
    }
  }
  
  int pos = -1, sg = -1;
  forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF) 
    pos = j, sg = k;
  if (pos == -1) {
    puts("NO");
    return;
  }
  for (int i = n - 1; i >= 0; i--) {
    a[i] = sg ? -p[i] : p[i];
    tie(pos, sg) = pr[i][pos][sg];
  }
  
  puts("YES");
  forn(i, n) printf("%d ", a[i]);
  puts("");
}

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

#include <bits/stdc++.h>

using namespace std;

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

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

int n;
int p[N], a[N];
int dp[N][2], pr[N][2];

void solve() {
  scanf("%d", &n);
  forn(i, n) scanf("%d", &p[i]);
  forn(i, n) forn(j, 2) dp[i][j] = INF;
  dp[0][0] = dp[0][1] = -INF;
  forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {
    int x = j ? -p[i] : p[i];
    int y = dp[i][j];
    if (x < y) swap(x, y);
    forn(nj, 2) {
      int z = nj ? -p[i + 1] : p[i + 1];
      if (z > x) {
        if (dp[i + 1][nj] > y) {
          dp[i + 1][nj] = y;
          pr[i + 1][nj] = j;
        }
      } else if (z > y)  {
        if (dp[i + 1][nj] > x) {
          dp[i + 1][nj] = x;
          pr[i + 1][nj] = j;
        }
      }
    }
  }
  int j = -1;
  forn(i, 2) if (dp[n - 1][i] != INF) j = i;
  if (j == -1) {
    puts("NO");
    return;
  }
  for (int i = n - 1; i >= 0; i--) {
    a[i] = j ? -p[i] : p[i];
    j = pr[i][j];
  }
  puts("YES");
  forn(i, n) printf("%d ", a[i]);
  puts("");
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 23;
const int A = 26;
const int S = 20043;
int n;
string inp[N];
char buf[S];
int cnt[N][A];
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;
}

void flip_all(vector<int>& a)
{
    int msk = (1 << n) - 1;
    for(int i = 0; i < (1 << (n - 1)); i++)
        swap(a[i], a[i ^ msk]);
}

int val[S];
int* where[S];
int cur = 0;

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

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

void zeta_transform(vector<int>& a)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < (1 << n); j++)
            if((j & (1 << i)) == 0)
                a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);
    }
}                     

void mobius_transform(vector<int>& a)
{
    for(int i = n - 1; i >= 0; i--)
    {
        for(int j = (1 << n) - 1; j >= 0; j--)
            if((j & (1 << i)) != 0)
                a[j] = sub(a[j], a[j ^ (1 << i)]);
    }
}

int cur_max[A];
vector<int> mask_cnt;

void rec(int depth, int mask)
{
    if(depth == n)
    {
        mask_cnt[mask] = 1;
        for(int i = 0; i < A; i++)
            mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);
    }
    else
    {
        int state = cur;
        for(int i = 0; i < A; i++)
            change(cur_max[i], min(cur_max[i], cnt[depth][i]));
        rec(depth + 1, mask + (1 << depth));
        while(state != cur) rollback();
        rec(depth + 1, mask);
    }   
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%s", buf);
        inp[i] = buf;
        for(auto x : inp[i])
            cnt[i][x - 'a']++;
    }

    for(int i = 0; i < A; i++)
        cur_max[i] = S;
    mask_cnt.resize(1 << n);
    rec(0, 0);
    flip_all(mask_cnt);
    mobius_transform(mask_cnt);
    flip_all(mask_cnt);
    int sum = 0;
    for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);
    zeta_transform(mask_cnt);
    vector<int> res(1 << n);
    for(int i = 0; i < (1 << n); i++)
        res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);

    long long ans = 0;

    for(int i = 0; i < (1 << n); i++)
    {
        int c = 0, s = 0;
        for(int j = 0; j < n; j++)
        {
            if(i & (1 << j))
            {
                c++;
                s += j + 1;
            }   
        }
        ans ^= res[i] * 1ll * c * 1ll * s;
    }

    //for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);
    printf("%lld\n", ans);
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
	int t;
	cin >> t;
	while (t--){
		long long x1, x2;
		int p1, p2;
		cin >> x1 >> p1 >> x2 >> p2;
		int mn = min(p1, p2);
		p1 -= mn;
		p2 -= mn;
		if (p1 >= 7)
			cout << ">" << endl;
		else if (p2 >= 7)
			cout << "<" << endl;
		else{
			for (int i = 0; i < p1; ++i) x1 *= 10;
			for (int i = 0; i < p2; ++i) x2 *= 10;
			if (x1 < x2)
				cout << "<" << endl;
			else if (x1 > x2)
				cout << ">" << endl;
			else
				cout << "=" << 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;
    int mn = *min_element(a.begin(), a.end());
    for (int i = 0, k = 0; k < n / 2; ++i) if (a[i] != mn) {
      cout << a[i] << ' ' << mn << '\n';
      k += 1;
    }
  }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    li h;
    cin >> n >> h;
    vector<li> a(n);
    for (li &x : a) cin >> x;
    li l = 1, r = 1e18;
    while (l <= r) {
      li m = (l + r) / 2;
      li sum = m;
      for (int i = 0; i < n - 1; ++i) 
        sum += min(m, a[i + 1] - a[i]);
      if (sum < h) l = m + 1;
      else r = m - 1;
    }
    cout << r + 1 << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> dp1(n + 2), dp2(n + 2);
    dp1[0] = 1;
    while (n--) {
      int x;
      scanf("%d", &x);
      dp1[x + 1] = add(dp1[x + 1], dp1[x + 1]);
      dp1[x + 1] = add(dp1[x + 1], dp1[x]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp2[x - 1]);
      if (x > 0) dp2[x - 1] = add(dp2[x - 1], dp1[x - 1]);
      dp2[x + 1] = add(dp2[x + 1], dp2[x + 1]);
    }
    int ans = 0;
    for (int x : dp1) ans = add(ans, x);
    for (int x : dp2) ans = add(ans, x);
    printf("%d\n", add(ans, MOD - 1));
  }
} 

#include <bits/stdc++.h>

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

using namespace std;

struct cell{
	int x, y;
};

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

int main() {
	int t;
	cin >> t;
	while (t--){
		int n, m;
		cin >> n >> m;
		vector<string> s(n);
		int lx = -1, ly = -1;
		forn(i, n){
			cin >> s[i];
			forn(j, m) if (s[i][j] == 'L'){
				lx = i;
				ly = j;
			}
		}
		auto in = [&](int x, int y){
			return 0 <= x && x < n && 0 <= y && y < m;
		};
		vector<vector<int>> d(n, vector<int>(m, 0));
		forn(x, n) forn(y, m) if (s[x][y] == '.'){
			forn(i, 4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				d[x][y] += in(nx, ny) && s[nx][ny] != '#';
			}
		}
		queue<cell> q;
		vector<vector<char>> used(n, vector<char>(m, 0));
		q.push({lx, ly});
		used[lx][ly] = true;
		while (!q.empty()){
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			forn(i, 4){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (!in(nx, ny) || s[nx][ny] == '#' || used[nx][ny]) continue;
				--d[nx][ny];
				if (d[nx][ny] <= 1){
					used[nx][ny] = true;
					q.push({nx, ny});
				}
			}
		}
		forn(i, n){
			forn(j, m) if (s[i][j] == '.' && used[i][j])
				s[i][j] = '+';
			cout << s[i] << "\n";
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;

struct Mint
{
  int val;

  bool operator==(const Mint& other)
  {
    return val == other.val;
  }

  Mint operator+(const Mint& other)
  {
    int res = val + other.val;
    while(res >= MOD) res -= MOD;
    while(res < 0) res += MOD;
    return Mint(res);
  }

  Mint operator-(const Mint& other)
  {
    int res = val - other.val;
    while(res >= MOD) res -= MOD;
    while(res < 0) res += MOD;
    return Mint(res);  
  }

  Mint operator*(const Mint& other)
  {
    return Mint((val * 1ll * other.val) % MOD);
  }

  Mint pow(int y)
  {
    Mint z(1);
    Mint x(val);
    while(y > 0)
    {
      if(y % 2 == 1) z = z * x;
      x = x * x;
      y /= 2;
    }
    return z;
  }

  Mint operator/(const Mint& other)
  {
    return Mint(val) * Mint(other.val).pow(MOD - 2);
  }

  Mint() {
      val = 0;
  };
  Mint(int x)
  {
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    val = x;
  };
};

ostream& operator<<(ostream& out, const Mint& x)
{
  return out << x.val;
}

const int g = 3;
const int LOGN = 19;

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

void prepare() {
  Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));
  forn(st, LOGN - 1) {
    w[st].assign(1 << st, 1);
    Mint bw = wb.pow(1 << (LOGN - st - 1));
    Mint cw = 1;
    forn(k, 1 << st) {
      w[st][k] = cw;
      cw = cw * bw;
    }
  }
  forn(st, LOGN) {
    rv[st].assign(1 << st, 0);
    if (st == 0) {
      rv[st][0] = 0;
      continue;
    }
    int h = (1 << (st - 1));
    forn(k, 1 << st)
      rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
  }
}

void ntt(vector<Mint> &a, bool inv) {
  int n = sz(a);
  int ln = __builtin_ctz(n);
  forn(i, n) {
    int ni = rv[ln][i];
    if (i < ni) swap(a[i], a[ni]);
  }
  forn(st, ln) {
    int len = 1 << st;
    for (int k = 0; k < n; k += (len << 1)) {
      fore(pos, k, k + len){
        Mint l = a[pos];
        Mint r = a[pos + len] * w[st][pos - k];
        a[pos] = l + r;
        a[pos + len] = l - r;
      }
    }
  }
  if (inv) {
    Mint rn = Mint(n).pow(MOD - 2);
    forn(i, n) a[i] = a[i] * rn;
    reverse(a.begin() + 1, a.end());
  }
}

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {
  int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));
  a.resize(cnt);
  b.resize(cnt);
  ntt(a, false);
  ntt(b, false);
  vector<Mint> c(cnt);
  forn(i, cnt) c[i] = a[i] * b[i];
  ntt(c, true);
  return c;
}

vector<Mint> norm(vector<Mint> a)
{
  while(a.size() > 1 && a.back() == Mint(0))
    a.pop_back();
  return a;
}

const int N = 250043;
vector<int> G[N];
int d[N];

Mint fact[N * 2];
Mint rev[N * 2];

void dfs(int x, int p)
{
  if(p != x) d[p]++;
  for(auto y : G[x]) if(y != p) dfs(y, x);
}

Mint C(int n, int k)
{
  return fact[n] * rev[k] * rev[n - k];
}

int main()
{
  prepare();
  fact[0] = Mint(1);
  for(int i = 1; i < N * 2; i++) fact[i] = fact[i - 1] * i;
  for(int i = 0; i < N * 2; i++) rev[i] = Mint(1) / fact[i];
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i++)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    G[x].push_back(y);
    G[y].push_back(x);  
  }
  dfs(0, 0);
  vector<vector<Mint>> cur;
  for(int i = 0; i < n; i++)
    if(d[i] > 0)
      cur.push_back(vector<Mint>({Mint(1), Mint(d[i])}));
  while(cur.size() > 1)
  {
    vector<vector<Mint>> ncur;
    for(int i = 0; i + 1 < cur.size(); i += 2)
      ncur.push_back(norm(mul(cur[i], cur[i + 1])));
    if(cur.size() % 2 == 1) ncur.push_back(cur.back());
    cur = ncur;  
  }
  Mint ans = 0;
  for(int i = 0; i < cur[0].size(); i++)
  {
    if(i % 2 == 0) ans = ans + cur[0][i] * fact[n - i];
    else ans = ans - cur[0][i] * fact[n - i];
  }
  cout << ans << endl;
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        println(s.last() + s.substring(1))
    }
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    li n, k;
    cin >> n >> k;
    li ans = 0, cur = 1;
    while (cur < k) {
      cur *= 2;
      ++ans;
    }
    if (cur < n) ans += (n - cur + k - 1) / k;
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    k += 1;
    vector<int> a(n);
    for (int& x : a) {
      cin >> x;
      int cur = 1;
      while (x--) cur *= 10;
      x = cur;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
      int cnt = k;
      if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1);
      res += a[i] * 1LL * cnt;
      k -= cnt;
    }
    cout << res << '\n';
  }
} 

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--){
		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]);
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){ return a[x][0] > a[y][0]; });
		vector<vector<int>> mxl(n, vector<int>(m, -INF));
		vector<vector<int>> mnr(n, vector<int>(m, INF));
		for (int i = n - 1; i >= 0; --i) forn(j, m){
			mxl[i][j] = a[ord[i]][j];
			if (i < n - 1) mxl[i][j] = max(mxl[i][j], mxl[i + 1][j]);
			if (j > 0) mxl[i][j] = max(mxl[i][j], mxl[i][j - 1]);
		}
		for (int i = n - 1; i >= 0; --i) for (int j = m - 1; j >= 0; --j){
			mnr[i][j] = a[ord[i]][j];
			if (i < n - 1) mnr[i][j] = min(mnr[i][j], mnr[i + 1][j]);
			if (j < m - 1) mnr[i][j] = min(mnr[i][j], mnr[i][j + 1]);
		}
		vector<int> mnl(m, INF), mxr(m, -INF);
		pair<int, int> ans(-1, -1);
		forn(i, n - 1){
			forn(j, m){
				mnl[j] = min(mnl[j], a[ord[i]][j]);
				if (j > 0) mnl[j] = min(mnl[j], mnl[j - 1]);
			}
			for (int j = m - 1; j >= 0; --j){
				mxr[j] = max(mxr[j], a[ord[i]][j]);
				if (j < m - 1) mxr[j] = max(mxr[j], mxr[j + 1]);
			}
			forn(j, m - 1) if (mnl[j] > mxl[i + 1][j] && mxr[j + 1] < mnr[i + 1][j + 1]){
				ans = {i, j};
			}
		}
		if (ans.first == -1){
			puts("NO");
			continue;
		}
		puts("YES");
		string res(n, '.');
		forn(i, n) res[ord[i]] = i <= ans.first ? 'R' : 'B';
		printf("%s %d\n", res.c_str(), ans.second + 1);
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const int MOD = 998244353;

int n, x;
int c[N][N], dp[N][N];

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

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

int main() {
  cin >> n >> x;
  for (int i = 0; i <= n; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; ++j) 
      c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
  }
  dp[n][0] = 1;
  for (int i = n; i > 1; i--) {
    for (int j = 0; j < x; ++j) {
      if (!dp[i][j]) continue;
      int pw = 1, nj = min(x, j + i - 1);
      for (int k = i; k >= 0; k--) {
        dp[k][nj] = add(dp[k][nj], mul(dp[i][j], mul(c[i][k], pw)));
        pw = mul(pw, nj - j);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i <= x; ++i)
    ans = add(ans, dp[0][i]);
  cout << ans << endl;
} 

#include <bits/stdc++.h>     

using namespace std;

struct Vertex
{
 	int cost;
 	int depth;
 	int idx;
 	Vertex() {};
 	Vertex(int cost, int depth, int idx) : cost(cost), depth(depth), idx(idx) {};
};

bool operator <(const Vertex& a, const Vertex& b)
{
 	if(a.cost != b.cost)
 		return a.cost > b.cost;
 	if(a.depth != b.depth)
 		return a.depth > b.depth;
 	return a.idx < b.idx;
}

struct DSU
{
	int n;
 	vector<int> p;
 	vector<int> top;

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

 	int get_top(int x)
 	{
 	 	return top[get(x)];
 	}

 	void merge(int x, int par)
 	{
 	 	p[x] = par;
 	}

 	DSU(int k = 0)
 	{
 	 	n = k;
 	 	p.resize(n);
 	 	iota(p.begin(), p.end(), 0);
 	 	top = p;
 	};
};

const int N = 200043;

int n;
vector<int> g[N];
int p[N], d[N], tin[N], tout[N];
int qv[N];
int qk[N];
int T = 0;

void dfs(int v = 0, int par = -1)
{
 	tin[v] = T++;
 	p[v] = par;
 	if(par == -1)
 		d[v] = 0;
 	else
 		d[v] = d[par] + 1;
 	for(auto x : g[v])
 		if(x != par)
 			dfs(x, v);
 	tout[v] = T;
}

pair<long long, long long> tree[4 * N];

pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
 	return make_pair(a.first + b.first, a.second + b.second);
}

pair<long long, long long> get(int v, int l, int r, int L, int R)
{
 	if(L >= R) return {0, 0};
 	if(l == L && r == R) return tree[v];
 	int m = (l + r) / 2;
 	return get(v * 2 + 1, l, m, L, min(R, m)) + get(v * 2 + 2, m, r, max(m, L), R);
}

void add(int v, int l, int r, int pos, pair<long long, long long> val)
{
 	if(l == r - 1)
 		tree[v] = tree[v] + val;
 	else
 	{
 	 	int m = (l + r) / 2;
 	 	if(pos < m) add(v * 2 + 1, l, m, pos, val);
 	 	else add(v * 2 + 2, m, r, pos, val);
 	 	tree[v] = tree[v] + val;
 	}                                                                  
}

pair<long long, long long> get_vertex_value(int v)
{
 	return get(0, 0, n, tin[v], tout[v]);
}

void add_on_path(int x, int y, pair<long long, long long> val)
{
 	// x is a descendant of y
 	add(0, 0, n, tin[x], val);
 	if(p[y] != -1)
 		add(0, 0, n, tin[p[y]], make_pair(-val.first, -val.second));
}

int calculate_cost(int v, int correction)
{
	//cerr << v << " " << correction << endl;
 	pair<long long, long long> res = get_vertex_value(v);
 	// first - (second + 1) * k <= 0
 	long long k = (res.first + res.second) / (res.second + 1) - 1;
 	if(correction < k) return correction;
 	return k;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; i++)
	{
	 	int x, y;
	 	scanf("%d %d", &x, &y);
	 	--x;
	 	--y;
	 	g[x].push_back(y);
	 	g[y].push_back(x);
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
	 	scanf("%d %d", &qv[i], &qk[i]);
	 	--qv[i];
	}                   

	dfs();
	DSU dsu(n);
                        
	vector<long long> ans(q);
	set<Vertex> pq;
	vector<Vertex> curv(n);
	for(int i = 0; i < n; i++)
	{                     
	 	int count_children = g[i].size();
	 	if(i != 0) count_children--;               
	 	add_on_path(i, i, make_pair((long long)(count_children), 0ll)); 
	 	if(i != 0)
	 	{
	 		curv[i] = Vertex(calculate_cost(i, 200000), d[i], i);
			pq.insert(curv[i]);                                   
	 	}
                          
	}
                        
	for(int i = 0; i < q; i++)
		pq.insert(Vertex(qk[i], -1, i));

	while(!pq.empty())
	{
		Vertex z = *pq.begin();
		pq.erase(pq.begin());
		if(z.depth == -1)
		{
		 	auto res = get_vertex_value(qv[z.idx]);
		 	ans[z.idx] = res.first - res.second * z.cost;
	    }
	    else
	    {
	     	int v = z.idx;
	     	int pv = p[v];
	     	int newtop = dsu.get_top(pv);
	     	pair<long long, long long> val = get_vertex_value(v);
	     	val.second++;
	     	val.first--;
	     	if(newtop != 0)
	     		pq.erase(curv[newtop]);
	     	add_on_path(pv, newtop, val);
	     	if(newtop != 0)
	     		curv[newtop].cost = calculate_cost(newtop, z.cost);
	     	if(newtop != 0)
	     		pq.insert(curv[newtop]);
	     	dsu.merge(v, pv);
	    }
	}	

	for(int i = 0; i < q; i++)
		printf("%lld\n", ans[i]);
}

def solve():
	n = int(input())
	s1 = input()
	s2 = input()
	bad = False
	for i in range(n):
		bad |= s1[i] == '1' and s2[i] == '1'
	if bad:
		print('NO')
	else:
		print('YES')

t = int(input())
for i in range(t):
	solve()

t = int(input())
for i in range(t):
    n = int(input())
    a = [[] for i in range(n)]
    for j in range(n):
        a[j] = list(map(int, input().split()))
    ans = False
    for j in range(5):
        for k in range(5):
            if k != j:
                cnt1 = 0
                cnt2 = 0
                cntno = 0
                for z in range(n):
                    if a[z][j] == 1:
                        cnt1 += 1
                    if a[z][k] == 1:
                        cnt2 += 1
                    if a[z][j] == 0 and a[z][k] == 0:
                        cntno += 1
                if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0:
                    ans = True
    if ans:
        print('YES')
    else:
        print('NO')

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    map<int, int> cnt;
    for (auto &x : a) {
      scanf("%d", &x);
      cnt[x] += 1;
    }
    long long sum = accumulate(a.begin(), a.end(), 0LL);
    if ((2 * sum) % n != 0) {
      puts("0");
      continue;
    }
    long long need = (2 * sum) / n;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      int a1 = a[i];
      int a2 = need - a1;
      if (cnt.count(a2)) ans += cnt[a2];
      if (a1 == a2) ans -= 1;
    }
    printf("%lld\n", ans / 2);
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n), ca(n + 1), cb(n + 1);
    for (int i = 0; i < n; ++i) {
      cin >> a[i] >> b[i];
      ca[a[i]]++; cb[b[i]]++;
    }
    long long ans = n * 1LL * (n - 1) * (n - 2) / 6;
    for (int i = 0; i < n; ++i) 
      ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1);
    cout << ans << '\n';
  }
} 

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	vector<vector<int>> a(n, vector<int>(m, 1));
	long long ans = 0;
	forn(x, n) forn(y, m){
		if (x == 0){
			for (int k = 1;; ++k){
				int nx = x + k / 2;
				int ny = y + (k + 1) / 2;
				if (nx == n || ny == m) break;
				ans += k;
			}
		}
		if (y == 0){
			for (int k = 1;; ++k){
				int nx = x + (k + 1) / 2;
				int ny = y + k / 2;
				if (nx == n || ny == m) break;
				ans += k;
			}
		}
	}
	ans += n * m;
	forn(i, q){
		int x, y;
		scanf("%d%d", &x, &y);
		--x, --y;
		forn(c, 2){
			int l = 1, r = 1;
			while (true){
				int nx = x + (l + c) / 2;
				int ny = y + (l + !c) / 2;
				if (nx == n || ny == m || a[nx][ny] == 0) break;
				++l;
			}
			while (true){
				int nx = x - (r + !c) / 2;
				int ny = y - (r + c) / 2;
				if (nx < 0 || ny < 0 || a[nx][ny] == 0) break;
				++r;
			}
			if (a[x][y] == 0){
				ans += l * r;
			}
			else{
				ans -= l * r;
			}
		}
		ans += a[x][y];
		a[x][y] ^= 1;
		ans -= a[x][y];
		printf("%lld\n", ans);
	}
}

#include <bits/stdc++.h>     

using namespace std;

const int INF = int(1e9);

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

struct BracketSeqn
{
 	int balance;
 	int lowestBalance;
 	vector<int> queryAns;

 	pair<int, bool> go(int x, bool f)
 	{
     	if(f)
     		return make_pair(0, true);
       	else
       		return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0);
    }

	BracketSeqn() {};
	BracketSeqn(string s)
	{
		vector<int> bal;
		int cur = 0;
		int n = s.size();
		for(auto x : s)
		{
		 	if(x == '(')
		 		cur++;
		 	else	
		 		cur--;
		 	bal.push_back(cur);	
		}
		balance = bal.back();
		lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
		vector<vector<int>> negPos(-lowestBalance + 1);
		for(int i = 0; i < n; i++)
		{
		 	if(bal[i] > 0) continue;
		 	negPos[-bal[i]].push_back(i);
		}
		queryAns.resize(-lowestBalance + 1);
		for(int i = 0; i < queryAns.size(); i++)
		{
		 	int lastPos = int(1e9);
		 	if(i != -lowestBalance)
		 		lastPos = negPos[i + 1][0];
		 	queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin();
		}
	};
};

int dp[M][2];
char buf[M];
int total_bal[M];

int main()
{
	int n;
	scanf("%d", &n);
	vector<BracketSeqn> bs;
	for(int i = 0; i < n; i++)
	{
	 	scanf("%s", buf);
	 	string s = buf;
	 	bs.push_back(BracketSeqn(s));
	}
	for(int i = 0; i < (1 << n); i++)               
	 	for(int j = 0; j < n; j++)
	 		if(i & (1 << j))
	 			total_bal[i] += bs[j].balance;
	for(int i = 0; i < (1 << n); i++)
		for(int j = 0; j < 2; j++)
			dp[i][j] = -int(1e9);
	dp[0][0] = 0;
	for(int i = 0; i < (1 << n); i++)
		for(int f = 0; f < 2; f++)
		{
		 	if(dp[i][f] < 0) continue;
		 	for(int k = 0; k < n; k++)
		 	{
		 	 	if(i & (1 << k)) continue;
		 	 	pair<int, bool> res = bs[k].go(total_bal[i], f);
		 	 	dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
		 	}
		}
	printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
}

#include <bits/stdc++.h>

using namespace std;

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

const int MOD[] = { 597804841, 618557587, 998244353 };
const int N = 500 * 1000 + 13;
const int K = 3;

using hs = array<int, K>;

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

int mul(int x, int y, int mod) {
  return x * 1LL * y % mod;
}

hs get(const int& x) {
  hs c;
  forn(i, K) c[i] = x;
  return c;
}

hs operator +(const hs& a, const hs& b) { 
  hs c;
  forn(i, K) c[i] = add(a[i], b[i], MOD[i]);
  return c;
}

hs operator -(const hs& a, const hs& b) {
  hs c;
  forn(i, K) c[i] = add(a[i], -b[i], MOD[i]);
  return c; 
}

hs operator *(const hs& a, const hs& b) {
  hs c;
  forn(i, K) c[i] = mul(a[i], b[i], MOD[i]);
  return c; 
}

int n, m;
string s, sx;
hs sum[N], pw[N];

hs get(int l, int r) {
  return sum[r] - sum[l] * pw[r - l];
}

vector<int> zfunction(const string& s) {
  int n = s.size();
  vector<int> z(n);
  int l = 0, r = 0;
  for (int i = 1; i < n; ++i) {
    if (i <= r) z[i] = min(z[i - l], r - i + 1);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  
  cin >> s >> sx;
  n = s.size();
  m = sx.size();
  
  pw[0] = get(1);
  forn(i, N - 1) pw[i + 1] = pw[i] * get(10); 
  sum[0] = get(0);
  forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0'); 
  hs x = get(0);
  forn(i, m) x = x * get(10) + get(sx[i] - '0');
  
  if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) {
    if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) {
      cout << i + 1 << ' ' << i + m - 1 << '\n';
      cout << i + m << ' ' << i + 2 * (m - 1) << '\n';
      return 0;
    }
  }
  
  auto z = zfunction(sx + "#" + s);
  
  for (int i = 0; i + m <= n; ++i) {
    int lcp = z[m + i + 1];
    for (int len = m - lcp - 1; len <= m - lcp; ++len) {
      if (len < 1) continue;
      if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) {
        cout << i + 1 << ' ' << i + m << '\n';
        cout << i + m + 1 << ' ' << i + m + len << '\n';
        return 0;
      }
      if (i >= len && get(i - len, i) + get(i, i + m) == x) {
        cout << i - len + 1 << ' ' << i << '\n';
        cout << i + 1 << ' ' << i + m << '\n';
        return 0;
      }
    }
  }
  
  assert(false);
}

t = int(input())
for i in range(t):
    n = int(input())
    for j in range(n):
        print("()" * j + "(" * (n - j) + ")" * (n - j))

for _ in range(int(input())):
	a, b, c, m = map(int, input().split())
	a, b, c = sorted([a, b, c])
	print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO")

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int n;
  cin >> n;
  vector<li> a(n);
  for (auto &x : a) cin >> x;
  sort(a.begin(), a.end());
  li sum = accumulate(a.begin(), a.end(), 0LL);
  int m;
  cin >> m;
  while (m--) {
    li x, y;
    cin >> x >> y;
    int i = lower_bound(a.begin(), a.end(), x) - a.begin();
    li ans = 2e18;
    if (i > 0) ans = min(ans, (x - a[i - 1]) + max(0LL, y - sum + a[i - 1]));
    if (i < n) ans = min(ans, max(0LL, y - sum + a[i]));
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>

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

using namespace std;

int n;
vector<vector<int>> a;
int m;
vector<vector<int>> b;

int main() {
	scanf("%d", &n);
	a.resize(n);
	forn(i, n){
		int c;
		scanf("%d", &c);
		a[i].resize(c);
		forn(j, c) scanf("%d", &a[i][j]);
	}
	scanf("%d", &m);
	b.resize(m);
	forn(i, m){
		b[i].resize(n);
		forn(j, n){
			scanf("%d", &b[i][j]);
			--b[i][j];
		}
	}
	sort(b.begin(), b.end());
	vector<int> ult(n);
	forn(i, n) ult[i] = int(a[i].size()) - 1;
	if (!binary_search(b.begin(), b.end(), ult)){
		forn(i, n) printf("%d ", ult[i] + 1);
		puts("");
		return 0;
	}
	int mx = 0;
	vector<int> ans(n, -1);
	forn(i, m){
		vector<int> tmp = b[i];
		int sum = 0;
		forn(j, n) sum += a[j][tmp[j]];
		forn(j, n) if (tmp[j] != 0){
			--tmp[j];
			if (!binary_search(b.begin(), b.end(), tmp) && sum - a[j][tmp[j] + 1] + a[j][tmp[j]] > mx){
				mx = sum - a[j][tmp[j] + 1] + a[j][tmp[j]];
				ans = tmp;
			}
			++tmp[j];
		}
	}
	forn(i, n){
		printf("%d ", ans[i] + 1);
	}
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 1'000'009;

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

int n, m, k;
map <pair <int, int>, char> c;
int cntr[N][2], cntc[N][2];
int cntx[2];
set <int> badr, badc;
set<int> ur, uc;
int p2[N];

void upd2(int pos, int col, int add, int cnt[N][2], set <int> &bad, set<int> &u) {
    cnt[pos][col] += add;
    assert(cnt[pos][col] >= 0);
    
    if (cnt[pos][0] > 0 && cnt[pos][1] > 0){
        if (!bad.count(pos))
            bad.insert(pos);
    } else {
        if (bad.count(pos))
            bad.erase(pos);
    }
    
    if (cnt[pos][0] > 0 || cnt[pos][1] > 0){
        if (!u.count(pos))
            u.insert(pos);
    } else {
        if (u.count(pos))
            u.erase(pos);
    }
}

void upd(int x, int y, int t) {
    int col = (x & 1) ^ (y & 1);
    if (c.count({x, y})) {
        int ncol = col ^ c[{x, y}];
        --cntx[ncol];
        upd2(x, ncol, -1, cntr, badr, ur);
        upd2(y, ncol, -1, cntc, badc, uc);
        c.erase({x, y});
    }
    
    if (t == -1)
        return;
        
    int ncol = col ^ t;
    ++cntx[ncol];
    upd2(x, ncol, 1, cntr, badr, ur);
    upd2(y, ncol, 1, cntc, badc, uc);
    c[{x, y}] = t;
}

int main(){
    p2[0] = 1;
    for (int i = 1; i < N; ++i)
        p2[i] = sum(p2[i - 1], p2[i - 1]);
        
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; ++i) {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        --x, --y;
        upd(x, y, t);
        
        int res = 0;
        if(badr.size() > 0 && badc.size() > 0) {
            res = 0;
        } else if (badr.size() > 0) {
            assert(m - uc.size() >= 0);
            res = p2[m - uc.size()];
        } else if (badc.size() > 0) {
            assert(n - ur.size() >= 0);
            res = p2[n - ur.size()];
        } else {
            if (ur.size() == 0 && uc.size() == 0)
                res = sum(sum(p2[n], p2[m]), -2);
            else {
                assert(m - uc.size() >= 0);
                res = sum(res, p2[m - uc.size()]);
                assert(n - ur.size() >= 0);
                res = sum(res, p2[n - ur.size()]);
                if (cntx[0] == 0 || cntx[1] == 0) {
                    assert(cntx[0] != 0 || cntx[1] != 0);
                    res = sum(res, -1);
                }
            }
        }
        
        printf("%d\n", res);
    }
    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 main()
{
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	vector<vector<int>> A(n);
	vector<int> bad_num(k);
	for(int i = 0; i < n; i++)
	{
		int c;
		scanf("%d", &c);
		A[i].resize(c);
		for(int j = 0; j < c; j++)
		{
			scanf("%d", &A[i][j]); 	
			A[i][j]--;
		}
	}

	for(int i = 0; i < n; i++)
	{
	 	if(set<int>(A[i].begin(), A[i].end()).size() != A[i].size())
	 	{
	 	 	for(auto x : A[i])
	 	 		bad_num[x] = 1;
	 	}
	}
	vector<vector<int>> nxt(k);
	vector<vector<int>> prv(k);
	for(int i = 0; i < n; i++)
		for(int j = 0; j + 1 < A[i].size(); j++)
		{
		 	nxt[A[i][j]].push_back(A[i][j + 1]);
		 	prv[A[i][j + 1]].push_back(A[i][j]);
		}

	for(int i = 0; i < k; i++)
	{
	    sort(nxt[i].begin(), nxt[i].end());
	    sort(prv[i].begin(), prv[i].end());
	 	nxt[i].erase(unique(nxt[i].begin(), nxt[i].end()), nxt[i].end());
	 	prv[i].erase(unique(prv[i].begin(), prv[i].end()), prv[i].end());
	}

	vector<int> used(k, 0);
	vector<int> cnt(k + 1, 0);
	for(int i = 0; i < k; i++)
	{
		if(used[i]) continue;
	 	queue<int> q;
	 	vector<int> comp;
	 	q.push(i);
	 	used[i] = 1;
	 	while(!q.empty())
	 	{
	 		int z = q.front();
	 		q.pop();
	 		comp.push_back(z);
	 	 	for(auto x : nxt[z])
	 	 		if(!used[x])
	 	 		{
	 	 		 	used[x] = 1;
	 	 		 	q.push(x);
	 	 		}
	 	 	for(auto x : prv[z])
	 	 		if(!used[x])
	 	 		{
	 	 		 	used[x] = 1;
	 	 		 	q.push(x);
	 	 		}
	 	}
	 	bool bad = false;
	 	int cnt_beg = 0;
	 	for(auto x : comp)
	 	{
	 	 	if(prv[x].empty())
	 	 		cnt_beg++;
	 	 	if(prv[x].size() > 1 || nxt[x].size() > 1 || bad_num[x])
	 	 		bad = true;
	 	}
	 	bad |= (cnt_beg == 0);
	 	if(!bad)
	 		cnt[comp.size()]++;
	}
	vector<int> nonzero;
	for(int i = 1; i <= k; i++)
		if(cnt[i] > 0)
			nonzero.push_back(i);
	vector<int> dp(m + 1, 0);
	dp[0] = 1;
	for(int i = 1; i <= m; i++)
		for(auto x : nonzero)
		 	if(x <= i)
		 		dp[i] = add(dp[i], mul(cnt[x], dp[i - x]));

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

for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			print(i + 1, i + 2)
			break
	else:
		print(-1, -1)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s;
    cin >> n >> s;
    vector<int> id;
    for (int i = 0; i < n; ++i) if (s[i] == '2')
      id.push_back(i);
    int k = id.size();
    if (k == 1 || k == 2) {
      cout << "NO\n";
      continue;
    }
    vector<string> t(n, string(n, '='));
    for (int i = 0; i < n; ++i) t[i][i] = 'X';
    for (int i = 0; i < k; ++i) {
      int x = id[i], y = id[(i + 1) % k];
      t[x][y] = '+';
      t[y][x] = '-';
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) cout << t[i] << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int mx = *max_element(a.begin(), a.end());
    int cmx = count(a.begin(), a.end(), mx);
    int k = count(a.begin(), a.end(), mx - 1);
    int ans = 1, sub = 1;
    for (long long i = 1; i <= n; ++i) {
      ans = ans * i % MOD;
      if (i != k + 1) sub = sub * i % MOD;
    }
    if (cmx == 1) ans = (ans - sub + MOD) % MOD;
    cout << ans << '\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())
#define all(a) (a).begin(), (a).end()

#define x first
#define y second

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

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

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

int n, m, k;
vector<int> x, y;
vector<pt> ps;

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

inline void solve() {
	li ans = 0;
	
	fore (_i, 0, 2) {
		vector<int> cntY(m, 0);
		sort(all(ps));
		
		vector<pt> bord(k);
		
		int u = 0;
		while (u < k) {
			int v = u;
			while (v < k && ps[v].x == ps[u].x)
				v++;
			
			fore (i, u, v) {
				int r = int(lower_bound(all(y), ps[i].y) - y.begin());
				int l = r;
				if (y[l] > ps[i].y)
					l--;
				assert(y[l] <= ps[i].y && ps[i].y <= y[r]);
				
				bord[i] = {l, r};
			}
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				ans += cntY[bord[i].x];
			
			fore (i, u, v) if (bord[i].x < bord[i].y)
				cntY[bord[i].x]++;
			
			u = v;
		}
		
		
		fore (i, 0, k)
			swap(ps[i].x, ps[i].y);
		swap(x, y);
		swap(n, m);
	}
	
	cout << ans << endl;
}

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

vector<int> evaluate(int n, int choice_mask)
{
 	int cur_place = n / 2 + 1;
 	int cur_bit = n - 2;
 	vector<int> p(n);
 	vector<int> c(n);
 	for(int i = 0; i < n; i++)
 		c[i] = i;
 	while(c.size() != 1)
 	{
 		vector<int> nc;
 	 	for(int i = 0; i < c.size(); i += 2)
 	 	{
 	 	 	if(choice_mask & (1 << cur_bit))
 	 	 	{
 	 	 		p[c[i]] = cur_place;
 	 	 		nc.push_back(c[i + 1]);
 	 	 	}
 	 	 	else
 	 	 	{
 	 	 		p[c[i + 1]] = cur_place;
 	 	 		nc.push_back(c[i]);
 	 	 	}
 	 	 	cur_bit--;
 	 	}
 	 	c = nc;
 	 	cur_place /= 2;
  		cur_place++;
	}
	p[c[0]] = 1;
	return p;
}

vector<int> adjust(int n, vector<int> p, bool winning)
{
	for(int i = 0; i < n; i++)
	{
		if(p[i] == 1)
		{
		 	if(!winning) p[i]++;	
		}
		else
		 	p[i] = p[i] * 2 - 1;
	}
	return p;
}	

int get_hash(int n, vector<int> p, int A, bool partial = false, bool winning = false, int shift = 0)
{
	if(partial)
		p = adjust(n, p, winning);
 	int res = 0;
 	for(int i = 0; i < n; i++)
 		res = add(res, mul(add(i + 1, shift), binpow(A, p[i])));
 	return res;
}

int main()
{
 	int k, A, h;
 	cin >> k >> A >> h;
 	if(k <= 4)
 	{
 		for(int i = 0; i < (1 << ((1 << k) - 1)); i++)
 		{             
 			vector<int> p = evaluate(1 << k, i);
 			if(get_hash(1 << k, p, A) == h)
 			{
 		 		for(auto x : p) cout << x << " ";
 		 		cout << endl;
 		 		return 0;
 			}
 		}
 	}
 	else
 	{
 		int mask_left = -1;
 		int mask_right = -1;
 		bool left_win = false;
 		for(int c = 0; c < 2; c++)
 		{
 		 	map<int, int> left_map;
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int left_hash = get_hash(16, p, A, true, c == 0, 0);
 		 	 	left_map[left_hash] = i;	
 		 	}
 		 	for(int i = 0; i < (1 << 16); i++)
 		 	{
 		 	 	vector<int> p = evaluate(16, i);
 		 	 	int right_hash = get_hash(16, p, A, true, c == 1, 16);
 		 	 	int left_hash = add(h, MOD - right_hash);
 		 	 	if(left_map.count(left_hash))
 		 	 	{
 		 	 	 	mask_left = left_map[left_hash];
 		 	 	 	mask_right = i;
 		 	 	 	left_win = (c == 0);
 		 	 	}
 		 	}
 	 	}
 	 	if(mask_left != -1)
 		{
 	 		vector<int> ans_left = evaluate(16, mask_left);
 	 		vector<int> ans_right = evaluate(16, mask_right);
 	 		ans_left = adjust(16, ans_left, left_win);
 	 		ans_right = adjust(16, ans_right, !left_win);
 	 		for(auto x : ans_left)
 	 			cout << x << " ";
 	   		for(auto x : ans_right)
 	   			cout << x << " ";
 	   		return 0;
 		}        
 	}
 	cout << -1 << endl;
 	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

vector<vector<char>> g;
map<long long, bool> dp;

void brute(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		vector<vector<char>> dp2(1 << n, vector<char>(n));
		vector<int> pos1(n), pos2(n);
		forn(i, p.size()){
			pos1[p[i]] = pos2[p[i]];
			pos2[p[i]] = i;
		}
		forn(i, n) if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
		forn(mask, 1 << n) forn(i, n) if (dp2[mask][i]){
			forn(j, n) if (!((mask >> j) & 1)){
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
				dp2[mask | (1 << j)][j] |= (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
			}
		}
		forn(i, n) if (dp2[(1 << n) - 1][i]){
			long long num = 0;
			for (int x : p) num = num * 6 + x;
			dp[num] = true;
			break;
		}
		return;
	}
	for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
		p[x] = p[y] = n;
		brute(n + 1, p);
		p[x] = p[y] = -1;
	}
}

bool dfs(vector<int> p){
	vector<int> used(int(p.size()), -1);
	int cnt = 0;
	forn(i, p.size()) if (used[p[i]] == -1)
		used[p[i]] = cnt++;
	long long num = 0;
	for (int& x : p){
		x = used[x];
		num = num * 6 + x;
	}
	if (dp.count(num)) return dp[num];
	bool res = false;
	vector<int> cur(cnt);
	forn(i, p.size()) ++cur[p[i]];
	forn(i, p.size()) if (cur[p[i]] > 2){
		int x = p[i];
		for (int j = i + 1; j < int(p.size()); ++j) if (p[j] == p[i]){
			p[i] = p[j] = cnt;
			if (dfs(p)){
				res = true;
				break;
			}
			p[i] = p[j] = x;
		}
		break;
	}
	return dp[num] = res;
}

void brute2(int n, vector<int> &p){
	int x = find(p.begin(), p.end(), -1) - p.begin();
	if (x == int(p.size())){
		dfs(p);
		return;
	}
	forn(i, n + 1){
		for (int y = x + 1; y < int(p.size()); ++y) if (p[y] == -1){
			p[x] = p[y] = i;
			brute2(max(n, i + 1), p);
			p[x] = p[y] = -1;
		}
	}
}

int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	g.resize(n, vector<char>(n));
	forn(_, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v][u] = g[u][v] = 1;
	}
	vector<int> cur(n, -1);
	brute(0, cur);
	brute2(0, cur);
	vector<long long> fact(k + 1);
	fact[0] = 1;
	for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
	long long ans = 0;
	for (auto it : dp) if (it.second){
		long long num = it.first;
		long long mx = 1;
		while (num){
			mx = max(mx, num % 6 + 1);
			num /= 6;
		}
		if (mx <= k){
			ans += fact[k] / fact[k - mx];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    cout << max(6LL, n + 1) / 2 * 5 << '\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())

#define x first
#define y second

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

const int INF = int(1e9);

int W, H;
int x1, y1, x2, y2;
int w, h;

inline bool read() {
	if(!(cin >> W >> H))
		return false;
	cin >> x1 >> y1 >> x2 >> y2;
	cin >> w >> h;
	return true;
}

inline void solve() {
	int ans = INF;
	if (x2 - x1 + w <= W) {
		ans = min(ans, max(0, w - x1));
		ans = min(ans, max(0, x2 - (W - w)));
	}
	if (y2 - y1 + h <= H) {
		ans = min(ans, max(0, h - y1));
		ans = min(ans, max(0, y2 - (H - h)));
	}
	if (ans == INF)
		cout << -1 << endl;
	else
		cout << double(ans) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif	
	cout << fixed << setprecision(9);
	int t; cin >> t;
	while(t--) {
		(read());
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 2e9 + 10;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n;
		scanf("%d", &n);
		vector<vector<int>> a(2, vector<int>(n));
		forn(i, 2) forn(j, n)
			scanf("%d", &a[i][j]);
		int ans = INF;
		int sum1 = 0, sum2 = 0;
		forn(i, n) sum1 += a[0][i];
		forn(i, n){
			sum1 -= a[0][i];
			ans = min(ans, max(sum1, sum2));
			sum2 += a[1][i];
		}
		printf("%d\n", ans);
	}
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<vector<int>> pr(6, vector<int>(n + 1));
  string t = "abc";
  int cur = 0;
  do {
    for (int i = 0; i < n; ++i)
      pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
    ++cur;
  } while (next_permutation(t.begin(), t.end()));
  while (m--) {
    int l, r;
    cin >> l >> r;
    int ans = n;
    for (int i = 0; i < 6; ++i)
      ans = min(ans, pr[i][r] - pr[i][l - 1]);
    cout << ans << "\n";
  }
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

vector<int> t, ps;

void push(int v){
	if (v * 2 + 1 < int(ps.size())){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v];
	ps[v] = 0;
}

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

int get(){
	return t[1] + ps[1];
}

struct seg{
	int l, r, w;
};

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<seg> a(n);
	forn(i, n){
		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
		--a[i].l, --a[i].r;
	}
	--m;
	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
		return a.w < b.w;
	});
	t.resize(4 * m);
	ps.resize(4 * m);
	int ans = INF;
	int j = 0;
	forn(i, n){
		while (j < n && get() == 0){
			upd(1, 0, m, a[j].l, a[j].r, 1);
			++j;
		}
		if (get() == 0){
			break;
		}
		ans = min(ans, a[j - 1].w - a[i].w);
		upd(1, 0, m, a[i].l, a[i].r, -1);
	}
	printf("%d\n", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n, q;
vector< array<int, 3> > es;

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

vector< vector<pt> > g;

const int LOG = 19;
vector<int> up[LOG];
vector<int> tin, tout;
vector<int> xr;
int T = 0;

void dfs(int v, int p, int curXor) {
	tin[v] = T++;
	xr[v] = curXor;
	up[0][v] = p;
	fore (pw, 1, LOG)
		up[pw][v] = up[pw - 1][up[pw - 1][v]];
	
	for (auto [to, w] : g[v]) {
		if (to == p)
			continue;
		dfs(to, v, curXor ^ w);
	}
	tout[v] = T;
}

void buildLCA() {
	fore (pw, 0, LOG)
		up[pw].resize(n);
	tin.assign(n, -1);
	tout.assign(n, -1);
	xr.assign(n, 0);
	
	T = 0;
	fore (v, 0, n) {
		if (tin[v] != -1)
			continue;
		dfs(v, v, 0);
	}
}

int isPar(int p, int v) {
	return tin[p] <= tin[v] && tout[v] <= tout[p];
}

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

vector<int> par, rk;

void init(int n) {
	par.assign(n, 0);
	iota(par.begin(), par.end(), 0);
	rk.assign(n, 1);
}

int top(int v) {
	if (par[v] != v)
		return par[v] = top(par[v]);
	return v;
}

bool unite(int u, int v) {
	u = top(u);
	v = top(v);
	if (u == v)
		return false;
	if (rk[u] < rk[v])
		swap(u, v);
	par[v] = u;
	rk[u] += rk[v];
	return true;
}

vector<int> F;
void inc(int pos, int val) {
	for(; pos < sz(F); 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;
}

void addOnPath(int v, int l) {
	while (v != l) {
		inc(tin[v], 1);
		inc(tout[v], -1);
		v = up[0][v];
	}
}

inline void solve() {
	init(n);
	g.resize(n);
	
	vector<int> ans(q, -1);
	fore (i, 0, q) {
		int u = es[i][0];
		int v = es[i][1];
		int x = es[i][2];
		
		if (unite(u, v)) {
			ans[i] = 1;
			g[u].emplace_back(v, x);
			g[v].emplace_back(u, x);
		}
	}
	
	buildLCA();
	F.assign(2 * n + 5, 0);
	
	fore (i, 0, q) {
		if (ans[i] != -1)
			continue;
		
		ans[i] = 0;
		int u = es[i][0];
		int v = es[i][1];
		int x = es[i][2];
		
		int xorPath = xr[u] ^ xr[v];
		if ((xorPath ^ x) != 1)
			continue;
		
		int l = lca(u, v);
		int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]);
		if (usedOnPath > 0)
			continue;
		
		ans[i] = 1;
		addOnPath(u, l);
		addOnPath(v, l);
	}
	
	for (int res : ans)
		cout << (res ? "YES" : "NO") << '\n';
}

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

def maxSum(x):
	return x ** 2

def getAns(x):
	res = 1
	while maxSum(res) < x:
		res += 1
	return res

def main():
	t = int(input())
	for i in range(t):
		print(getAns(int(input())))

main()

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;
    int m = unique(s.begin(), s.end()) - s.begin();
    cout << n * a + max(n * b, (m / 2 + 1) * b) << '\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())

#define x first
#define y second

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

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

int n;
vector<li> a;

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

li d(const pt &a, const pt &b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

inline void solve() {
	li ans = 0;
	fore (i, 0, n) {
		fore (j, i, n) {
			if (i + 2 <= j) {
				bool ok = true;
				fore (i1, i, j) fore (i2, i1 + 1, j) {
					if (d(pt(a[i1], i1), pt(a[j], j)) == d(pt(a[i1], i1), pt(a[i2], i2)) + d(pt(a[i2], i2), pt(a[j], j)))
						ok = false;
				}
				if (!ok)
					break;
			}
			ans++;
		}
	}
	cout << ans << endl;
}

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

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

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

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

int norm(int a) {
	while (a >= MOD)
		a -= MOD;
	while (a < 0)
		a += MOD;
	return a;
}
int mul(int a, int b) {
	return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
	int ans = 1;
	while (k > 0) {
		if (k & 1)
			ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int N = 200 * 1000 + 55;
int f[N], inf[N];

void precalc() {
	f[0] = inf[0] = 1;
	fore (i, 1, N) {
		f[i] = mul(f[i - 1], i);
		inf[i] = binPow(f[i], MOD - 2);
	}
}

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

int n, l, r;

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

inline void solve() {
	int half = n / 2;
	int st = min(1 - l, r - n);
	
	int ans = mul(st, C(n, half));
	if (n & 1)
		ans = norm(ans + mul(st, C(n, half + 1)));
	
	for (int k = st + 1; ; k++) {
		int lf = max(1, l + k);
		int rg = min(n, r - k);
		
		if (rg + 1 - lf < 0)
			break;
		
		ans = norm(ans + C(rg + 1 - lf, half - (lf - 1)));
		if (n & 1)
			ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1)));
	}
	
	cout << ans << endl;
}

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

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

using namespace std;

int n, k;
string s;

bool check(int d){
	vector<int> lst(k, n);
	vector<vector<int>> pos(n + 1, vector<int>(k, n + 1));
	for (int i = n - 1; i >= 0; --i){
		if (s[i] != '?'){
			lst[s[i] - 'a'] = i;
		}
		int cur = n;
		forn(j, k){
			pos[i][j] = (i + d <= cur ? i + d : pos[i + 1][j]);
			cur = min(cur, lst[j]);
		}
		cur = n;
		for (int j = k - 1; j >= 0; --j){
			if (i + d > cur) pos[i][j] = pos[i + 1][j];
			cur = min(cur, lst[j]);
		}
	}
	vector<int> dp(1 << k, n + 1);
	dp[0] = 0;
	forn(mask, 1 << k) if (dp[mask] < n + 1){
		forn(i, k) if (!((mask >> i) & 1))
			dp[mask | (1 << i)] = min(dp[mask | (1 << i)], pos[dp[mask]][i]);
	}
	return dp[(1 << k) - 1] <= n;
}

int main() {
	cin >> n >> k;
	cin >> s;
	int l = 1, r = n;
	int res = 0;
	while (l <= r){
		int m = (l + r) / 2;
		if (check(m)){
			res = m;
			l = m + 1;
		}
		else{
			r = m - 1;
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

struct edge2{
	int u, w;
};

vector<vector<edge2>> g;

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

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

vector<vector<int>> comps;
vector<int> p;

bool unite(int a, int b){
	a = p[a], b = p[b];
	if (a == b) return false;
	if (comps[a].size() < comps[b].size()) swap(a, b);
	for (int v : comps[b]){
		p[v] = a;
		comps[a].push_back(v);
	}
	comps[b].clear();
	return true;
}

vector<int> mn;

void dfs(int v, int p, int d){
	mn[v] = d;
	for (auto e : g[v]) if (e.u != p)
		dfs(e.u, v, max(d, e.w));
}

int main() {
	int n, q, s, d;
	scanf("%d%d%d%d", &n, &q, &s, &d);
	--s;
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> idx(a[n - 1] + 1);
	forn(i, n) idx[a[i]] = i;
	comps.resize(n);
	p.resize(n);
	forn(i, n) comps[i] = vector<int>(1, i), p[i] = i;
	g.resize(n);
	set<int> pos(a.begin(), a.end());
	int cnt = n;
	while (cnt > 1){
		vector<edge3> es;
		for (const vector<int> &comp : comps) if (!comp.empty()){
			for (int i : comp)
				pos.erase(a[i]);
			edge3 mn = {-1, -1, INF};
			for (int i : comp){
				for (int dx : {-d, d}){
					auto it = pos.lower_bound(a[i] + dx);
					if (it != pos.end())
						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
					if (it != pos.begin()){
						--it;
						mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)});
					}
				}
			}
			for (int i : comp)
				pos.insert(a[i]);
			assert(mn.v != -1);
			es.push_back(mn);
		}
		for (auto e : es){
			if (unite(e.v, e.u)){
				--cnt;
				g[e.v].push_back({e.u, e.w});
				g[e.u].push_back({e.v, e.w});
			}
		}
	}
	mn.resize(n);
	dfs(s, -1, 0);
	forn(_, q){
		int i, k;
		scanf("%d%d", &i, &k);
		--i;
		puts(mn[i] <= k ? "Yes" : "No");
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

struct edge2{
	int u, w;
};

vector<vector<edge2>> g;

struct edge3{
	int v, u, w;
	edge3(){}
	edge3(int v, int u, int w) : v(v), u(u), w(w) {
		if (v > u) swap(v, u);
	}
};

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

vector<int> p, rk;

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

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

vector<int> mn;

void dfs(int v, int p, int d){
	mn[v] = d;
	for (auto e : g[v]) if (e.u != p)
		dfs(e.u, v, max(d, e.w));
}

int main() {
	int n, q, s, d;
	scanf("%d%d%d%d", &n, &q, &s, &d);
	--s;
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	p.resize(n);
	rk.resize(n);
	forn(i, n) rk[i] = 1, p[i] = i;
	g.resize(n);
	int cnt = n;
	int iter = 0;
	while (cnt > 1){
		++iter;
		vector<edge3> es(n, edge3(-1, -1, INF));
		int j, mn1, mn2;
		j = 0, mn1 = -1, mn2 = -1;
		forn(i, n) getp(i);
		forn(i, n){
			while (j < n && a[i] - a[j] > d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				++j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = 0, mn1 = -1, mn2 = -1;
		forn(i, n){
			while (j < n && a[j] - a[i] <= d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				++j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = n - 1, mn1 = -1, mn2 = -1;
		for (int i = n - 1; i >= 0; --i){
			while (j >= 0 && a[j] - a[i] > d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				--j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		j = n - 1, mn1 = -1, mn2 = -1;
		for (int i = n - 1; i >= 0; --i){
			while (j >= 0 && a[i] - a[j] <= d){
				if (mn1 == -1 || p[mn1] == p[j])
					mn1 = j;
				else{
					mn2 = mn1;
					mn1 = j;
				}
				--j;
			}
			if (mn1 != -1 && p[mn1] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d)));
			}
			if (mn2 != -1 && p[mn2] != p[i]){
				es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d)));
			}
		}
		for (auto e : es) if (e.v != -1){
			if (unite(e.v, e.u)){
				--cnt;
				g[e.v].push_back({e.u, e.w});
				g[e.u].push_back({e.v, e.w});
			}
		}
	}
	mn.resize(n);
	dfs(s, -1, 0);
	forn(_, q){
		int i, k;
		scanf("%d%d", &i, &k);
		--i;
		puts(mn[i] <= k ? "Yes" : "No");
	}
	return 0;
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (r, b, d) = readLine()!!.split(' ').map { it.toInt() }
        println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO")
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }
        println(if (n * m - 1 == k) "YES" else "NO")
    }
}

#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> s(n), u(n);
        forn(i, n){
            scanf("%d", &s[i]);
            --s[i];
        }
        forn(i, n){
            scanf("%d", &u[i]);
        }
        vector<vector<int>> bst(n);
        forn(i, n) bst[s[i]].push_back(u[i]);
        forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>());
        vector<vector<long long>> pr(n, vector<long long>(1, 0));
        forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x);
        vector<long long> ans(n);
        forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k)
            ans[k - 1] += pr[i][bst[i].size() / k * k];
        forn(i, n)
            printf("%lld ", ans[i]);
        puts("");
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

using li = long long;

int main() {
  int n;
  cin >> n;
  vector<li> a(n), b(n);
  for (auto& x : a) cin >> x;
  for (auto& x : b) cin >> x;
  vector<li> pr(n + 1, 0);
  for (int i = 0; i < n; ++i)
    pr[i + 1] = pr[i] + a[i] * b[i];
  li ans = pr[n];
  for (int c = 0; c < n; ++c) {
    li cur = a[c] * b[c];
    for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) {
      cur += a[l] * b[r];
      cur += a[r] * b[l];
      ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    }
    cur = 0;
    for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) {
      cur += a[l] * b[r];
      cur += a[r] * b[l];
      ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
    }
  }
  cout << ans << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

struct point{
    int a, b, c, d;
};

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

int n;
vector<point> a;
map<frac, int> sv;

frac norm(long long x, long long y){
    long long g = __gcd(x, y);
    return {x / g, y / g};
}

vector<vector<pt>> g;
vector<int> used;
vector<pt> ans;

int dfs(int v){
    used[v] = 1;
    int cur = -1;
    for (auto it : g[v]){
        int u = it.x;
        int i = it.y;
        if (used[u] == 1) continue;
        int nw = i;
        if (!used[u]){
            int tmp = dfs(u);
            if (tmp != -1){
                ans.push_back({nw, tmp});
                nw = -1;
            }
        }
        if (nw != -1){
            if (cur != -1){
                ans.push_back({cur, nw});
                cur = -1;
            }
            else{
                cur = nw;
            }
        }
    }
    used[v] = 2;
    return cur;
}

int main() {
    scanf("%d", &n);
    a.resize(n);
    forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
    g.resize(2 * n);
    forn(i, n){
        frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c);
        frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d));
        if (!sv.count(f1)){
            int k = sv.size();
            sv[f1] = k;
        }
        if (!sv.count(f2)){
            int k = sv.size();
            sv[f2] = k;
        }
        g[sv[f1]].push_back({sv[f2], i});
        g[sv[f2]].push_back({sv[f1], i});
    }
    used.resize(sv.size());
    forn(i, sv.size()) if (!used[i])
        dfs(i);
    printf("%d\n", int(ans.size()));
    for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1);
}

#include<bits/stdc++.h>

using namespace std;

const int N = 6;
const int M = 400;
const int INF = int(1e9);

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

struct state
{
    vector<int> need;
    int v2;
    int v1;
    int rem;
    state() {};
    state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {};
};

int get_code(const vector<int>& v)
{
    int ans = 0;
    for(int i = 0; i < v.size(); i++)
        ans = ans * 5 + v[i];
    return ans;
}

int get_code(const state& s)
{
    int code = get_code(s.need);
    code = code * 6 + s.v2;
    code = code * 6 + s.v1;
    code = code * 5 + s.rem;
    return code; 
}

vector<int> get_vector(int code, int n)
{
    vector<int> res(n);
    for(int i = n - 1; i >= 0; i--)
    {
        res[i] = code % 5;
        code /= 5;
    }
    return res;
}

state get_state(int code)
{
    int rem = code % 5;
    code /= 5;
    int v1 = code % 6;
    code /= 6;
    int v2 = code % 6;
    code /= 6;
    vector<int> need = get_vector(code, n);
    return state(need, v1, v2, rem);
}

const int Z = 40 * int(1e6);
int dp[Z];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> c[i][j];
    for(int i = 0; i < Z; i++)
        dp[i] = INF;
    state start(vector<int>(n, 0), 0, 0, 0);
    int ans = INF;
    dp[get_code(start)] = 0;
    for(int i = 0; i < Z; i++)
    {
        if(dp[i] == INF) continue;
        state s = get_state(i);
        for(int f = 0; f <= 4; f++)
        {
            if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2])
                continue;
            int add = (f == 0 ? 0 : c[s.v1][s.v2]);
            state nw = s;
            nw.need[s.v1] += f;
            nw.rem += f;
            if(s.v1 == n - 1)
            {
                nw.v1 = 0;
                nw.v2 = s.v2 + 1;
                nw.rem = 0;
            }
            else
            {
                nw.v1 = s.v1 + 1;
            }
            if(nw.need == vector<int>(a, a + n))
                ans = min(ans, dp[i] + add);
            if(nw.v2 < m)
            {
                int code = get_code(nw);
                dp[code] = min(dp[code], dp[i] + add);
            }
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;

}

fun main() {
    repeat(readLine()!!.toInt()) {
        readLine()!!.toInt()
        println(readLine()!!.split(' ').count { it != "2" })
    }
}

for t in range(int(input())):
	a, b, c = map(int, input().split())
	print("1" + "0" * (a - 1), "1" * (b - c + 1) + "0" * (c - 1))

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<int> a(n);
  for (int& x : a) scanf("%d", &x);
  while (q--) {
    int x;
    scanf("%d", &x);
    int p = find(a.begin(), a.end(), x) - a.begin();
    printf("%d ", p + 1);
    rotate(a.begin(), a.begin() + p, a.begin() + p + 1);
  }
}

#include <bits/stdc++.h>

using namespace std;

int n, k;
int cur[26];
vector<int> path;

void dfs(int v) {
  while (cur[v] < k) {
    int u = cur[v]++;
    dfs(u);
    path.push_back(u);
  }
}

int main() {
  scanf("%d%d", &n, &k);
  dfs(0);
  printf("a");
  for (int i = 0; i < n - 1; ++i)
    printf("%c", path[i % path.size()] + 'a');
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300043;
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 mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

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

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

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

string s[N];
int p[N];
int n, m;
char buf[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%s", buf);
        s[i] = buf;
    }
    p[0] = divide(1, 2);
    for(int i = 1; i < N; i++)
        if(i % 2 == 1)
            p[i] = sub(p[i - 1], divide(1, binpow(2, i)));
        else
            p[i] = add(p[i - 1], divide(1, binpow(2, i)));
    int ans = 0;
    int w = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(s[i][j] != '*')
                w = add(w, 1);
    for(int i = 0; i < n; i++)
    {
        int c = 0;
        for(int j = 0; j < m; j++)
        {
            if(s[i][j] == '*')
                c = 0;
            else
                c++;
            if(c > 0)
                ans = add(ans, p[c]);
        }
    }
    for(int j = 0; j < m; j++)
    {
        int c = 0;
        for(int i = 0; i < n; i++)
        {
            if(s[i][j] == '*')
                c = 0;
            else
                c++;
            if(c > 0)
                ans = add(ans, p[c]);
        }
    }
    ans = mul(ans, binpow(2, w));
    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;
const int K = 161;
const int AL = 26;

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

vector<node> trie;

int tot;

void add(const string &s){
	int cur = 0;
	int d = 1;
	for (const char &c : s){
		++d;
		if (trie[cur][c - 'a'] == -1){
			trie[cur][c - 'a'] = trie.size();
			trie.push_back(node());
			tot += d;
		}
		cur = trie[cur][c - 'a'];
	}
	trie[cur].term = true;
}

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

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

typedef array<array<int, K>, K> mat;

mat operator *(const mat &a, const mat &b){
	mat c;
	forn(i, K) forn(j, K) c[i][j] = 0;
	forn(i, K) forn(j, K) forn(k, K)
		c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
	return c;
}

mat binpow(mat a, long long b){
	mat res;
	forn(i, K) forn(j, K) res[i][j] = i == j;
	while (b){
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}

map<pair<int, int>, int> num;
queue<pair<int, int>> q;

int get(int v, int u){
	if (v > u) swap(v, u);
	if (!num.count({v, u})){
		int k = num.size();
		assert(k < K);
		num[{v, u}] = k;
		q.push({v, u});
	}
	return num[{v, u}];
}

int main() {
	int n;
	long long m;
	cin >> n >> m;
	trie = vector<node>(1, node());
	tot = 1;
	forn(i, n){
		string s;
		cin >> s;
		add(s);
	}
	q.push({0, 0});
	num[q.front()] = 0;
	mat init;
	forn(i, K) forn(j, K) init[i][j] = 0;
	while (!q.empty()){
		int v = q.front().first;
		int u = q.front().second;
		q.pop();
		int x = get(v, u);
		forn(c, AL){
			int tov = trie[v][c];
			int tou = trie[u][c];
			if (tov == -1 || tou == -1) continue;
			++init[x][get(tov, tou)];
			if (trie[tov].term) ++init[x][get(0, tou)];
			if (trie[tou].term) ++init[x][get(tov, 0)];
			if (trie[tov].term && trie[tou].term) ++init[x][0];
		}
	}
	init = binpow(init, m);
	printf("%d\n", init[0][0]);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200043;
const int K = 10;
const int Z = 1 << K;

int rem[Z];
int t[N];

int get(int r)
{
    int result = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        result ^= t[r];
    return result;
}

void change(int i, int delta)
{
    for (; i < N; i = (i | (i + 1)))
        t[i] ^= delta;
}

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

int ans[N];
int c[N];
int cnt[N];
int n, m;
int ls[N];
int rs[N];
vector<int> qs[N];
vector<int> qs2[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &c[i]);
        cnt[c[i]]++;
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        ls[i] = l;                                                                         
        rs[i] = r;
        qs[l].push_back(i);
        qs2[r + 1].push_back(i);
    }
    for(int i = m; i >= 1; i--)
    {
        for(int j = 0; j < cnt[i]; j++)
        {
            rem[i % (1 << K)]++;
            int r = i;
            while(true)
            {
                int l = r - Z + 1;
                l = max(1, l);
                if(l > r)
                    break;
                int diff = i - l;
                diff >>= K;
                change(l, diff);
                change(r + 1, diff);
                r -= Z;
            }
        }
        for(auto x : qs[i])
        {
            int cur = (get(i)) << K;
            for(int k = 0; k < Z; k++)
            {
                int dist = (k - i) % Z;
                if(dist < 0)
                    dist += Z;
                if(rem[k] & 1)
                    cur ^= dist;
            }
            ans[x] ^= cur;
        }
        for(auto x : qs2[i])
        {
            int cur = (get(ls[x])) << K;
            for(int k = 0; k < Z; k++)
            {
                int dist = (k - ls[x]) % Z;
                if(dist < 0)
                    dist += Z;
                if(rem[k] & 1)
                    cur ^= dist;
            }
            ans[x] ^= cur;
        }
    }
    for(int i = 0; i < q; i++)
        if(ans[i] == 0)
            printf("B");
        else
            printf("A");
}