#include <bits/stdc++.h>

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

using namespace std;

int n, m, m2;
vector<vector<char>> g;

int T;
vector<int> mt;
vector<int> used;

bool try_kuhn(int v){
    if (used[v] == T)
        return false;
    used[v] = T;
    forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
        mt[u] = v;
        return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    vector<string> b(m, string(n, '0'));
    forn(i, n){
        string t;
        cin >> t;
        forn(j, m) b[j][i] = t[j];
    }
    
    vector<string> nw = b;
    sort(nw.begin(), nw.end());
    nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
    m2 = nw.size();
    g.assign(m2, vector<char>(m2, 0));
    forn(i, m2) forn(j, m2) if (i != j){
        bool in = true;
        forn(k, n) in &= nw[i][k] >= nw[j][k];
        if (in) g[i][j] = 1;
    }
    
    mt.assign(m2, -1);
    used.assign(m2, -1);
    T = 0;
    int k = m2;
    forn(i, m2) if (try_kuhn(i)){
        ++T;
        --k;
    }
    
    vector<int> nxt(m2, -1);
    vector<char> st(m2, true);
    forn(i, m2) if (mt[i] != -1){
        nxt[mt[i]] = i;
        st[i] = false;
    }
    
    vector<int> gr(m2), req(m2);
    int t = 0;
    forn(i, m2) if (st[i]){
        int v = i;
        int pos = 2;
        while (v != -1){
            gr[v] = t;
            req[v] = pos;
            ++pos;
            v = nxt[v];
        }
        ++t;
    }
    assert(t == k);
    
    vector<int> num(m);
    forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
    
    printf("%d\n", k);
    forn(i, m) printf("%d ", gr[num[i]] + 1);
    puts("");
    forn(i, m) printf("%d ", req[num[i]]);
    puts("");
    forn(i, n){
        vector<int> l(k, 1);
        forn(j, m2) if (nw[j][i] == '1')
            l[gr[j]] = max(l[gr[j]], req[j]);
        forn(j, k)
            printf("%d ", l[j]);
        puts("");
    }
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    s = input()
    print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')

#include <bits/stdc++.h>

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

using namespace std;

const int MOD = 998244353;

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

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

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    vector<int> fact(4 * n + 1);
    fact[0] = 1;
    fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
    vector<int> rfact(4 * n + 1);
    rfact.back() = binpow(fact.back(), MOD - 2);
    for (int i = int(fact.size()) - 2; i >= 0; --i)
        rfact[i] = mul(rfact[i + 1], i + 1);
    
    auto cnk = [&](int n, int k){
        return mul(fact[n], mul(rfact[k], rfact[n - k]));
    };
    
    vector<vector<int>> sv(n + 1, vector<int>(5));
    forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
    
    vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
    forn(ii, n + 1){
        int i = ii & 1;
        int ni = i ^ 1;
        dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
        for (int t = 1; t <= 4; ++t)
            dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
        forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
            dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
            for (int t = 1; p + t <= 4; ++t)
                dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
        }
    }
    
    int ans = 0;
    forn(sum, k + 1){
        ans = add(ans, mul(mul(mul(
            sum < k ? 1 : 4 * n - k, 
            dp[(n & 1) ^ 1][sum][4]), 
            mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))), 
            mul(fact[4], fact[sum]))
        );
    }
    
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

#define N 200000

int a[N], n, s;

bool can(int x) {
    int l = x - 1, r = n - 1;
    while (l < r) {
        if (a[r] > s - a[l]) return false;
        ++l;
        if (l < r) {
            if (a[l] > s - a[r]) return false;
            --r;
        }
    }
    return true;
}


int main() {
    long long sum = 0;
    scanf("%d %d\n", &n, &s);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    sort(a, a + n, greater<int>());

    int l = 1, r = n;
    while (l < r) {
        int m = (l + r) >> 1;
        if (can(m)) r = m;
        else l = m + 1;
    }

    long long ans = sum + r;
    cout << ans << endl;

    return 0;
}

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

void solve() 
{
    int n, a, b;
    cin >> n >> a >> b;
    int x = (n + a - 1) / a;
    if(a > b) x = 1;
    cout << x << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

typedef long long li;

const li INF64 = 1e18;

struct base{
    int x, w, c;
};

li area(const base &a, const base &b){
    return (a.c + b.c) * li(abs(a.x - b.x));
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<base> a(n);
    forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
    sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
    vector<li> dp(n, -INF64);
    li ans = 0;
    forn(i, n){
        dp[i] = max(dp[i], -a[i].w * 200ll);
        for (int j = i + 1; j < n; ++j)
            dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
        ans = max(ans, dp[i]);
    }
    printf("%.15Lf\n", ans / (long double)(200));
    return 0;
}

#include <bits/stdc++.h>     

using namespace std;

mt19937 rnd(42);
uniform_int_distribution<int> d(1, 2);

int ask(int t, int i)
{
    cout << t << " " << i + 1 << endl;
    int x;
    cin >> x;
    return x;
}

void giveAnswer(const string& s)
{
    cout << 0 << " " << s << endl;
    int x;
    cin >> x;
    assert(x == 1);
}

void guessOne(string& s, int i)
{
    int res = ask(1, i);
    if(res == 0)
        s[i] = '1';
    else
        s[i] = s[res - 1];
}

char inv(char c)
{
    if(c == '0') return '1';
    return '0';
}

void guessTwo(string& s, int i)
{
    if(s[1] == '0')
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                s[i - 1] = '1';
            }
            else
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                s[i - 1] = '0';
            }
            else
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
        }
    }
    else
    {
        if(d(rnd) == 1)
        {
            int res = ask(1, i);
            if(res >= 2)
            {
                s[i] = s[res - 1];
                s[i - 1] = s[res - 2];
            }
            else if(res == 1)
            {
                s[i] = '0';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '1';
                s[i - 1] = '1';
            }
        }
        else
        {
            int res = ask(2, i);
            if(res >= 2)
            {
                s[i] = inv(s[res - 1]);
                s[i - 1] = inv(s[res - 2]);
            }
            else if(res == 1)
            {
                s[i] = '1';
                guessOne(s, i - 1);
            }
            else
            {
                s[i] = '0';
                s[i - 1] = '0';
            }
        }
    }
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        string s(n, '0');
        for(int j = 1; j < n; j += 2)
        {
            if(j == 1) guessOne(s, j);
            else guessTwo(s, j);
        }
        if(n % 2 == 1) guessOne(s, n - 1);
        giveAnswer(s);
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    g[y - 1].push_back(x - 1);
  }
    
  vector<int> ans(n, -1);
  for (int s = 0; s < n; ++s) {
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) 
      for (int j : g[i]) ++deg[j];
    priority_queue<pair<int, int>> q;
    for (int v = 0; v < n; ++v)
      if (deg[v] == 0 && v != s)
        q.push({a[v], v});
    for (int i = n; i > 0; --i) {
      if (q.empty() || q.top().first < i) {
        if (deg[s] == 0 && i <= a[s])
          ans[s] = i;
        break;
      }
      int v = q.top().second;
      q.pop();
      for (int u : g[v]) {
        --deg[u];
        if (deg[u] == 0 && u != s)
          q.push({a[u], u});
      }
    }
  }
  
  for (int &x : ans) cout << x << ' ';
}
 

#include <bits/stdc++.h>

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

using namespace std;

const string al = "KQRBN";

const int INF = 1e9;

struct mv{ int dx, dy; };
struct piece{ int x, y, t; };
struct seg{ int l, r; };
struct pos{ int x, y; };

bool operator <(const pos &a, const pos &b){
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

vector<vector<mv>> mvs({
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
    {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
    {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
});

int main() {
    int sx, sy, fx, fy;
    cin >> sx >> sy >> fx >> fy;
    swap(sx, sy), swap(fx, fy);
    --sx, --fx;
    
    int k;
    cin >> k;
    vector<piece> a(k);
    forn(i, k){
        string t;
        cin >> t >> a[i].x >> a[i].y;
        swap(a[i].x, a[i].y);
        --a[i].x;
        a[i].t = al.find(t[0]);
    }
    
    sort(a.begin(), a.end(), [](const piece &a, const piece &b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    
    vector<int> base({sy, fy});
    forn(i, k) base.push_back(a[i].y);
    vector<int> ys;
    for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
        ys.push_back(i);
    sort(ys.begin(), ys.end());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    
    vector<vector<char>> tk(8, vector<char>(ys.size()));
    forn(i, k){
        a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
        tk[a[i].x][a[i].y] = true;
    }
    sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
    fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
    
    vector<vector<char>> bad = tk;
    
    forn(i, k){
        int x = a[i].x, y = a[i].y;
        if (a[i].t == 0 || a[i].t == 4){
            for (auto it : mvs[a[i].t]){
                int nx = x + it.dx;
                int ny = y + it.dy;
                if (0 <= nx && nx < 8)
                    bad[nx][ny] = true;
            }
        }
        else{
            for (auto it : mvs[a[i].t]){
                for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
                    if (nx < 0 || nx >= 8) break;
                    if (ny < 0 || ny >= int(ys.size())) break;
                    if (tk[nx][ny]) break;
                    bad[nx][ny] = true;
                }
            }
        }
    }
    
    vector<vector<int>> d(8, vector<int>(ys.size(), INF));
    vector<vector<pos>> p(8, vector<pos>(ys.size()));
    set<pair<int, pos>> q;
    d[sx][sy] = 0;
    q.insert({0, {sx, sy}});
    while (!q.empty()){
        int x = q.begin()->second.x;
        int y = q.begin()->second.y;
        q.erase(q.begin());
        if (x == fx && y == fy){
            cout << d[x][y] << endl;
            return 0;
        }
        for (int ny : {y - 1, y, y + 1}){
            if (ny < 0 || ny >= int(ys.size())) continue;
            int dy = max(1, abs(ys[y] - ys[ny]));
            for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
                int nd = d[x][y] + dy;
                if (d[nx][ny] > nd){
                    q.erase({d[nx][ny], {nx, ny}});
                    d[nx][ny] = nd;
                    p[nx][ny] = {x, y};
                    q.insert({d[nx][ny], {nx, ny}});
                }
            }
        }
    }
    
    cout << -1 << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    long long total = 0;
    for(int i = 0; i < n; i++)
    {
        total += n * 1ll * (a[i] + b[i]);
        total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
        total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
    }
    for(int i = 0; i < n; i++)
        total -= (n - 1) * 1ll * abs(a[i] - b[i]);
    cout << total << endl;
}

#include<bits/stdc++.h>

using namespace std;

int n;
vector< vector<int> > a;

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

void solve() {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += accumulate(a[i].begin(), a[i].end(), 0LL);
    
    int mn = a[0][n - 1];
    for (int i = 0; i < n; i++)
        mn = min(mn, a[i][n - 1 - i]);
    
    cout << sum - mn << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<char>> ds(n, vector<char>(7));
    forn(i, n){
        int t;
        cin >> t;
        forn(_, t){
            string s;
            cin >> s;
            ds[i][find(days, days + 7, s) - days] = true;
        }
    }
    vector<int> h(m);
    forn(i, m) cin >> h[i];
    vector<vector<int>> a(k);
    forn(i, k){
        int p;
        cin >> p;
        a[i].resize(p);
        forn(j, p){
            cin >> a[i][j];
            --a[i][j];
        }
    }
    int j = 0;
    vector<int> ans(k, -1), lst(k);
    int done = 0;
    vector<map<int, int>> cur(7);
    vector<set<int>> wk(n);
    forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
        ++cur[j][a[i][0]];
    forn(i, k)
        wk[a[i][0]].insert(i);
    for (int d = 1;; ++d){
        if (j < m && h[j] == d){
            ++j;
            continue;
        }
        int wd = (d - 1) % 7;
        vector<int> now, sv;
        for (auto it : cur[wd]) now.push_back(it.first);
        for (int x : now){
            forn(i, 7){
                auto it = cur[i].find(x);
                if (it != cur[i].end()){
                    if (it->second == 1)
                        cur[i].erase(it);
                    else
                        --it->second;
                }
            }
            int y = *wk[x].begin();
            sv.push_back(y);
            wk[x].erase(wk[x].begin());
        }
        forn(i, now.size()){
            int y = sv[i];
            ++lst[y];
            if (lst[y] == int(a[y].size())){
                ans[y] = d;
                ++done;
                continue;
            }
            wk[a[y][lst[y]]].insert(y);
            forn(j, 7) if (ds[a[y][lst[y]]][j])
                ++cur[j][a[y][lst[y]]];
        }
        if (done == k) break;
    }
    forn(i, k) cout << ans[i] << " ";
    cout << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int a = 1;
    for (int g = 2; g * g <= n; ++g) {
      if (n % g == 0) {
        a = n / g;
        break;
      }
    }
    cout << a << ' ' << n - a << '\n';
  }
}
 

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int t;
  cin >> t;
  while (t--) {
    string x;
    cin >> x;
    int k;
    cin >> k;
    int n = x.size();
    vector<vector<int>> pos(10);
    for (int i = 0; i < n; ++i)
      pos[x[i] - '0'].push_back(i);
    for (int i = 0; i < 10; ++i)
      reverse(pos[i].begin(), pos[i].end());
    string ans;
    int lst = 0, len = n - k;
    for (int i = 0; i < len; ++i) {
      for (int d = (i == 0); d <= 9; ++d) {
        while (!pos[d].empty() && pos[d].back() < lst)
          pos[d].pop_back();
        if (!pos[d].empty() && pos[d].back() - lst <= k) {
          ans += d + '0';
          k -= pos[d].back() - lst;
          lst = pos[d].back() + 1;
          break;
        }
      }
    }
    cout << ans << '\n';
  }
}