codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2034.md (44114B)


      1 Source: https://codeforces.com/blog/entry/136579
      2 
      3 ### 👋 Salam Codeforces!
      4 
      5 Here are the step-by-step solutions. Hoping you enjoy them! 😊
      6 
      7 The announcement blog is available [here](https://codeforces.com/blog/entry/136396) and you can also explore all blogs related to Rayan [here!](https://codeforces.com/rayan)
      8 
      9 #### [2034A - King Keykhosrow's Mystery](/contest/2034/problem/A)
     10 
     11 **Idea:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
     12 
     13 **Solution**
     14 
     15 * **Step 1:** Prove that for the minimum value of $m$, we must have $m \% a = m \% b = 0$.
     16 * **Step 2:** To prove this, show that if $m \% a = m \% b = x \gt 0$, then $m-1$ will also satisfy the problem's requirements.
     17 * **Step 3:** Since $m \ge \min(a , b)$, if $x \gt 0$, then $m \gt \min(a , b)$ must hold. Therefore, $m - 1 \ge \min(a , b)$ implies that $m-1$ satisfies the requirements.
     18 * **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)))$.
     19 
     20 **Implementation**
     21 
     22 ```
     23 #include <bits/stdc++.h>
     24 
     25 using namespace std;
     26 
     27 int main(){
     28   int tt;
     29   cin >> tt;
     30   while(tt--){
     31     int a, b;
     32     cin >> a >> b;
     33     cout << lcm(a , b) << endl;
     34   }
     35 }
     36 ```
     37 
     38 #### [2034B - Rakhsh's Revival](/contest/2034/problem/B)
     39 
     40 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") and [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") — **Preparation:** [AmShZ](/profile/AmShZ "Grandmaster AmShZ")
     41 
     42 **Solution**
     43 
     44 We will solve the problem using the following approach:
     45 
     46 * Start from the leftmost spot and move rightwards.
     47 * 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.
     48 * Repeat this process until no segment of $m$ consecutive weak spots remains.
     49 
     50 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.
     51 
     52 **Correctness Proof:**
     53 
     54 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.
     55 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.
     56 
     57 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.
     58 
     59 **Implementation**
     60 
     61 ```
     62 # include <bits/stdc++.h>
     63 
     64 using namespace std;
     65 
     66 const int xn = 2e5 + 10;
     67 
     68 int q, n, m, k, ps[xn];
     69 string s;
     70 
     71 int main() {
     72     cin >> q;
     73     while (q --) {
     74         cin >> n >> m >> k >> s;
     75         fill(ps, ps + n, 0);
     76         int ans = 0, cnt = 0, sum = 0;
     77         for (int i = 0; i < n; ++ i) {
     78             sum += ps[i];
     79             if (sum || s[i] == '1') cnt = 0;
     80             else {
     81                 cnt++;
     82                 if (cnt == m) {
     83                     sum++, ans++, cnt = 0;
     84                     if (i + k < n) ps[i + k]--;
     85                 }
     86             }
     87         }
     88         cout << ans << "\n";
     89     }
     90 }
     91 ```
     92 
     93 #### [2034C - Trapped in the Witch's Labyrinth](/contest/2034/problem/C)
     94 
     95 **Idea:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM")
     96 
     97 **Solution**
     98 
     99 * 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.
    100 * 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.
    101 * 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.
    102 * 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.
    103 * 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.
    104 * 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).
    105 
    106 **Implementation**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110  
    111 using namespace std;
    112  
    113 int main() 
    114 {
    115     int tc;
    116     cin >> tc;
    117     while(tc--){
    118         int n, m;
    119         cin >> n >> m;
    120         string c[n+1];
    121         for(int i = 1 ; i <= n ; i++) cin >> c[i] , c[i] = "-" + c[i];
    122         vector<pair<int,int>> jda[n+2][m+2];
    123         for(int i = 1 ; i <= n ; i++){
    124             for(int j = 1 ; j <= m ; j++){
    125                 if(c[i][j] == 'U') jda[i-1][j].push_back({i , j});
    126                 if(c[i][j] == 'R') jda[i][j+1].push_back({i , j});
    127                 if(c[i][j] == 'D') jda[i+1][j].push_back({i , j});
    128                 if(c[i][j] == 'L') jda[i][j-1].push_back({i , j});
    129             }
    130         }
    131         int vis[n+2][m+2] = {};
    132         queue<pair<int,int>> q;
    133         for(int j = 0 ; j <= m+1 ; j++) vis[0][j] = 1 , q.push({0 , j});
    134         for(int i = 1 ; i <= n+1 ; i++) vis[i][0] = 1 , q.push({i , 0});
    135         for(int j = 1 ; j <= m+1 ; j++) vis[n+1][j] = 1 , q.push({n+1 , j});
    136         for(int i = 1 ; i <= n ; i++) vis[i][m+1] = 1 , q.push({i , m+1});
    137         while(q.size()){
    138             auto [i , j] = q.front();
    139             q.pop();
    140             for(auto [a , b] : jda[i][j]){
    141                 if(vis[a][b] == 0){
    142                     vis[a][b] = 1;
    143                     q.push({a , b});
    144                 }
    145             }
    146         }
    147         for(int i = 1 ; i <= n ; i++){
    148             for(int j = 1 ; j <= m ; j++){
    149                 if(c[i][j] == '?' and
    150                 vis[i-1][j] and vis[i][j+1] and vis[i+1][j] and vis[i][j-1]) vis[i][j] = 1;
    151             }
    152         }
    153         int ans = n * m;
    154         for(int i = 1 ; i <= n ; i++){
    155             for(int j = 1 ; j <= m ; j++){
    156                 if(vis[i][j] == 1) ans -= 1;
    157             }
    158         }
    159         cout << ans << endl;
    160     }
    161     return 0;
    162 }
    163 ```
    164 
    165 #### [2034D - Darius' Wisdom](/contest/2034/problem/D)
    166 
    167 **Idea and Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
    168 
    169 **Solution**
    170 
    171 * **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.
    172 * **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.
    173 * **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}$.
    174 * **Step 4:** We can assume $count(0) \leq count(2)$ without loss of generality (Why?). So, the maximum number of moves are:
    175 
    176 $2 \min(count(0), count(1)+count(2))+\min(count(1), count(2))$ $= 2 \cdot count(0) + \min(count(1), count(2))$ $\le count(0) + \max(count(1), count(2)) + \min(count(1), count(2))$ $=count(0)+count(1)+count(2)=n$
    177 
    178 **Better approach:**
    179 
    180 * **Step 1:** Since we are allowed to perform $n$ moves, assign each index one *"move"* as its *"specified cost"*.
    181 * **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.
    182 * **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:
    183 
    184 $2\ 2\ \dots\ 2\ (x\ \text{times})\ 1\ 0\ 0\ \dots\ 0\ (x\ \text{times}),$
    185 
    186 * **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$.
    187 
    188 **Implementation (first approach)**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 
    193 using namespace std;
    194 
    195 const int N = 200000;
    196 int n, cnt[3], a[N];
    197 vector<int> vip[3][3]; // Value In Position
    198 vector<pair<int, int>> swaps;
    199 
    200 inline int Pos(int index) {
    201     if(index < cnt[0])
    202         return 0;
    203     else if(index < cnt[0]+cnt[1])
    204         return 1;
    205     else
    206         return 2; 
    207 }
    208 
    209 inline void AddBack(int index) {
    210     vip[a[index]][Pos(index)].push_back(index);
    211 }
    212 
    213 inline void RemoveBack(int index) {
    214     vip[a[index]][Pos(index)].pop_back();
    215 }
    216 
    217 inline void Swap(int i, int j) {
    218     swaps.push_back({i, j});
    219     RemoveBack(i);
    220     RemoveBack(j);
    221     swap(a[i], a[j]);
    222     AddBack(i);
    223     AddBack(j);
    224 }
    225 
    226 inline void Fix(int x) {
    227     while(!vip[1][x].empty() or !vip[2-x][x].empty()) {
    228         if(vip[1][x].empty()) {
    229             if(!vip[1][2-x].empty())
    230                 Swap(vip[2-x][x].back(), vip[1][2-x].back());
    231             else
    232                 Swap(vip[2-x][x].back(), vip[1][1].back());
    233         }
    234         if(!vip[x][1].empty()) 
    235             Swap(vip[1][x].back(), vip[x][1].back());
    236         else
    237             Swap(vip[1][x].back(), vip[x][2-x].back());
    238     }  
    239 }
    240 
    241 int main() 
    242 {
    243     ios_base::sync_with_stdio(false), cin.tie(0);
    244     int t;
    245     cin >> t;
    246     while (t--) {
    247         cin >> n;
    248         for(int i = 0; i < n; i++)
    249             cin >> a[i], cnt[a[i]]++;
    250         for(int i = 0; i < n; i++)
    251             AddBack(i);
    252         if(cnt[0] <= cnt[2]) {
    253             Fix(0);
    254             Fix(2);
    255         } else {
    256             Fix(2);
    257             Fix(0);
    258         }
    259         cout << swaps.size() << endl;
    260         for(auto [i, j]: swaps)
    261             cout << i+1 << ' ' << j+1 << endl;
    262         cnt[0] = cnt[1] = cnt[2] = 0;
    263         for(int i = 0; i < 3; i++)
    264             for(int j = 0; j < 3; j++)
    265                 vip[i][j].clear();
    266         swaps.clear();
    267     }
    268     return 0;
    269 }
    270 ```
    271 
    272 **Implementation (second approach)**
    273 
    274 ```
    275 // In the name of god
    276 #include <bits/stdc++.h>
    277 
    278 using namespace std;
    279 
    280 const int N = 200000;
    281 int n, cnt[3], a[N];
    282 vector<int> vip[3][3]; // Value In Position
    283 vector<pair<int, int>> swaps;
    284 
    285 inline int Pos(int index) {
    286     if(index < cnt[0])
    287         return 0;
    288     else if(index < cnt[0]+cnt[1])
    289         return 1;
    290     else
    291         return 2; 
    292 }
    293 
    294 inline void AddBack(int index) {
    295     vip[a[index]][Pos(index)].push_back(index);
    296 }
    297 
    298 inline void RemoveBack(int index) {
    299     vip[a[index]][Pos(index)].pop_back();
    300 }
    301 
    302 inline void Swap(int i, int j) {
    303     swaps.push_back({i, j});
    304     RemoveBack(i);
    305     RemoveBack(j);
    306     swap(a[i], a[j]);
    307     AddBack(i);
    308     AddBack(j);
    309 }
    310 
    311 inline void Fix() {
    312     bool change;
    313     do {
    314         change = false;
    315         while ((!vip[1][0].empty()) && (!vip[0][1].empty()))
    316             Swap(vip[1][0].back(), vip[0][1].back()), change = true;
    317         while ((!vip[1][0].empty()) && (!vip[0][2].empty()))
    318             Swap(vip[1][0].back(), vip[0][2-0].back()), change = true;
    319         while ((!vip[1][2].empty()) && (!vip[2][1].empty()))
    320             Swap(vip[1][2].back(), vip[2][1].back()), change = true;
    321         while ((!vip[1][2].empty()) && (!vip[2][0].empty()))
    322             Swap(vip[1][2].back(), vip[2][0].back()), change = true;
    323     } while (change);    
    324 }
    325 
    326 inline void PingPong() {
    327     if(vip[0][2].empty())
    328         return;
    329     Swap(vip[1][1].back(), vip[0][2].back());
    330     while (true){
    331         Swap(vip[1][2].back(), vip[2][0].back());
    332         if(vip[0][2].empty())
    333             break;
    334         Swap(vip[1][0].back(), vip[0][2].back());
    335     }
    336     Swap(vip[1][0].back(), vip[0][1].back());
    337 }
    338 
    339 int main() 
    340 {
    341     ios_base::sync_with_stdio(false), cin.tie(0);
    342     int t;
    343     cin >> t;
    344     while (t--) {
    345         cin >> n;
    346         for(int i = 0; i < n; i++)
    347             cin >> a[i], cnt[a[i]]++;
    348         for(int i = 0; i < n; i++)
    349             AddBack(i);
    350         Fix();
    351         PingPong();
    352         cout << swaps.size() << endl;
    353         for(auto [i, j]: swaps)
    354             cout << i+1 << ' ' << j+1 << endl;
    355         // reset
    356         cnt[0] = cnt[1] = cnt[2] = 0;
    357         for(int i = 0; i < 3; i++)
    358             for(int j = 0; j < 3; j++)
    359                 vip[i][j].clear();
    360         swaps.clear();
    361     }
    362     return 0;
    363 }
    364 ```
    365 
    366 #### [2034E - Permutations Harmony](/contest/2034/problem/E)
    367 
    368 **Idea:** [AmirrzwM](/profile/AmirrzwM "Master AmirrzwM") and [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh") — **Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
    369 
    370 **Solution**
    371 
    372 * **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!$.
    373 * **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$.
    374 * **Step 3:** For $k = 1$, $n$ must be $1$. Symmetrically, $k$ cannot be $n! - 1$. Solutions for other odd $k$ will now be provided.
    375 * **Step 4:** To construct an answer for $k = 3$ and $n = 2x + 1$, consider the following derived using a greedy approach:
    376 
    377 | $p_1$ | $p_2$ | $p_3$ | $p_4$ | $p_5$ | $ \ldots $ | $p_{2x-1} $ | $ p_{2x} $ | $ p_{2x+1} $ |
    378 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
    379 | 1 | 2 | 3 | 4 | 5 | $ \ldots $ | $ 2x-1 $ | $ 2x $ | $ 2x+1 $ |
    380 | $ x+1 $ | $ 2x+1 $ | $ x $ | $ 2x $ | $ x-1 $ | $ \ldots $ | 2 | $ x+2 $ | 1 |
    381 | $ 2x+1 $ | $ x $ | $ 2x $ | $ x-1 $ | $ 2x-1 $ | $ \ldots $ | $ x+2 $ | 1 | $ x+1 $ |
    382 
    383 * **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.
    384 
    385 **Implementation**
    386 
    387 ```
    388 // In the name of God
    389 #include <bits/stdc++.h>
    390 using namespace std;
    391  
    392 int main() {
    393     ios_base::sync_with_stdio(false), cin.tie(0);
    394     int t;
    395     cin >> t;
    396     int f[8] = {1,1,2,6,24,120,720,5040};
    397     while(t--) {
    398         int n, k;
    399         cin >> n >> k;
    400         if(min(n, k) == 1) {
    401             if(n*k == 1) {
    402                 cout << "Yes\n1\n";
    403             } else cout << "No\n";
    404         } else if(n < 8 and (f[n] < k or f[n] == k+1)) {
    405             cout << "No\n";
    406         } else if(n % 2 == 0 and k % 2 == 1) {
    407             cout << "No\n";
    408         } else {
    409             vector<vector<int>> base, all;
    410             vector<int> per(n);
    411             for(int i = 0; i < n; i++) per[i] = i+1;
    412             if(k % 2) {
    413                 vector<int> p1(n), p2(n);
    414                 for(int i = 0; i < n; i += 2) p1[i] = (n+1)/2-i/2, p2[i] = n-i/2;
    415                 for(int i = 1; i < n; i += 2) p1[i] = n-i/2, p2[i] = n/2-i/2;
    416                 all = base = {per, p1, p2};
    417                 k -= 3;
    418             }
    419             do {
    420                 if(k == 0)
    421                     break;
    422                 vector<int> mirror(n);
    423                 for(int i = 0; i < n; i++)
    424                     mirror[i] = n+1-per[i];
    425                 if(per < mirror) {
    426                     bool used = false;
    427                     for(auto &p: base) used |= (p == per), used |= (p == mirror);
    428                     if(not used) {
    429                         k -= 2;
    430                         all.push_back(per);
    431                         all.push_back(mirror);
    432                     }
    433                 }
    434             } while (next_permutation(per.begin(), per.end()));
    435             cout << "Yes\n";
    436             for(auto p: all) {
    437                 for(int i = 0; i < n; i++)
    438                     cout << p[i] << (i+1==n?'\n':' ');
    439             }
    440         }
    441     }
    442  
    443     return 0;
    444 }
    445  
    446 // Thanks God
    447 ```
    448 
    449 #### [2034F1 - Khayyam's Royal Decree (Easy Version)](/contest/2034/problem/F1)
    450 
    451 **Idea and Preparation:** [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    452 
    453 **Solution**
    454 
    455 * **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.
    456 * **Step 2:** Order the redefined conditions $(x, y)$ in increasing order based on the value of $x + y$.
    457 * **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)$.
    458 * **Step 4:** Define $cost_{i,j}$, the increase in value for moving directly from state $i$ to state $j$ without intermediate doubling, as:
    459 
    460 $cost_{i,j} = 2|x_i - x_j| + |y_i - y_j|$
    461 
    462 * **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:
    463 
    464 $dp_i = 2 \sum_{0 \leq j \lt i} ways_{j,i} \times (dp_j + \binom{x_j + y_j}{x_j} \times cost_{j,i})$
    465 
    466 * **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}$.
    467 
    468 **Implementation**
    469 
    470 ```
    471 #include <bits/stdc++.h>
    472 using namespace std;
    473  
    474 #define nl "\n"
    475 #define nf endl
    476 #define ll long long
    477 #define pb push_back
    478 #define _ << ' ' <<
    479  
    480 #define INF (ll)1e18
    481 #define mod 998244353
    482 #define maxn 400010
    483  
    484 ll fc[maxn], nv[maxn];
    485  
    486 ll fxp(ll b, ll e) {
    487     ll r = 1, k = b;
    488     while (e != 0) {
    489         if (e % 2) r = (r * k) % mod;
    490         k = (k * k) % mod; e /= 2;
    491     }
    492     return r;
    493 }
    494  
    495 ll inv(ll x) {
    496     return fxp(x, mod - 2);
    497 }
    498  
    499 ll bnm(ll a, ll b) {
    500     if (a < b || b < 0) return 0;
    501     ll r = (fc[a] * nv[b]) % mod;
    502     r = (r * nv[a - b]) % mod;
    503     return r;
    504 }
    505  
    506 int main() {
    507     ios::sync_with_stdio(0);
    508     cin.tie(0);
    509  
    510     fc[0] = 1; nv[0] = 1;
    511     for (ll i = 1; i < maxn; i++) {
    512         fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    513     }
    514  
    515     ll t; cin >> t;
    516     while (t--) {
    517         ll n, m, k; cin >> n >> m >> k;
    518         vector<array<ll, 2>> a(k + 2, {0, 0});
    519         for (ll i = 1; i <= k; i++) {
    520             cin >> a[i][0] >> a[i][1];
    521             a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1];
    522         }
    523         a[k + 1] = {n, m}; k++;
    524         sort(a.begin() + 1, a.end());
    525  
    526         auto paths = [&](ll i, ll j) {
    527             ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1];
    528             return bnm(dx + dy, dx);
    529         };
    530  
    531         auto add = [&](ll &x, ll y) {
    532             x = (x + y) % mod;
    533             x = (x + mod) % mod;
    534         };
    535  
    536         vector direct(k + 1, vector<ll>(k + 1, 0));
    537         for (ll i = 1; i <= k; i++) {
    538             for (ll j = i - 1; j >= 0; j--) {
    539                 direct[j][i] = paths(j, i);
    540                 for (ll l = j + 1; l < i; l++) {
    541                     add(direct[j][i], -paths(j, l) * direct[l][i]);
    542                 }
    543             }
    544         }
    545  
    546         vector<ll> dp(k + 1, 0);
    547         for (ll i = 1; i <= k; i++) {
    548             for (ll j = 0; j < i; j++) {
    549                 if (direct[j][i] == 0) continue;
    550                 ll partial = dp[j];
    551                 ll delta = 2 * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]);
    552                 add(partial, paths(0, j) * delta);
    553                 add(dp[i], partial * direct[j][i]);
    554             }
    555             if (i != k) dp[i] = (2 * dp[i]) % mod;
    556         }
    557  
    558         ll ans = (dp[k] * inv(bnm(n + m, m))) % mod;
    559         cout << ans << nl;
    560     }
    561  
    562     return 0;
    563 }
    564 ```
    565 
    566 #### [2034F2 - Khayyam's Royal Decree (Hard Version)](/contest/2034/problem/F2)
    567 
    568 **Idea and Preparation:** [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    569 
    570 **Solution**
    571 
    572 * **Step 1:** For simplicity, redefine the special conditions for the number of rubies and sapphires in your satchel (not chest).
    573 * **Step 2:** Order the redefined conditions $(x, y)$ in increasing order based on the value of $x + y$.
    574 * **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:
    575 
    576 $total_{i,j} = \binom{|x_i - x_j| + |y_i - y_j|}{|x_i - x_j|}$
    577 
    578 * **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:
    579 
    580 $weight_i = \sum_{i \lt j \leq k} total_{i,j} \times weight_j$
    581 
    582 * **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.
    583 * **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:
    584 
    585 $dp_i = (2x_i + y_i) \times total_{0, i} \times weight_i$
    586 
    587 * **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}$.
    588 
    589 **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.
    590 
    591 **Implementation**
    592 
    593 ```
    594 #include <bits/stdc++.h>
    595 using namespace std;
    596  
    597 #define nl "\n"
    598 #define nf endl
    599 #define ll long long
    600 #define pb push_back
    601 #define _ << ' ' <<
    602  
    603 #define INF (ll)1e18
    604 #define mod 998244353
    605 #define maxn 400010
    606  
    607 ll fc[maxn], nv[maxn];
    608  
    609 ll fxp(ll b, ll e) {
    610     ll r = 1, k = b;
    611     while (e != 0) {
    612         if (e % 2) r = (r * k) % mod;
    613         k = (k * k) % mod; e /= 2;
    614     }
    615     return r;
    616 }
    617  
    618 ll inv(ll x) {
    619     return fxp(x, mod - 2);
    620 }
    621  
    622 ll bnm(ll a, ll b) {
    623     if (a < b || b < 0) return 0;
    624     ll r = (fc[a] * nv[b]) % mod;
    625     r = (r * nv[a - b]) % mod;
    626     return r;
    627 }
    628  
    629 int main() {
    630     ios::sync_with_stdio(0);
    631     cin.tie(0);
    632  
    633     fc[0] = 1; nv[0] = 1;
    634     for (ll i = 1; i < maxn; i++) {
    635         fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    636     }
    637  
    638     ll t; cin >> t;
    639     while (t--) {
    640         ll n, m, k; cin >> n >> m >> k;
    641         vector<array<ll, 2>> a(k + 2, {0, 0});
    642         for (ll i = 1; i <= k; i++) {
    643             cin >> a[i][0] >> a[i][1];
    644             a[i][0] = n - a[i][0]; a[i][1] = m - a[i][1];
    645         }
    646         a[k + 1] = {n, m}; k++;
    647         sort(a.begin() + 1, a.end());
    648  
    649         auto paths = [&](ll i, ll j) {
    650             ll dx = a[j][0] - a[i][0], dy = a[j][1] - a[i][1];
    651             return bnm(dx + dy, dx);
    652         };
    653  
    654         auto add = [&](ll &x, ll y) {
    655             x = (x + y) % mod;
    656             x = (x + mod) % mod;
    657         };
    658  
    659         vector<ll> cnt_weighted(k + 1, 0);
    660         cnt_weighted[k] = 1;
    661         for (ll i = k - 1; i >= 1; i--) {
    662             for (ll j = i + 1; j <= k; j++) {
    663                 add(cnt_weighted[i], paths(i, j) * cnt_weighted[j]);
    664             }
    665         }
    666  
    667         ll ans = 0;
    668         for (ll i = 1; i <= k; i++) {
    669             ll delta = 2 * a[i][0] + a[i][1];
    670             add(ans, delta * paths(0, i) % mod * cnt_weighted[i]);
    671         }
    672  
    673         ans = (ans * inv(bnm(n + m, m))) % mod;
    674         cout << ans << nl;
    675     }
    676  
    677     return 0;
    678 }
    679 ```
    680 
    681 **Note:** Thanks to [peti1234](/profile/peti1234 "Legendary Grandmaster peti1234") and [_istil](/profile/_istil "International Grandmaster _istil") for suggesting the idea of including this subtask!
    682 
    683 #### [2034G1 - Simurgh's Watch (Easy Version)](/contest/2034/problem/G1)
    684 
    685 **Idea:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras") — **Preparation:** [AmShZ](/profile/AmShZ "Grandmaster AmShZ") and [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras")
    686 
    687 **Solution**
    688 
    689 * 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.
    690 * 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.
    691   + For each step, we find the leftmost point that has not been colored yet and color the segment that contains this point.
    692   + We always choose the interval with the largest endpoint that contains the current point.
    693   + By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these colors.
    694 * Now, we check if we can color the intervals with just two colors using a greedy algorithm:
    695   + We iterate over the intervals sorted by start (increasingly) and then by end (decreasingly).
    696   + 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$.
    697   + We color the current interval based on the value of $I$:
    698     - If $I = 0$, color interval $i$ with color 1.
    699     - If $I = 1$, color interval $i$ with the opposite color of the current used color.
    700     - If $I = 2$, color interval $i$ with the same color of the interval with the smallest endpoint among the currently open intervals.
    701   + 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.
    702 
    703 **Solving G1 using G2:**
    704 
    705 * 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?).
    706 * To handle this, we can multiply all the given points by two, effectively converting the problem into one in which only integer points exist.
    707 * After this transformation, we solve the problem in the integer system of G2, where the intervals and coloring rules are defined using integer boundaries!
    708 
    709 **Note:** A brief explanation of why this greedy algorithm works can be found [here](https://codeforces.com/blog/entry/136579?#comment-1223389).
    710 
    711 **Implementation**
    712 
    713 ```
    714 /* In the name of Allah */
    715 // Welcome to the Soldier Side!
    716 // Where there's no one here, but me...
    717 #include<bits/stdc++.h>
    718 using namespace std;
    719 
    720 const int N = 2e5 + 5;
    721 int t, n, l[N], r[N], col[N];
    722 vector<int> st[N << 1], en[N << 1];
    723 
    724 void compress_points() {
    725     vector<int> help;
    726     for (int i = 0; i < n; i++) {
    727         help.push_back(l[i]);
    728         help.push_back(r[i]);
    729     }
    730 
    731     sort(help.begin(), help.end());
    732     help.resize(unique(help.begin(), help.end()) - help.begin());
    733     for (int i = 0; i < n; i++) {
    734         l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin();
    735         r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin();
    736     }
    737 }
    738 
    739 void record_points() {
    740     for (int i = 0; i < n; i++) {
    741         st[l[i]].push_back(i);
    742         en[r[i] + 1].push_back(i);
    743     }
    744     for (int i = 0; i < 2 * n; i++)
    745         sort(st[i].begin(), st[i].end(), [](int i, int j) {
    746             return r[i] > r[j];
    747         });
    748 }
    749 
    750 void try3_points() {
    751     fill(col, col + n, 0);
    752     int cur = -1, nxt = -1, c = 2;
    753     for (int i = 0; i < 2 * n; i++) {
    754         if (st[i].empty())
    755             continue;
    756 
    757         if (!~cur || i > r[cur]) {
    758             if (cur ^ nxt && r[nxt] < i) {
    759                 col[nxt] = (c ^= 3);
    760                 cur = nxt;
    761             }
    762 
    763             if (cur ^ nxt)
    764                 cur = nxt;
    765             else {
    766                 cur = st[i][0];
    767                 for (int p: st[i])
    768                     if (r[p] > r[cur])
    769                         cur = p;
    770                 nxt = cur;
    771             }
    772             col[cur] = (c ^= 3);
    773         }
    774         
    775         for (int p: st[i])
    776             if (r[p] > r[nxt])
    777                 nxt = p;
    778     }
    779     if (cur ^ nxt)
    780         col[nxt] = c ^ 3;
    781 }
    782 
    783 bool is_bad(set<pair<int, int>> s[2]) {
    784     int cnt1 = s[0].size(), cnt2 = s[1].size();
    785     return cnt1 + cnt2 && cnt1 ^ 1 && cnt2 ^ 1;
    786 }
    787 
    788 void try2_points() {
    789     set<pair<int, int>> s[2];
    790     for (int i = 0; i <= 2 * n; i++) {
    791         for (int p: en[i])
    792             s[col[p]].erase({r[p], p});
    793         if (is_bad(s)) {
    794             try3_points();
    795             return;
    796         }
    797 
    798         for (int p: st[i]) {
    799             int cnt1 = s[0].size();
    800             int cnt2 = s[1].size();
    801             if (!cnt1 || !cnt2)
    802                 col[p] = cnt1 > 0;
    803             else if (cnt1 ^ cnt2)
    804                 col[p] = cnt1 < cnt2;
    805             else
    806                 col[p] = s[0].begin()->first > s[1].begin()->first;
    807 
    808             s[col[p]].insert({r[p], p});
    809             if (is_bad(s)) {
    810                 try3_points();
    811                 return;
    812             }
    813         }
    814     }
    815 }
    816 
    817 void read_input() {
    818     cin >> n;
    819     for (int i = 0; i < n; i++)
    820         cin >> l[i] >> r[i];
    821 }
    822 
    823 void solve() {
    824     compress_points();
    825     record_points();
    826     try2_points();
    827 }
    828 
    829 void write_output() {
    830     cout << *max_element(col, col + n) + 1 << endl;
    831     for (int i = 0; i < n; i++)
    832         cout << col[i] + 1 << "\n "[i < n - 1];
    833 }
    834 
    835 void reset_variables() {
    836     for (int i = 0; i < n; i++) {
    837         col[i] = 0;
    838         st[l[i]].clear();
    839         en[r[i] + 1].clear();
    840     }
    841 }
    842 
    843 int main() {
    844     ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    845     for (cin >> t; t--; reset_variables())
    846         read_input(), solve(), write_output();
    847     return 0;
    848 }
    849 ```
    850 
    851 **Note:** Special thanks to **Prof. Mohammad Ali Abam** for proposing this problem!
    852 
    853 **Fun fact:** He wasn’t able to solve it himself, but when he presented it to me (Arshia is talking...), he said, *“I don’t know how to solve it yet, but I guess its difficulty would be at most around E…”*
    854 
    855 #### [2034G2 - Simurgh's Watch (Hard Version)](/contest/2034/problem/G2)
    856 
    857 **Idea and Preparation:** [ArshiaDadras](/profile/ArshiaDadras "Master ArshiaDadras")
    858 
    859 **Solution**
    860 
    861 * **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.
    862 * **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.
    863 * **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$.
    864   + **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$.
    865   + **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$.
    866   + 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.
    867 * **Step 4:** To efficiently move from time $x$ to $x + 1$, we perform the following steps:
    868   + Remove the intervals that have $r_i = x$ (since they no longer contain $x+1$).
    869   + Add the intervals that have $l_i = x + 1$.
    870   + Update the set of intervals that can be uniquely colored at time $x+1$.
    871 * **Step 5:** Finally, we observe that only the following points are important for the coloring:
    872 
    873   + $l_i$ and $r_i$ for each interval.
    874   + $l_i - 1$ and $r_i + 1$, since these points mark the boundaries where intervals start or end.
    875 
    876 Thus, we can compress the numbers to reduce the range of values we need to process.
    877 
    878 **Implementation**
    879 
    880 ```
    881 /* In the name of Allah */
    882 // Welcome to the Soldier Side!
    883 // Where there's no one here, but me...
    884 #include<bits/stdc++.h>
    885 using namespace std;
    886 
    887 const int N = 2e5 + 5;
    888 vector<int> st[N << 2], en[N << 2];
    889 int t, n, k, l[N], r[N], dp[N], col[N], prv[N];
    890 
    891 void compress_numbers() {
    892     vector<int> help;
    893     for (int i = 0; i < n; i++) {
    894         help.push_back(l[i] - 1);
    895         help.push_back(l[i]);
    896         help.push_back(r[i]);
    897         help.push_back(r[i] + 1);
    898     }
    899 
    900     sort(help.begin(), help.end());
    901     help.resize(k = unique(help.begin(), help.end()) - help.begin());
    902     for (int i = 0; i < n; i++) {
    903         l[i] = lower_bound(help.begin(), help.end(), l[i]) - help.begin();
    904         r[i] = lower_bound(help.begin(), help.end(), r[i]) - help.begin();
    905     }
    906 }
    907 
    908 void save_checkpoints() {
    909     for (int i = 0; i < n; i++) {
    910         st[l[i]].push_back(i);
    911         en[r[i]].push_back(i);
    912     }
    913 }
    914 
    915 bool check_one() {
    916     for (int i = 0, open = 0; i < k; i++) {
    917         open += st[i].size();
    918         if (open > 1)
    919             return false;
    920         open -= en[i].size();
    921     }
    922     return true;
    923 }
    924 
    925 void color_with_two() {
    926     for (int i = k - 1, cur = -1; ~i; i--) {
    927         if (en[i].empty())
    928             continue;
    929 
    930         while (!~cur || i < dp[cur])
    931             if (~cur && ~prv[cur]) {
    932                 col[prv[cur]] = col[cur];
    933                 if (r[prv[cur]] >= l[cur])
    934                     col[prv[cur]] ^= 1;
    935                 cur = prv[cur];
    936             }
    937             else
    938                 for (int p: en[i])
    939                     if (~dp[p] && (!~cur || dp[p] < dp[cur]))
    940                         cur = p;
    941 
    942         for (int p: en[i])
    943             if (p ^ cur)
    944                 col[p] = col[cur] ^ 1;
    945     }
    946 }
    947 
    948 bool check_two() {
    949     set<int> goods, bads;
    950     fill(dp, dp + n, -1);
    951     fill(prv, prv + n, -1);
    952     for (int i = 0; i < k; i++) {
    953         int prev = -1;
    954         if (i)
    955             for (int p: en[i - 1]) {
    956                 bads.erase(p), goods.erase(p);
    957                 if (~dp[p] && (!~prev || dp[p] < dp[prev]))
    958                     prev = p;
    959             }
    960         int open = goods.size() + bads.size();
    961 
    962         if (open == 1 || (open == 2 && !goods.empty())) {
    963             for (int p: bads) {
    964                 if (open == 1)
    965                     prv[p] = prev;
    966                 else
    967                     prv[p] = *goods.begin();
    968                 goods.insert(p);
    969                 dp[p] = i;
    970             }
    971             bads.clear();
    972         }
    973 
    974         if (open == 1)
    975             prev = *goods.begin();
    976         for (int p: st[i])
    977             if (!open || open == 1 || ~prev) {
    978                 goods.insert(p);
    979                 prv[p] = prev;
    980                 dp[p] = i;
    981             }
    982             else
    983                 bads.insert(p);
    984         open += st[i].size();
    985 
    986         if (open && goods.empty())
    987             return false;
    988     }
    989 
    990     color_with_two();
    991     return true;
    992 }
    993 
    994 void color_with_three() {
    995     int cur = -1, nxt = -1;
    996     for (int i = 0; i < k; i++) {
    997         if (st[i].empty())
    998             continue;
    999 
   1000         if (~cur && i > r[cur] && nxt ^ cur) {
   1001             col[nxt] = col[cur] ^ 3;
   1002             cur = nxt;
   1003         }
   1004         if (!~cur || i > r[cur]) {
   1005             for (int p: st[i])
   1006                 if (!~cur || r[p] > r[cur])
   1007                     cur = p;
   1008             col[nxt = cur] = 1;
   1009         }
   1010 
   1011         for (int p: st[i])
   1012             if (r[p] > r[nxt])
   1013                 nxt = p;
   1014     }
   1015 
   1016     if (cur ^ nxt)
   1017         col[nxt] = col[cur] ^ 3;
   1018 }
   1019 
   1020 void read_input() {
   1021     cin >> n;
   1022     for (int i = 0; i < n; i++)
   1023         cin >> l[i] >> r[i];
   1024 }
   1025 
   1026 void solve() {
   1027     compress_numbers();
   1028     save_checkpoints();
   1029     if (check_one())
   1030         return;
   1031     if (check_two())
   1032         return;
   1033     color_with_three();
   1034 }
   1035 
   1036 void write_output() {
   1037     cout << *max_element(col, col + n) + 1 << endl;
   1038     for (int i = 0; i < n; i++)
   1039         cout << col[i] + 1 << "\n "[i < n - 1];
   1040 }
   1041 
   1042 void reset_variables() {
   1043     fill(col, col + n, 0);
   1044     for (int i = 0; i < k; i++) {
   1045         st[i].clear();
   1046         en[i].clear();
   1047     }
   1048 }
   1049 
   1050 int main() {
   1051     ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
   1052     for (cin >> t; t--; reset_variables())
   1053         read_input(), solve(), write_output();
   1054     return 0;
   1055 }
   1056 ```
   1057 
   1058 **Note:** Thanks to [_istil](/profile/_istil "International Grandmaster _istil") and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") for suggesting the idea of including this subtask!
   1059 
   1060 #### [2034H - Rayan vs. Rayaneh](/contest/2034/problem/H)
   1061 
   1062 **Idea and Preparation:** [MohammadParsaElahimanesh](/profile/MohammadParsaElahimanesh "Master MohammadParsaElahimanesh")
   1063 
   1064 **Solution**
   1065 
   1066 * **Step 1:** According to [Bézout's Identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_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$.
   1067 * **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$.
   1068 * **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$.
   1069 * **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} \lt p_2^{q_2} \lt \ldots \lt p_k^{q_k}$, where $p_i \neq p_j$ and $p_i$ is prime.
   1070 * **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$.
   1071 * **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.
   1072 * **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)$.
   1073 * **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] \gt CM[G] \geq 0$ for all $i$.
   1074 * **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.
   1075 * **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}.$
   1076 * **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})$.
   1077 * **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 \lt 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17.$
   1078 * **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)$.
   1079 
   1080 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).$
   1081 
   1082 **Implementation**
   1083 
   1084 ```
   1085 /// In the name of God the most beneficent the most merciful
   1086 
   1087 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
   1088 #include <bits/stdc++.h>
   1089 using namespace std;
   1090 typedef long long ll;
   1091 
   1092 constexpr int T = 100;
   1093 constexpr int M = 100001;
   1094 constexpr int SQM = 320;
   1095 constexpr int LGM = 20;
   1096 vector<pair<int,int>> factor;
   1097 int t, n[T], count_multipliers[T][M];
   1098 bitset<M> is_composite;
   1099 vector<int> ans[T], a[T];
   1100 
   1101 inline void calculate_importants() {
   1102     for(int i = 2; i < SQM; i++)
   1103         if(!is_composite[i]) {
   1104             for(int j = i; j < M; j *= i)
   1105                 factor.push_back({j,i});
   1106             for(int j = i*i; j < M; j += i)
   1107                 is_composite.set(j);
   1108         }
   1109     for(int i = SQM; i < M; i++)
   1110         if(!is_composite[i])
   1111             factor.push_back({i,i});
   1112     sort(factor.begin(), factor.end());
   1113 }
   1114 
   1115 void check(vector<int> &factors, int G) {
   1116     if(factors.size() > 2u) {
   1117         for(int i = 0; i < t; i++) 
   1118             if(ans[i].size() < factors.size()) {
   1119                 int count_product = (G < M? count_multipliers[i][G] : 0);
   1120                 bool can = true;	
   1121                 for(auto u: factors)
   1122                     if(count_multipliers[i][G/factor[u].first] == count_product) {
   1123                         can = false;
   1124                         break;
   1125                     }
   1126                 if(can)
   1127                     ans[i] = factors;
   1128             }
   1129     }
   1130     int bound = (factors.size() == 1 ? SQM : M);
   1131     if(1LL*G/factor[factors[0]].first*factor[factors.back()].first > bound)
   1132         return;
   1133     for(int new_factor = factors.back(); G/factor[factors[0]].first*factor[new_factor].first <= bound; new_factor++) 
   1134         if(G%factor[new_factor].second) {
   1135             factors.push_back(new_factor);
   1136             check(factors, G*factor[new_factor].first);
   1137             factors.pop_back();
   1138         }
   1139 }
   1140 
   1141 int main() {
   1142     ios_base :: sync_with_stdio(false); cin.tie(nullptr);
   1143     calculate_importants();
   1144     cin >> t;
   1145     for(int i = 0; i < t; i++) {
   1146         cin >> n[i];
   1147         a[i].resize(n[i]);
   1148         for(int j = 0; j < n[i]; j++) {
   1149             cin >> a[i][j];
   1150             count_multipliers[i][a[i][j]]++;
   1151         }
   1152         ans[i] = {a[i][0]};
   1153         sort(a[i].begin(), a[i].begin()+min(n[i], LGM));
   1154         for(int c = 0; c+1 < n[i]; c++)
   1155             if(a[i][c+1]%a[i][c]) {
   1156                 ans[i] = {a[i][c], a[i][c+1]};
   1157                 break;
   1158             }
   1159         for(int c = 1; c < M; c++)
   1160             for(int j = c+c; j < M; j += c)
   1161                 count_multipliers[i][c] += count_multipliers[i][j];
   1162     }
   1163     for(int i = 0; factor[i].first < SQM; i++) {
   1164         vector<int> starter = {i};
   1165         check(starter, factor[i].first);
   1166     }
   1167     for(int i = 0; i < t; i++) {
   1168         int k = ans[i].size();
   1169         cout << k << '\n';
   1170         if(k == 1u) {
   1171             cout << ans[i][0] << '\n';
   1172         } else if(k == 2u) {
   1173             cout << ans[i][0] << ' ' << ans[i][1] << '\n';
   1174         } else {
   1175             int subset[k];
   1176             for(auto u: a[i]) {
   1177                 int ls = -1;
   1178                 for(int j = 0; j < (int)k; j++)
   1179                     if(u%factor[ans[i][j]].first)
   1180                         ls = (ls == -1? j: -2);
   1181                 if(ls >= 0)
   1182                     subset[ls] = u;
   1183             }
   1184             for(int j = 0; j < k; j++)
   1185                 cout << subset[j] << (j+1 == k? '\n' : ' ');
   1186         }
   1187     }
   1188     return 0;
   1189 }
   1190 
   1191 /// Thank God . . .
   1192 ```