#include <bits/stdc++.h>

using namespace std;

bool solve() {
  string s;
  cin >> s;
  vector<int> d(3);
  int x = s[0] - 'A';
  int y = s.back() - 'A';
  if (x == y)
    return false;
  d[x] = 1; d[y] = -1;
  if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2)
    d[3 ^ x ^ y] = -1;
  else
    d[3 ^ x ^ y] = 1;
  int bal = 0;
  for (char c : s) {
    bal += d[c - 'A'];
    if (bal < 0) return false;
  }
  return bal == 0;
}

int main() {
  int t; cin >> t;
  while (t--) {
    cout << (solve() ? "YES\n" : "NO\n");
  }
}

for _ in range(int(input())):
    n, U, R, D, L = map(int, input().split())
    for mask in range(16):
        rU, rR, rD, rL = U, R, D, L
        if mask & 1:
            rU -= 1
            rL -= 1
        if mask & 2:
            rL -= 1
            rD -= 1
        if mask & 4:
            rD -= 1
            rR -= 1
        if mask & 8:
            rR -= 1
            rU -= 1
        if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2:
            print("YES")
            break
    else:
        print("NO")

#include <bits/stdc++.h>

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

using namespace std;

int calc(const vector<int> &a, const vector<int> &b){
    int n = a.size();
    int m = b.size();
    vector<int> su(n + 1);
    int r = m - 1;
    for (int i = n - 1; i >= 0; --i){
        su[i] = su[i + 1];
        while (r >= 0 && b[r] > a[i]) --r;
        if (r >= 0 && b[r] == a[i]) ++su[i];
    }
    int ans = 0;
    int j = 0;
    r = 0;
    forn(l, m){
        while (j < n && a[j] <= b[l] + j) ++j;
        while (r < m && b[r] - b[l] < j) ++r;
        ans = max(ans, r - l + su[j]);
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(n), b(m);
        forn(i, n) scanf("%d", &a[i]);
        forn(i, m) scanf("%d", &b[i]);
        vector<int> al, bl, ar, br;
        forn(i, n){
            if (a[i] < 0) al.push_back(-a[i]);
            else ar.push_back(a[i]);
        }
        forn(i, m){
            if (b[i] < 0) bl.push_back(-b[i]);
            else br.push_back(b[i]);
        }
        reverse(al.begin(), al.end());
        reverse(bl.begin(), bl.end());
        printf("%d\n", calc(al, bl) + calc(ar, br));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 505;

int n;
int a[N][N];
int c[2 * N];
vector<pair<int, int>> e;

int calc(vector<int> ls) {
  if (sz(ls) == 1)
    return ls[0];
  
  int res = -1;
  for (int u : ls)
    res = max(res, a[ls[0]][u]);
  
  vector<vector<int>> ch;
  ch.push_back({ls[0]});
  for (int i = 1; i < sz(ls); ++i) {
    int v = ls[i];
    int group = -1;
    for (int j = 0; j < sz(ch); ++j) {
      if (a[v][ch[j][0]] != res) {
        group = j;
        break;
      }
    }
    if (group == -1) {
      group = sz(ch);
      ch.push_back({});
    }
    ch[group].push_back(v);
  }
  
  int v = n++;
  c[v] = res;
  for (int i = 0; i < sz(ch); ++i) {
    int u = calc(ch[i]);
    e.emplace_back(u, v);
  }
  return v;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      cin >> a[i][j];
  for (int i = 0; i < n; ++i)
    c[i] = a[i][i];
  vector<int> ls(n);
  iota(ls.begin(), ls.end(), 0);
  int root = calc(ls);
  cout << n << '\n';
  for (int i = 0; i < n; ++i)
    cout << c[i] << ' ';
  cout << '\n' << root + 1 << '\n';
  for (auto it : e)
    cout << it.first + 1 << ' ' << it.second + 1 << '\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 pair<int, int> pt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    map<pt, int> allEdges;
    set<pt> difPairs, eqPairs;
    
    fore (q, 0, m) {
        char tp; cin >> tp;
        if (tp == '+') {
            int u, v;
            char c;
            cin >> u >> v >> c;
            
            if (allEdges.count({v, u})) {
                if (allEdges[{v, u}] == c)
                    eqPairs.emplace(min(u, v), max(u, v));
                else
                    difPairs.emplace(min(u, v), max(u, v));
            }
            allEdges[{u, v}] = c;
            
        } else if (tp == '-') {
            int u, v;
            cin >> u >> v;
            if (eqPairs.count({min(u, v), max(u, v)}))
                eqPairs.erase({min(u, v), max(u, v)});
            if (difPairs.count({min(u, v), max(u, v)}))
                difPairs.erase({min(u, v), max(u, v)});
            
            allEdges.erase({u, v});
        } else {
            int k;
            cin >> k;
            
            bool hasAns = !eqPairs.empty();
            if (k & 1)
                hasAns |= !difPairs.empty();
            cout << (hasAns ? "YES" : "NO") << '\n';
        }
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 300043;

int n, m;
set<int> g[N];
set<int> g2[N];

vector<int> res;

void euler(int x)
{
    while(!g2[x].empty())
    {
        int y = *g2[x].begin();
        g2[x].erase(y);
        g2[y].erase(x);
        euler(y);
    }
    res.push_back(x);
}

bool check(int c)
{
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    res = vector<int>();
    euler(c);
    int curm = 0;
    for(int i = 1; i <= n; i++)
        curm += g[i].size();
    for(int i = 1; i <= n; i++)
        g2[i] = g[i];
    for(int i = 1; i < res.size(); i++)
    {
        int x = res[i - 1];
        int y = res[i];
        if(g2[x].count(y) != 1)
            return false;
        g2[x].erase(y);
        g2[y].erase(x);
    }
    return curm / 2 + 1 == res.size();    
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        g[x].insert(y);
        g[y].insert(x);
    }
    for(int i = 1; i <= n; i++)
    {
        set<int> pr = g[i];
        set<int> diff;
        for(auto x : pr)
            if(g[x].size() % 2 == 1)
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
        if(check(i))
        {
            res.push_back(-1);
            for(auto x : diff)
            {
                res.push_back(x);
                res.push_back(i);
            }
            printf("%d\n", res.size());
            for(auto x : res) printf("%d ", x);
            puts("");
            exit(0);
        }
        for(auto x : pr)
        {
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
            if(check(i))
            {
                res.push_back(-1);
                for(auto x : diff)
                {
                    res.push_back(x);
                    res.push_back(i);
                }
                printf("%d\n", res.size());
                for(auto x : res) printf("%d ", x);
                puts("");
                exit(0);
            }
            if(g[i].count(x))
            {
                g[i].erase(x);
                g[x].erase(i);
                diff.insert(x);
            }
            else
            {
                g[i].insert(x);
                g[x].insert(i);
                diff.erase(x);
            }
        }
        for(auto x : diff)
        {
            g[i].insert(x);
            g[x].insert(i);
        }
    }
    puts("0");
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl;
  }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        var (n, k) = readLine()!!.split(' ').map { it.toInt() }
        k--
        val floor = n / 2
        println((k + (n % 2) * k / floor) % n + 1)
    }
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        if(n % 2 == 1)
        {
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    if(j - i <= n / 2)
                        cout << 1 << " ";
                    else
                        cout << -1 << " ";
            cout << endl;
        }
        else
        {
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    if(j - i < n / 2)
                        cout << 1 << " ";
                    else if(j - i == n / 2)
                        cout << 0 << " ";
                    else
                        cout << -1 << " ";
            cout << endl;
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

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

#include<bits/stdc++.h>

using namespace std;


int main()
{   
    vector<int> ns(4);
    for(int i = 0; i < 4; i++)
        scanf("%d", &ns[i]);
    vector<vector<int>> cs(4);
    for(int i = 0; i < 4; i++)
    {
        cs[i].resize(ns[i]);
        for(int j = 0; j < ns[i]; j++)
            scanf("%d", &cs[i][j]);
    }
    vector<vector<vector<int>>> bad(3);
    for(int i = 0; i < 3; i++)
    {
        bad[i].resize(ns[i + 1]);
        int m;
        scanf("%d", &m);
        for(int j = 0; j < m; j++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            x--;
            y--;
            bad[i][y].push_back(x);
        }
    }                   
    vector<vector<int>> dp(4);
    dp[0] = cs[0];
    for(int i = 0; i < 3; i++)
    {
        dp[i + 1].resize(ns[i + 1]);                
        multiset<int> s;
        for(int j = 0; j < ns[i]; j++)
            s.insert(dp[i][j]);
        for(int j = 0; j < ns[i + 1]; j++)
        {
            for(auto k : bad[i][j])
                s.erase(s.find(dp[i][k]));
            if(s.empty())
                dp[i + 1][j] = int(4e8 + 43);
            else
                dp[i + 1][j] = *s.begin() + cs[i + 1][j];
            for(auto k : bad[i][j])
                s.insert(dp[i][k]);       
        }
    }
    int ans = *min_element(dp[3].begin(), dp[3].end());
    if(ans > int(4e8))
        ans = -1;
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

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

const int N = 250;
const int M = 28;
const int INF = 1e9;

int dp[2][M * 2 + 1][N][N];

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  s += "0";
  
  forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF;
  dp[0][M][N - 1][N - 1] = 0;
  
  forn(i, sz(s)) {
    forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF;
    forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) {
      if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]);
      if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]);
      int rcarry = carry - M;
      int val = rcarry + cp - cn;
      int digit = val % 10;
      if (digit < 0) digit += 10;
      int ncarry = val / 10;
      if (val < 0 && digit != 0) --ncarry;
      if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn);
    }
    swap(dp[0], dp[1]);
  }
  
  int ans = INF;
  forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]);
  cout << ans << endl;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 402;

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

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

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

int c[26];
int dp[2][N][N][3][3];
int sumDp[N][N];
int p1[N][N];
int p2[N][N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < 26; i++)
        cin >> c[i];
    for(int i = 0; i < 26; i++)
        for(int j = 0; j < 26; j++)
            for(int k = 0; k < 26; k++)
                if(i != k)
                {                                                                    
                    multiset<int> s = {i, j, k};
                    dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++;
                }
    for(int i = 4; i <= n; i++)
    {
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                for(int x = 0; x < 3; x++)
                    for(int y = 0; y < 3; y++)
                    {
                        dp[0][j][k][x][y] = dp[1][j][k][x][y];
                        dp[1][j][k][x][y] = 0;
                    }
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                for(int x = 0; x < 3; x++)
                    for(int y = 0; y < 3; y++)
                    {
                        int cur = dp[0][j][k][x][y];
                        if(cur == 0) continue;
                        for(int z = 0; z < 3; z++)
                        {                      
                            int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z];
                            nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0)));
                        }
                    }
    }
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < 3; k++)
                for(int l = 0; l < 3; l++)
                    sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]);
    for(int i = 0; i < N; i++)
    {
        p1[i][N - 1] = sumDp[i][N - 1];
        for(int j = N - 2; j >= 0; j--)
            p1[i][j] = add(sumDp[i][j], p1[i][j + 1]);
    }
    for(int j = 0; j < N; j++)
    {
        p2[N - 1][j] = p1[N - 1][j];
        for(int i = N - 2; i >= 0; i--)
            p2[i][j] = add(p1[i][j], p2[i + 1][j]);
    }
    int ans = p2[0][0]; 
    for(int i = 0; i < 26; i++)
    {
        for(int j = 0; j < N; j++)
            for(int k = c[i] + 1; k < N; k++)
                ans = sub(ans, sumDp[k][j]);
    }
    for(int i = 0; i < 26; i++)
        for(int j = 0; j < i; j++)
            ans = add(ans, p2[c[i] + 1][c[j] + 1]);
    cout << ans << endl;    
}

#include<bits/stdc++.h>

using namespace std;

int main() {
  int t; cin >> t;
  while(t--) {
    long long n, k;
    cin >> n >> k;
    
    long long cf = (n + k - 1) / k;
    k *= cf;
    
    cout << (k + n - 1) / n << endl;
  }
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int INF = int(1e9);

int main() {
  int t; cin >> t;
  while(t--) {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
      cin >> p[i];
    
    li x = 0;
    li pSum = p[0];
    for (int i = 1; i < n; i++) {
      x = max(x, (100ll * p[i] - k * pSum + k - 1) / k);
      pSum += p[i];
    }
    cout << x << endl;
  }
  return 0;
}

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

typedef long long li;

int main() {
  int t;
  cin >> t;

  while (t--) {
    int n;
    cin >> n;
    vector<int> c(n), a(n), b(n);
    for (int i = 0; i < n; i++)
      cin >> c[i];
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> b[i];
    
    li ans = 0;
    li lstLen = 0;
    for (int i = 1; i < n; i++) {
      li curLen = c[i] + 1ll + abs(a[i] - b[i]);
      if (a[i] != b[i])
        curLen = max(curLen, c[i] + 1ll + lstLen - abs(a[i] - b[i]));
      ans = max(ans, curLen);
      lstLen = curLen;  
    }
    cout << ans << endl;
  }
  return 0;
};

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

char buf[300043];

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        scanf("%s", buf);
        string s = buf;
        vector<vector<int>> g(2 * n + 2);
        for(int i = 0; i < n; i++)
            if(s[i] == 'L')
            {
                g[(i + 1) * 2].push_back(i * 2 + 1);
                g[i * 2 + 1].push_back((i + 1) * 2);
            }
            else
            {
                g[i * 2].push_back((i + 1) * 2 + 1);
                g[(i + 1) * 2 + 1].push_back(i * 2);   
            }
        vector<int> comp(2 * n + 2, -1);
        vector<int> cnt;
        for(int i = 0; i < 2 * n + 2; i++)
        {
            if(comp[i] != -1) continue;
            int c = 1;
            int cc = cnt.size();
            queue<int> q;
            comp[i] = cc;
            q.push(i);
            while(!q.empty())
            {
                int k = q.front();
                q.pop();
                for(auto y : g[k])
                {
                    if(comp[y] == -1)
                    {
                        c++;
                        comp[y] = cc;
                        q.push(y);
                    }
                }
            }
            cnt.push_back(c);
        }
        for(int i = 0; i <= n; i++)
            printf("%d%c", cnt[comp[i * 2]], " \n"[i == n]);
    }
}

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    dpl = [i for i in range(n + 1)]
    dpr = [i for i in range(n + 1)]
    for i in range(n + 1):
        if i == 0 or s[i - 1] == 'R':
            dpl[i] = i
        elif i == 1 or s[i - 2] == 'L':
            dpl[i] = i - 1
        else:
            dpl[i] = dpl[i - 2]
    for i in range(n, -1, -1):
        if i == n or s[i] == 'L':
            dpr[i] = i
        elif i == n - 1 or s[i + 1] == 'R':
            dpr[i] = i + 1
        else:
            dpr[i] = dpr[i + 2]
    ans = [(dpr[i] - dpl[i]) + 1 for i in range(n + 1)]
    print(*ans)

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

int main() {
    cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  vector<pattern> p(n);
  g.assign(n, vector<int>());
  forn(i, n){
    cin >> p[i].s;
    p[i].i = i;
  }
  sort(p.begin(), p.end());
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    --mt;
    bool ok = false;
    forn(mask, 1 << k){
      forn(j, k)
        nw.s[j] = ((mask >> j) & 1 ? cur[j] : '_');
      auto it = lower_bound(p.begin(), p.end(), nw);
      if (it != p.end() && it->s == nw.s){
        if (it->i != mt)
          g[mt].push_back(it->i);
        else
          ok = true;
      }
    }
    if (!ok){
      puts("NO");
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

struct pattern{
  string s;
  int i;
};

bool operator <(const pattern &a, const pattern &b){
  return a.s < b.s;
}

vector<vector<int>> g;
vector<int> used, ord;
bool cyc;

void ts(int v){
  used[v] = 1;
  for (int u : g[v]){
    if (used[u] == 0)
      ts(u);
    else if (used[u] == 1)
      cyc = true;
    if (cyc)
      return;
  }
  used[v] = 2;
  ord.push_back(v);
}

struct node{
  int nxt[28];
  int term;
  node(){
    memset(nxt, -1, sizeof(nxt));
    term = -1;
  }
};

vector<node> trie;

void add(const string &s, int i){
  int cur = 0;
  for (char c : s){
    int x = c - '_';
    if (trie[cur].nxt[x] == -1){
      trie[cur].nxt[x] = trie.size();
      trie.push_back(node());
    }
    cur = trie[cur].nxt[x];
  }
  trie[cur].term = i;
}

bool check(int i, int v, const string &s, int mt){
  if (i == int(s.size())){
    assert(trie[v].term != -1);
    if (trie[v].term != mt)
      g[mt].push_back(trie[v].term);
    else
      return true;
    return false;
  }
  bool res = false;
  if (trie[v].nxt[s[i] - '_'] != -1 && check(i + 1, trie[v].nxt[s[i] - '_'], s, mt))
    res = true;
  if (trie[v].nxt[0] != -1 && check(i + 1, trie[v].nxt[0], s, mt))
    res = true;
  return res;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  trie = vector<node>(1);
  int n, m, k;
  cin >> n >> m >> k;
  g.assign(n, vector<int>());
  forn(i, n){
    string cur;
    cin >> cur;
    add(cur, i);
  }
  pattern nw;
  nw.s = string(k, '_');
  forn(i, m){
    string cur;
    int mt;
    cin >> cur >> mt;
    if (!check(0, 0, cur, mt - 1)){
      cout << "NO\n";
      return 0;
    }
  }
  used.assign(n, 0);
  cyc = false;
  ord.clear();
  forn(i, n) if (!used[i]){
    ts(i);
    if (cyc){
      cout << "NO\n";
      return 0;
    }
  }
  reverse(ord.begin(), ord.end());
  cout << "YES\n";
  forn(i, n)
    cout << ord[i] + 1 << " ";
  cout << "\n";
  return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int INF = int(1e9);

struct segTree
{
    int n;
    bool mx;
    vector<int> t;

    void fix(int v)
    {
        t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
    }

    void build(int v, int l, int r)
    {
        if(l == r - 1)
            t[v] = (mx ? -INF : INF);
        else
        {
            int m = (l + r) / 2;
            build(v * 2 + 1, l, m);
            build(v * 2 + 2, m, r);
            fix(v);
        }
    }

    void upd(int v, int l, int r, int pos, int val)
    {
        if(l == r - 1)
            t[v] = (mx ? max(t[v], val) : min(t[v], val));
        else
        {
            int m = (l + r) / 2;
            if(pos < m)
                upd(v * 2 + 1, l, m, pos, val);
            else
                upd(v * 2 + 2, m, r, pos, val);
            fix(v);
        }
    }

    int get(int v, int l, int r, int L, int R)
    {
        if(L >= R)
            return (mx ? -INF : INF);
        if(l == L && r == R)
            return t[v];
        int m = (l + r) / 2;
        int lf = get(v * 2 + 1, l, m, L, min(R, m));
        int rg = get(v * 2 + 2, m, r, max(m, L), R);
        return (mx ? max(lf, rg) : min(lf, rg));
    }

    void upd(int pos, int val)
    {
        upd(0, 0, n, pos, val);
    }

    int get(int L, int R)
    {
        return get(0, 0, n, L, R);
    }

    void build()
    {
        return build(0, 0, n);
    }

    segTree() {};
    segTree(int n, bool mx) : n(n), mx(mx)
    {
        t.resize(4 * n);
    }
};

int main()
{
    int t;
    scanf("%d", &t);
    for(int _ = 0; _ < t; _++)
    {
        int n;
        scanf("%d", &n);
        vector<int> p(n);
        for(int i = 0; i < n; i++)
            scanf("%d", &p[i]);
        vector<int> dp(n + 1, -INF);
        vector<int> par(n + 1, -2);
        dp[0] = 0;
        par[0] = -1;
        vector<int> lf(n), rg(n);
        for(int i = 0; i < n; i++)
        {
            lf[i] = max(1, i - p[i] + 1);
            rg[i] = min(n, i + p[i] + 1);
        }
        segTree sn(n + 1, false);        
        segTree sx(n, true);
        sn.build();
        sx.build();
        for(int i = 0; i < n; i++)
            sx.upd(i, rg[i]);
        sn.upd(0, 0);
        for(int i = 1; i <= n; i++)
        {
            int j = i - 1;
            int k = lf[j] - 1;
            
            int m = sn.get(k, n + 1);                 
            if(m != INF)
            {
                int nval = max(sx.get(m, i - 1), i - 1);
                if(nval > dp[i])
                {
                    dp[i] = nval;
                    par[i] = m;
                }
            }
            if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
            {
                dp[i] = max(dp[j], rg[j]);
                par[i] = -1;
            }
            if(dp[j] > dp[i])
            {
                dp[i] = dp[j];
                par[i] = -1;
            }
            sn.upd(dp[i], i);                
        }
        if(dp[n] != n)
            puts("NO");
        else
        {
            puts("YES");
            string ans;
            int cur = n;
            while(cur != 0)
            {
                if(par[cur] == -1)
                {
                    cur--;
                    ans += "R";
                }
                else
                {
                    int pcur = par[cur];
                    int diff = cur - pcur;
                    ans += "L";
                    for(int j = 0; j < diff - 1; j++)
                        ans += "R";
                    cur = pcur;    
                }
            }
            reverse(ans.begin(), ans.end());
            puts(ans.c_str());
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int N = 100 * 1000 + 13;
const int P = 2000;

struct query {
  int t, l, r, k, i;
};

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a(n);
  forn(i, n) scanf("%d", &a[i]);
  
  vector<query> q;
  vector<array<int, 3>> upd;
  
  forn(i, m) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      q.push_back({sz(upd), l - 1, r - 1, k, sz(q)});
    } else {
      int p, x;
      scanf("%d%d", &p, &x); --p;
      upd.push_back({p, a[p], x});
      a[p] = x;
    }
  }
  
  sort(q.begin(), q.end(), [](const query &a, const query &b) {
    if (a.t / P != b.t / P)
      return a.t < b.t;
    if (a.l / P != b.l / P)
      return a.l < b.l;
    if ((a.l / P) & 1)
      return a.r < b.r;
    return a.r > b.r; 
  });
  
  for (int i = sz(upd) - 1; i >= 0; --i)
    a[upd[i][0]] = upd[i][1];
  
  vector<int> cnt(N), ord(N);
  vector<pt> bounds(N, {N, 0});
  bounds[0] = {0, N - 1};
  int L = 0, R = -1, T = 0;
  
  auto add = [&](int x) {
    int c = cnt[x];
    ++ord[bounds[c].x];
    bounds[c + 1].y = bounds[c].x;
    if (bounds[c + 1].x == N)
      bounds[c + 1].x = bounds[c].x;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N - 1;
    ++bounds[c].x;
    ++cnt[x];
  };
  
  auto rem = [&](int x) {
    int c = cnt[x];
    --ord[bounds[c].y];
    if (bounds[c - 1].x == N)
      bounds[c - 1].y = bounds[c].y;
    bounds[c - 1].x = bounds[c].y;
    if (bounds[c].x == bounds[c].y)
      bounds[c].x = N;
    --bounds[c].y;
    --cnt[x];
  };
  
  auto apply = [&](int i, int fl) {
    int p = upd[i][0];
    int x = upd[i][fl + 1];
    if (L <= p && p <= R) {
      rem(a[p]);
      add(x);
    }
    a[p] = x;
  };
  
  vector<int> ans(sz(q));
  
  for (auto qr : q) {
    int t = qr.t, l = qr.l, r = qr.r, k = qr.k;
    while (T < t) apply(T++, 1);
    while (T > t) apply(--T, 0);
    while (R < r) add(a[++R]);
    while (L > l) add(a[--L]);
    while (R > r) rem(a[R--]);
    while (L < l) rem(a[L++]);
    
    int res = N;
    for (int i = 0, j = 0, sum = 0; i < N && ord[i] > 0; i = bounds[ord[i]].y + 1) {
      while (j < N && ord[j] > 0 && sum < k) {
        sum += bounds[ord[j]].y - bounds[ord[j]].x + 1;
        j = bounds[ord[j]].y + 1;
      }
      if (sum >= k) res = min(res, ord[i] - ord[j - 1]);
      sum -= bounds[ord[i]].y - bounds[ord[i]].x + 1;
    }
    if (res == N) res = -1;
    ans[qr.i] = res;
  }
  
  for (int x : ans) printf("%d\n", x);
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    cout << (a.back() <= d || a[0] + a[1] <= d ? "YES" : "NO") << endl;
  }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
  auto mul = [](string s, int k) -> string {
    string res = "";
    while (k--) res += s;
    return res;
  };
  
  int tc;
  cin >> tc;
  while (tc--) {
    string s, t;
    cin >> s >> t;
    int n = s.length(), m = t.length();
    int g = __gcd(n, m);
    if (mul(s, m / g) == mul(t, n / g))
      cout << mul(s, m / g) << endl;
    else
      cout << "-1" << endl;
  }
}

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

        for (i in 1 until (k - (n - k)))
            print("$i ")
        for (i in k downTo (k - (n - k)))
            print("$i ")
        println("")
    }
}

#include <bits/stdc++.h>

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

using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	forn(_, t){
		int n, m;
		string s;
		cin >> n >> m;
		cin >> s;
		vector<int> sul(1, 0), sur(1, 0);
		for (int i = n - 1; i >= 0; --i){
			int d = s[i] == '+' ? 1 : -1;
			sul.push_back(min(0, sul.back() + d));
			sur.push_back(max(0, sur.back() + d));
		}
		reverse(sul.begin(), sul.end());
		reverse(sur.begin(), sur.end());
		vector<int> prl(1, 0), prr(1, 0), pr(1, 0);
		forn(i, n){
			int d = s[i] == '+' ? 1 : -1;
			pr.push_back(pr.back() + d);
			prl.push_back(min(prl.back(), pr.back()));
			prr.push_back(max(prr.back(), pr.back()));
		}
		forn(i, m){
			int l, r;
			cin >> l >> r;
			--l;
			int l1 = prl[l], r1 = prr[l];
			int l2 = sul[r] + pr[l], r2 = sur[r] + pr[l];
			printf("%d\n", max(r1, r2) - min(l1, l2) + 1);
		}
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 13;

int n, m;
vector<pair<int, int>> g[N];
long long d[N][2][2];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int v, u, w;
    scanf("%d%d%d", &v, &u, &w);
    --v; --u;
    g[v].emplace_back(u, w);
    g[u].emplace_back(v, w);
  }
  
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        d[i][j][k] = (long long)1e18;

  d[0][0][0] = 0;
  set<pair<long long, array<int, 3>>> q;
  q.insert({0, {0, 0, 0}});

  while (!q.empty()) {
    auto [v, mx, mn] = q.begin()->second;
    q.erase(q.begin());
    for (auto [u, w] : g[v]) {
      for (int i = 0; i <= 1 - mx; i++) {
        for (int j = 0; j <= 1 - mn; j++) {
          if (d[u][mx | i][mn | j] > d[v][mx][mn] + (1 - i + j) * w) {
            auto it = q.find({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
            if (it != q.end())
              q.erase(it);
            d[u][mx | i][mn | j] = d[v][mx][mn] + (1 - i + j) * w;
            q.insert({d[u][mx | i][mn | j], {u, mx | i, mn | j}});
          }
        }
      }
    }
  }

  for (int i = 1; i < n; i++) {
    printf("%lld ", d[i][1][1]);
  }
  puts("");
}

#include<bits/stdc++.h>

using namespace std;

template<typename T>
struct dinic {
    struct edge {
        int u, rev;
        T cap, flow;
    };
    
    int n, s, t;
    T flow;
    vector<int> lst;
    vector<int> d;
    vector<vector<edge>> g;
    
    T scaling_lim;
    bool scaling;
    
    dinic() {}
    
    dinic(int n, int s, int t, bool scaling = false) : n(n), s(s), t(t), scaling(scaling) {
        g.resize(n);
        d.resize(n);
        lst.resize(n);
        flow = 0;
    }

    void add_edge(int v, int u, T cap, bool directed = true) {
        g[v].push_back({u, g[u].size(), cap, 0});
        g[u].push_back({v, int(g[v].size()) - 1, directed ? 0 : cap, 0});
    }

    T dfs(int v, T flow) {
        if (v == t)
            return flow;
        if (flow == 0)
            return 0;
        T result = 0;
        for (; lst[v] < g[v].size(); ++lst[v]) {
            edge& e = g[v][lst[v]];
            if (d[e.u] != d[v] + 1)
                continue;
            T add = dfs(e.u, min(flow, e.cap - e.flow));
            if (add > 0) {
                result += add;
                flow -= add;
                e.flow += add;
                g[e.u][e.rev].flow -= add;
            }
            if (flow == 0)
                break;
        }
        return result;
    }

    bool bfs() {
        fill(d.begin(), d.end(), -1);
        queue<int> q({s});
        d[s] = 0;
        while (!q.empty() && d[t] == -1) {
            int v = q.front(); q.pop();
            for (auto& e : g[v]) {
                if (d[e.u] == -1 && e.cap - e.flow >= scaling_lim) {
                    q.push(e.u);
                    d[e.u] = d[v] + 1;
                }
            }
        }
        return d[t] != -1;
    }

    T calc() {
        T max_lim = numeric_limits<T>::max() / 2 + 1;
        for (scaling_lim = scaling ? max_lim : 1; scaling_lim > 0; scaling_lim >>= 1) {
            while (bfs()) {
                fill(lst.begin(), lst.end(), 0);
                T add;
                while((add = dfs(s, numeric_limits<T>::max())) > 0)
                flow += add;
            }
        }   
        return flow;
    }
    
    vector<bool> min_cut() {
        vector<bool> res(n);
        for(int i = 0; i < n; i++) 
            res[i] = (d[i] != -1);
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    int s = n;
    int t = n + 1;
    dinic<int> d(n + 2, s, t, true);
    vector<int> last(101, -1);
    for(int i = 0; i < n; i++){
        if(b[i] > 0)
            d.add_edge(s, i, b[i]);
        if(b[i] < 0)
            d.add_edge(i, t, -b[i]);
        for(int k = 1; k <= 100; k++)
            if(last[k] != -1 && a[i] % k == 0)
                d.add_edge(i, last[k], int(1e9));
        last[a[i]] = i;    
    }   
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += max(0, b[i]);
    cout << sum - d.calc() << endl;
}

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

template<const int &MOD>
struct _m_int {
  int val;
 
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(uint64_t v) {
    if (v >= MOD) v %= MOD;
    val = int(v);
  }
 
  _m_int(int v) : _m_int(int64_t(v)) {}
  _m_int(unsigned v) : _m_int(uint64_t(v)) {}
 
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
 
    while (r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
 
    return x < 0 ? x + m : x;
  }
 
  explicit operator int() const { return val; }
  explicit operator unsigned() const { return val; }
  explicit operator int64_t() const { return val; }
  explicit operator uint64_t() const { return val; }
  explicit operator double() const { return val; }
  explicit operator long double() const { return val; }
 
  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
 
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return unsigned(x % m);
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
    unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }
 
  _m_int& operator*=(const _m_int &other) {
    val = fast_mod(uint64_t(val) * other.val);
    return *this;
  }
 
  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }
 
  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
 
  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
 
  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
 
  _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  _m_int operator--(int) { _m_int before = *this; --*this; return before; }
 
  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }
 
  friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
  friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
  friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
  friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
  friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
  friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
 
  _m_int inv() const {
    return inv_mod(val);
  }
 
  _m_int pow(int64_t p) const {
    if (p < 0)
      return inv().pow(-p);
 
    _m_int a = *this, result = 1;
 
    while (p > 0) {
      if (p & 1)
        result *= a;
      a *= a;
      p >>= 1;
    }
 
    return result;
  }
  
  friend string to_string(_m_int<MOD> x) {
    return to_string(x.val);
  }
 
  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

extern const int MOD = 998244353;
using Mint = _m_int<MOD>;

const int g = 3;
const int LOGN = 15;

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 *= 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).inv();
    forn(i, n) 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;
}

int main() {
  prepare();
  
  vector<Mint> fact(1, 1), ifact(1, 1);
  auto C = [&](int n, int k) -> Mint {
    if (k < 0 || k > n) return 0;
    while (sz(fact) <= n) {
      fact.push_back(fact.back() * sz(fact));
      ifact.push_back(fact.back().inv());
    }
    return fact[n] * ifact[k] * ifact[n - k];
  };
  
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  forn(i, n) cin >> a[i] >> b[i];
  
  vector<Mint> ans(1, 1);
  forn(i, n) {
    vector<Mint> Cs;
    for (int j = b[i] - sz(ans) + 1; j < sz(ans) + a[i]; ++j)
      Cs.push_back(C(a[i] + b[i], j));
    auto res = mul(ans, Cs);
    int cnt = sz(ans);
    ans.resize(cnt + a[i] - b[i]);
    forn(j, sz(ans)) ans[j] = res[cnt + j - 1];
  }
  
  cout << accumulate(ans.begin(), ans.end(), Mint(0)) << endl;
}

t = int(input())
for i in range(t):
    s = input()
    if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
        print('YES')
    else:
        print('NO')

t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    a = [s[i] for i in range(n)]
    cnt = n // 2 - 1
    for j in range(n):
        if a[j] == '?':
            if cnt > 0:
                cnt -= 1
                a[j] = '('
            else:
                a[j] = ')'
    bal = 0
    minbal = 0
    for j in range(n):
        if a[j] == '(':
            bal += 1
        else:
            bal -= 1
        minbal = min(bal, minbal)
    print('YES' if bal == 0 and minbal >= 0 else 'NO') 

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> r(n);
	for (int &x : r) cin >> x;
	int m;
	cin >> m;
	vector<int> b(m);
	for (int &x : b) cin >> x;
	partial_sum(r.begin(), r.end(), r.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
}

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

for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
	dp[0][0] = 0
	ans = 0
	for i in range(n + 1):
		for j in range(m + 1):
			if i < n:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
			if j < m:
				dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
			ans = max(ans, dp[i][j])
	print(ans)

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }
        val h = readLine()!!.split(' ').map { it.toInt() }

        var mn = h[0]
        var mx = h[0]
        var ok = true
        for (i in 1 until n) {
            mn = maxOf(mn - k + 1, h[i])
            mx = minOf(mx + k - 1, h[i] + k - 1)
            if (mn > mx) {
                ok = false
                break
            }
        }
        if (h[n - 1] !in mn..mx)
            ok = false
        println(if (ok) "YES" else "NO")
    }
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

int n;

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

void calc(int n, vector<pt> &ans) {
	if (n == 2)
		return;
	
	int y = max(1, (int)sqrt(n) - 1);
	while (y < (n + y - 1) / y)
		y++;
	
	fore (pos, y + 1, n)
		ans.emplace_back(pos, n);
	ans.emplace_back(n, y);
	ans.emplace_back(n, y);
	
	calc(y, ans);
}

inline void solve() {
	vector<pt> ans;
	calc(n, ans);
	
	cout << sz(ans) << endl;
	for(auto p : ans)
		cout << p.first << " " << p.second << '\n';
}

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

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;                 
int q;
char buf[N];
int n, k;

int ceilLog(int x)
{
    int y = 0;
    while((1 << y) < x)
        y++;
    return y;
}

int main()
{
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", buf);
        string s = buf;
        int m = min(k, ceilLog(n - k + 2));
        vector<int> used(1 << m, 0);
        vector<int> next0(n, int(1e9));
        if(s[n - 1] == '0')
            next0[n - 1] = n - 1;
        for(int j = n - 2; j >= 0; j--)
            if(s[j] == '0')
                next0[j] = j;
            else
                next0[j] = next0[j + 1];
        int d = k - m;
        for(int j = 0; j < n - k + 1; j++)
        {
            if(next0[j] - j < d)
                continue;
            int cur = 0;
            for(int x = j + d; x < j + k; x++)
                cur = cur * 2 + (s[x] - '0');
            used[((1 << m) - 1) ^ cur] = 1;    
        }
        int ans = -1;
        for(int j = 0; j < (1 << m); j++)
            if(used[j] == 0)
            {
                ans = j;
                break;    
            }
        if(ans == -1)
            puts("NO");
        else
        {
            puts("YES");
            string res(d, '0');
            string res2;
            for(int j = 0; j < m; j++)
            {
                res2.push_back('0' + (ans % 2));
                ans /= 2;
            }
            reverse(res2.begin(), res2.end());
            res += res2;
            puts(res.c_str());
        }
    }
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

int n, k, nn;

vector<long long> t, ps;

void push(int v, int l, int r){
	if (l < r - 1){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v] * (r - l);
	ps[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int val){
	push(v, l, r);
	if (L >= R)
		return;
	if (l == L && r == R){
		ps[v] = val;
		push(v, l, r);
		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] = t[v * 2] + t[v * 2 + 1];
}

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

int trav(int v, int l, int r, int cnt){
	push(v, l, r);
	if (l == r - 1)
		return l;
	int m = (l + r) / 2;
	push(v * 2, l, m);
	push(v * 2 + 1, m, r);
	int res = INF;
	if (t[v * 2] >= cnt)
		res = trav(v * 2, l, m, cnt);
	else if (t[v * 2 + 1] >= cnt - t[v * 2])
		res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int main() {
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	sort(a.begin(), a.end(), greater<int>());
	nn = a[0] + 500;
	t.resize(4 * nn);
	ps.resize(4 * nn);
	upd(1, 0, nn, 0, 1, 1);
	int fst = 0;
	int ans = INF;
	forn(i, n){
		while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
		upd(1, 0, nn, fst, fst + 1, -1);
		upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
		upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
		ans = min(ans, trav(1, 0, nn, k));
	}
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}

for i in range(int(input())):
	a, b, c = map(int, input().split())
	if (a + b + c) % 9 != 0:
		print("NO")
	else:
	    print("YES" if min(a, b, c) >= (a + b + c) // 9 else "NO")

for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	cur = [0, 0]
	for i in range(n):
		cur[i % 2] += a[i] - 1
	for j in range(2):
		if 2 * cur[j] > s:
			continue
		for i in range(n):
			if i % 2 == j:
				a[i] = 1
		break
	print(*a)

def inside(l, r, x):
	return min(l, r) <= x <= max(l, r)

def sg(x):
	return -1 if x < 0 else int(x > 0)

for _ in range(int(input())):
	n = int(input())
	qs = []
	for i in range(n):
		qs.append(list(map(int, input().split())))
	qs.append([4*10**9, 0])
	ans = 0
	pos, dr, lft = 0, 0, 0
	for i in range(n):
		t, x = qs[i]
		tn = qs[i + 1][0]
		if lft == 0:
			lft = abs(pos - x)
			dr = sg(x - pos)
		tmp = min(lft, tn - t)
		if inside(pos, pos + dr * tmp, x):
			ans += 1
		pos += dr * tmp
		lft -= tmp
	print(ans)

#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 INF = int(1e9);

int n;
vector<int> b;

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

bool ok(const vector<int> &a, const vector<int> &b, int cnt) {
	fore (i, 0, cnt) {
		if (a[i] >= b[sz(b) - cnt + i])
			return false;
	}
	return true;
}

inline void solve() {
	vector<int> nb;
	fore (i, 1, 2 * n + 1) {
		if (!binary_search(b.begin(), b.end(), i))
			nb.push_back(i);
	}
	
	int mx[2] = {-1, -1};
	fore (k, 0, 2) {
		int lf = 0, rg = n + 1;
		while (rg - lf > 1) {
			int mid = (lf + rg) / 2;
			if (ok(b, nb, mid))
				lf = mid;
			else
				rg = mid;
		}
		mx[k] = lf;
		if (!ok(nb, b, n - lf)) {
			cout << 0 << endl;
			return;
		}
		swap(b, nb);
	}
	
	assert(n - mx[1] <= mx[0]);
	cout << mx[0] - (n - mx[1]) + 1 << 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 INF = int(1e9);

int n;
vector<int> b;

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

int getMax(const vector<int> &a, const vector<int> &b) {
	int uk = 0;
	fore (i, 0, sz(a)) {
		while (uk < sz(b) && b[uk] < a[i])
			uk++;
		if (uk >= sz(b))
			return i;
		uk++;
	}
	return sz(a);
}

inline void solve() {
	vector<int> nb;
	fore (i, 1, 2 * n + 1) {
		if (!binary_search(b.begin(), b.end(), i))
			nb.push_back(i);
	}
	
	int mxX = getMax(b, nb);
	int mnX = n - getMax(nb, b);
	
	cout << mxX - mnX + 1 << 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 forn(i, n) for(int i = 0; i < int(n); i++) 

vector<vector<int>> g, h, ng;

vector<int> rk, p;

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

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

vector<vector<int>> comp;

vector<int> ord;
vector<int> used;
bool fl;

void ts(int v, const vector<vector<int>> &g){
	used[v] = 1;
	for (int u : g[v]){
		if (used[u] == 0)
			ts(u, g);
		else if (used[u] == 1)
			fl = false;
		if (!fl) return;
	}
	ord.push_back(v);
	used[v] = 2;
}

bool topsort(const vector<vector<int>> &g){
	int n = g.size();
	used.assign(n, 0);
	ord.clear();
	fl = true;
	forn(i, n) if (!used[i]){
		ts(i, g);
		if (!fl) return false;
	}
	reverse(ord.begin(), ord.end());
	return true;
}

vector<int> pos;

bool dfs(int v){
	for (int u : g[v]){
		if (pos[u] < pos[v])
			return false;
		if (!dfs(u))
			return false;
	}
	return true;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	g.resize(n);
	h.resize(n);
	ng.resize(n);
	int rt = -1;
	forn(i, n){
		int p;
		scanf("%d", &p);
		--p;
		if (p == -1)
			rt = i;
		else
			g[p].push_back(i);
	}
	rk.assign(n, 1);
	p.resize(n);
	iota(p.begin(), p.end(), 0);
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		h[v].push_back(u);
		unite(v, u);
	}
	if (!topsort(h)){
		puts("0");
		return 0;
	}
	auto ord1 = ord;
	vector<int> pos1(n);
	forn(i, n) pos1[ord1[i]] = i;
	forn(v, n) for (int u : g[v]) if (getp(v) != getp(u))
		ng[getp(v)].push_back(getp(u));
	if (!topsort(ng)){
		puts("0");
		return 0;
	}
	comp.resize(n);
	forn(i, n) comp[getp(i)].push_back(i);
	vector<int> fin;
	for (int it : ord){
		sort(comp[it].begin(), comp[it].end(), [&](int v, int u){ return pos1[v] < pos1[u]; });
		for (int v : comp[it])
			fin.push_back(v);
	}
	pos.resize(n);
	forn(i, n) pos[fin[i]] = i;
	if (!dfs(rt)){
		puts("0");
		return 0;
	}
	for (int v : fin)
		printf("%d ", v + 1);
	puts("");
}

#include <bits/stdc++.h>

using namespace std;

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

int dp[2][1 << N];
int val[2 * N];

int main() {
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);
	
	int k = x + y;
	int m = max(x, y);
	int FULL = (1 << m) - 1;
	
	for (int i = 0; i < k; ++i)
		val[i] = n / k + (i < n % k);
	for (int mask = 0; mask < (1 << m); ++mask)
		dp[0][mask] = -INF;
	dp[0][0] = 0;
	
	for (int i = 0; i < k; ++i) {
		for (int mask = 0; mask < (1 << m); ++mask)
			dp[1][mask] = -INF;
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (dp[0][mask] == -INF)
				continue;
			int nmask = (mask << 1) & FULL;
			dp[1][nmask] = max(dp[1][nmask], dp[0][mask]);
			if (((mask >> (x - 1)) & 1) | ((mask >> (y - 1)) & 1))
				continue;
			nmask |= 1;
			dp[1][nmask] = max(dp[1][nmask], dp[0][mask] + val[i]);
		}
		swap(dp[0], dp[1]);
	}
	
	int ans = 0;
	for (int mask = 0; mask < (1 << m); ++mask) 
		ans = max(ans, dp[0][mask]);
	printf("%d\n", ans);
}

for i in range(int(input())):
	print(len(input()))

#include<bits/stdc++.h>

using namespace std;

int main() {
	int t; cin >> t;
	while (t--) {
		int x; cin >> x;
		
		int steps = 0;
		while (steps * (steps + 1) < 2 * x)
			steps++;
		
		if (steps * (steps + 1) / 2 == x + 1)
			steps++;
		cout << steps << endl;
	}
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int x, y;
	cin >> x >> y;
	cout << x - 1 << " " << y << endl;	
}

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

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        for(int i = 0; i < n; i++)
            cin >> a[i];
        if(is_sorted(a.begin(), a.end()))
        {
            cout << 0 << endl;
            continue;
        }
        vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
        for(int i = 0; i < n; i++)
        {
            if(a[i] > x && (i == 0 || a[i - 1] <= x))
                dp[i][x] = 1;
            if(i < n - 1 && a[i] > a[i + 1])
                break;
        }
        int ans = int(1e9);
        for(int i = 0; i < n; i++)
            for(int j = 0; j <= 500; j++)
            {
                if(dp[i][j] == int(1e9))
                    continue;
                if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
                    ans = min(ans, dp[i][j]);
                bool good = true;
                for(int k = i + 1; k < n; k++)
                {
                    int pr = k == i + 1 ? j : a[k - 1];
                    if(good && a[i] >= pr && a[i] < a[k])
                        dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
                    good &= a[k] >= pr;
                }
            }
        if(ans == int(1e9))
            ans = -1;
        cout << ans << endl;
        
    }   
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n, x;
vector<int> a;

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

inline void solve() {
	vector<int> sf(n + 1, 0);
	sf[n] = sf[n - 1] = 1;
	for (int i = n - 2; i >= 0; i--) {
		if (a[i] <= a[i + 1])
			sf[i] = sf[i + 1];
	}
	
	int ans = 0;
	int uk = 0;
	while (true) {
		int np = uk;
		while (np < n && a[np] <= x)
			np++;
		fore (i, uk, np) {
			if (i == 0) continue;
			if (a[i - 1] > a[i]) {
				cout << -1 << endl;
				return;
			}
		}
		if (sf[np])
			break;
		
		assert(a[np] > x);
		swap(a[np], x);
		ans++;
		uk = np;
	}
	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())

#define x first
#define y second

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

const li INF64 = li(1e18);

pt p[4];

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

inline void solve() {
	li ans = INF64;
	fore (st, 0, 2) {
		fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) {
			li x1 = p[idx1].x;
			li x2 = p[idx2].x;
			li y1 = p[idy1].y;
			
			if (x1 > x2)
				continue;
			
			for (int k = -1; k <= 1; k += 2) {
				li y2 = y1 + k * abs(x1 - x2);
				
				vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} };
				sort(fp.begin(), fp.end());
				
				do {
					li cur = 0;
					fore (i, 0, 4)
						cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y);
						
					ans = min(ans, cur);
				} while(next_permutation(fp.begin(), fp.end()));
			}
		}
		
		fore (i, 0, 4)
			swap(p[i].x, p[i].y);
	}
	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--) {
		assert(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

const li INF64 = li(1e18);

pt p[4];

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

li len(const pt &a) {
	assert(a.y >= a.x);
	return a.y - a.x;
}
pt getSeg(li a, li b) {
	return { min(a, b), max(a, b) };
}
pt getOpt(const pt &a, const pt &b) {
	return {
		max({ a.x - b.y, b.x - a.y, 0LL }),
		max({ b.y - a.x, a.y - b.x, 0LL })
	};
}

inline void solve() {
	li ans = INF64;
	
	vector<int> id = { 0, 1, 2, 3 };
	do {
		li cur = 0;
		auto x1 = getSeg(p[id[0]].x, p[id[3]].x);
		auto x2 = getSeg(p[id[1]].x, p[id[2]].x);
		
		cur += len(x1) + len(x2);
		pt xSeg = getOpt(x1, x2);
		
		auto y1 = getSeg(p[id[0]].y, p[id[1]].y);
		auto y2 = getSeg(p[id[2]].y, p[id[3]].y);
		
		cur += len(y1) + len(y2);
		pt ySeg = getOpt(y1, y2);
		
		li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x);
		cur += 2 * max(0LL, -is);
		
		ans = min(ans, cur);
	}
	while (next_permutation(id.begin(), id.end()));
	
	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--) {
		assert(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int n, k;
string s;
string dp[N];

void solve() {
	cin >> n >> k >> s;
	for (int i = 1; i <= n; i++)
		dp[i] = char('z' + 1);
	for (int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		int nc = min({c, (c + 1) % k, (c + k - 1) % k});
		dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc));
		if (i > 0) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]);
			dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back());
		}
		if (i > 1) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]);
		}
	}
	cout << dp[n] << endl;
}

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

#include <bits/stdc++.h>

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

using namespace std;

const long long INF = 1e18;

struct op{
	string tp;
	int y, v, to;
};

struct addmap{
	long long add;
	map<int, long long> val;
	multiset<long long> mn;
};

void reset(addmap &a, int x, long long val){
	if (a.val.count(x))
		a.mn.erase(a.mn.find(a.val[x]));
	a.val[x] = val - a.add;
	a.mn.insert(val - a.add);
}

int main() {
	int n, s;
	scanf("%d%d", &n, &s);
	static char buf[10];
	op a;
	vector<addmap> st;
	st.push_back({});
	st.back().val[0] = 0;
	st.back().add = 0;
	st.back().mn.insert(0);
	forn(i, n){
		scanf("%s", buf);
		a.tp = buf;
		if (a.tp == "set"){
			scanf("%d%d", &a.y, &a.v);
			assert(!st.back().mn.empty());
			long long mn = st.back().add + *st.back().mn.begin();
			st.back().add += a.v;
			if (a.y != s) reset(st.back(), a.y, mn);
		}
		else if (a.tp == "if"){
			scanf("%d", &a.y);
			long long val = INF;
			if (st.back().val.count(a.y)){
				val = st.back().val[a.y] + st.back().add;
				st.back().mn.erase(st.back().mn.find(st.back().val[a.y]));
				st.back().val.erase(a.y);
			}
			st.push_back({});
			reset(st.back(), a.y, val);
			st.back().add = 0;
		}
		else{
			if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size())
				swap(st[int(st.size()) - 1], st[int(st.size()) - 2]);
			addmap& v = st[int(st.size()) - 2];
			for (auto it : st.back().val){
				if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){
					if (v.val.count(it.x))
						v.mn.erase(v.mn.find(v.val[it.x]));
					v.val[it.x] = it.y + st.back().add - v.add;
					v.mn.insert(it.y + st.back().add - v.add);
				}
			}
			st.pop_back();
		}
	}
	printf("%lld\n", *st.back().mn.begin() + st.back().add);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int x, y;
        cin >> x >> y;
        int ans = max(x, y) * 2 - 1;
        if(x == y) ans++;
        cout << ans << endl;
    }
}

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

        val k = maxOf(a.max()!!, (a.sum() + n - 2) / (n - 1))
        println(k * (n - 1) - a.sum())
    }
}

def calc(s, x, y):
	bal, cnt = 0, 0
	for c in s:
		if c == y:
			if bal > 0:
				bal -= 1
				cnt += 1
		elif c == x:
			bal += 1
	return cnt

for _ in range(int(input())):
	s = input()
	print(calc(s, '(', ')') + calc(s, '[', ']'))

#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 ans = 1;
    while(y > 0)
    {
        if(y % 2 == 1)
            ans = mul(ans, x);
        x = mul(x, x);
        y /= 2;
    }
    return ans;
}

int divide(int x, int y)
{
    return mul(x, binpow(y, MOD - 2));
}

int main()
{
    int n;
    cin >> n;
    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i <= n; i++)
        fib[i] = add(fib[i - 1], fib[i - 2]);
    cout << divide(fib[n], binpow(2, n)) << endl;    
}

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<seg> a(m);
	forn(i, m){
		cin >> a[i].l >> a[i].r;
		--a[i].l;
	}
	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
		return a.l + a.r < b.l + b.r;
	});
	vector<int> su(m + 1);
	forn(i, n - k + 1){
		int cur = 0;
		for (int j = m - 1; j >= 0; --j){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			su[j] = max(su[j], cur);
		}
	}
	int ans = su[0];
	forn(i, n - k + 1){
		int cur = 0;
		forn(j, m){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			ans = max(ans, cur + su[j + 1]);
		}
	}
	cout << ans << endl;
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

int n, q;
vector<li> cnt;

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

inline void solve() {
	fore (qs, 0, q) {
		int tp, pos;
		li val;
		cin >> tp >> pos >> val;
		if (tp == 1) {
			cnt[pos] = val;
		} else {
			li small = 0, cur = 0;
			fore (i, 0, pos + 1) {
				small += cnt[i] * ((1ll << i) - 1);
				val -= cnt[i];
			}
			if (val <= 0) {
				cout << 0 << '\n';
				continue;
			}
			
			int id = pos + 1;
			while (id < n) {
				li add = 1ll << (id - pos);
				li need = min(val / add, cnt[id]);
				cur += need * (add - 1);
				val -= need * add;
				small += need * add * ((1ll << pos) - 1);
				
				if (need == cnt[id])
					id++;
				else
					break;
			}
			if (val <= 0) {
				cout << cur << '\n';
				continue;
			}
			if (id >= n) {
				cout << (val > small ? -1 : cur + val) << '\n';
				continue;
			}
			
			li ans = INF64;
			while (id > pos) {
				if (small >= val)
					ans = min(ans, cur + val);
				cur++;
				id--;
				li add = 1ll << (id - pos);
				if (val >= add) {
					cur += add - 1;
					val -= add;
					small += add * ((1ll << pos) - 1);
				}
			}
			assert(val <= 0);
			cout << min(ans, cur) << endl;
		}
	}
}

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

#include <bits/stdc++.h>

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

using namespace std;

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

vector<int> h, pcd, d;
vector<vector<int>> st, vals;
vector<int> a;
 
int dfs(int v, int s, int &cd, int p = -1){
	int sum = 1;
	for (int u : g[v]) if (h[u] == -1 && u != p)
		sum += dfs(u, s, cd, v);
	if (cd == -1 && (2 * sum >= s || p == -1))
		cd = v;
	return sum;
}
 
void build(int v, int s, int d, int p = -1){
	int cd = -1;
	dfs(v, s, cd);
	h[cd] = d;
	pcd[cd] = p;
	for (int u : g[cd]) if (h[u] == -1)
		build(u, s / 2, d + 1, cd);
}

vector<char> cur;

void calcd(int v, int p = -1){
	for (int u : g[v]) if (u != p && cur[u]){
		d[u] = d[v] + 1;
		calcd(u, v);
	}
}

vector<vector<int>> dist;

void init(){
	a.resize(n, -1);
	int k;
	scanf("%d", &k);
	queue<int> q;
	forn(i, k){
		int v;
		scanf("%d", &v);
		--v;
		q.push(v);
		a[v] = 0;
	}
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (int u : g[v]) if (a[u] == -1){
			a[u] = a[v] + 1;
			q.push(u);
		}
	}
	h.resize(n, -1);
	pcd.resize(n);
	build(0, n, 0);
	st.resize(n);
	vector<int> nd(n);
	forn(v, n){
		int u = v;
		while (u != -1){
			st[u].push_back(v);
			if (pcd[u] != -1)
				nd[pcd[u]] = max(nd[pcd[u]], nd[u] + 1);
			u = pcd[u];
		}
	}
	cur.resize(n);
	vals.resize(n);
	dist.resize(n);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&nd](int x, int y){
		return nd[x] < nd[y];
	});
	d.resize(n);
	for (int v : ord){
		for (int u : st[v]) cur[u] = true;
		d[v] = 0;
		calcd(v);
		int mx = 0;
		for (int u : st[v]) mx = max(mx, d[u]);
		vals[v].resize(mx + 1, 0);
		for (int u : st[v]) vals[v][d[u]] = max(vals[v][d[u]], a[u]);
		forn(j, mx) vals[v][j + 1] = max(vals[v][j + 1], vals[v][j]);
		for (int u : st[v]) cur[u] = false;
		for (int u : st[v]) dist[u].push_back(d[u]);
	}
}

bool check(int v, int x){
	for (int i = 0, u = v; u != -1; u = pcd[u], ++i)
		if (x - dist[v][i] >= 0 && vals[u][min(int(vals[u].size()) - 1, x - dist[v][i])] > x)
			return true;
	return false;
}

int main() {
	scanf("%d", &n);
	g.resize(n);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	init();
	forn(v, n){
		int res = 0;
		int l = 0, r = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (check(v, m)){
				res = m + 1;
				l = m + 1;
			}
			else{
				r = m - 1;
			}
		}
		printf("%d ", res);
	}
	puts("");
}

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int LN = 18;

vector<int> g[N];
vector<int> dist[N];
int sz[N];
int par[N];
bool used[N];
int max_dist[N];
vector<int> val[N];

int calc_size(int x, int p = -1)
{
    sz[x] = 1;
    for(auto y : g[x])
        if(y != p && !used[y])
            sz[x] += calc_size(y, x);
    return sz[x];   
}

int find_centroid(int x, int p, int s)
{
    int ans = -1;
    bool good = true;
    for(auto y : g[x])
        if(y != p && !used[y])
            good &= sz[y] * 2 <= s;
        else if(y == p && !used[y])
            good &= (s - sz[x]) * 2 <= s;
    if(good)
        ans = x;
    for(auto y : g[x])
        if(y != p && !used[y])
            ans = max(ans, find_centroid(y, x, s));
    return ans;
}

void calc_dist(int x, int p, int d, int s)
{
    dist[x].push_back(d);
    for(auto y : g[x])
        if(y != p && !used[y])
            calc_dist(y, x, d + 1, s);
    max_dist[s] = max(max_dist[s], d);  
}

int decomposition(int v)
{
    calc_size(v);
    int c = find_centroid(v, v, sz[v]);
    used[c] = true;
    for(auto y : g[c])
        if(!used[y])
        {
            par[decomposition(y)] = c;
        }
    used[c] = false;
    calc_dist(c, c, 0, c); 
    return c;
}

int main()
{
    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);
    }
    decomposition(0);
    for(int i = 0; i < n; i++)
        val[i].resize(max_dist[i] + 1);    
    int k;
    scanf("%d", &k);
    vector<int> d(n, int(1e9));
    queue<int> q;
    for(int i = 0; i < k; i++)
    {
        int x;
        scanf("%d", &x);
        --x;
        q.push(x);
        d[x] = 0;
    }
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(auto y : g[x])
            if(d[y] > d[x] + 1)
            {
                q.push(y);
                d[y] = d[x] + 1;
            }
    }
    for(int i = 0; i < n; i++)
    {
        if(d[i] == 0) continue;
        
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            if(dd > d[i] - 1)
            {
                curc = par[curc];
                continue;
            }
            dd = d[i] - 1 - dd;
            if(dd >= val[curc].size())
                dd = val[curc].size() - 1; 
            val[curc][dd] = max(val[curc][dd], d[i]);
            curc = par[curc];
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = max_dist[i]; j >= 1; j--)
            val[i][j - 1] = max(val[i][j], val[i][j - 1]);
    for(int i = 0; i < n; i++)
    {
        int ans = 0; 
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            ans = max(ans, val[curc][dd]);
            curc = par[curc];
        }
        if(d[i] == 0)
            ans = 0;
        printf("%d%c", ans, " \n"[i == n - 1]);
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (l, r) = readLine()!!.split(' ').map { it.toInt() }
        println(if (2 * l > r) "YES" else "NO");
    }
}

#include<bits/stdc++.h>

using namespace std;

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

const int INF = int(1e9);

int n;
string s;

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

int cntSame(const string &s) {
	int ans = 0;
	fore (i, 1, sz(s))
		ans += (s[i - 1] == s[i]);
	assert(ans % 2 == 0);
	return ans / 2;
}

inline void solve() {
	int ans = INF;
	fore (k, 0, 2) {
		ans = min(ans, cntSame(string(1, '0' + k) + s + string(1, '1' - k)));
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		assert(read());
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int INF = 1e9;

void solve(){
	int n;
	scanf("%d", &n);
	vector<int> t(n);
	forn(i, n){
		scanf("%d", &t[i]);
		--t[i];
	}
	sort(t.begin(), t.end());
	vector<vector<int>> dp(n + 1, vector<int>(2 * n, INF));
	dp[0][0] = 0;
	forn(i, n + 1) forn(j, 2 * n - 1) if (dp[i][j] < INF){
		if (i < n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(t[i] - j));
		dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
	}
	printf("%d\n", dp[n][2 * n - 1]);
}

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

#include <bits/stdc++.h>

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

using namespace std;

template<typename T>
T hungarian(const vector<vector<T>>& cost) {
    const T INF = numeric_limits<T>::max();
    int n = cost.size(), m = cost[0].size();
    vector<T> u(n + 1), v(m + 1), dist(m + 1);
    vector<int> p(m + 1), way(m + 1), used(m + 1);
    for (int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0;
        fill(dist.begin(), dist.end(), INF);
        do {
            used[j0] = i;
            int i0 = p[j0], j1 = -1;
            T delta = INF;
            for (int j = 1; j <= m; ++j) if (used[j] != i) {
                T cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                if (cur < dist[j]) dist[j] = cur, way[j] = j0;
                if (dist[j] < delta) delta = dist[j], j1 = j;
            }
            forn(j, m + 1) {
                if (used[j] == i) u[p[j]] += delta, v[j] -= delta;
                else dist[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        for (int j1; j0; j0 = j1)
            p[j0] = p[j1 = way[j0]];
    }
    
    return -v[0];
}

void solve(){
	int n;
	scanf("%d", &n);
	vector<int> t(n);
	forn(i, n){
		scanf("%d", &t[i]);
		--t[i];
	}
	vector<vector<int>> cost(n, vector<int>(2 * n));
	forn(i, n) forn(j, 2 * n) cost[i][j] = abs(t[i] - j);
	printf("%d\n", hungarian(cost));
}

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

#include<bits/stdc++.h>

using namespace std;

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

#define x first
#define y second

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

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

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

inline void solve() {
	vector<int> h(n, INF);
	h[0] = 0;
	int lst = 0;
	fore (i, 1, n) {
		if (i - 1 > 0 && a[i - 1] > a[i])
			lst++;
		h[i] = h[lst] + 1;
	}
	cout << h[n - 1] << endl;
}

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

#include <bits/stdc++.h>

using namespace std;

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

const int N = 500 * 1000 + 13;

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

int main() {
	scanf("%d%d", &n, &k);
	forn(i, n) scanf("%d", &a[i + 1]);
	a[0] = -1e9;
	a[n + 1] = 2e9;
	forn(i, n + 2) a[i] -= i;
	forn(i, k) scanf("%d", &b[i + 1]);
	b[k + 1] = n + 1;
	
	int ans = 0;
	forn(i, k + 1) {
		int l = b[i], r = b[i + 1];
		if (a[l] > a[r]) {
			puts("-1");
			return 0;
		}
		vector<int> lis;
		for (int j = l + 1; j < r; ++j) if (a[l] <= a[j] && a[j] <= a[r]) {
			auto pos = upper_bound(lis.begin(), lis.end(), a[j]);
			if (pos == lis.end()) lis.push_back(a[j]);
			else *pos = a[j];
		}
		ans += (r - l - 1) - int(lis.size());
	}
	
	printf("%d\n", ans);
}

#include<bits/stdc++.h>

using namespace std;

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

int dp[N][N];
int pdp[N][N];
int cntLess[N];
int lastLess[N];
int a[N];
int n;

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 main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	for(int i = 0; i < n; i++)
	{
	 	cntLess[i] = 0;
	 	lastLess[i] = -1;
	 	for(int j = 0; j < n; j++)
	 		if(a[j] * 2 <= a[i])
	 		{
	 		 	lastLess[i] = j;
	 		 	cntLess[i]++;
	 		}
	}
	for(int i = 0; i < n; i++)
	{
	 	dp[i][1] = 1;
	 	pdp[i + 1][1] = add(pdp[i][1], dp[i][1]);
	}
	for(int k = 2; k <= n; k++)
		for(int i = 0; i < n; i++)
		{
			if(cntLess[i] + 1 >= k)
		 		dp[i][k] = add(mul(dp[i][k - 1], add(cntLess[i], sub(2, k))), pdp[lastLess[i] + 1][k - 1]);
		 	else
		 		dp[i][k] = 0;
		 	//cerr << i << " " << k << " " << dp[i][k] << endl;                                
		 	pdp[i + 1][k] = add(pdp[i][k], dp[i][k]);
		}

	cout << dp[n - 1][n] << endl;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;

vector<int> val;
vector<int> pos;

struct aho_corasick {
	struct node {
		map<int, int> nxt, go;
		int p, pch;
		int suf, ssuf;
		multiset<int> vals;
		bool term;
		
		node() {
			nxt.clear();
			go.clear();
			suf = ssuf = -1;
			term = false;
			vals.clear();
			p = -1, pch = -1;
		}
	};

	vector<node> nodes;
	
	aho_corasick() {
		nodes = vector<node>(1, node());
	}

	int add(const string& s) {
		int v = 0;
		forn(i, s.size()) {
			int c = s[i] - 'a';
			if (!nodes[v].nxt.count(c)) {
				nodes.push_back(node());
				nodes[v].nxt[c] = int(nodes.size()) - 1;
				nodes.back().p = v;
				nodes.back().pch = c;
			}
			v = nodes[v].nxt[c];
		}
		nodes[v].term = true;
		nodes[v].vals.insert(0);
		return v;
	}
	
	int feed(const string &s){
		int v = 0;
		int ans = -1;
		forn(i, s.size()){
			int c = s[i] - 'a';
			v = go(v, c);
			int u = v;
			while (u != 0){
				if (!nodes[u].vals.empty())
					ans = max(ans, *nodes[u].vals.rbegin());
				u = ssuf(u);
			}
		}
		return ans;
	}
	
	int go(int v, int c) {
		if (nodes[v].go.count(c))
			return nodes[v].go[c];
		if (nodes[v].nxt.count(c))
			return nodes[v].go[c] = nodes[v].nxt[c];
		if (v == 0)
			return nodes[v].go[c] = 0;
		return nodes[v].go[c] = go(suf(v), c);
	}
	
	int suf(int v) {
		if (nodes[v].suf != -1)
			return nodes[v].suf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].suf = 0;
		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
	}
	
	int ssuf(int v) {
		if (nodes[v].ssuf != -1)
			return nodes[v].ssuf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].ssuf = 0;
		int s = suf(v);
		if (nodes[s].term)
			return nodes[v].ssuf = s;
		return nodes[v].ssuf = ssuf(s);
	}
};

aho_corasick ac;

int main() {
	int n, m;
	ios::sync_with_stdio(!cin.tie(0));
	cin >> n >> m;
	pos.resize(n);
	val.resize(n, 0);
	
	vector<int> tp2;
	
	ac = aho_corasick();
	
	forn(i, n){
		string s;
		cin >> s;
		pos[i] = ac.add(s);
	}
	
	forn(i, m){
		int t;
		cin >> t;
		if (t == 1){
			int j, x;
			cin >> j >> x;
			--j;
			ac.nodes[pos[j]].vals.erase(ac.nodes[pos[j]].vals.find(val[j]));
			val[j] = x;
			ac.nodes[pos[j]].vals.insert(val[j]);
		}
		else{
			string q;
			cin >> q;
			printf("%d\n", ac.feed(q));
		}
	}
	
	return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 26;
vector<vector<pair<int, int>>> upd;
vector<int> ans;
int n, m;

struct segtree{
	vector<int*> where;
	vector<int> vals;
	vector<int> t;
	int n;
	
	segtree(){}
	
	segtree(int n) : n(n){
		t.assign(4 * n, -1);
		where.clear();
		vals.clear();
	}
	
	void updh(int v, int l, int r, int L, int R, int val){
		if (L >= R)
			return;
		if (l == L && r == R){
			where.push_back(&t[v]);
			vals.push_back(t[v]);
			t[v] = max(t[v], val);
			return;
		}
		int m = (l + r) / 2;
		updh(v * 2, l, m, L, min(m, R), val);
		updh(v * 2 + 1, m, r, max(m, L), R, val);
	}
	
	void upd(int l, int r, int val){
		updh(1, 0, n, l, r, val);
	}
	
	int geth(int v, int l, int r, int pos){
		if (l == r - 1)
			return t[v];
		int m = (l + r) / 2;
		if (pos < m)
			return max(t[v], geth(v * 2, l, m, pos));
		return max(t[v], geth(v * 2 + 1, m, r, pos));
	}
	
	int get(int pos){
		return geth(1, 0, n, pos);
	}
	
	void rollback(){
		*where.back() = vals.back();
		where.pop_back();
		vals.pop_back();
	}
};

segtree st;

struct aho_corasick {
	struct node {
		map<int, int> nxt, go;
		int p, pch;
		int suf, ssuf;
		vector<int> term, qs;
		
		node() {
			nxt.clear();
			go.clear();
			suf = ssuf = -1;
			term.clear();
			p = -1, pch = -1;
			qs.clear();
		}
	};

	vector<node> nodes;
	vector<vector<int>> g;
	
	aho_corasick() {
		nodes = vector<node>(1, node());
	}

	void add(const string& s, int id) {
		int v = 0;
		forn(i, s.size()) {
			int c = s[i] - 'a';
			if (!nodes[v].nxt.count(c)) {
				nodes.push_back(node());
				nodes[v].nxt[c] = int(nodes.size()) - 1;
				nodes.back().p = v;
				nodes.back().pch = c;
			}
			v = nodes[v].nxt[c];
		}
		nodes[v].term.push_back(id);
	}
	
	void feed(const string &s, int id){
		int v = 0;
		forn(i, s.size()){
			int c = s[i] - 'a';
			v = go(v, c);
			nodes[v].qs.push_back(id);
		}
	}
	
	int go(int v, int c) {
		if (nodes[v].go.count(c))
			return nodes[v].go[c];
		if (nodes[v].nxt.count(c))
			return nodes[v].go[c] = nodes[v].nxt[c];
		if (v == 0)
			return nodes[v].go[c] = 0;
		return nodes[v].go[c] = go(suf(v), c);
	}
	
	int suf(int v) {
		if (nodes[v].suf != -1)
			return nodes[v].suf;
		if (v == 0 || nodes[v].p == 0)
			return nodes[v].suf = 0;
		return nodes[v].suf = go(suf(nodes[v].p), nodes[v].pch);
	}
	
	void build_tree() {
		g.resize(nodes.size());
		forn(v, nodes.size()) {
			int u = suf(v);
			if (v != u)
				g[u].push_back(v);
		}
	}
	
	void dfs(int v){
		int cur = st.where.size();
		for (auto i : nodes[v].term){
			int lst = m;
			for (auto it : upd[i]){
				st.upd(it.first, lst, it.second);
				lst = it.first;
			}
			st.upd(0, lst, 0);
		}
		for (auto j : nodes[v].qs){
			ans[j] = max(ans[j], st.get(j));
		}
		for (int u : g[v]){
			dfs(u);
		}
		int nw = st.where.size();
		forn(_, nw - cur){
			st.rollback();
		}
	}
};

aho_corasick ac;

int main() {
	ios::sync_with_stdio(!cin.tie(0));
	cin >> n >> m;
	upd.resize(n);
	ans.resize(m, -1);
	
	vector<int> tp2;
	
	ac = aho_corasick();
	st = segtree(m);
	
	forn(i, n){
		string s;
		cin >> s;
		ac.add(s, i);
	}
	forn(i, m){
		int t;
		cin >> t;
		if (t == 1){
			int j, x;
			cin >> j >> x;
			--j;
			upd[j].push_back(make_pair(i, x));
		}
		else{
			string q;
			cin >> q;
			ac.feed(q, i);
			tp2.push_back(i);
		}
	}
	forn(i, n){
		reverse(upd[i].begin(), upd[i].end());
	}
	
	ac.build_tree();
	ac.dfs(0);
	for (auto it : tp2)
		cout << ans[it] << "\n";
	return 0;
}

for i in range(int(input())):
    x, y, k = map(int, input().split())
    print(((y + 1) * k - 1 + x - 2) // (x - 1) + k)

#include <bits/stdc++.h>

using namespace std;

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c;
    forn(i, n) cin >> a[i];
    forn(i, n) cin >> b[i];
    forn(i, n) if (!b[i])
        c.push_back(a[i]);
    sort(c.rbegin(), c.rend());
    int j = 0;
    forn(i, n) {
        if (b[i]) cout << a[i] << ' ';
        else cout << c[j++] << ' ';
    }
    cout << '\n';
}

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

#include <bits/stdc++.h>

using namespace std;

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

#include <bits/stdc++.h>

using namespace std;

int get(const set<int> &x, const multiset<int> &len) {
    if (len.empty()) return 0;
    return *x.rbegin() - *x.begin() - *len.rbegin();
}

void add(int p, set<int> &x, multiset<int> &len) {
    x.insert(p);
    auto it = x.find(p);
    int prv = -1, nxt = -1;
    if (it != x.begin()) {
        --it;
        len.insert(p - *it);
        prv = *it;
        ++it;
    }
    ++it;
    if (it != x.end()) {
        len.insert(*it - p);
        nxt = *it;
    }
    if (prv != -1 && nxt != -1) {
        len.erase(len.find(nxt - prv));
    }
}

void rem(int p, set<int> &x, multiset<int> &len) {
    auto it = x.find(p);
    int prv = -1, nxt = -1;
    if (it != x.begin()) {
        --it;
        len.erase(len.find(p - *it));
        prv = *it;
        ++it;
    }
    ++it;
    if (it != x.end()) {
        len.erase(len.find(*it - p));
        nxt = *it;
    }
    x.erase(p);
    if (prv != -1 && nxt != -1) {
        len.insert(nxt - prv);
    }
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
    
    int n, q;
    cin >> n >> q;
    set<int> x;
    multiset<int> len;
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        add(p, x, len);
    }
    
    cout << get(x, len) << endl;
    for (int i = 0; i < q; ++i) {
        int t, p;
        cin >> t >> p;
        if (t == 0) {
            rem(p, x, len);
        } else {
            add(p, x, len);
        }
        cout << get(x, len) << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

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

int bp(int a, int n) {
    int res = 1;
    for (; n > 0; n /= 2) {
        if (n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    
    return res;
}

int inv(int a) {
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n, m;
int d[N];
long long sd[N];

long long sum (int l, int r) {
    return (sd[r] - sd[l]) % MOD;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        scanf("%d", d + i);
    sort(d, d + n);
    for (int i = 0; i < n; ++i)
        sd[i + 1] = sd[i] + d[i];
        
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b); // dur, def
        int cnt = (d + n) - lower_bound(d, d + n, b);
        int res = 0;
        if (cnt >= a) {
            res = mul( mul(cnt - a, inv(cnt)), sum(n - cnt, n) );
            res += mul( mul(cnt - a + 1, inv(cnt + 1)), sum(0, n - cnt) );
            res %= MOD;
        }
        printf("%d\n", res);
    }
    
    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) {
    out << "[";
    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;
li l, r;

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

const int N = int(2e5) + 555;
vector<int> divs[N];

inline void solve() {
    fore(d, 1, N) {
        for(int pos = d; pos < N; pos += d)
            divs[pos].push_back(d);
    }
    
    li lf = m + 1, rg = m;
    vector<int> cnt(m + 1, 0);
    vector<int> id(m + 1, -1);
    set<int> curDivs;
    
    vector< vector<int> > ans(n + 1);
    
    fore(x1, 1, n + 1) {
        li newlf = (l + x1 - 1) / x1;
        li newrg = r / x1;
        assert(newrg - newlf + 1 >= 0);
        
        while (lf > newlf) {
            lf--;
            for (int d : divs[lf]) {
                if (cnt[d] == 0)
                    curDivs.insert(d);
                cnt[d]++;
                id[d] = (int)lf;
            }
        }
        while (rg > newrg) {
            for (int d : divs[rg]) {
                cnt[d]--;
                if (cnt[d] == 0)
                    curDivs.erase(d);
            }
            rg--;
        }
        
        for (int a : divs[x1]) {
            auto it = curDivs.upper_bound(a);
            if (it == curDivs.end())
                continue;
            
            int b = *it;
            if (x1 / a * 1ll * b <= n) {
                int y1 = id[b];
                
                ans[x1] = {x1, y1, x1 / a * b, y1 / b * a};
            }
        }
    }
    
    fore(i, 1, n + 1) {
        if (ans[i].empty())
            cout << -1 << '\n';
        else {
            cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << '\n';
        }
    }
}

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

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

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

const int N = 60;

typedef array<int, N> num;

num operator ^(const num &a, const num &b){
    num c;
    forn(i, N){
        c[i] = a[i] + b[i];
        if (c[i] >= 3) c[i] -= 3;
    }
    return c;
}

mt19937 rnd(42);

int main(){
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    forn(i, n){
        scanf("%d", &a[i]);
        --a[i];
    }
    
    vector<num> nums(n);
    forn(i, n) forn(j, N) nums[i][j] = rnd() % 3;
    
    vector<vector<int>> pos(n);
    vector<num> pr(1);
    map<num, int> cnt;
    cnt[pr[0]] = 1;
    int cur = 0;
    long long ans = 0;
    forn(i, n){
        pr.push_back(pr.back() ^ nums[a[i]]);
        pos[a[i]].push_back(i);
        if (pos[a[i]].size() >= 4){
            while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]){
                --cnt[pr[cur]];
                ++cur;
            }
        }
        ans += cnt[pr.back()];
        ++cnt[pr.back()];
    }
    
    printf("%lld\n", ans);
}

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

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

typedef unsigned long long uli;

vector<int> a;
vector<pair<int, int>> t;
vector<int> ps;

pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b){
    if (a.first != b.first)
        return min(a, b);
    return make_pair(a.first, a.second + b.second);
}

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

void build(int v, int l, int r){
    if (l == r - 1){
        t[v] = make_pair(0, 1);
        return;
    }
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m, r);
    t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

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] = merge(t[v * 2], t[v * 2 + 1]);
}

int main(){
    int n;
    scanf("%d", &n);
    a.resize(n);
    forn(i, n){
        scanf("%d", &a[i]);
        --a[i];
    }
    t.resize(4 * n);
    ps.resize(4 * n);
    build(1, 0, n);
    vector<vector<int>> pos(n, vector<int>(1, -1));
    long long ans = 0;
    forn(i, n){
        int k = pos[a[i]].size();
        if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1);
        if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1);
        if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1);
        pos[a[i]].push_back(i);
        push(1);
        if (t[1].first == 0) ans += t[1].second - (n - i - 1);
    }
    printf("%lld\n", ans);
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val c = readLine()!!.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println(c.toString().repeat(n))
    }
}

fun main() {
    repeat(readLine()!!.toInt()) {
        val (p, f) = readLine()!!.split(' ').map { it.toInt() }
        var (cntS, cntW) = readLine()!!.split(' ').map { it.toInt() }
        var (s, w) = readLine()!!.split(' ').map { it.toInt() }
        
        if (s > w) {
            s = w.also { w = s }
            cntS = cntW.also { cntW = cntS }
        }

        var ans = 0
        for (s1 in 0..minOf((p / s), cntS)) {
            val w1 = minOf(cntW, (p - s * s1) / w)
            val s2 = minOf(cntS - s1, f / s)
            val w2 = minOf(cntW - w1, (f - s * s2) / w)
            ans = maxOf(ans, s1 + s2 + w1 + w2)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

int t;
string s;
int x;

string f(string s) {
    string res = s;
    for (int i = 0; i < s.size(); ++i) {
        if (i - x >= 0 && s[i - x] == '1' || i + x < s.size() && s[i + x] == '1')
            res[i] = '1';
        else
            res[i] = '0';
    }
    return res;
}

int main() {    
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        cin >> s >> x;
        int n = s.size();
 
        string ns = string(n, '1');
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                if (i - x >= 0) ns[i - x] = '0';
                if (i + x < n) ns[i + x] = '0';
            }
        }
        if (f(ns) == s) cout << ns << endl;
        else cout << -1 << endl;
    }
    return 0;
}

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

        val cntLeft = IntArray(n) { 0 }
        val cntRight = IntArray(n) { 0 }

        var ans = 0L
        for (j in a.indices) {
            cntRight.fill(0)
            for (k in n - 1 downTo j + 1) {
                ans += cntLeft[a[k]] * cntRight[a[j]]
                cntRight[a[k]]++
            }
            cntLeft[a[j]]++
        }
        println(ans)
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e3) + 9;

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

int calc (int pos, int x) {
    int &res = dp[pos][x];
    if (res != -1) return res;
    
    if (pos == n) return res = 0;
    res = 1 + calc(pos + 1, n);
    res = min(res, calc(pos + 1, pos) + a[pos]);
    if (x != n) {
        if (a[x] >= a[pos])
            res = min(res, calc(pos + 1, pos));
        else {
            res = min(res, calc(pos + 1, pos) + a[pos] - a[x]);
            res = min(res, 1 + calc(pos + 1, x));
        }
    }
    
    return res;
}

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

    memset(dp, -1, sizeof(dp));       
    printf("%d\n", calc(0, n));
    
    return 0;
}

#include <bits/stdc++.h>

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

using namespace std;

const int AL = 9;
const int N = 5000;
const int INF = 1e9;

string s;
int x;

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

vector<node> trie;

void add_string(string s){
    int v = 0;
    for (auto it : s){
        int c = it - '1';
        if (trie[v][c] == -1){
            trie.push_back(node());
            trie[trie.size() - 1].p = v;
            trie[trie.size() - 1].pch = c;
            trie[v][c] = trie.size() - 1;
        }
        v = trie[v][c];
    }
    trie[v].term = true;
}

int go(int v, int c);
 
int get_link(int v){
    if (trie[v].link == -1){
        if (v == 0 || trie[v].p == 0)
            trie[v].link = 0;
        else
            trie[v].link = go(get_link(trie[v].p), trie[v].pch);
    }
    return trie[v].link;
}
 
int go(int v, int c) {
    if (trie[v].go[c] == -1){
        if (trie[v][c] != -1)
            trie[v].go[c] = trie[v][c];
        else
            trie[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
    }
    return trie[v].go[c];
}

string t;

void brute(int i, int sum){
    if (sum == x){
        bool ok = true;
        for (int l = 0; l < int(t.size()); ++l){
            int cur = 0;
            for (int r = l; r < int(t.size()); ++r){
                cur += (t[r] - '0');
                if (x % cur == 0 && cur != x)
                    ok = false;
            }
        }
        if (ok){
            add_string(t);
        }
        return;
    }
    for (int j = 1; j <= min(x - sum, 9); ++j){
        t += '0' + j;
        brute(i + 1, sum + j);
        t.pop_back();
    }
}

int main() {
    cin >> s >> x;
    trie.push_back(node());
    brute(0, 0);
    vector<vector<int>> dp(s.size() + 1, vector<int>(trie.size(), INF));
    dp[0][0] = 0;
    forn(i, s.size()) forn(j, trie.size()) if (dp[i][j] != INF){
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
        int nxt = go(j, s[i] - '1');
        if (!trie[nxt].term)
            dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
    }
    printf("%d\n", *min_element(dp[s.size()].begin(), dp[s.size()].end()));
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 300043;
const int MOD = 998244353;

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

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

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

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

int fact[N];
int rfact[N];

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

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

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> l(n), r(n), a(m), b(m);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &l[i], &r[i]);
    for(int i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    vector<int> cnt(n + 2);
    for(int i = 0; i < n; i++)
    {
        cnt[l[i]]++;
        cnt[r[i] + 1]--;
    }
    for(int i = 0; i < n + 1; i++)
        cnt[i + 1] += cnt[i];
    prepare_fact();
    vector<vector<int> > p(2 * m + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= 2 * m; j++)
            p[j][i] = add(p[j][i - 1], c(cnt[i] - j, i - j));
    int ans = 0;
    for(int mask = 0; mask < (1 << m); mask++)
    {
        int sign = 1;
        set<int> used;
        for(int i = 0; i < m; i++)
            if(mask & (1 << i))
            {
                sign = mul(sign, MOD - 1);
                used.insert(a[i] - 1);
                used.insert(b[i] - 1);
            }
        int L = 1, R = n;
        for(auto x : used)
        {
            L = max(L, l[x]);
            R = min(R, r[x]);
        }
        if(R < L) continue;
        ans = add(ans, mul(sign, add(p[used.size()][R], -p[used.size()][L - 1])));
    }
    printf("%d\n", ans);
}

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

print(ans)

#include <bits/stdc++.h>

using namespace std;

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

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

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


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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

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

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

typedef double ld;
typedef long long li;

const ld PI = acos(-1.0);

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

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

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

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

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

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

void precalc() 
{
    for(int st = 0; st < LOGN; st++) 
    {
        w[st].assign(1 << st, comp());
        for(int k = 0; k < (1 << st); k++) 
        {
            double ang = PI / (1 << st) * k;
            w[st][k] = comp(cos(ang), sin(ang));
        }
        
        rv[st].assign(1 << st, 0);
        if(st == 0) 
        {
            rv[st][0] = 0;
            continue;
        }
        int h = (1 << (st - 1));
        for(int k = 0; k < (1 << st); k++)
            rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    }
}

inline void fft(comp a[N], int n, int ln, bool inv) 
{
    for(int i = 0; i < n; i++) 
    {
        int ni = rv[ln][i];
        if(i < ni)
            swap(a[i], a[ni]);
    }
    
    for(int st = 0; (1 << st) < n; st++) 
    {
        int len = (1 << st);
        for(int k = 0; k < n; k += (len << 1)) 
        {
            for(int pos = k; pos < k + len; pos++) 
            {
                comp l = a[pos];
                comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
                
                a[pos] = l + r;
                a[pos + len] = l - r;
            }
        }
    }
    
    if(inv) for(int i = 0; i < n; i++)
        a[i] = a[i] / n;
}

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

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

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

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

import kotlin.math.*

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

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

const int N = 200 * 1000;

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

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

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

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int, int> pt;

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

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

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

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

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 300043;

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

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

int n, m, k;

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

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

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

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

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

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

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

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