• Step 1: Prove that for the minimum value of $$$m$$$, we must have $$$m \% a = m \% b = 0$$$.
• Step 2: To prove this, show that if $$$m \% a = m \% b = x > 0$$$, then $$$m-1$$$ will also satisfy the problem's requirements.
• Step 3: Since $$$m \ge \min(a , b)$$$, if $$$x > 0$$$, then $$$m > \min(a , b)$$$ must hold. Therefore, $$$m - 1 \ge \min(a , b)$$$ implies that $$$m-1$$$ satisfies the requirements.
• Step 4: Thus, $$$m$$$ must be divisible by both $$$a$$$ and $$$b$$$. The smallest such $$$m$$$ is $$$lcm(a, b)$$$ which can be calculated in $$$O(\log(\max(a, b)))$$$.

#include <bits/stdc++.h>

using namespace std;

int main(){
  int tt;
  cin >> tt;
  while(tt--){
    int a, b;
    cin >> a >> b;
    cout << lcm(a , b) << endl;
  }
}

We will solve the problem using the following approach:

• Start from the leftmost spot and move rightwards.
• Whenever a consecutive segment of $$$m$$$ weak spots (i.e., $$$0$$$'s) is found, apply Timar to a segment of length $$$k$$$, starting from the last index of the weak segment.
• Repeat this process until no segment of $$$m$$$ consecutive weak spots remains.

The key idea behind this solution is that whenever we encounter a block of $$$m$$$ consecutive $$$0$$$'s, we need to strengthen it. Since we can apply Timar to a segment of length $$$k$$$, the optimal strategy is always to apply Timar starting at the last index of the block of $$$m$$$ consecutive $$$0$$$'s.

Correctness Proof:

1. For any block of $$$m$$$ consecutive $$$0$$$'s, we must apply Timar to at least one index within this block. Hence, the strengthened segment of length $$$k$$$ must overlap with the block of weak spots.
2. Suppose an optimal solution exists where Timar is applied to a segment starting leftward within the block. Suppose we shift this segment one step to the right (closer to the end of the block). In that case, the solution remains valid and optimal since it covers all weak spots in the block while reducing unnecessary overlap with already-strengthened areas.

By always starting from the last index of a block of $$$m$$$ consecutive $$$0$$$'s, this greedy strategy ensures that Timar is used in the minimum number of applications, making it correct and efficient.

# include <bits/stdc++.h>

using namespace std;

const int xn = 2e5 + 10;

int q, n, m, k, ps[xn];
string s;

int main() {
    cin >> q;
    while (q --) {
        cin >> n >> m >> k >> s;
        fill(ps, ps + n, 0);
        int ans = 0, cnt = 0, sum = 0;
        for (int i = 0; i < n; ++ i) {
            sum += ps[i];
            if (sum || s[i] == '1') cnt = 0;
            else {
                cnt++;
                if (cnt == m) {
                    sum++, ans++, cnt = 0;
                    if (i + k < n) ps[i + k]--;
                }
            }
        }
        cout << ans << "\n";
    }
}

• If a cell has a fixed direction (i.e., it points to another cell), and following that direction leads outside the maze, it must eventually exit the maze. Such cells cannot be part of any loop.
• We can analyze the remaining cells once we identify cells that lead out of the maze. Any undirected cell or $$$?$$$ cell might either lead to the exit or form part of a loop.
• If all neighboring cells of a $$$?$$$ cell can eventually lead out of the maze, then this $$$?$$$ cell will also lead out of the maze. The state of such $$$?$$$ cells can be determined based on their surroundings.
• For any remaining cells (directed cells that do not lead out of the maze, or other $$$?$$$ cells that cannot be determined to lead to an exit), we can assign directions such that starting from those cells will eventually lead to a loop. These cells will form the loops.
• To find how many cells will eventually lead to a loop, we can use a Depth-First Search (DFS) on the reversed graph, where all directions are reversed. By performing DFS starting from the "out-of-maze" cells, we can identify all cells that are reachable from the outside and thus will eventually lead out of the maze.
• Count the number of cells that can reach the exit. Subtract this number from the total number of cells in the maze to determine how many are part of loops (i.e., cells that cannot reach the exit).

#include <bits/stdc++.h>
 
using namespace std;
 
int main() 
{
    int tc;
    cin >> tc;
    while(tc--){
        int n, m;
        cin >> n >> m;
        string c[n+1];
        for(int i = 1 ; i <= n ; i++) cin >> c[i] , c[i] = "-" + c[i];
        vector<pair<int,int>> jda[n+2][m+2];
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){
                if(c[i][j] == 'U') jda[i-1][j].push_back({i , j});
                if(c[i][j] == 'R') jda[i][j+1].push_back({i , j});
                if(c[i][j] == 'D') jda[i+1][j].push_back({i , j});
                if(c[i][j] == 'L') jda[i][j-1].push_back({i , j});
            }
        }
        int vis[n+2][m+2] = {};
        queue<pair<int,int>> q;
        for(int j = 0 ; j <= m+1 ; j++) vis[0][j] = 1 , q.push({0 , j});
        for(int i = 1 ; i <= n+1 ; i++) vis[i][0] = 1 , q.push({i , 0});
        for(int j = 1 ; j <= m+1 ; j++) vis[n+1][j] = 1 , q.push({n+1 , j});
        for(int i = 1 ; i <= n ; i++) vis[i][m+1] = 1 , q.push({i , m+1});
        while(q.size()){
            auto [i , j] = q.front();
            q.pop();
            for(auto [a , b] : jda[i][j]){
                if(vis[a][b] == 0){
                    vis[a][b] = 1;
                    q.push({a , b});
                }
            }
        }
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){
                if(c[i][j] == '?' and
                vis[i-1][j] and vis[i][j+1] and vis[i+1][j] and vis[i][j-1]) vis[i][j] = 1;
            }
        }
        int ans = n * m;
        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++){
                if(vis[i][j] == 1) ans -= 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

• Step 1: Using two moves, we can move an element to any arbitrary position in the array. Thus, we can place all $$$0$$$'s in their correct positions with at most $$$2 \min(count(0), count(1) + count(2))$$$ moves.
• Step 2: After placing all $$$0$$$'s, the rest of the array will contain only $$$1$$$'s and $$$2$$$'s. To sort this part of the array, we need at most $$$min(count(1), count(2))$$$ moves.
• Step 3: The first step takes at most $$$n$$$ moves, and the second step takes at most $$$\frac{n}{2}$$$ moves. However, it can be proven that the total number of moves is at most $$$\frac{8n}{7}$$$.
• Step 4: We can assume $$$count(0) \leq count(2)$$$ without loss of generality (Why?). So, the maximum number of moves are:

Better approach:

• Step 1: Since we are allowed to perform $$$n$$$ moves, assign each index one "move" as its "specified cost".
• Step 2: While there exists an index with a value of $$$0$$$ or $$$2$$$ that can be fixed with just one move, fix it using its assigned cost.
• Step 3: After fixing all $$$0$$$'s, $$$2$$$'s, and all $$$1$$$'s except one, the remaining array will have the following structure and we are now allowed to use $$$2x+1$$$ moves:

• Step 4: First, swap the $$$1$$$ with a random element (denote it as $$$r$$$). Then, for $$$2x-1$$$ moves, swap the index with the value $$$1$$$ with any index where the correct value must be placed, except $$$r$$$. Finally, swap $$$1$$$ and $$$r$$$.

#include <bits/stdc++.h>

using namespace std;

const int N = 200000;
int n, cnt[3], a[N];
vector<int> vip[3][3]; // Value In Position
vector<pair<int, int>> swaps;

inline int Pos(int index) {
    if(index < cnt[0])
        return 0;
    else if(index < cnt[0]+cnt[1])
        return 1;
    else
        return 2; 
}

inline void AddBack(int index) {
    vip[a[index]][Pos(index)].push_back(index);
}

inline void RemoveBack(int index) {
    vip[a[index]][Pos(index)].pop_back();
}

inline void Swap(int i, int j) {
    swaps.push_back({i, j});
    RemoveBack(i);
    RemoveBack(j);
    swap(a[i], a[j]);
    AddBack(i);
    AddBack(j);
}

inline void Fix(int x) {
    while(!vip[1][x].empty() or !vip[2-x][x].empty()) {
        if(vip[1][x].empty()) {
            if(!vip[1][2-x].empty())
                Swap(vip[2-x][x].back(), vip[1][2-x].back());
            else
                Swap(vip[2-x][x].back(), vip[1][1].back());
        }
        if(!vip[x][1].empty()) 
            Swap(vip[1][x].back(), vip[x][1].back());
        else
            Swap(vip[1][x].back(), vip[x][2-x].back());
    }  
}


int main() 
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i], cnt[a[i]]++;
        for(int i = 0; i < n; i++)
            AddBack(i);
        if(cnt[0] <= cnt[2]) {
            Fix(0);
            Fix(2);
        } else {
            Fix(2);
            Fix(0);
        }
        cout << swaps.size() << endl;
        for(auto [i, j]: swaps)
            cout << i+1 << ' ' << j+1 << endl;
        cnt[0] = cnt[1] = cnt[2] = 0;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                vip[i][j].clear();
        swaps.clear();
    }
    return 0;
}

// In the name of god
#include <bits/stdc++.h>

using namespace std;

const int N = 200000;
int n, cnt[3], a[N];
vector<int> vip[3][3]; // Value In Position
vector<pair<int, int>> swaps;

inline int Pos(int index) {
    if(index < cnt[0])
        return 0;
    else if(index < cnt[0]+cnt[1])
        return 1;
    else
        return 2; 
}

inline void AddBack(int index) {
    vip[a[index]][Pos(index)].push_back(index);
}

inline void RemoveBack(int index) {
    vip[a[index]][Pos(index)].pop_back();
}

inline void Swap(int i, int j) {
    swaps.push_back({i, j});
    RemoveBack(i);
    RemoveBack(j);
    swap(a[i], a[j]);
    AddBack(i);
    AddBack(j);
}

inline void Fix() {
    bool change;
    do {
        change = false;
        while ((!vip[1][0].empty()) && (!vip[0][1].empty()))
            Swap(vip[1][0].back(), vip[0][1].back()), change = true;
        while ((!vip[1][0].empty()) && (!vip[0][2].empty()))
            Swap(vip[1][0].back(), vip[0][2-0].back()), change = true;
        while ((!vip[1][2].empty()) && (!vip[2][1].empty()))
            Swap(vip[1][2].back(), vip[2][1].back()), change = true;
        while ((!vip[1][2].empty()) && (!vip[2][0].empty()))
            Swap(vip[1][2].back(), vip[2][0].back()), change = true;
    } while (change);    
}

inline void PingPong() {
    if(vip[0][2].empty())
        return;
    Swap(vip[1][1].back(), vip[0][2].back());
    while (true){
        Swap(vip[1][2].back(), vip[2][0].back());
        if(vip[0][2].empty())
            break;
        Swap(vip[1][0].back(), vip[0][2].back());
    }
    Swap(vip[1][0].back(), vip[0][1].back());
}

int main() 
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i], cnt[a[i]]++;
        for(int i = 0; i < n; i++)
            AddBack(i);
        Fix();
        PingPong();
        cout << swaps.size() << endl;
        for(auto [i, j]: swaps)
            cout << i+1 << ' ' << j+1 << endl;
        // reset
        cnt[0] = cnt[1] = cnt[2] = 0;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                vip[i][j].clear();
        swaps.clear();
    }
    return 0;
}

• Step 1: There are $$$n$$$ positions that must be equal, and their sum is $$$\frac{n \cdot (n+1) \cdot k}{2}$$$. Hence, each position must be $$$\frac{(n+1) \cdot k}{2}$$$. Additionally, there must be $$$k$$$ distinct permutations, so $$$k \leq n!$$$.
• Step 2: For even $$$k$$$, we can group $$$n!$$$ permutations into $$$\frac{n!}{2}$$$ double handles, where each group corresponds to a solution for $$$k = 2$$$. Then, pick $$$\frac{k}{2}$$$ handles. The match for permutation $$$a_1, a_2, \ldots, a_n$$$ is $$$(n+1)-a_1, (n+1)-a_2, \ldots, (n+1)-a_n$$$.
• Step 3: For $$$k = 1$$$, $$$n$$$ must be $$$1$$$. Symmetrically, $$$k$$$ cannot be $$$n! - 1$$$. Solutions for other odd $$$k$$$ will now be provided.
• Step 4: To construct an answer for $$$k = 3$$$ and $$$n = 2x + 1$$$, consider the following derived using a greedy approach:

• Step 5: Now, combine the solution for even $$$k$$$ and the $$$k = 3$$$ solution by selecting the 3 permutations and $$$\frac{k-3}{2}$$$ other handles.

// In the name of God
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    int f[8] = {1,1,2,6,24,120,720,5040};
    while(t--) {
        int n, k;
        cin >> n >> k;
        if(min(n, k) == 1) {
            if(n*k == 1) {
                cout << "Yes\n1\n";
            } else cout << "No\n";
        } else if(n < 8 and (f[n] < k or f[n] == k+1)) {
            cout << "No\n";
        } else if(n % 2 == 0 and k % 2 == 1) {
            cout << "No\n";
        } else {
            vector<vector<int>> base, all;
            vector<int> per(n);
            for(int i = 0; i < n; i++) per[i] = i+1;
            if(k % 2) {
                vector<int> p1(n), p2(n);
                for(int i = 0; i < n; i += 2) p1[i] = (n+1)/2-i/2, p2[i] = n-i/2;
                for(int i = 1; i < n; i += 2) p1[i] = n-i/2, p2[i] = n/2-i/2;
                all = base = {per, p1, p2};
                k -= 3;
            }
            do {
                if(k == 0)
                    break;
                vector<int> mirror(n);
                for(int i = 0; i < n; i++)
                    mirror[i] = n+1-per[i];
                if(per < mirror) {
                    bool used = false;
                    for(auto &p: base) used |= (p == per), used |= (p == mirror);
                    if(not used) {
                        k -= 2;
                        all.push_back(per);
                        all.push_back(mirror);
                    }
                }
            } while (next_permutation(per.begin(), per.end()));
            cout << "Yes\n";
            for(auto p: all) {
                for(int i = 0; i < n; i++)
                    cout << p[i] << (i+1==n?'\n':' ');
            }
        }
    }
 
    return 0;
}
 
// Thanks God

• Step 1: For simplicity, redefine the special conditions for the number of rubies and sapphires in your satchel (not chest). Add two dummy states, $$$(0,0)$$$ and $$$(n,m)$$$ for convenience (the first one indexed as $$$0$$$ and the second one indexed as $$$k+1$$$). Note that these dummy states won’t involve doubling the value.
• Step 2: Order the redefined conditions $$$(x, y)$$$ in increasing order based on the value of $$$x + y$$$.
• Step 3: Define $$$ways_{i,j}$$$ as the number of ways to move from state $$$i$$$ to state $$$j$$$ without passing through any other special condition. This can be computed using inclusion-exclusion in $$$O(k^3)$$$.
• Step 4: Define $$$cost_{i,j}$$$, the increase in value for moving directly from state $$$i$$$ to state $$$j$$$ without intermediate doubling, as:

• Step 5: Define $$$dp_i$$$ as the total sum of the value of your satchel across all ways to reach the state defined by the $$$i$$$-th condition. This can be computed recursively as:

• Step 6: Compute the final answer as the value of $$$dp_{k+1}$$$ divided by the total number of ways to move from $$$(0,0)$$$ to $$$(n,m)$$$, which is $$$\binom{n+m}{n}$$$.

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 400010
 
ll fc[maxn], nv[maxn];
 
ll fxp(ll b, ll e) {
    ll r = 1, k = b;
    while (e != 0) {
        if (e % 2) r = (r * k) % mod;
        k = (k * k) % mod; e /= 2;
    }
    return r;
}
 
ll inv(ll x) {
    return fxp(x, mod - 2);
}
 
ll bnm(ll a, ll b) {
    if (a < b || b < 0) return 0;
    ll r = (fc[a] * nv[b]) % mod;
    r = (r * nv[a - b]) % mod;
    return r;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    fc[0] = 1; nv[0] = 1;
    for (ll i = 1; i < maxn; i++) {
        fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    }
 
    ll t; cin >> t;
    while (t--) {
        ll n, m, k; cin >> n >> m >> k;
        vector<array<ll, 2>> a(k + 2, {0, 0});
        for (ll i = 1; i <= k; i++) {
            cin >> a[i][0] >> a[i][1];
            a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1];
        }
        a[k + 1] = {n, m}; k++;
        sort(a.begin() + 1, a.end());
 
        auto paths = [&](ll i, ll j) {
            ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1];
            return bnm(dx + dy, dx);
        };
 
        auto add = [&](ll &x, ll y) {
            x = (x + y) % mod;
            x = (x + mod) % mod;
        };
 
        vector direct(k + 1, vector<ll>(k + 1, 0));
        for (ll i = 1; i <= k; i++) {
            for (ll j = i - 1; j >= 0; j--) {
                direct[j][i] = paths(j, i);
                for (ll l = j + 1; l < i; l++) {
                    add(direct[j][i], -paths(j, l) * direct[l][i]);
                }
            }
        }
 
        vector<ll> dp(k + 1, 0);
        for (ll i = 1; i <= k; i++) {
            for (ll j = 0; j < i; j++) {
                if (direct[j][i] == 0) continue;
                ll partial = dp[j];
                ll delta = 2 * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]);
                add(partial, paths(0, j) * delta);
                add(dp[i], partial * direct[j][i]);
            }
            if (i != k) dp[i] = (2 * dp[i]) % mod;
        }
 
        ll ans = (dp[k] * inv(bnm(n + m, m))) % mod;
        cout << ans << nl;
    }
 
    return 0;
}

• Step 1: For simplicity, redefine the special conditions for the number of rubies and sapphires in your satchel (not chest).
• Step 2: Order the redefined conditions $$$(x, y)$$$ in increasing order based on the value of $$$x + y$$$.
• Step 3: Define $$$total_{i,j}$$$ as the total number of ways to move from state $$$i$$$ to state $$$j$$$ (ignoring special condition constraints). This can be computed as:

• Step 4: Define $$$weight_i$$$ as the total contribution of all paths passing through condition $$$i$$$ to reach the final state $$$(n, m)$$$. This can be computed recursively as:

• Step 5: The main insight is to account for the doubling effect of passing through multiple scrolls. If a path passes through a sequence of conditions $$$s_1, \dots, s_c$$$, each gem collected before entering $$$s_1$$$ is counted with multiplicity $$$2^c$$$. Instead of explicitly multiplying by $$$2^c$$$, consider the number of subsets $$$q_1, \dots, q_d$$$ of $$$s_1, \dots, s_c$$$. By summing over all subsets, the correct multiplicity is automatically handled.
• Step 6: Define $$$dp_i$$$ as the total value of all paths passing through condition $$$i$$$, considering the contribution of each state’s rubies and sapphires. This can be computed as:

• Step 7: Compute the final answer as $$$\sum dp_i$$$ divided by the total number of ways to move from $$$(0,0)$$$ to $$$(n,m)$$$, which is equal to $$$\binom{n+m}{n}$$$.

Clarification: The approach hinges on the insight that $$$2^i$$$ can be derived from the structure of subsets of scrolls $$$s_1, \dots, s_c$$$. Generalizations to $$$3^i$$$ or other multiplicative factors are possible by appropriately modifying $$$weight_i$$$ and adjusting the factor in Step 5. For example, a factor of 3 can be applied by multiplying path contributions by 2 at the relevant steps.

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 400010
 
ll fc[maxn], nv[maxn];
 
ll fxp(ll b, ll e) {
    ll r = 1, k = b;
    while (e != 0) {
        if (e % 2) r = (r * k) % mod;
        k = (k * k) % mod; e /= 2;
    }
    return r;
}
 
ll inv(ll x) {
    return fxp(x, mod - 2);
}
 
ll bnm(ll a, ll b) {
    if (a < b || b < 0) return 0;
    ll r = (fc[a] * nv[b]) % mod;
    r = (r * nv[a - b]) % mod;
    return r;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    fc[0] = 1; nv[0] = 1;
    for (ll i = 1; i < maxn; i++) {
        fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    }
 
    ll t; cin >> t;
    while (t--) {
        ll n, m, k; cin >> n >> m >> k;
        vector<array<ll, 2>> a(k + 2, {0, 0});
        for (ll i = 1; i <= k; i++) {
            cin >> a[i][0] >> a[i][1];
            a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1];
        }
        a[k + 1] = {n, m}; k++;
        sort(a.begin() + 1, a.end());
 
        auto paths = [&](ll i, ll j) {
            ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1];
            return bnm(dx + dy, dx);
        };
 
        auto add = [&](ll &x, ll y) {
            x = (x + y) % mod;
            x = (x + mod) % mod;
        };
 
        vector<ll> cnt_weighted(k + 1, 0);
        cnt_weighted[k] = 1;
        for (ll i = k - 1; i >= 1; i--) {
            for (ll j = i + 1; j <= k; j++) {
                add(cnt_weighted[i], paths(i, j) * cnt_weighted[j]);
            }
        }
 
        ll ans = 0;
        for (ll i = 1; i <= k; i++) {
            ll delta = 2 * a[i][0] + a[i][1];
            add(ans, delta * paths(0, i) % mod * cnt_weighted[i]);
        }
 
        ans = (ans * inv(bnm(n + m, m))) % mod;
        cout << ans << nl;
    }
 
    return 0;
}

• It is easy to check if the solution can be achieved with only one color. For any time point $$$x$$$, there must be at most one interval containing $$$x$$$, since if multiple intervals contain $$$x$$$, they must be colored differently.
• A simple strategy is to solve the problem using three colors. First, we color some intervals with colors 1 and 2, then color others with color 3.
  • For each step, we find the leftmost point that has not been colored yet and color the segment that contains this point.
  • We always choose the interval with the largest endpoint that contains the current point.
  • By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these colors.
• Now, we check if we can color the intervals with just two colors using a greedy algorithm:
  • We iterate over the intervals sorted by start (increasingly) and then by end (decreasingly).
  • At each point, we keep track of the number of colors used in previous intervals that are not yet closed. Let this number be $$$I$$$, and suppose we are currently at interval $$$i$$$.
  • We color the current interval based on the value of $$$I$$$:
    • If $$$I = 0$$$, color interval $$$i$$$ with color 1.
    • If $$$I = 1$$$, color interval $$$i$$$ with the opposite color of the current used color.
    • If $$$I = 2$$$, color interval $$$i$$$ with the opposite color of the interval with the greatest endpoint among the currently open intervals.
  • If it is impossible to assign a unique color between overlapping intervals at any point, it can be shown that coloring the intervals using only 2 colors is impossible.

Solving G1 using G2:

• It’s sufficient to check the integer points and half-points (e.g., 1.5, 2.5, …) to verify whether the coloring is valid (Why?).
• To handle this, we can multiply all the given points by two, effectively converting the problem into one in which only integer points exist.
• After this transformation, we solve the problem in the integer system of G2, where the intervals and coloring rules are defined using integer boundaries!

Note: A brief explanation of why this greedy algorithm works can be found here.

/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int t, n, l[N], r[N], col[N];
vector<int> st[N << 1], en[N << 1];

void compress_points() {
    vector<int> help;
    for (int i = 0; i < n; i++) {
        help.push_back(l[i]);
        help.push_back(r[i]);
    }

    sort(help.begin(), help.end());
    help.resize(unique(help.begin(), help.end()) - help.begin());
    for (int i = 0; i < n; i++) {
        l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin();
        r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin();
    }
}

void record_points() {
    for (int i = 0; i < n; i++) {
        st[l[i]].push_back(i);
        en[r[i] + 1].push_back(i);
    }
    for (int i = 0; i < 2 * n; i++)
        sort(st[i].begin(), st[i].end(), [](int i, int j) {
            return r[i] > r[j];
        });
}

void try3_points() {
    fill(col, col + n, 0);
    int cur = -1, nxt = -1, c = 2;
    for (int i = 0; i < 2 * n; i++) {
        if (st[i].empty())
            continue;

        if (!~cur || i > r[cur]) {
            if (cur ^ nxt && r[nxt] < i) {
                col[nxt] = (c ^= 3);
                cur = nxt;
            }

            if (cur ^ nxt)
                cur = nxt;
            else {
                cur = st[i][0];
                for (int p: st[i])
                    if (r[p] > r[cur])
                        cur = p;
                nxt = cur;
            }
            col[cur] = (c ^= 3);
        }
        
        for (int p: st[i])
            if (r[p] > r[nxt])
                nxt = p;
    }
    if (cur ^ nxt)
        col[nxt] = c ^ 3;
}

bool is_bad(set<pair<int, int>> s[2]) {
    int cnt1 = s[0].size(), cnt2 = s[1].size();
    return cnt1 + cnt2 && cnt1 ^ 1 && cnt2 ^ 1;
}

void try2_points() {
    set<pair<int, int>> s[2];
    for (int i = 0; i <= 2 * n; i++) {
        for (int p: en[i])
            s[col[p]].erase({r[p], p});
        if (is_bad(s)) {
            try3_points();
            return;
        }

        for (int p: st[i]) {
            int cnt1 = s[0].size();
            int cnt2 = s[1].size();
            if (!cnt1 || !cnt2)
                col[p] = cnt1 > 0;
            else if (cnt1 ^ cnt2)
                col[p] = cnt1 < cnt2;
            else
                col[p] = s[0].begin()->first > s[1].begin()->first;

            s[col[p]].insert({r[p], p});
            if (is_bad(s)) {
                try3_points();
                return;
            }
        }
    }
}

void read_input() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> l[i] >> r[i];
}

void solve() {
    compress_points();
    record_points();
    try2_points();
}

void write_output() {
    cout << *max_element(col, col + n) + 1 << endl;
    for (int i = 0; i < n; i++)
        cout << col[i] + 1 << "\n "[i < n - 1];
}

void reset_variables() {
    for (int i = 0; i < n; i++) {
        col[i] = 0;
        st[l[i]].clear();
        en[r[i] + 1].clear();
    }
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (cin >> t; t--; reset_variables())
        read_input(), solve(), write_output();
    return 0;
}

• Step 1: It is easy to check if the solution can be achieved with only one color. For any time point $$$x$$$, there must be at most one interval containing $$$x$$$, since if multiple intervals contain $$$x$$$, they must be colored differently.
• Step 2: A simple strategy is to solve the problem using three colors; First, we color some intervals with colors 1 and 2, then color others with color 3. For each step, we find the leftmost point that has not been colored yet and color the segment that contains this point. We always choose the interval with the largest endpoint that contains the current point. By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these colors.
• Step 3: Now, we check if we can color the intervals with just two colors. For some point, $$$x$$$, suppose we have already colored the intervals $$$[l_i, r_i]$$$ with $$$l_i \leq x$$$, such that all points before $$$x$$$ have a unique color. At each step, we only need to determine which of the intervals like $$$p$$$ that $$$l_p \leq x \leq r_p$$$ can have a unique color. The key observation is that if an interval can be uniquely colored at time $$$x$$$, it can also remain uniquely colored for all times $$$t$$$ such that $$$x \leq t \leq r_i$$$.
  • Lemma: If an interval $$$[l_i, r_i]$$$ can be uniquely colored at time $$$x$$$, it can also be uniquely colored at all subsequent times $$$x \leq t \leq r_i$$$.
  • Proof: Consider coloring the intervals at time $$$x$$$. Intervals starting at $$$x + 1$$$ will be colored with the opposite color to interval $$$i$$$, ensuring that the interval remains uniquely colored at time $$$x+1$$$.
  • With this lemma, we can conclude that the changes in the coloring are $$$O(n)$$$. It suffices to track the intervals that are added and removed at each point in time.
• Step 4: To efficiently move from time $$$x$$$ to $$$x + 1$$$, we perform the following steps:
  • Remove the intervals that have $$$r_i = x$$$ (since they no longer contain $$$x+1$$$).
  • Add the intervals that have $$$l_i = x + 1$$$.
  • Update the set of intervals that can be uniquely colored at time $$$x+1$$$.

• Step 5: Finally, we observe that only the following points are important for the coloring:

  • $$$l_i$$$ and $$$r_i$$$ for each interval.
  • $$$l_i - 1$$$ and $$$r_i + 1$$$, since these points mark the boundaries where intervals start or end.

Thus, we can compress the numbers to reduce the range of values we need to process.

/* In the name of Allah */
// Welcome to the Soldier Side!
// Where there's no one here, but me...
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
vector<int> st[N << 2], en[N << 2];
int t, n, k, l[N], r[N], dp[N], col[N], prv[N];

void compress_numbers() {
    vector<int> help;
    for (int i = 0; i < n; i++) {
        help.push_back(l[i] - 1);
        help.push_back(l[i]);
        help.push_back(r[i]);
        help.push_back(r[i] + 1);
    }

    sort(help.begin(), help.end());
    help.resize(k = unique(help.begin(), help.end()) - help.begin());
    for (int i = 0; i < n; i++) {
        l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin();
        r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin();
    }
}

void save_checkpoints() {
    for (int i = 0; i < n; i++) {
        st[l[i]].push_back(i);
        en[r[i]].push_back(i);
    }
}

bool check_one() {
    for (int i = 0, open = 0; i < k; i++) {
        open += st[i].size();
        if (open > 1)
            return false;
        open -= en[i].size();
    }
    return true;
}

void color_with_two() {
    for (int i = k - 1, cur = -1; ~i; i--) {
        if (en[i].empty())
            continue;

        while (!~cur || i < dp[cur])
            if (~cur && ~prv[cur]) {
                col[prv[cur]] = col[cur];
                if (r[prv[cur]] >= l[cur])
                    col[prv[cur]] ^= 1;
                cur = prv[cur];
            }
            else
                for (int p: en[i])
                    if (~dp[p] && (!~cur || dp[p] < dp[cur]))
                        cur = p;

        for (int p: en[i])
            if (p ^ cur)
                col[p] = col[cur] ^ 1;
    }
}

bool check_two() {
    set<int> goods, bads;
    fill(dp, dp + n, -1);
    fill(prv, prv + n, -1);
    for (int i = 0; i < k; i++) {
        int prev = -1;
        if (i)
            for (int p: en[i - 1]) {
                bads.erase(p), goods.erase(p);
                if (~dp[p] && (!~prev || dp[p] < dp[prev]))
                    prev = p;
            }
        int open = goods.size() + bads.size();

        if (open == 1 || (open == 2 && !goods.empty())) {
            for (int p: bads) {
                if (open == 1)
                    prv[p] = prev;
                else
                    prv[p] = *goods.begin();
                goods.insert(p);
                dp[p] = i;
            }
            bads.clear();
        }

        if (open == 1)
            prev = *goods.begin();
        for (int p: st[i])
            if (!open || open == 1 || ~prev) {
                goods.insert(p);
                prv[p] = prev;
                dp[p] = i;
            }
            else
                bads.insert(p);
        open += st[i].size();

        if (open && goods.empty())
            return false;
    }

    color_with_two();
    return true;
}

void color_with_three() {
    int cur = -1, nxt = -1;
    for (int i = 0; i < k; i++) {
        if (st[i].empty())
            continue;

        if (~cur && i > r[cur] && nxt ^ cur) {
            col[nxt] = col[cur] ^ 3;
            cur = nxt;
        }
        if (!~cur || i > r[cur]) {
            for (int p: st[i])
                if (!~cur || r[p] > r[cur])
                    cur = p;
            col[nxt = cur] = 1;
        }

        for (int p: st[i])
            if (r[p] > r[nxt])
                nxt = p;
    }

    if (cur ^ nxt)
        col[nxt] = col[cur] ^ 3;
}

void read_input() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> l[i] >> r[i];
}

void solve() {
    compress_numbers();
    save_checkpoints();
    if (check_one())
        return;
    if (check_two())
        return;
    color_with_three();
}

void write_output() {
    cout << *max_element(col, col + n) + 1 << endl;
    for (int i = 0; i < n; i++)
        cout << col[i] + 1 << "\n "[i < n - 1];
}

void reset_variables() {
    fill(col, col + n, 0);
    for (int i = 0; i < k; i++) {
        st[i].clear();
        en[i].clear();
    }
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    for (cin >> t; t--; reset_variables())
        read_input(), solve(), write_output();
    return 0;
}

• Step 1: According to Bézout's Identity, we can compute $$$\gcd(x_1, \ldots, x_t)$$$ and all its multipliers as an integer linear combination of $$$x_1, x_2, \ldots, x_t$$$.
• Step 2: A set {$$$a_1, \ldots, a_k$$$} is good (integer linearly independent) if for every $$$i$$$, $$$\gcd($$${$$$a_j \mid j \neq i$$$}$$$) \nmid a_i$$$.
• Step 3: A set {$$$a_1, \ldots, a_k$$$} is good if and only if there exists a set {$$${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$$$} such that $$${p_i}^{q_i} \mid a_j$$$ for $$$j \neq i$$$ and $$${p_i}^{q_i} \nmid a_i$$$.
• Step 4: The set {$$$a_1, \ldots, a_k$$$} can be identified by determining {$$${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$$$}. Assume $$$p_1^{q_1} < p_2^{q_2} < \ldots < p_k^{q_k}$$$, where $$$p_i \neq p_j$$$ and $$$p_i$$$ is prime.
• Step 5: Let $$$G = {p_1}^{q_1} \cdot {p_2}^{q_2} \ldots \cdot {p_k}^{q_k}.$$$ Then {$$$a_1, \ldots, a_k$$$} is good if and only if $$$\frac{G}{{p_i}^{q_i}} \mid a_i$$$ and $$$G \nmid a_i$$$ for every $$$i$$$.
• Step 6: The answer is a singleton if, for every pair of numbers $$$x$$$ and $$$y$$$ in the array, $$$x \mid y$$$ or $$$y \mid x$$$. Since the numbers are distinct, a good subset {$$$a_1, a_2$$$} can always be found by searching the first $$$\log M + 2$$$ elements.
• Step 7: Define $$$CM[i]$$$ (count multipliers of $$$i$$$) as the number of $$$x$$$ such that $$$i \mid a_x$$$. This can be computed in $$$O(n + M \log M)$$$.
• Step 8: A corresponding set {$$$a_1, \ldots, a_k$$$} exists for a set {$$${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$$$} if and only if $$$CM\left[\frac{G}{{p_i}^{q_i}}\right] > CM[G] \geq 0$$$ for all $$$i$$$.
• Step 9: Iterate over all valid sets of the form {$$${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$$$}, and check if a corresponding {$$$a_1, a_2, \ldots, a_k$$$} exists. Note that $$$k \geq 3$$$ since a good subset {$$$a_1, a_2$$$} is found using another method.
• Step 10: We know $$$\frac{G}{{p_1}^{q_1}} \leq M$$$ and also $$${p_1}^{q_1} \leq \sqrt{M},$$$ as $$${p_1}^{q_1} \leq \sqrt{{p_2}^{q_2} \cdot {p_3}^{q_3}} \leq \sqrt{\frac{G}{{p_1}^{q_1}}} \leq \sqrt{M}.$$$
• Step 11: There are $$$\sum_{i=1}^{\frac{\log M}{2}} P[\lfloor \sqrt[2i]{M} \rfloor]$$$ numbers in the form $$${p_1}^{q_1}$$$, where $$$P[i]$$$ denotes the number of primes in the range $$$[1, i]$$$. This count is $$$O(\frac{\sqrt M}{\log M})$$$.
• Step 12: The value of $$$k$$$ is at most 6 (denoted as $$$K$$$), as $$${p_2}^{q_2} \ldots {p_k}^{q_k} = \frac{G}{{p_1}^{q_1}} \leq M,$$$ and $$$3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \leq M < 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17.$$$
• Step 13: We can determine {$$$a_1, \ldots, a_k$$$} from {$$${p_1}^{q_1}, {p_2}^{q_2}, \ldots, {p_k}^{q_k}$$$} in $$$O(n \cdot K)$$$.

The total time complexity is $$$O\left(T \cdot M \cdot \frac{\sqrt M}{\log M} \cdot K + T \cdot M \cdot \log M + \sum_{i=0}^T n_i \cdot K\right).$$$

/// In the name of God the most beneficent the most merciful

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

constexpr int T = 100;
constexpr int M = 100001;
constexpr int SQM = 320;
constexpr int LGM = 20;
vector<pair<int,int>> factor;
int t, n[T], count_multipliers[T][M];
bitset<M> is_composite;
vector<int> ans[T], a[T];

inline void calculate_importants() {
    for(int i = 2; i < SQM; i++)
        if(!is_composite[i]) {
            for(int j = i; j < M; j *= i)
                factor.push_back({j,i});
            for(int j = i*i; j < M; j += i)
                is_composite.set(j);
        }
    for(int i = SQM; i < M; i++)
        if(!is_composite[i])
            factor.push_back({i,i});
    sort(factor.begin(), factor.end());
}

void check(vector<int> &factors, int G) {
    if(factors.size() > 2u) {
        for(int i = 0; i < t; i++) 
            if(ans[i].size() < factors.size()) {
                int count_product = (G < M? count_multipliers[i][G] : 0);
                bool can = true;	
                for(auto u: factors)
                    if(count_multipliers[i][G/factor[u].first] == count_product) {
                        can = false;
                        break;
                    }
                if(can)
                    ans[i] = factors;
            }
    }
    int bound = (factors.size() == 1 ? SQM : M);
    if(1LL*G/factor[factors[0]].first*factor[factors.back()].first > bound)
        return;
    for(int new_factor = factors.back(); G/factor[factors[0]].first*factor[new_factor].first <= bound; new_factor++) 
        if(G%factor[new_factor].second) {
            factors.push_back(new_factor);
            check(factors, G*factor[new_factor].first);
            factors.pop_back();
        }
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(nullptr);
    calculate_importants();
    cin >> t;
    for(int i = 0; i < t; i++) {
        cin >> n[i];
        a[i].resize(n[i]);
        for(int j = 0; j < n[i]; j++) {
            cin >> a[i][j];
            count_multipliers[i][a[i][j]]++;
        }
        ans[i] = {a[i][0]};
        sort(a[i].begin(), a[i].begin()+min(n[i], LGM));
        for(int c = 0; c+1 < n[i]; c++)
            if(a[i][c+1]%a[i][c]) {
                ans[i] = {a[i][c], a[i][c+1]};
                break;
            }
        for(int c = 1; c < M; c++)
            for(int j = c+c; j < M; j += c)
                count_multipliers[i][c] += count_multipliers[i][j];
    }
    for(int i = 0; factor[i].first < SQM; i++) {
        vector<int> starter = {i};
        check(starter, factor[i].first);
    }
    for(int i = 0; i < t; i++) {
        int k = ans[i].size();
        cout << k << '\n';
        if(k == 1u) {
            cout << ans[i][0] << '\n';
        } else if(k == 2u) {
            cout << ans[i][0] << ' ' << ans[i][1] << '\n';
        } else {
            int subset[k];
            for(auto u: a[i]) {
                int ls = -1;
                for(int j = 0; j < (int)k; j++)
                    if(u%factor[ans[i][j]].first)
                        ls = (ls == -1? j: -2);
                if(ls >= 0)
                    subset[ls] = u;
            }
            for(int j = 0; j < k; j++)
                cout << subset[j] << (j+1 == k? '\n' : ' ');
        }
    }
    return 0;
}

/// Thank God . . .

/// In the name of God the most beneficent the most merciful

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

template<const bool negative = true, const int BITS = 9, typename _RandomAccessIterator>
inline void radix_sort(_RandomAccessIterator _first, _RandomAccessIterator _last, const bool reverse = false)
{
	typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
	if(negative)
	{
		if(!reverse) {
			_RandomAccessIterator _middle = partition(_first, _last, [](value_type a) -> bool {return a<0;});	
			for(auto it = _first; it != _middle; it++)*it *= -1;
			radix_sort<false>(_first, _middle, true);
			for(auto it = _first; it != _middle; it++)*it *= -1;
			radix_sort<false>(_middle, _last);
		} else {
			_RandomAccessIterator _middle = partition(_first, _last, [](value_type a) -> bool {return a>=0;});	
			radix_sort<false>(_first, _middle, true);
			for(auto it = _middle; it != _last; it++)*it *= -1;
			radix_sort<false>(_middle, _last);
			for(auto it = _middle; it != _last; it++)*it *= -1;
		}
		return;
	}
	constexpr int PART = (1<<BITS);
	constexpr int FULL = (1<<BITS)-1;
	int shift = 0;
	auto MAX = *max_element(_first, _last);
	vector<value_type> P[PART];
	while(log2(MAX) >= shift)
	{
		for(auto it = _first; it != _last; it++)P[(((*it)>>shift)&FULL)^(reverse?FULL:0)].push_back(*it);
		auto it = _first;
		for(int i = 0; i < PART; i++)
		{
			for(auto u: P[i]) *it++ = u;
			P[i].clear();
		}
		shift += BITS;
	}
}

int main() {
    vector<int> v{-3, 2, 3, -4, 1};
    radix_sort(v.begin(), v.end());
    for (auto i : v) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

step 1:

It's obvious that the answer is "NO" if $$$a_{i} = 0$$$ for all $$$1 \le i \le n$$$.

step 2:

Lets prove that the answer is "YES" if $$$a_{i} = 1$$$ for at least one $$$1 \le i \le n$$$.

step 3:

If size of $$$a$$$ is equal to $$$k$$$, just use second type operation once and we are done.

step 4:

Otherwise (if $$$|a| > k$$$), there will be three cases: (assume that $$$a_{j} = 1$$$)

• if $$$j > 2$$$, you can use first type operation on first and second element and decrease size of $$$a$$$ by 1.
• else if $$$j < |a|-1$$$, you can use first type operation on last and second to last element and decrease size of $$$a$$$ by 1.
• else, it can be shown easily that $$$|a| = 3$$$ and $$$k = 2$$$ so you can use second type operation twice and turn $$$a$$$ into a single $$$1$$$.

In first and second case, you can continue decreasing size of $$$a$$$ until $$$|a| = k$$$ (or you reach $$$3$$$-rd case) and you can use second type operation to reach your aim.

step 5:

So we proved that the answer is "YES" iff $$$a_{i} = 1$$$ for at least one $$$1 \le i \le n$$$ or in other words, iff $$$\sum_{i = 1}^n a_{i} > 0$$$.

// In the name of God
#include <iostream>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        int sum = 0;
        for(int i = 0 ; i < n ; i++){
            int a;
            cin >> a;
            sum += a;
        }
        if(sum > 0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
// Thank God

step 1:

step 2:

step 3:

step 4:

/// In the name of God
#include <iostream>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		int A[n], cnt[2][n+1];
		cnt[0][0] = cnt[1][0] = 0;
		for(int i = 0; i < n; i++)
		{
			cin >> A[i];
			cnt[0][i+1] = cnt[0][i]+(A[i]==0?1:0);
			cnt[1][i+1] = cnt[1][i]+(A[i]==1?1:0);
		}
		int ans = n-1;
		for(int last_zero = 0; last_zero <= n; last_zero++)
			ans= min(ans, max(cnt[1][last_zero], cnt[0][n]-cnt[0][last_zero]));
		cout << ans << endl;
	}
}
 
/// Thank God . . .

step 1:

step 2:

step 3:

step 4:

step 5:

/// In the name of God
#include <bits/stdc++.h>

using namespace std;

inline void solve()
{
	int n;
	cin >> n;
	int permutation[n], location[n];
	for(int i = 0; i < n; i++)
	{
		cin >> permutation[i];
		permutation[i]--;
		location[permutation[i]] = i;
	}
	for(int i = 0; i < n; i++)
	{
		if(location[i] == n-1)
			cout << rand()%n+1 << (i == n-1?'\n':' ');
		else
			cout << location[i]+2 << (i == n-1?'\n':' ');
	}
}

int main()
{
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}
/// Thank God . . .

Define $$$f(u, cnt)$$$ represents the maximum score of $$$cnt$$$ balls passing through the subtree of node $$$u$$$.

Define $$$num$$$ as the number of the sons of node $$$u$$$. The transition is only related to $$$\lceil cnt / num \rceil$$$ and $$$\lfloor cnt / num \rfloor$$$ two states of the subtree.

For each node $$$u$$$, $$$cnt$$$ can only be two adjacent integer $$$(x, x + 1)$$$.

It can be proved that the four numbers $$$\lfloor x/num \rfloor$$$, $$$\lceil x/num \rceil$$$, $$$\lceil (x + 1)/num \rceil$$$ and $$$\lfloor (x + 1)/num \rfloor$$$ can only have two kinds of numbers at most, and they are adjacent natural numbers.

So the number of states can be proved to be $$$\mathcal{O}(n)$$$.

/// In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200000;
ll V[N], dp[N];
int dad[N];
vector<int> child[N];
vector<pair<int, ll>> answers[N];

inline ll DP(int v, ll k)
{
	for(auto [kp, ans]: answers[v])
		if(k == kp)
			return ans;
	ll cnt_child = (ll)child[v].size();
	ll ans = k*V[v];
	if(cnt_child == 0)
		return ans;
	if(k%cnt_child == 0)
		for(auto u: child[v])
			ans += DP(u, k/cnt_child);
	else
	{
		ll dp1[cnt_child], dp2[cnt_child], diff[cnt_child];
		for(int i = 0; i < cnt_child; i++)
			dp1[i] = DP(child[v][i], k/cnt_child), dp2[i] = DP(child[v][i], k/cnt_child+1);
		for(int i = 0; i < cnt_child; i++)
			diff[i] = dp2[i] - dp1[i];
		sort(diff, diff+cnt_child, greater<int>());
		for(int i = 0; i < cnt_child; i++)
			ans += dp1[i];
		for(int i = 0; i < k%cnt_child; i++)
			ans += diff[i];
	}
	answers[v].push_back({k, ans});
	return ans;
}

inline ll solve()
{
	ll n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		child[i].clear(), answers[i].clear();
	dad[0] = 0;
	for(int i = 0; i < n-1; i++)
	{
		cin >> dad[i+1];
		dad[i+1]--;
		child[dad[i+1]].push_back(i+1);
	}
	for(int i = 0; i < n; i++)
		cin >> V[i];
	return DP(0, k);
}

int main()
{
	int t;
	cin >> t;
	while(t--)
		cout << solve() << '\n';
	return 0;
}
/// Thank God . . .

step 1:

step 2:

step 3:

step 4:

/// In the name of God
#pragma GCC optimize("Ofast","unroll-loops","O3")
#include <bits/stdc++.h>

using namespace std;

inline bool get_answer(){string s; cin >> s; return s == "YES";}

inline bool f(int i){return i&1;}
inline bool g(int i){return i&2;}

void solve(const vector<int> &Valid)
{
    if(Valid.size() < 3u)
	{
	    cout << "! " << Valid[0] << endl;
		string s;
		cin >> s;
		if(s == ":)")return;
		cout << "! " << Valid[1] << endl;
		return;
	}
	else if(Valid.size() == 3u)
	{
		bool is[4];
		cout << "? 1 " << Valid[0] << endl;is[0] = get_answer();
		cout << "? 1 " << Valid[1] << endl;is[1] = get_answer();
		cout << "? 1 " << Valid[1] << endl;is[2] = get_answer();
		cout << "? 1 " << Valid[0] << endl;is[3] = get_answer();
		if(is[1] and is[2])return solve({Valid[1]});
		else if(!is[1] and !is[2])return solve({Valid[0], Valid[2]});
		else if((is[0] and is[1]) or (is[2] and is[3]))return solve({Valid[0], Valid[1]});
		else if((is[0] and !is[1]) or (!is[2] and is[3]))return solve({Valid[0], Valid[2]});
		else return solve({Valid[1], Valid[2]});
	}
	else
	{
		vector<int> query[2];
		for(int i = 0; i < (int)Valid.size(); i++)
		{
			if(f(i))query[0].push_back(Valid[i]);
			if(g(i))query[1].push_back(Valid[i]);
		}
		bool is[2];
		for(int i = 0; i < 2; i++)
		{
			cout << "? " << query[i].size();
			for(auto u: query[i])cout << ' ' << u;
			cout << endl;
			is[i] = get_answer();
		}
		vector<int> NewValid;
		for(int i = 0; i < (int)Valid.size(); i++)
		{
			if((!f(i) ^ is[0]) or (!g(i) ^ is[1]))NewValid.push_back(Valid[i]);
		}
		return solve(NewValid);
	}
}
int main()
{
	int n = 0;
	cin >> n;
	vector<int> all(n);
	for(int i = 0; i < n; i++)all[i] = i+1;
	solve(all);
	return 0;
}
/// Thank God . . .

step 1:

First note that in any question we ask, a set will be introduced as the set that contains $$$x$$$. If the answer is "YES", then the set that we asked is introduced and otherwise, its complement.

step 2:

step 3:

/// In the name of God
#pragma GCC optimize("Ofast","unroll-loops","O3")
#include <bits/stdc++.h>
 
using namespace std;
 
const int SUM = 50;
int dp[SUM][SUM];
pair<int,int> updater[SUM][SUM];
map<pair<int,int>, int> Dp;
map<pair<int,int>, pair<int,int>> Updater;
 
inline void preprocess()
{
	for(int i = 0; i < SUM; i++)
	{
		for(int j = 0; j < SUM; j++)
		{
			dp[i][j] = SUM;
			updater[i][j] = {i, j};
		}
	}
	dp[0][0] = dp[0][1] = dp[1][0] = dp[2][0] = dp[1][1] = dp[0][2] = 0;
	for(int sum = 0; sum < SUM; sum ++)for(int last = sum; last >= 0; last--)
	{
		int now = sum - last;
		for(int SelectLast = 0; SelectLast <= last; SelectLast++)for(int SelectNow = 0; SelectNow <= now; SelectNow++)
		{
			if(dp[last][now] > 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][sum-SelectNow-SelectLast]))
			{
				dp[last][now] = 1 + max(dp[now-SelectNow][SelectNow+SelectLast], dp[SelectNow][now+last-SelectNow-SelectLast]);
				updater[last][now] = {SelectLast, SelectNow};
			}
		}
	}
}
 
inline int DP(const int last, const int now)
{
	if(last < 0 || now < 0)return SUM;
	if(last + now < SUM)return dp[last][now];
	if(Dp.find({last, now}) != Dp.end())return Dp[{last, now}];
	if((last&1) && (now&1))
	{
		Dp[{last, now}] = 1 + DP((now+1)/2, (last+ now)/2);
		Updater[{last, now}] = {(last+1)/2, now/2};
	}
	else
	{
		Dp[{last, now}] = 1 + DP((now+1)/2, (last+1)/2+(now+1)/2);
		Updater[{last, now}] = {(last+1)/2, (now+1)/2};
	}
	return Dp[{last, now}];
}
 
inline bool IsIn(const int x, const vector<int> &Sorted)
{
	auto u = lower_bound(Sorted.begin(), Sorted.end(), x);
	if(u == Sorted.end() or *u != x)return false;
	return true;
}
 
vector<int> solve(const vector<int> &LastAns, const vector<int> &Valid)
{
	if((int)Valid.size() < 3)
	{
		return Valid;
	}
	pair<int,int> Select;
	if((int)Valid.size() < SUM)
	{
		Select = updater[LastAns.size()][Valid.size()-LastAns.size()];
	}
	else
	{
		DP((int)LastAns.size(), (int)(Valid.size()-LastAns.size()));
		Select = Updater[{LastAns.size(), Valid.size()-LastAns.size()}];
	}
	vector<int> query;
	int p = 0;
	while(Select.first --)query.push_back(LastAns[p++]);
	p = 0;
	vector<int> LastAnsSorted = LastAns;
	sort(LastAnsSorted.begin(), LastAnsSorted.end());
	while(Select.second --)
	{
		while(IsIn(Valid[p], LastAnsSorted)) p++;
		query.push_back(Valid[p++]);
	}
	cout << "? " << query.size();
	for(auto u: query)cout << ' ' << u;
	cout << endl;
	
	string s;
	cin >> s;
	bool correct = (s == "YES");
	sort(query.begin(), query.end());
	vector<int> NewLast, NewValid;
	for(auto u: Valid)
	{
		if(!IsIn(u, LastAnsSorted) and (correct ^ IsIn(u, query)))
		{
			NewLast.push_back(u);
		}
		if(!IsIn(u, LastAnsSorted) or !(correct ^ IsIn(u, query)))
		{
			NewValid.push_back(u);
		}
	}
	vector<int> ans = solve(NewLast, NewValid);
	return ans;
}
 
int main()
{
	preprocess();
 
	int n;
	cin >> n;
	vector<int> all(n);
	for(int i = 0; i < n; i++)all[i] = i+1;
	vector<int> valid = solve({}, all);
	for(auto guess: valid)
	{
		cout << "! " << guess << endl;
		string s;
		cin >> s;
		if(s == ":)")return 0;
	}
	
	return 0;
}
/// Thank God . . .

step 1:

First of all, we can compress $$$a_{i}$$$'s and $$$x$$$'s (in second type query). so we can assume that all numbers are less than $$$n+q \le 6 \cdot 10^5$$$.

step 2:

step 3:

step 4:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
 
mt19937 rnd(time(0));
 
const int N = 300'000 + 5; 
const int Q = 300'000 + 5; 
const int T = 50;
bitset<N+Q> RandomSet[T];
unordered_map<int, int> id; int cnt_id = 0;
int n, q, A[N];
 
struct fenwick
{
	int PartialSum[N];
	fenwick()
	{
		for(int i = 0; i < N; i++)PartialSum[i] = 0;
	}
	inline void add(int index, bool increase)
	{
		while(index < N)
		{
			PartialSum[index] += (increase? 1 : -1);
			index += index&-index;
		}
	}
	inline int get(int index)
	{
		int sum = 0;
		while(index)
		{
			sum += PartialSum[index];
			index -= index&-index;
		}
		return sum;
	}
}Fen[T];
 
inline int GetId(const int x)
{
	auto id_iterator = id.find(x);
	if(id_iterator == id.end())
	{
		return id[x] = cnt_id++;
	}
	else return (*id_iterator).second;
}
 
inline void ChooseRandomSets()
{
	for(int i = 0; i < T; i++)
	{
		for(int j = 0; j < N+Q; j++)
		{
			if(rnd()&1)RandomSet[i].set(j);
		}
	}
}
 
inline void AddArrayToFenwick()
{
	for(int i = 0; i < n; i++)
	{
		int MyId = GetId(A[i]);
		for(int j = 0; j < T; j++)
		{
			if(RandomSet[j][MyId])Fen[j].add(i+1, true);
		}
	}
}
	
inline void Query()
{
	int index, l, r, k, x, type;
	for(int i = 0; i < q; i++)
	{
		cin >> type;
		if(type == 1)
		{
			cin >> index >> x;
			index --;
			int IdPre = GetId(A[index]);
			int IdNew = GetId(x);
			A[index] = x;
			for(int j = 0; j < T; j++)
			{
				if(RandomSet[j][IdPre])Fen[j].add(index+1, false);
				if(RandomSet[j][IdNew])Fen[j].add(index+1, true);
			}
		}
		if(type == 2)
		{
			cin >> l >> r >> k;
			l--;
			if(k == 1){cout << "YES\n"; continue;}
			else if((r-l)%k != 0){cout << "NO\n"; continue;}
			bool answer = true;
			for(int j = 0; j < T; j++)
			{
				if((Fen[j].get(r)-Fen[j].get(l))%k != 0){answer = false; break;}
			}
			cout << (answer?"YES":"NO") << '\n';
		}
	}
}
 
int main()
{
    ios::sync_with_stdio(false) , cin.tie(0);
    ChooseRandomSets();
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> A[i];
    AddArrayToFenwick();
    Query();
    return 0;
}

Consider all subsets of the original set in which tasks can be performed in some order to satisfy the constraints on their completion, and also that the size of each of them does not exceed $$$a+b+c$$$. It is easy to show that this set is a weighted matroid. This means that the optimal set of tasks can be found using a greedy algorithm.

So, we can find a set of tasks with maximum total usefulness, which:

• satisfies all deadline constraints
• has no more than $$$a+b+c$$$ elements

For the given parameters $$$(x, y, z)$$$, we introduce the following transformation:

• Increase the usefulness of all tasks of the first type by $$$x$$$, the second type~--- by $$$y$$$, and the third type~--- by $$$z$$$.

Let's assume that the optimal solution after the transformation is described by the triple $$$[a',b',c']$$$~--- the number of problems of each type, respectively. We need to get a solution described by the triple $$$[a,b,c]$$$. For $$$[a,b,c] \neq [a',b',c']$$$, $$$a+b+c=a'+b'+c'$$$ holds. Then (without limitation of generality, since there are at least two inequalities among $$$a\vee a',b\vee b',c\vee c'$$$) we assume that $$$a'>a,b'<b$$$.

Consider the following coordinate system on a two-dimensional plane (modulo the addition of $$$\overrightarrow{(1;1;1)})$$$:

For the coordinates of the point, we take the value $$$\vec{x}\times x+\vec{y}\times y + \vec{z}\times z$$$$$$(\vec{x}+\vec{y}+\vec{z} =\vec{0})$$$. It is easy to understand that the coordinates of the point $$$(x; y)$$$ on the plane are uniquely set by the triple $$$(x; y; z)$$$ up to the addition of $$$\overrightarrow{(1;1;1)} \times k, k \in\mathbb{Z}$$$

Let's assume that there are parameters $$$(x,y,z)$$$ for which the optimal solution is unique and equal to $$$[a,b,c]$$$ (see "But what if..?" to see what needs to be done to the input to make this hold).

Consider the solution $$$[a',b',c']$$$ for the "center" of the current polygon (initially it is a hexagon with infinitely distant coordinates). The "center" is the center of the triangle formed by the middle lines of our polygon.

On this plane, decreasing $$$z$$$ or $$$y$$$ does not increase $$$b'+c'$$$, therefore, it does not decrease $$$a'$$$. Thus, the red area in the picture below does not suit us.

Increasing $$$x$$$ or $$$z$$$ does not decrease $$$a'+c'$$$, therefore, it does not increase $$$b'$$$. Because of this, the blue area in the picture below does not suit us either.

So, we need to cut off one half-plane along the $$$z$$$ axis. It can be shown that the area of the polygon under consideration decreases by a constant time for every 2-3 iterations.

But what if the number of tasks of the desired color jumps from $$$a-1$$$ to $$$a+1$$$ at once? This is possible if and only if with the addition of some $$$x$$$ we get several pairs of elements of equal weight at the same time. To get rid of this, we can simply add a random number from $$$0$$$ to $$$\frac{1}{3}$$$ to each weight. The fact that such a change will fix the problem described above and will not change the optimal answer to the original problem remains to the reader as an exercise (the authors have proof).

After $$$O(\log C)$$$ iterations, our algorithm will converge to a point (a triple of real numbers). It remains only to check that the solution found is suitable for us.

$$$O(n\log n\log C)$$$

#include <bits/stdc++.h>
using namespace std;
 
#ifdef SG
	#include <debug.h>
#else
	template<typename T> struct outputer;
	struct outputable {};
	#define PRINT(...)
	#define OUTPUT(...)
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
	#define fbegin(...)
	#define fend
	#define pbegin(...)
	#define pend
#endif
 
#define ARG4(_1,_2,_3,_4,...) _4
 
#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)
 
#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)
 
#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb emplace_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())
 
typedef long double ld;
typedef signed __int128 lll;
typedef unsigned __int128 ulll;
typedef int64_t ll;
typedef uint64_t ull;
typedef uint32_t ui;
typedef uint16_t us;
typedef uint8_t uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;
 
template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}
 
const int N = 100000;
const int X = 1000000000;
const int T = 3;
 
struct Input {
	int n;
	std::array<int, T> k;
	int a[N], t[N], d[N];
	
	bool read() {
		if (!(cin >> n)) {
			return 0;
		}
		forn (i, T) {
			cin >> k[i];
		}
		forn (i, n) {
			cin >> a[i] >> t[i] >> d[i];
			--t[i];
			--d[i];
		}
		return 1;
	}
 
	void init(const Input& input) {
		*this = input;
	}
};
 
struct Data: Input {
	ll ans;
	
	void write() {
		cout << ans << endl;
	}
};
 
 
namespace Main {
	const lll P = 2 * N + 1;
	const lll Q = 2 * N + 2;
	const lll R = 2 * N + 3;
	const lll A[3] = {3 * P * Q, 3 * P * R, 3 * Q * R};
	const lll M = 3 * P * Q * R * N;
	const lll inf = (X + 1) * M;
 
	struct SNM {
		int rnd = 0;
		int n;
		int pr[N];
 
		void init(int cnt) {
			n = cnt;
			forn (i, n) {
				pr[i] = i;
			}
		}
 
		int get_p(int v) {
			if (v < 0 || pr[v] == v) {
				return v;
			}
			return pr[v] = get_p(pr[v]);
		}
 
		bool add(int v) {
			v = get_p(v);
			if (v == -1) {
				return 0;
			}
			pr[v] = v - 1;
			return 1;
		}
	};
	
	struct Solution: Data {
		SNM snm;
 
		int m;
		lll b[N], c[N];
		vi ord[T];
 
		array<int, T> check(const array<lll, T>& adds) {
			forn (i, n) {
				c[i] = b[i] + adds[t[i]];
			}
			auto cmp = [&](int lhs, int rhs) {
				return c[lhs] > c[rhs];
			};
			static vi q;
			q.clear();
			forn (i, T) {
				static vi w;
				w.resize(sz(q) + sz(ord[i]));
				merge(all(q), all(ord[i]), w.begin(), cmp);
				q.swap(w);
			}
 
			snm.init(n);
			array<int, T> cnt{};
			int tot = 0;
			ll val = 0;
			for (int i : q) {
				if (tot >= m) {
					break;
				}
				if (snm.add(d[i])) {
					cnt[t[i]]++;
					tot++;
					val += a[i];
				}
			}
			if (cnt == k) {
				ans = val;
			}
			return cnt;
		}
 
		// x[i] == adds[(i + 1) % T] - adds[i]
 
		array<lll, T> get_middle_point(const array<lll, T>& lb, const array<lll, T>& rb) {
			array<lll, T> x;
			forn (i, T) {
				x[i] = lb[i] + rb[i];
			}
			lll sum = accumulate(all(x), lll(0));
			forn (i, T) {
				x[i] = T * x[i] - sum;
				if (x[i] >= 0) {
					x[i] /= (2 * T);
				} else {
					x[i] = (x[i] - 2 * T + 1) / (2 * T);
				}
			}
			sum = accumulate(all(x), lll(0));
			forn (i, T) {
				if (sum < 0 && x[i] < rb[i]) {
					x[i]++;
					sum++;
				}
				assert(x[i] >= lb[i]);
				assert(x[i] <= rb[i]);
			}
			assert(sum == 0);
			return x;
		}
 
		bool search() {
			array<lll, T> lb, rb;
			forn (i, T) {
				lb[i] = -2 * inf;
				rb[i] = 2 * inf;
			}
 
			while (true) {
				{
					lll sum_l = accumulate(all(lb), lll(0));
					lll sum_r = accumulate(all(rb), lll(0));
					forn (i, T) {
						lll sol = sum_l - lb[i];
						lll sor = sum_r - rb[i];
						umx(lb[i], -sor);
						umn(rb[i], -sol);
						if (lb[i] > rb[i]) {
							return 0;
						}
					}
				}
				array<lll, T> x = get_middle_point(lb, rb);
				array<lll, T> adds{};
				forn (i, T - 1) {
					adds[i + 1] = adds[i] + x[i];
				}
				array<int, T> cnt = check(adds);
				assert(accumulate(all(cnt), 0) == m);
				if (cnt == k) {
					return 1;
				}
				forn (i, T) {
					lll d1 = cnt[i] - k[i];
					lll d2 = cnt[(i + 1) % T] - k[(i + 1) % T];
					if (d1 > 0 && d2 < 0) {
						lb[i] = x[i] + 1;
					}
					if (d1 < 0 && d2 > 0) {
						rb[i] = x[i] - 1;
					}
				}
			}
		}
		
		void solve() {
			forn (i, n) {
				b[i] = a[i] * M + i * A[t[i]];
			}
			forn (i, n) {
				ord[t[i]].pb(i);
			}
			forn (i, T) {
				sort(all(ord[i]), [&](int lhs, int rhs) {
					return b[lhs] > b[rhs];
				});
			}
			m = accumulate(all(k), 0);
 
			{
				array<int, T> r = check({});
				if (accumulate(all(r), 0) != m) {
					ans = -1;
					return;
				}
			}
			forn (i, T) {
				array<lll, T> adds{};
				adds[i] = inf;
				if (check(adds)[i] < k[i]) {
					ans = -1;
					return;
				}
				adds[i] = -inf;
				if (check(adds)[i] > k[i]) {
					ans = -1;
					return;
				}
			}
			assert(search());
		}
		
		void clear() {
			forn (i, T) {
				ord[i].clear();
			}
		}
	};
}
 
 
Main::Solution sol;
 
int main() {
	#ifdef SG
		freopen((problemname + ".in").c_str(), "r", stdin);
//		freopen((problemname + ".out").c_str(), "w", stdout);
	#endif
	
	int t;
	cin >> t;
	forn (i, t) {
		sol.read();
		sol.solve();
		sol.write();
		sol.clear();
	}
	
	return 0;
}