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

const int N = 1e6 + 5;
const int SZ = 19;

int n, m, a[N];
pair<int, int> b[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
map<int, vector<int>> mpl;

int sum = 0;
vector<int> cur;

void answer() {
    // found answer?
    vector<int> oth = mpl[sum];
    vector<int> ans(n + 1);
    int cnt = 0;
    for (int i : oth) {
        ans[i] = 1;
        cnt++;
    }
    for (int i : cur) {
        if (ans[i] > 0) {
            ans[i] = 0;
            cnt--;
        } else {
            ans[i] = 2;
            cnt++;
        }
    }
    if (cnt == 0) return;

    cout << "alhamdolellah\n";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
    exit(0);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = {a[i], i};
    }

    shuffle(b + 1, b + n + 1, rng);

    int szl = min(SZ, n);
    int szr = min(SZ, n);

    for (int msk = 0; msk < (1 << szl); msk++) {
        sum = 0;
        cur.clear();
        for (int i = 1; i <= szl; i++) {
            if (msk >> (i - 1) & 1) {
                sum += b[i].first;
                if (sum >= m) sum -= m;
                cur.push_back(b[i].second);
            }
        }
        if (mpl.count(sum)) {
            answer();
        } else {
            mpl[sum] = cur;   
        }
    }

    for (int msk = 1; msk < (1 << szr); msk++) {
        sum = 0;
        cur.clear();
        for (int i = n; i >= n - szr + 1; i--) {
            if (msk >> (n - i) & 1) {
                sum += b[i].first;
                if (sum >= m) sum -= m;
                cur.push_back(b[i].second);
            }
        }
        if (mpl.count(sum)) {
            answer();
        }
    }

    cout << "laelahaellallah\n";
}

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

const int N = 2e5 + 5;
const int LG = __lg(N) + 2;
const int INF = 1e9;

int n, d;
vector<int> adj[N];
int m1, m2;
int a[N], b[N];
bool ca[N], cb[N];
int cnta[N], cntb[N]; // count of a[i] and b[i] subtree of u

int timer = 0, tin[N], tout[N], up[LG][N], dep[N], par[N];
void prelca(int u, int p) {
    tin[u] = ++timer;
    up[0][u] = p;
    for (int j = 1; j < LG; j++) {
        up[j][u] = up[j - 1][up[j - 1][u]];
    }
    dep[u] = dep[p] + 1;
    par[u] = p;
    for (int v : adj[u]) {
        if (v != p) {
            prelca(v, u);
        }
    }
    tout[u] = ++timer;
}

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

int lca(int u, int v) {
    if (isanc(u, v)) return u;
    if (isanc(v, u)) return v;
    for (int j = LG - 1; j >= 0; j--) {
        if (!isanc(up[j][u], v)) {
            u = up[j][u];
        }
    }
    return up[0][u];
}

int dist(int u, int v) {
    int l = lca(u, v);
    return dep[u] + dep[v] - 2 * dep[l];
}

void pre(int u, int p) {
    cnta[u] += ca[u];
    cntb[u] += cb[u];
    for (int v : adj[u]) {
        if (v != p) {
            pre(v, u);
            cnta[u] += cnta[v];
            cntb[u] += cntb[v];
        }
    }
}

int Findkth(int u, int k) {
    for (int j = LG - 1; j >= 0; j--) {
        if (k >> j & 1) {
            u = up[j][u];
        }
    }
    return u;
}

// find child of u that is also ancestor of v
int Find(int u, int v) {
    int diff = dep[v] - dep[u] - 1;
    return Findkth(v, diff);
}

void Movea(int u);
void Moveb(int u);

int ans;
int posa, posb;

void Movea(int u) {
    if (u == 0) return;
    if (posa == u) return;
    if (isanc(posa, u)) {
        ans++;
        posa = Find(posa, u);
        if (dist(posa, posb) > d) Moveb(posa);
    } else {
        ans++;
        posa = par[posa];
        if (dist(posa, posb) > d) Moveb(posa);
    }
}

void Moveb(int u) {
    if (u == 0) return;
    if (posb == u) return;
    if (isanc(posb, u)) {
        ans++;
        posb = Find(posb, u);
        if (dist(posa, posb) > d) Movea(posb);
    } else {
        ans++;
        posb = par[posb];
        if (dist(posa, posb) > d) Movea(posb);
    }
}

void dfs(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            if (cnta[v] > 0 && cntb[v] > 0) {
                while (posa != v) Movea(v);
                while (posb != v) Moveb(v);
                dfs(v, u);
            } else if (cnta[v] > 0) {
                while (posa != v) Movea(v);
                dfs(v, u);
            } else if (cntb[v] > 0) {
                while (posb != v) Moveb(v);
                dfs(v, u);
            }
        }
    }
    if (posa == u) {
        while (p != 0 && posa != p) Movea(p);
    }
    if (posb == u) {
        while (p != 0 && posb != p) Moveb(p);
    }
}

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

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> m1;
    for (int i = 1; i <= m1; i++) {
        cin >> a[i];
        ca[a[i]] = 1;
    }
    cin >> m2;
    for (int i = 1; i <= m2; i++) {
        cin >> b[i];
        cb[b[i]] = 1;
    }

    tin[0] = 0, tout[0] = INF;
    prelca(1, 0);
    
    pre(1, 0);
    ans = 0;
    posa = 1, posb = 1;
    dfs(1, 0);
    while (posa != 1 && posb != 1) {
        Movea(1);
        Moveb(1);
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    // cin >> t;
    t = 1;

    while (t--) {
        solve();
    }
}

#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")

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

// https://cp-algorithms.com/algebra/linear-diophantine-equation.html
int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

void shift_solution(int & x, int & y, int a, int b, int cnt) {
    x += cnt * b;
    y -= cnt * a;
}

int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
    int x, y, g;
    if (!find_any_solution(a, b, c, x, y, g))
        return 0;
    a /= g;
    b /= g;

    int sign_a = a > 0 ? +1 : -1;
    int sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (minx - x) / b);
    if (x < minx)
        shift_solution(x, y, a, b, sign_b);
    if (x > maxx)
        return 0;
    int lx1 = x;

    shift_solution(x, y, a, b, (maxx - x) / b);
    if (x > maxx)
        shift_solution(x, y, a, b, -sign_b);
    int rx1 = x;

    shift_solution(x, y, a, b, -(miny - y) / a);
    if (y < miny)
        shift_solution(x, y, a, b, -sign_a);
    if (y > maxy)
        return 0;
    int lx2 = x;

    shift_solution(x, y, a, b, -(maxy - y) / a);
    if (y > maxy)
        shift_solution(x, y, a, b, sign_a);
    int rx2 = x;

    if (lx2 > rx2)
        swap(lx2, rx2);
    int lx = max(lx1, lx2);
    int rx = min(rx1, rx2);

    if (lx > rx)
        return 0;
    return (rx - lx) / abs(b) + 1;
}

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

    int ans = 0;
    for (int x = 1; x <= n; x++) {
        for (int z = 1; z <= n; z++) {
            int mk = n * (x + z) / (x * z);
            for (int k = 1; k <= mk; k++) {
                ans += find_all_solutions(x, z, x * z * k, 1, n, 1, n);
            }
        }
    }

    return ans;
//    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("output.txt", "w", stdout);
//    int t;
//    cin >> t;
//
//    while (t--) {
//        solve();
//    }

    for (int i = 1; i <= 1000; i++) {
        cout << solve(i) << ',';
    }
}

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

int N;
vector<int> adj, ans;
vector<vector<int>> radj;

void fill_radj(int x)
{
	for (auto &child : radj[x])
	{
		/* 
		 * As all nodes in the cycle are processed in function floyd,
		 * the recursive call will only start at the nodes which
		 * combine the cycle with the acyclic part of the connected component
		 * where one of its outgoing arrows points to the node that is not processed yet. 
		 */
		if (ans[child] == -1)
		{
			ans[child] = ans[x];
			fill_radj(child);
		}
	}
}

void floyd(int x)
{
	int y = x;
	do
	{  // find a cycle using Floyd's algorithm
		x = adj[x];
		y = adj[adj[y]];
	} while (y != x);
	do
	{  // set ans[x] = x for all x along cycle
		ans[x] = x;
		x = adj[x];
	} while (y != x);
	do
	{  // set ans'es for all x not along cycle
		fill_radj(x);
		x = adj[x];
	} while (y != x);
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	cin >> N;

	adj.assign(N, -1);
	for (auto &e : adj)
	{
		cin >> e;
		e--;
	}

	/* 
	 * For each node, we have to use a vector to store its children;  
	 * at nodes combining the cycle with other parts of the connected component,
	 * there would be more than one outgoing arrow in the reversed adjacency list
	 */
	radj.assign(N, {});
	for (int i = 0; i < N; i++)
		radj[adj[i]].push_back(i);

	ans.assign(N, -1);
	// we run Floyd's algorithm for each connected component
	for (int i = 0; i < N; i++)
		if (ans[i] == -1)
			floyd(i);

	for (auto &a : ans)
		cout << a + 1 << " ";
}

/*
 * Author: bubu2006
**/

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

const long long MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    string s;
    cin >> s;
    
    long long n = (long long)s.size();
    vector<long long> dp(n + 2), last(26, -1), pref(n + 2);
    
    dp[0] = 1;
    dp[1] = 0;
    pref[0] = 1;
    pref[1] = 1;
    
    for(long long i = 0; i < n; i++) {
    	if(last[s[i] - 'a'] == -1) {
    		dp[i + 2] = (dp[i + 2] + pref[i]) % MOD;
    	} else {
    		dp[i + 2] = (dp[i + 2] + pref[i] - pref[last[s[i] - 'a']]) % MOD;
    	}
    	
    	last[s[i] - 'a'] = i;
    	pref[i + 2] = pref[i + 1] + dp[i + 2];
    }
    
    long long ans = 0;
    for(long long i = 0; i <= n + 1; i++) {
    	ans = (ans + dp[i]) % MOD;
    }
    
    cout << (ans - 1 + MOD) % MOD << '\n';
}

      int j = i;
      s[i] = 1;
      while (j % d[i] == 0) {
        j /= d[i];
        s[i] = s[i] * d[i] + 1;
      }
      s[i] *= s[j];

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

const int N = (int) 1e7 + 100;

long long s[N];
int d[N];
int ans[N];

int main() {
  fill(d, d + N, -1);
  d[1] = 1;
  for (int i = 2; i * i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      for (int j = i * i; j < N; j += i) {
        if (d[j] == -1) {
          d[j] = i;
        }
      }
    }
  }
  s[1] = 1;
  for (int i = 2; i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      s[i] = i + 1;
    } else {
      int j = i;
      s[i] = 1;
      while (j % d[i] == 0) {
        j /= d[i];
        s[i] = s[i] * d[i] + 1;
      }
      s[i] *= s[j];
    }
  }
  fill(ans, ans + N, -1);
  for (int i = N - 1; i > 0; i--) {
    if (s[i] < N) {
      ans[s[i]] = i;
    }
  }
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    int c;
    cin >> c;
    cout << ans[c] << endl;
  }
  return 0;
}

vertical: use aa and bb abab... abab... baba... baba...

then change to horizontal using cc and dd

ccab... ddab... baba... baba...

Alternatively, notice that when we add 100 to our scores, it just adds 100 to our overall score except for the case when the total number of completed stages becomes divisible by 4, when we also need to subtract the score of the worst currently included stage from the sum. We can similarly handle adding 0 to Ilya's scores. If we sort all our and Ilya's scores at the beginning and maintain a pointer to the current worst included stage in both scoresheets, we can add a new 100/0 stage and recalculate the totals in O(1).

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

void solve() {
	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];
	
	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());
	
	int k = n - (n / 4);
	int sa = 0, sb = 0;
	
	deque<int> mxa, mnb;
	for(int i = 0; i < k; i++) {
		sa += a[i];
		mxa.push_back(a[i]);
		
		sb += b[i];
	}
	
	for(int i = k; i < n; i++) {
		mnb.push_back(b[i]);
	}
	
	if(sa >= sb) {
		cout << 0 << '\n';
		return;
	}
	
	int curn = n;
	while(true) {
		curn++;
		if(curn % 4 != 0) {
			// only add new element
			sa += 100;
			if(!mnb.empty()) {
				sb += mnb.back();
				mnb.pop_back();
			}
		} else {
			// remove one smallest element
			if(!mxa.empty()) {
				sa -= mxa.back();
				mxa.pop_back();
			} else {
				sa -= 100;
			}
			
			sa += 100;
		}
		
		if(sa >= sb) break;
		
	}
	
	cout << curn - n << '\n';
}

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