codeforces-scrape

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

2047.md (48723B)


      1 Source: https://codeforces.com/blog/entry/136908
      2 
      3 ### Div2A
      4 
      5 Alyona is happy when there are no unfinished layers — that is, in front of her is a perfect square with odd side length. Since the order of pieces is fixed, it is enough to keep track of the total current size $s$ of the puzzle, and after each day check, if the $s$ is a perfect square of an odd number. The easiest way to do that is to create an additional array containing $1^2, 3^2, 5^3, ..., 99^2$, and check after each day, whether $s$ is in this array.
      6 
      7 **Code**
      8 
      9 ```
     10 NT = int(input())
     11 
     12 sqs = set()
     13 k = 1
     14 while k * k <= 100 * 1000:
     15 	sqs.add(k * k)
     16 	k += 2
     17 
     18 for T in range(NT):
     19 	n = int(input())
     20 	a = list(map(int, input().split()))
     21 	answer = 0
     22 	cursum = 0
     23 	for t in a:
     24 		cursum += t
     25 		if cursum in sqs:
     26 			answer += 1
     27 	print(answer)
     28 ```
     29 
     30 ### Div2B
     31 
     32 Find the character which appears the lowest number of times — if tied, take the earlier character in the alphabet. Find the character which appears the highest number of times — if tied, take the later character in the alphabet. Then, replace any of the lowest-occurrence characters with the highest-occurrence character.
     33 
     34 **Code**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 int main() {
     42     cin.tie(0)->sync_with_stdio(0);
     43     int t;
     44     cin >> t;
     45     while (t--) {
     46         int n;
     47         cin >> n;
     48         string s;
     49         cin >> s;
     50         vector<int> occ(26);
     51         for (int i=0; i<n; i++)
     52             occ[s[i] - 'a'] += 1;
     53         pair<pair<int,char>,int> low, high;
     54         low = high = {{occ[s[0] - 'a'], s[0]}, 0};
     55         for (int i=1; i<n; i++) {
     56             low = min(low, {{occ[s[i] - 'a'], s[i]}, i});
     57             high = max(high, {{occ[s[i] - 'a'], s[i]}, i});
     58         }
     59         s[low.second] = s[high.second];
     60         cout << s << "\n";
     61     }
     62   return 0;
     63 }
     64 ```
     65 
     66 ### Div2C
     67 
     68 We can divide the columns in the matrix into three different groups:
     69 
     70 1. the columns where we go through the top cell;
     71 2. the columns where we go through the bottom cell;
     72 3. the columns where we go through both cells.
     73 
     74 There should be exactly one column in the $3$-rd group — this will be the column where we shift from the top row to the bottom row. However, all other columns can be redistributed between groups $1$ and $2$ as we want: if we want to put a column into the $1$-st group, we put it before the column where we go down; otherwise, we put it after the column where we go down. So, we can get any distribution of columns between the $1$-st and the $2$-nd group.
     75 
     76 Now let's consider the contribution of each column to the answer. Columns from the $1$-st group add $a_{1,i}$ to the answer, columns from the $2$-nd group add $a_{2,i}$, the column from the $3$-rd group adds both of these values. So, we can iterate on the index of the column where we go down, take $a_{1,i} + a_{2,i}$ for it, and take $\max(a_{1,j}, a_{2,j})$ for every other column. This works in $O(n^2)$, and under the constraints of the problem, it is enough.
     77 
     78 However, it is possible to solve the problem in $O(n)$. To do so, calculate the sum of $\max(a_{1,j}, a_{2,j})$ over all columns. Then, if we pick the $i$-th column as the column where we go down, the answer be equal to this sum, plus $\min(a_{1,i}, a_{2,i})$, since this will be the only column where we visit both cells.
     79 
     80 **Code**
     81 
     82 ```
     83 for _ in range(int(input())):
     84     n = int(input())
     85     a = []
     86     for i in range(2):
     87         a.append(list(map(int, input().split())))
     88     best = [max(a[0][i], a[1][i]) for i in range(n)]
     89     full = [a[0][i] + a[1][i] for i in range(n)]
     90     sum_best = sum(best)
     91     ans = -10 ** 19
     92     for i in range(n):
     93         ans = max(ans, sum_best + full[i] - best[i])
     94     print(ans)
     95 ```
     96 
     97 ### Div2D
     98 
     99 The first idea is to notice, that each element is moved to the back at most once. Indeed, if we fix a subset of elements that we ever move to the back, we can perform the operation once on each of them in any order we like, and that becomes their final order with the smallest possible increase. The optimal order is, of course, the increasing order. The question is how to select this subset of elements to move to the back.
    100 
    101 Since we need the lexicographically smallest array, we're looking for some greedy approach that chooses the smallest possible element on the next position one by one, left to right.
    102 
    103 * What's the smallest number our resulting array can start with? Of course, the minimum. That means, all the elements in front of the minimum have to be moved to the back and be increased by one.
    104 * What's the smallest number we can have on the second place, given that we have the minimum in the first positions? Either the smallest element to the right of the minimum, or the smallest element among those already moved to the back.
    105 * ...
    106 
    107 Analysing this approach, we see that as we go left to right, we keep picking elements from the suffix minima sequence, and keep growing the set of elements we have to move to the right to ''extract'' this sequence from the initial array. At one point, the next smallest element comes not from the suffix minima sequence, but from the pile of integers we move to the right. At this point, all the remaining elements have to be moved to the right once (that is, increased by $1$), and then listed in sorted order.
    108 
    109 So, the answer is always several first elements of the suffix minima sequence, starting from the global minimum, and then all other elements, increased by $1$ and sorted in increased order. To find the point where we switch from the suffix minima sequence to the moved elements, it is convenient to precomute the minima, and keep a set of those elements we already move to the right.
    110 
    111 This solution runs in $O(n \log n)$, along with many other.
    112 
    113 **Code**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 
    118 using namespace std;
    119 
    120 #ifdef LOCAL
    121     #define eprintf(...) fprintf(stderr, __VA_ARGS__)
    122 #else
    123     #define eprintf(...) 42
    124 #endif
    125 
    126 using ll = long long;
    127 using ld = long double;
    128 using D = double;
    129 using uint = unsigned int;
    130 template<typename T>
    131 using pair2 = pair<T, T>;
    132 
    133 #define pb push_back
    134 #define mp make_pair
    135 #define all(x) (x).begin(),(x).end()
    136 #define fi first
    137 #define se second
    138 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    139 
    140 void solve()
    141 {
    142 	int n;
    143 	scanf("%d", &n);
    144 	vector<int> a(n);
    145 	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    146 	vector<int> front(n);
    147 	int frontfront = n;
    148 	int frontback = n;
    149 	multiset<int> back;
    150 	for (int i = n - 1; i >= 0; i--)
    151 	{
    152 		if (frontfront >= frontback || a[i] <= front[frontfront]) front[--frontfront] = a[i];
    153 		else back.insert(a[i] + 1);
    154 		while (frontfront < frontback && !back.empty() && front[frontback - 1] > *back.begin())
    155 		{
    156 			back.insert(front[frontback - 1] + 1);
    157 			frontback--;
    158 		}
    159 	}
    160 	vector<int> answer;
    161 	for (int i = frontfront; i < frontback; i++) answer.pb(front[i]);
    162 	for (auto t : back) answer.pb(t);
    163 	for (auto t : answer) printf("%d ", t);
    164 	printf("\n");
    165 }
    166 
    167 int main()
    168 {
    169     int NT = 1;
    170     scanf("%d", &NT);
    171     for (int T = 1; T <= NT; T++)
    172     {
    173         solve();
    174     }
    175     return 0;
    176 }
    177 ```
    178 
    179 ### Div1C
    180 
    181 First, we will use the idea of binary search on the answer. Let's assume we are currently checking if we can achieve the answer $k$.
    182 
    183 We will iterate over all the necessary coordinates of the vertical lines. To do this, we note that it makes sense to iterate only over those where the lines coincide in the Y-coordinate with at least one of the points. It is obvious that in this case, the necessary vertical lines will be on the order of $O(n)$.
    184 
    185 During the iteration over the vertical line, we will maintain two segment trees for the sum: one for the left half of the plane and the other for the right. $t_y$ in each of the segment trees will represent how many points have a Y-coordinate of $y$ in the corresponding half of the plane. In each of the segment trees, we will check if it is possible to divide the half-plane into two parts by a line parallel to the x-axis, so that there are at least $k$ points in both parts; and if this is possible, we will find the set of suitable lines — it will obviously be some segment $[y_{l}, \, y_{r}]$. If the intersection of the resulting segments in both segment trees is not empty, then we have found the answer. This can be done by descending the tree in $O(\log n)$ time.
    186 
    187 Thus, the total time complexity of the described solution is $O(n \log^2 n)$.
    188 
    189 **Code**
    190 
    191 ```
    192 #include <math.h>
    193 #include <unordered_set>
    194 #include <unordered_map>
    195 #include <map>
    196 #include <iostream>
    197 #include <fstream>
    198 #include <vector>
    199 #include <set>
    200 #include <array>
    201 #include <cstring>
    202 #include <ctime>
    203 #include <cassert>
    204 #include <string_view>
    205 #include <functional>
    206 #include <sstream>
    207 #include <numeric>
    208 #include <cmath>
    209 #include <deque>
    210 #include <list>
    211 #include <algorithm>
    212 #include <iomanip>
    213  
    214 using namespace std;
    215  
    216 using i64 = long long;
    217 using ui32 = unsigned int;
    218 using ui64 = unsigned long long;
    219  
    220 #define all(a) (a).begin(), (a).end()
    221  
    222  
    223 struct Tree;
    224  
    225 Tree* NewNode();
    226  
    227 struct Count {
    228     int left = 0;
    229     int right = 0;
    230     void Add(int delta) {
    231         left += delta;
    232         if (delta < 0) {
    233             right -= delta;
    234         }
    235     }
    236     void operator += (const Count& c) {
    237         left += c.left;
    238         right += c.right;
    239     }
    240  
    241     int GetMin() {
    242         return min(left, right);
    243     }
    244 };
    245  
    246 struct Tree {
    247         Count count;
    248         Tree* left = nullptr;
    249         Tree* right = nullptr;
    250  
    251         void Add(int l, int r, int p, int delta = 1) {
    252             count.Add(delta);
    253             if (r - l == 1) {
    254                 return;
    255             }
    256             int mid = (l + r) / 2;
    257             if (p < mid) {
    258                 if (left == nullptr) {
    259                     left = NewNode();
    260                 }
    261                 left->Add(l, mid, p, delta);
    262             } else {
    263                 if (right == nullptr) {
    264                     right = NewNode();
    265                 }
    266                 right->Add(mid, r, p, delta);
    267             }
    268         } 
    269  
    270         Count LeftCount() {
    271             if (left) {
    272                 return left->count;
    273             }
    274             return {};
    275         }
    276         Count RightCount() {
    277             if (right) {
    278                 return right->count;
    279             }
    280             return {};
    281         }
    282  
    283         void Remove(int l, int r, int p) {
    284             Add(l, r, p, -1);
    285         }
    286 };
    287  
    288 Tree nodes[7000000];
    289  
    290 Tree* NewNode() {
    291     static Tree* nextNode = nodes;
    292     return nextNode++;
    293 }
    294  
    295  
    296 struct Solver {
    297     struct Point {
    298         int x, y;
    299         bool operator < (const Point& p) const {
    300             return x < p.x;
    301         }
    302     };
    303  
    304     int max = 0;
    305     int bx = 0;
    306     int by = 0;
    307  
    308     bool FindBest(int l, int r, Tree* node, const Count& left = {}, const Count& right = {}) {
    309         if (node == nullptr) {
    310             return false;
    311         }
    312         int mid = (l + r) / 2;
    313         Count newLeft = node->LeftCount();
    314         Count newRight = node->RightCount();
    315         newLeft += left;
    316         newRight += right;
    317         int mn = min(newLeft.GetMin(), newRight.GetMin());
    318         bool updated = false;
    319         if (mn > max) {
    320             max = mn;
    321             by = mid;
    322             updated = true;
    323         }
    324         if (mn == newLeft.GetMin()) {
    325             if (FindBest(mid, r, node->right, newLeft, right)) {
    326                 return true;
    327             }
    328         } else {
    329             if (FindBest(l, mid, node->left, left, newRight)) {
    330                 return true;
    331             }
    332         }
    333         return updated;
    334     }
    335  
    336     void Solve(istream& cin, ostream& cout) {
    337         int n;
    338         cin >> n;
    339         vector<Point> a(n);
    340         int t9 = 1000000001;
    341         #ifdef pperm
    342             t9 = 100;
    343         #endif
    344         Tree* tree = NewNode();
    345         for (Point& p : a) {
    346             cin >> p.x >> p.y;
    347             tree->Add(-t9, t9, p.y);
    348         }
    349         sort(all(a));
    350         for (int i = 0; i < n;) {
    351             int j = i + 1;
    352             while (j < n && a[j].x == a[i].x) {
    353                 ++j;
    354             }
    355             if (FindBest(-t9, t9, tree)) {
    356                 bx = a[i].x;
    357             }
    358             for (;i < j; ++i) {
    359                 tree->Remove(-t9, t9, a[i].y);
    360  
    361             }
    362         }
    363         cout << max << '\n' << bx << ' ' << by << endl;
    364     }
    365 };
    366  
    367 int main(int argc, char* args[]) {
    368 #ifdef pperm
    369     ifstream cin("/home/pperm86/My/Codeforces/input.txt");
    370 #endif
    371     ios_base::sync_with_stdio(false);
    372     cin.tie(NULL);
    373 #ifndef pperm
    374     srand(time(0));
    375 #endif
    376     int T = 1;
    377     cin >> T;
    378     for (int iTest = 1; iTest <= T; ++iTest) {
    379 		Solver solver{};
    380         solver.Solve(cin, cout);
    381     }
    382 #ifdef pperm
    383     cout << clock() / static_cast<double>(CLOCKS_PER_SEC) << endl;
    384 #endif
    385     return 0;
    386 }
    387 ```
    388 
    389 ### Div1D
    390 
    391 We will compress the graph into strongly connected components. Inside a component, each runner can move between any pair of vertices and thus visit all. We will now solve the problem for a directed acyclic graph.
    392 
    393 We will check for the existence of an answer. Suppose all runners already know the winning plan, and we will try to send them out so that each vertex is visited at least once. To do this, it is necessary to decompose the graph into paths such that:
    394 
    395 * each vertex belongs to at least one path;
    396 * no more than $a[i]$ paths start at each vertex (where $a[i]$ is the number of runners initially located at the vertex);
    397 * paths may intersect.
    398 
    399 Take the source $s$ and the sink $t$, and now a path can be represented as a sequence $s$, $u_1$, ..., $u_k$, $t$.
    400 
    401 We will divide $u$ into $u_{in}$ and $u_{out}$ and will consider that a vertex $u$ belongs to least one transition from $u_{in}$ to $u_{out}$. We will draw the following edges:
    402 
    403 * from $s$ to $u_{in}$ with capacity $cap = a[u]$;
    404 * from $u_{in}$ to $u_{out}$ with $cap = inf$ and the condition of flow through the edge $f \geq 1$;
    405 * from $u_{out}$ to $t$ with $cap = inf$;
    406 * from $u_{out}$ to $v_{in}$ with $cap = inf$ for all edges (u, v) in the original graph.
    407 
    408 ![ ](/predownloaded/41/d3/41d3da67b74ad5eda560d04845cc6ca97f68949e.jpg) This is equivalent to finding a flow with constraints in this graph.
    409 
    410 To do this, we will create a dummy source $s'$ and sink $t'$, and now for each edge $(u_{in}, u_{out})$ with flow through it $1 \le f \le inf$, we will make the following replacements by drawing edges:
    411 
    412 * from $u_{in}$ to $u_{out}$ with $cap = inf - 1$;
    413 * from $s'$ to $u_{out}$ with $cap = 1$;
    414 * from $u_{in}$ to $t'$ with $cap = 1$;
    415 * from $t$ to $s$ with $cap = inf$.
    416 
    417 Finding a flow that satisfies the constraints is equivalent to finding the maximum flow from $s'$ to $t'$, and if it equals the number of vertices, then the answer exists; otherwise, we can output $-1$ at this step.
    418 
    419 ![ ](/predownloaded/4c/e2/4ce2771a796ad3b3d5310694f14c80422245e536.jpg)
    420 
    421 Now we minimize the number of runners who initially know the plan. Note that:
    422 
    423 * it makes no sense for runners to move until they know the plan;
    424 * it makes no sense to pass the plan to more than one runner from one city.
    425 
    426 We try to take this into account when constructing. Instead of adding edges from the source to $u_{in}$, we will do the following:
    427 
    428 * create a vertex $u_{cnt}$ to control the number of runners and draw edges:
    429 * from $s$ to $u_{cnt}$ with $cap = a[u]$;
    430 * from $u_{cnt}$ to $u_{out}$ with $cap = a[u]$;
    431 * from $u_{cnt}$ to $u_{in}$ with $cap = 1$, $cost = 1$.
    432 * assign zero cost to all other edges.
    433 
    434 ![ ](/predownloaded/52/57/525770492f58a1e415184633040fbe140aea471c.jpg) This is equivalent to ensuring that all $a[i]$ runners learn the plan, but if no one comes to our city, we will personally tell exactly one runner from this number, paying $cost=1$ for that person.
    435 
    436 The answer to the problem is the minimum cost of the maximum flow from $s'$ to $t'$ with this graph construction. The proof follows from the graph construction.
    437 
    438 MCMF can be considered as $O(n^2m^2)$ or $O(n^3m)$ for any graphs, but it is worth noting that the flow value $f$ is limited to $n$, and we have a solution in $O(fnm)$ using Ford-Bellman or $O(fm\log n)$ using Dijkstra's algorithm with potentials.
    439 
    440 Interestingly, we note that as a result, we obtained $3n$ vertices and $m + 7n$ edges. With careful implementation, MCMF fits well within TL.
    441 
    442 **Code**
    443 
    444 ```
    445 #define _CRT_SECURE_NO_WARNINGS
    446 
    447 #include<iostream>
    448 #include<fstream>
    449 #include<vector>
    450 #include<stack>
    451 #include<queue>
    452 #include<set>
    453 #include<map>
    454 #include<array>
    455 #include<unordered_set>
    456 #include<unordered_map>
    457 #include<cstring>
    458 #include<string>
    459 #include<memory>
    460 #include<iomanip>
    461 #include<cassert>
    462 #include<cmath>
    463 #include<random>
    464 #include<algorithm>
    465 #include<chrono>
    466 
    467 #pragma GCC optimize("O3,unroll-loops")
    468 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    469 
    470 #define int long long
    471 #define ld long double
    472 #define endl '\n'
    473 
    474 using namespace std;
    475 
    476 constexpr int N = 500;
    477 vector<int> g[N], gr[N], gcmp[N];
    478 int a[N], acmp[N], used[N], color[N], cur_color = 0;
    479 vector<int> order, cmp;
    480 
    481 void dfs1(int u) {
    482 	for (int v : g[u]) {
    483 		if (used[v] == 0) {
    484 			used[v] = 1;
    485 			dfs1(v);
    486 		}
    487 	}
    488 	order.push_back(u);
    489 }
    490 
    491 void dfs2(int u) {
    492 	for (int v : gr[u]) {
    493 		if (used[v] == 0) {
    494 			used[v] = 1;
    495 			dfs2(v);
    496 		}
    497 	}
    498 	color[u] = cur_color;
    499 }
    500 
    501 inline array<int, 3> getInd(int u) {
    502 	return { 3 * u, 3 * u + 1, 3 * u + 2 };
    503 }
    504 
    505 constexpr int INF = 0x3f3f3f3f;
    506 
    507 struct MCMF {
    508 	struct rib {
    509 		int b, u, c, f;
    510 		size_t back;
    511 	};
    512 
    513 	MCMF(int size) : n(size), g_mcmf(size) {};
    514 
    515 	int n;
    516 	vector<vector<rib>> g_mcmf;
    517 
    518 	void rebuild(int sz) {
    519 		n = sz, g_mcmf.clear(); g_mcmf.resize(sz);
    520 	}
    521 
    522 	void add_rib(int a, int b, int u, int c) {
    523 		rib r1 = { b, u, c, 0, g_mcmf[b].size() };
    524 		rib r2 = { a, 0, -c, 0, g_mcmf[a].size() };
    525 		g_mcmf[a].push_back(r1);
    526 		g_mcmf[b].push_back(r2);
    527 	}
    528 
    529 	pair<int, int> get_flow(int s, int t, int maxflow = INF) {
    530 		int flow = 0, cost = 0;
    531 		while (flow < maxflow) {
    532 			vector<int> id(n, 0);
    533 			vector<int> d(n, INF);
    534 			vector<int> q(n);
    535 			vector<int> p(n);
    536 			vector<size_t> p_rib(n);
    537 			int qh = 0, qt = 0;
    538 			q[qt++] = s;
    539 			d[s] = 0;
    540 			while (qh != qt) {
    541 				int v = q[qh++];
    542 				id[v] = 2;
    543 				if (qh == n)  qh = 0;
    544 				for (size_t i = 0; i < g_mcmf[v].size(); ++i) {
    545 					rib& r = g_mcmf[v][i];
    546 					if (r.f < r.u && d[v] + r.c < d[r.b]) {
    547 						d[r.b] = d[v] + r.c;
    548 						if (id[r.b] == 0) {
    549 							q[qt++] = r.b;
    550 							if (qt == n)  qt = 0;
    551 						}
    552 						else if (id[r.b] == 2) {
    553 							if (--qh == -1)  qh = n - 1;
    554 							q[qh] = r.b;
    555 						}
    556 						id[r.b] = 1;
    557 						p[r.b] = v;
    558 						p_rib[r.b] = i;
    559 					}
    560 				}
    561 			}
    562 
    563 			if (d[t] == INF)  break;
    564 			int addflow = maxflow - flow;
    565 			for (int v = t; v != s; v = p[v]) {
    566 				int pv = p[v];  size_t pr = p_rib[v];
    567 				addflow = min(addflow, g_mcmf[pv][pr].u - g_mcmf[pv][pr].f);
    568 			}
    569 			for (int v = t; v != s; v = p[v]) {
    570 				int pv = p[v];  size_t pr = p_rib[v], r = g_mcmf[pv][pr].back;
    571 				g_mcmf[pv][pr].f += addflow;
    572 				g_mcmf[v][r].f -= addflow;
    573 				cost += g_mcmf[pv][pr].c * addflow;
    574 			}
    575 			flow += addflow;
    576 		}
    577 		return { flow, cost };
    578 	}
    579 };
    580 
    581 void solve() {
    582 	
    583 	for (int i =0 ; i < N; i++)
    584 	{
    585 		g[i] = {};
    586 		gr[i] = {};
    587 		gcmp[i] = {};
    588 	}
    589 	memset(a, 0, sizeof a);
    590 	memset(acmp, 0, sizeof acmp);
    591 	memset(used, 0, sizeof used);
    592 	memset(color, 0, sizeof color);
    593 	cur_color = 0;
    594 	order = {};
    595 	cmp = {};
    596 	
    597 	int n, m; cin >> n >> m;
    598 	for (int i = 0; i < n; i++) {
    599 		g[i].clear();
    600 		gr[i].clear();
    601 	}
    602 
    603 	for (int i = 0; i < n; i++) cin >> a[i];
    604 
    605 	for (int i = 0; i < m; i++) {
    606 		int u, v; cin >> u >> v; u--, v--;
    607 		g[u].push_back(v);
    608 		gr[v].push_back(u);
    609 	}
    610 
    611 	order.clear();
    612 	memset(used, 0, sizeof(used[0]) * n);
    613 	for (int i = 0; i < n; i++) {
    614 		if (used[i] == 0) {
    615 			used[i] = 1;
    616 			dfs1(i);
    617 		}
    618 	}
    619 
    620 	memset(used, 0, sizeof(used[0]) * n);
    621 	for (int i = 0; i < n; i++) {
    622 		int u = order[n - i - 1];
    623 		if (used[u] == 0) {
    624 			used[u] = 1;
    625 			dfs2(u);
    626 			cur_color++;
    627 		}
    628 	}
    629 
    630 	// for (int i = 0; i < n; i++) cout << color[i] << " "; cout << endl;
    631 
    632 	memset(acmp, 0, sizeof(acmp[0]) * cur_color);
    633 	for (int i = 0; i < n; i++) {
    634 		acmp[color[i]] += a[i];
    635 		for (int v : g[i]) {
    636 			if (color[i] != color[v]) {
    637 				gcmp[color[i]].push_back(color[v]);
    638 			}
    639 		}
    640 	}
    641 
    642 	for (int i = 0; i < cur_color; i++) {
    643 		auto& e = gcmp[i];
    644 		sort(e.begin(), e.end());
    645 		e.erase(unique(e.begin(), e.end()), e.end());
    646 
    647 		// cout << i << " " << acmp[i] << ": ";
    648 		// for (int v : e) cout << v << " "; cout << endl;
    649 	}
    650 
    651 	int s = 3 * cur_color, t = s + 1, so = t + 1, to = so + 1;
    652 	MCMF gg(to + 1);
    653 
    654 	for (int i = 0; i < cur_color; i++) {
    655 		auto [uin, uout, ucnt] = getInd(i);
    656 		gg.add_rib(s, ucnt, acmp[i], 0);
    657 		gg.add_rib(ucnt, uin, 1, 1);
    658 		gg.add_rib(ucnt, uout, INF, 0);
    659 
    660 		gg.add_rib(uin, uout, INF, 0);
    661 		gg.add_rib(uout, t, INF, 0);
    662 
    663 		gg.add_rib(so, uout, 1, 0);
    664 		gg.add_rib(uin, to, 1, 0);
    665 	}
    666 
    667 	gg.add_rib(t, s, INF, 0);
    668 
    669 	for (int i = 0; i < cur_color; i++) {
    670 		auto [uin, uout, ucnt] = getInd(i);
    671 		for (int v : gcmp[i]) {
    672 			auto [vin, vout, vcnt] = getInd(v);
    673 			gg.add_rib(uout, vin, INF, 0);
    674 		}
    675 	}
    676 
    677 	auto [flow, cost] = gg.get_flow(so, to);
    678 	// cout << flow << " " << cost << endl;
    679 
    680 	if (flow < cur_color) {
    681 		cout << -1 << endl;
    682 		return;
    683 	}
    684 
    685 	cout << cost << endl;
    686 }
    687 
    688 signed main() {
    689 	// freopen("input.txt", "r", stdin);
    690 	ios_base::sync_with_stdio(false);
    691 	cin.tie(0); cout.tie(0);
    692 
    693 	int q; cin >> q; while (q--)
    694 	solve();
    695 }
    696 ```
    697 
    698 ### Div1E1+E2
    699 
    700 For convenience, we will call groups that include certain cities.
    701 
    702 The key condition is that each specialization can correspond to no more than one task. Thus, cities from different groups must have "practically sorted" strength values as the group order increases.
    703 
    704 Let $[l_i, r_i]$ denote the segment that includes all the strengths of the cities in group $i$, where $r_i$ is the maximum strength of a city from this group, and $l_i$ is the minimum. If $l_i \le r_{i+2}$, it is impossible to build a contest, as there must be at least a difference of 2 tasks between the cities corresponding to $l_i$ and $r_{i+2}$, but they can differ by at most 1 task in specialization. After this, the problem reduces to considering two neighboring groups and subsequently checking the task difficulties for compliance with the linear conditions of each group.
    705 
    706 Let's consider two cases:
    707 
    708 * If $l_i \ge r_{i+1}$, it is sufficient to add a few tasks (specifically, just 2) of difficulty from the segment $[r_{i+1} + 1, l_i]$ to maintain order.
    709 * Otherwise, each city in the $i$-th group that lies in the intersection must solve a task with its specialization. In this case, no task can be in the segment $[l_i + 1, r_{i+1}]$, as the city with the highest strength in group $i+1$ will solve at least as many tasks as the weakest city in group $i$, which we cannot allow. To maintain order with the other groups, it is sufficient to add 2 tasks of difficulty $r_{i+1} + 1$ (unlike the first case, due to the fact that $l_i \le r_{i+2}$ cannot occur, we can immediately determine the appropriate task difficulty, but they can be arranged using the same algorithm as for the first case).
    710 
    711 It can be noted that when adding pairs of tasks, they need to choose an unused specification (since we are not using it in principle, but otherwise it may cause collisions).
    712 
    713 We conclude that we need to arrange tasks with a specified specification that a city from the intersection of groups can solve, meaning its difficulty must not exceed the wisdom of that city, and also arrange 2 tasks of certain difficulties to maintain order between groups. These difficulties arise from possible intersections with other groups when using $r_{i+1} + 1$ as the task difficulty and possible specification collisions of cities, which may allow a city from a weaker group to solve a task that we did not intend for it, thus violating the strictness conditions between groups.
    714 
    715 Most problems cannot arise when $m=2$, so what has been said above is already a solution (without minor adjustments) to the simple version of the problem.
    716 
    717 First, we will solve how to choose the difficulty for tasks with a specific specification. To do this, we will prohibit using the task specification corresponding to cities that form the second case (i.e., from the $i+1$-th group) with difficulty $[l_i, b_j]$, where j is the number of such a city. Also, as mentioned, we cannot have a task from the segment $[l_i + 1, r_{i+1}]$ regardless of the type. To determine the difficulty, it is sufficient to set it to the maximum possible (equal to wisdom) and then gradually decrease it until we reach an allowed difficulty.
    718 
    719 To resolve the problem from the first case, we will place barriers with 2 tasks of difficulty equal to the strength of a certain city wherever possible.
    720 
    721 If there exists an answer for the given configuration, we will guarantee to construct it this way, using no more than $3 \cdot n$ tasks. After all calculations, we need to check whether the contest we constructed meets the problem's conditions and output -1 otherwise.
    722 
    723 **Code**
    724 
    725 ```
    726 /**
    727  *    author:  tourist
    728  *    created: 01.12.2024 18:36:51
    729 **/
    730 #undef _GLIBCXX_DEBUG
    731 
    732 #include <bits/stdc++.h>
    733 
    734 using namespace std;
    735 
    736 #ifdef LOCAL
    737 #include "algo/debug.h"
    738 #else
    739 #define debug(...) 42
    740 #endif
    741 
    742 int main() {
    743   ios::sync_with_stdio(false);
    744   cin.tie(nullptr);
    745   int tt;
    746   cin >> tt;
    747   while (tt--) {
    748     int n, m;
    749     cin >> n >> m;
    750     vector<int> a(n), b(n), c(n);
    751     set<int> s;
    752     for (int i = 0; i < n; i++) {
    753       cin >> a[i] >> b[i] >> c[i];
    754       s.insert(c[i]);
    755     }
    756     vector<vector<int>> vs(m);
    757     for (int i = 0; i < m; i++) {
    758       int foo;
    759       cin >> foo;
    760       vs[i].resize(foo);
    761       for (int j = 0; j < foo; j++) {
    762         cin >> vs[i][j];
    763         --vs[i][j];
    764       }
    765     }
    766     const int inf = int(1.01e9);
    767     vector<int> min_a(m, inf);
    768     vector<int> max_a(m, -1);
    769     for (int i = 0; i < m; i++) {
    770       for (int j : vs[i]) {
    771         min_a[i] = min(min_a[i], a[j]);
    772         max_a[i] = max(max_a[i], a[j]);
    773       }
    774     }
    775     auto Unify = [&](vector<pair<int, int>>& bad) {
    776       sort(bad.begin(), bad.end());
    777       int ptr = 0;
    778       for (int i = 1; i < int(bad.size()); i++) {
    779         if (bad[i].first <= bad[ptr].second + 1) {
    780           bad[ptr].second = max(bad[ptr].second, bad[i].second);
    781         } else {
    782           bad[++ptr] = bad[i];
    783         }
    784       }
    785       bad.resize(ptr + 1);
    786     };
    787     vector<pair<int, int>> bad;
    788     for (int id = 0; id < m - 1; id++) {
    789       if (min_a[id] < max_a[id + 1]) {
    790         bad.emplace_back(min_a[id] + 1, max_a[id + 1]);
    791       }
    792     }
    793     Unify(bad);
    794     vector<int> ctr(n);
    795     for (int i = 0; i < m; i++) {
    796       for (int x : vs[i]) {
    797         ctr[x] = i;
    798       }
    799     }
    800     vector<pair<int, int>> tasks;
    801     int unused = 0;
    802     vector<int> order(n);
    803     iota(order.begin(), order.end(), 0);
    804     sort(order.begin(), order.end(), [&](int i, int j) {
    805       return a[i] > a[j];
    806     });
    807     multiset<int> before, after;
    808     for (int i = 0; i < n; i++) {
    809       after.insert(ctr[i]);
    810     }
    811     {
    812       int beg = 0;
    813       while (beg < n) {
    814         int end = beg;
    815         while (end + 1 < n && a[order[end + 1]] == a[order[end]]) {
    816           end += 1;
    817         }
    818         for (int i = beg; i <= end; i++) {
    819           before.insert(ctr[order[i]]);
    820           after.erase(after.find(ctr[order[i]]));
    821         }
    822         if (!before.empty() && !after.empty() && *prev(before.end()) <= *after.begin()) {
    823           for (int i = 0; i < 2; i++) {
    824             do {
    825               unused += 1;
    826             } while (s.find(unused) != s.end());
    827             tasks.emplace_back(a[order[end]], unused);
    828           }
    829         }
    830         beg = end + 1;
    831       }
    832     }
    833     map<int, int> add;
    834     for (int id = 0; id < m - 1; id++) {
    835       for (int i : vs[id]) {
    836         if (a[i] <= max_a[id + 1]) {
    837           if (add.find(c[i]) == add.end()) {
    838             add[c[i]] = b[i];
    839           } else {
    840             add[c[i]] = min(add[c[i]], b[i]);
    841           }
    842         }
    843       }
    844     }
    845     map<int, vector<pair<int, int>>> kill;
    846     for (int id = 1; id < m; id++) {
    847       for (int i : vs[id]) {
    848         if (a[i] >= min_a[id - 1]) {
    849           kill[c[i]].push_back({min_a[id - 1] + 1, b[i]});
    850         }
    851       }
    852     }
    853     for (auto& [type, x] : add) {
    854       auto& k = kill[type];
    855       Unify(k);
    856       int dif = x;
    857       while (true) {
    858         bool changed = false;
    859         {
    860           auto it = lower_bound(bad.begin(), bad.end(), make_pair(dif + 1, -1));
    861           if (it != bad.begin()) {
    862             it = prev(it);
    863             if (it->second >= dif) {
    864               dif = it->first - 1;
    865               changed = true;
    866             }
    867           }
    868         }
    869         {
    870           auto it = lower_bound(k.begin(), k.end(), make_pair(dif + 1, -1));
    871           if (it != k.begin()) {
    872             it = prev(it);
    873             if (it->second >= dif) {
    874               dif = it->first - 1;
    875               changed = true;
    876             }
    877           }
    878         }
    879         if (!changed) {
    880           break;
    881         }
    882       }
    883       tasks.emplace_back(dif, type);
    884     }
    885     debug(tasks);
    886     vector<int> all;
    887     map<int, int> spec;
    888     for (auto& [x, y] : tasks) {
    889       all.push_back(x);
    890       assert(spec.find(y) == spec.end());
    891       spec[y] = x;
    892     }
    893     sort(all.begin(), all.end());
    894     vector<int> solved(n);
    895     for (int i = 0; i < n; i++) {
    896       solved[i] = int(upper_bound(all.begin(), all.end(), a[i]) - all.begin());
    897       if (spec.find(c[i]) != spec.end() && spec[c[i]] > a[i] && spec[c[i]] <= b[i]) {
    898         solved[i] += 1;
    899       }
    900     }
    901     vector<int> min_solved(m, inf);
    902     vector<int> max_solved(m, -1);
    903     for (int i = 0; i < m; i++) {
    904       for (int j : vs[i]) {
    905         min_solved[i] = min(min_solved[i], solved[j]);
    906         max_solved[i] = max(max_solved[i], solved[j]);
    907       }
    908     }
    909     bool win = true;
    910     for (int id = 0; id < m - 1; id++) {
    911       if (min_solved[id] <= max_solved[id + 1]) {
    912         win = false;
    913         break;
    914       }
    915     }
    916     if (win) {
    917       cout << tasks.size() << '\n';
    918       for (auto& [x, y] : tasks) {
    919         cout << x << " " << y << '\n';
    920       }
    921     } else {
    922       cout << -1 << '\n';
    923     }
    924   }
    925   return 0;
    926 }
    927 ```
    928 
    929 ### Div1F1
    930 
    931 It can be noted that if the string contains the correct number of symbols 'Y', 'D', 'X' and does not have two consecutive identical symbols, then it can be obtained using the given operations.
    932 
    933 To demonstrate this, we will provide an algorithm that constructs a sequence of operations leading to the desired string. We will start from the end (from the string we want to obtain to the empty string) gradually removing symbols.
    934 
    935 Let's look at the current string. Without loss of generality, let its first symbol be 'Y'. Then the string must contain the substring 'DX' and/or the substring 'XD'. This is true because for the absence of 'DX' and 'XD', it is necessary that between any pair of symbols not equal to 'Y', there is at least one symbol 'Y'. This can be achieved at best by placing 'Y' between every symbol. Thus, the number of symbols not equal to 'Y' with $n-1$ 'Y' can be at most $n$. But $3n-1 \gt n$ when $n \gt 0$.
    936 
    937 Thus, the string has the form 'Y...ADXB...'.
    938 
    939 If A $\neq$ B, we can remove the symbols 'Y', 'D', 'X' and nothing will break.
    940 
    941 If A = B, then A = B = 'Y', since A != 'D' and A != 'X'.
    942 
    943 Then the string has the form 'Y...YDXY...', and we can remove the substring 'YDX' and still have an unbroken string 'Y...Y...'.
    944 
    945 ### Div1F2
    946 
    947 We will isolate substrings from the string that consist entirely of '?'. For each, we will denote its length as $len_i$ and the two neighboring symbols (standing to the left and right) as $l_i$, $r_i$. (If the right and/or left symbol is absent, we will take it as '#', a symbol that does not match any of our interests).
    948 
    949 We will write trivial constraints on the number of available symbols of each type on the segment. It is obvious that the number of symbols of each type cannot exceed $\frac{len_i+1}{2}$: we will place one symbol for every other symbol. But if, for example, we had a symbol 'Y' on the left, the number of positions where we can place 'Y' decreases by $1$. In total, we can place no more than $\frac{len+1-(l_i=b)-(r_i=b)}{2}$ symbols of type b. We will write such constraints for each type of symbol and denote them as $Y, D, X$ respectively.
    950 
    951 It turns out that we can arrange $y$ symbols 'Y', $d$ symbols 'D' and $x$ symbols 'X' if and only if $y+d+x=len_i$ and $0\leq y \leq Y, 0 \leq d \leq D, 0 \leq x \leq X$. This can be proven by induction or checked with stress tests on small values. From this, we conclude that in order to be able to arrange $x, d, y$ symbols of each type, the inequalities above must hold.
    952 
    953 From the equality $y+d+x=len_i$, we express $d=len_i - (x+y)$.
    954 
    955 This results in three constraints: $0\leq x \leq X, 0 \leq y \leq Y, 0 \leq len_i - (x+y) \leq D$. The first two form a rectangle, and the third cuts off two corners at a $45$ degree angle. This is a convex polygon.
    956 
    957 Thus, if for each segment of '?' we write a polygon and sum them using Minkowski sum, we will obtain constraints for the entire string.
    958 
    959 Since in the Minkowski sum (after merging collinear consecutive segments) there will be at most 6 points, we can write a greedy algorithm that sequentially tries to match the required symbol to each '?'.
    960 
    961 The final asymptotic complexity is $O(n)$ with some constant.
    962 
    963 **Code**
    964 
    965 ```
    966 #pragma GCC optimize("Ofast")
    967 #include <iostream>
    968 #include <cmath>
    969 #include <cstdint>
    970 #include <vector>
    971 #include <string>
    972 #include <iomanip>
    973 #include <set>
    974 #include <map>
    975 #include <unordered_map>
    976 #include <unordered_set>
    977 #include <algorithm>
    978 #include <functional>
    979 #include <queue>
    980 #include <fstream>
    981 #include <random>
    982 //#include <numbers>
    983 #include <optional>
    984 #include <deque>
    985 #include <sstream>
    986 #include <list>
    987 #include <chrono>
    988 #include <thread>
    989 #include <cassert>
    990  
    991 using namespace std;
    992 using i64 = int64_t;
    993 using ui64 = uint64_t;
    994 #define YN(b) if (b) cout << "YES\n"; else cout << "NO\n";
    995  
    996 template<typename T>
    997 istream& operator>>(istream& is, vector<T>& v) { for (auto &e: v) { is >> e; } return is; }
    998  
    999 template<typename T>
   1000 ostream& operator<<(ostream& os, vector<T>& v) { for (auto &e: v) { os << e << " "; } return os; }
   1001  
   1002 template<typename T, typename V>
   1003 istream& operator>>(istream& is, pair<T, V>& v) { return is >> v.first >> v.second; }
   1004  
   1005 template<typename T, typename V>
   1006 ostream& operator<<(ostream& os, pair<T, V>& v) { return os << v.first << " " << v.second; }
   1007  
   1008 const int64_t md = 1e9+7;
   1009 
   1010 int dx[4] = {-1, 0, 1, 0};
   1011  
   1012 inline int64_t sqr(int64_t x) {
   1013     return x * x;
   1014 }
   1015  
   1016 inline int popcount(int64_t x) {
   1017     int c = 0;
   1018     while (x) c += x & 1, x >>= 1;
   1019     return c;
   1020 }
   1021  
   1022 pair<int64_t, int64_t> inter(pair<int64_t, int64_t> a, pair<int64_t, int64_t> b) {
   1023     return {max(a.first, b.first), min(a.second, b.second)};
   1024 }
   1025 
   1026 struct pt {
   1027     using T = int;
   1028     using V = int64_t;
   1029     T x = 0, y = 0;
   1030     pt() = default;
   1031     pt(T x, T y) : x(x), y(y) {}
   1032     inline pt& operator-=(const pt& other) {
   1033         x -= other.x;
   1034         y -= other.y;
   1035         return *this;
   1036     }
   1037     inline pt operator-(const pt& other) const {
   1038         pt copy(*this);
   1039         copy -= other;
   1040         return copy;
   1041     }
   1042     inline pt& operator+=(const pt& other) {
   1043         x += other.x;
   1044         y += other.y;
   1045         return *this;
   1046     }
   1047     inline pt operator+(const pt& other) const {
   1048         pt copy(*this);
   1049         copy += other;
   1050         return copy;
   1051     }
   1052     V operator^(const pt& other) const {
   1053         return (V)x * other.y - (V)y * other.x;
   1054     }
   1055     V operator*(const pt& other) const {
   1056         return (V)x * other.x + (V)y * other.y;
   1057     }
   1058     void print() const {
   1059         cerr << x << " " << y << "\n";
   1060     }
   1061     bool operator==(const pt&) const = default;
   1062 };
   1063 
   1064 inline bool in_triangle(const pt& a, const pt& b, const pt& c, const pt& point) {
   1065     int64_t s1 = abs((b - a) ^ (c - a));
   1066     int64_t s2 = abs((a - point) ^ (b - point)) + abs((b - point) ^ (c - point)) + abs((c - point) ^ (a - point));
   1067     return s1 == s2;
   1068 }
   1069 
   1070 struct mi {
   1071     size_t i = 0;
   1072     size_t ni = 1;
   1073     const size_t m;
   1074     mi(size_t m) : m(m) {}
   1075     void add() {
   1076         ++i;
   1077         if (++ni == m) ni = 0;
   1078     }
   1079 };
   1080 int64_t orientation(pt a, pt b, pt c) {
   1081     return -((int64_t)a.x * (b.y - c.y) + (int64_t)b.x * (c.y - a.y) + (int64_t)c.x * (a.y - b.y));
   1082 }
   1083 inline bool comp(pt a, pt b) {
   1084     auto cp = a ^ b;
   1085     if (!cp) {
   1086         return a * a < b * b;
   1087     }
   1088     return (pt::V)a.x * b.x < 0 ? (a.x > b.x) : cp > 0;
   1089 }
   1090 
   1091 struct NMP {
   1092     array<pt, 13> pts;
   1093     int len = 0;
   1094     template<typename... Args>
   1095     void emplace_back(Args&& ...p) {
   1096         new (&pts[len++]) pt(p...);
   1097     }
   1098     void push_back(const pt& x) {
   1099         pts[len++] = x;
   1100     }
   1101     pt& operator[](size_t x) {
   1102         return pts[x];
   1103     }
   1104     size_t size() const {
   1105         return len;
   1106     }
   1107 
   1108     const pt& operator[](size_t x) const {
   1109         return pts[x];
   1110     }
   1111     pt* begin() {
   1112         return &pts[0];
   1113     }
   1114     pt* end() {
   1115         return &pts[len];
   1116     }
   1117     void resize(size_t x) {
   1118         len = x;
   1119     }
   1120 };
   1121 
   1122 struct poly {
   1123     using P = pt;
   1124     NMP pts;
   1125     void add(const P& p) {
   1126         pts.push_back(p);
   1127     }
   1128     
   1129     template<typename... Args>
   1130     void emplace(Args&& ...p) {
   1131         pts.emplace_back(p...);
   1132     }
   1133 
   1134     void sort() {
   1135         size_t min_id = 0;
   1136         for (size_t i = 1; i < pts.size(); ++i) {
   1137             if (pts[i].y < pts[min_id].y || (pts[i].y == pts[min_id].y && pts[i].x < pts[min_id].x)) {
   1138                 min_id = i;
   1139             }
   1140         }
   1141         std::rotate(pts.begin(), pts.begin() + min_id, pts.end());
   1142         auto p0 = pts[0];
   1143         std::sort(pts.begin(), pts.end(), [&](const P& a, const P& b) {
   1144             auto o = orientation(p0, a, b);
   1145             if (!o)
   1146                 return (int64_t)(p0.x-a.x)*(p0.x-a.x) + (int64_t)(p0.y-a.y)*(p0.y-a.y)
   1147                     < (int64_t)(p0.x-b.x)*(p0.x-b.x) + (int64_t)(p0.y-b.y)*(p0.y-b.y);
   1148             return o < 0;
   1149         });
   1150     }
   1151 
   1152     void no_coll() {
   1153         if (pts.size() < 3) {
   1154             return;
   1155         }
   1156         size_t ptr = 1;
   1157         for (size_t j = 2; j < pts.size(); ++j) {
   1158             if ((pts[ptr] - pts[ptr - 1]) ^ (pts[j] - pts[ptr])) {
   1159                 pts[++ptr] = pts[j];
   1160                 continue;
   1161             }
   1162             pts[ptr] = pts[j];
   1163         }
   1164         pts.resize(ptr + 1);
   1165     }
   1166 
   1167     poly operator+(const poly& other) const {
   1168         if (pts.size() == 1) {
   1169             poly c(other);
   1170             for (auto& p: c.pts) p += pts[0];
   1171             return c;
   1172         }
   1173         if (other.pts.size() < pts.size()) {
   1174             return other + *this;
   1175         }
   1176         // size at least 2s
   1177         poly res;
   1178         mi i(pts.size()), j(other.pts.size());
   1179 
   1180         while (i.i < pts.size() && j.i < other.pts.size()) {
   1181             res.emplace(pts[i.i] + other.pts[j.i]);
   1182             auto a = (pts[i.ni] - pts[i.i]);
   1183             auto b = (other.pts[j.ni] - other.pts[j.i]);
   1184             auto cp = a ^ b;
   1185             if (cp < 0) {
   1186                 j.add();
   1187             } else if (cp > 0) {
   1188                 i.add();
   1189             } else if ((P::V)a.y * b.y >= 0) {
   1190                 i.add();
   1191                 j.add();
   1192             } else if (a.y > b.y) {
   1193                 i.add();
   1194             } else {
   1195                 j.add();
   1196             }
   1197         }
   1198         while (i.i < pts.size()) {
   1199             res.emplace(pts[i.i] + other.pts[0]);
   1200             i.add();
   1201         }
   1202         
   1203         while (j.i < other.pts.size()) {
   1204             res.emplace(pts[0] + other.pts[j.i]);
   1205             j.add();
   1206         }
   1207         
   1208         res.no_coll();
   1209         return res;
   1210     }
   1211 
   1212     void print() {
   1213         for (auto &e: pts) {
   1214             cout << "(" << e.x << " " << e.y << ") ";
   1215         }
   1216         cout << "\n";
   1217     }
   1218 
   1219     bool in(const pt& p) const {
   1220         if (pts.size() == 1) {
   1221             return pts[0] == p;
   1222         }
   1223         if (pts.size() == 2) {
   1224             return ((pts[0] - p) ^ (pts[1] - p)) == 0 
   1225                 && min(pts[0].x, pts[1].x) <= p.x && p.x <= max(pts[0].x, pts[1].x)
   1226                 && min(pts[0].y, pts[1].y) <= p.y && p.y <= max(pts[0].y, pts[1].y);
   1227         }
   1228         for (int i = 2; i < pts.size(); ++i) {
   1229             if (in_triangle(pts[i], pts[i - 1], pts[0], p)) {
   1230                 return true;
   1231             }
   1232         }
   1233         return false;
   1234     }
   1235 };
   1236 
   1237 struct co {
   1238     array<int, 3> cst {};
   1239     poly p;
   1240     co() {
   1241         p.emplace(0, 0);
   1242     }
   1243 
   1244     co(int l, int a, int b) {
   1245         cst = {
   1246             max(0, 1 + l - (a == 0) - (b == 0)) / 2,
   1247             max(0, 1 + l - (a == 1) - (b == 1)) / 2,
   1248             max(0, 1 + l - (a == 2) - (b == 2)) / 2
   1249         };
   1250         p.emplace(min(cst[0], l - cst[2]), max(0, l - cst[0] - cst[2]));
   1251         p.emplace(min(cst[0], l), max(0, l - cst[0] - cst[2]));
   1252         p.emplace(cst[0], min(cst[1], l - cst[0]));
   1253         p.emplace(min(l - cst[1], cst[0]), cst[1]);
   1254         p.emplace(max(0, l - cst[1] - cst[2]), min(l, cst[1]));
   1255         p.emplace(max(0, l - cst[1] - cst[2]), min(cst[1], l - cst[2]));
   1256         p.sort();
   1257         p.no_coll();
   1258     }
   1259 
   1260     co operator+(const co& rhs) {
   1261         co res;
   1262         res.p = p + rhs.p;
   1263         for (int j = 0; j < 3; ++j) res.cst[j] = cst[j] + rhs.cst[j];
   1264         return res;
   1265     }
   1266 
   1267     bool ok(int x, int y, int z) {
   1268         return x <= cst[0] && y <= cst[1] && z <= cst[2]; 
   1269     }
   1270 
   1271     bool in(int x, int y, int z) {
   1272         return ok(x, y, z) && p.in(pt(x, y));
   1273     }
   1274 };
   1275 
   1276 char idx[128]{};
   1277 string ydx = "YDX";
   1278 
   1279 struct fenwick {
   1280     fenwick(int x) : t(x), n(x) {}
   1281     vector<int> t;
   1282     int n;
   1283     int sum (int r) {
   1284         int result = 0;
   1285         for (; r >= 0; r = (r & (r+1)) - 1)
   1286             result += t[r];
   1287         return result;
   1288     }
   1289 
   1290     void inc (int i, int delta) {
   1291         for (; i < n; i = (i | (i+1)))
   1292             t[i] += delta;
   1293     }
   1294 };
   1295 
   1296 using S = std::list<pair<short, int>>;
   1297 
   1298 struct cmp {
   1299     bool operator()(S::iterator a, S::iterator b) const {
   1300         return a->second < b->second;
   1301     };
   1302 };
   1303 
   1304 auto encode1(auto a, auto b) {
   1305     return a * 256 + b;
   1306 };
   1307 
   1308 auto encode(auto it) {
   1309     auto prev = it++;
   1310     return encode1(prev->first, it->first);
   1311 };
   1312 
   1313 auto erase_char(auto& curr_pos, S& str, fenwick& alive, auto& pos, auto it) {
   1314     auto curr = it;
   1315     auto prev = --it;
   1316     it = curr;
   1317     auto next = ++it;
   1318     if (next != str.end()) {
   1319         if (!pos[encode(curr)].count(curr)) {
   1320             exit(-1);
   1321         }
   1322         pos[encode(curr)].erase(curr);
   1323     }
   1324     if (prev != str.end()) {
   1325         if (!pos[encode(prev)].count(prev)) {
   1326             exit(-1);
   1327         }
   1328         pos[encode(prev)].erase(prev);
   1329     }
   1330     curr_pos.emplace_back(curr->first, alive.sum(curr->second) - 1);
   1331     alive.inc(curr->second, -1);
   1332     str.erase(curr);
   1333     if (next != str.end() && prev != str.end()) {
   1334         auto p = prev;
   1335         ++p;
   1336         if (p != next) {
   1337             exit(-1);
   1338         }
   1339         pos[encode(prev)].emplace(prev);
   1340     }
   1341 };
   1342 
   1343 bool is_ok(S::iterator x, S::iterator end) {
   1344     auto curr = x;
   1345     auto prev = --x;
   1346     auto next = ++curr;
   1347     if (prev != end && next != end) {
   1348         return prev->first != next->first;
   1349     }
   1350     return true;
   1351 }
   1352 
   1353 auto got(auto& curr_pos, auto& str, auto& alive, auto& pos, vector<S::iterator> t) {
   1354     for (auto &e: t) {
   1355         erase_char(curr_pos, str, alive, pos, e);
   1356     }
   1357 };
   1358 
   1359 auto relax(auto& curr_pos, auto& str, auto& alive, auto& pos, short sym, short co) {
   1360     auto &v = pos[co];
   1361     auto it = *v.begin();
   1362     auto A = it;
   1363     auto prev = --it;
   1364     it = A;
   1365     auto B = ++it;
   1366     auto next = ++it;
   1367     if (prev != str.end() && next != str.end() && prev->first == next->first) {
   1368         if (prev->first != sym) {
   1369             exit(-1);
   1370         }
   1371         got(curr_pos, str, alive, pos, {prev, A, B});
   1372         return false;
   1373     }
   1374     
   1375     got(curr_pos, str, alive, pos, {A, B});
   1376     return true;
   1377 };
   1378 
   1379 vector<array<pair<char, int>, 3>> solve_str(const string& s) {
   1380     S str;
   1381     fenwick alive(s.size());
   1382 
   1383     for (int i = 0; i < s.size(); ++i) {
   1384         str.emplace_back(s[i], i);
   1385         alive.inc(i, 1);
   1386     }
   1387 
   1388     auto it = str.begin();
   1389 
   1390     map<int, set<decltype(it), cmp>> pos;
   1391     while (it != str.end()) {
   1392         auto prev = it++;
   1393         if (it == str.end()) break;
   1394         pos[encode(prev)].emplace(prev);   
   1395     }
   1396     vector<pair<char, int>> curr_pos;
   1397     vector<decltype(it)> curr_t;
   1398     vector<array<pair<char, int>, 3>> res;
   1399     while (str.size()) {
   1400         it = str.begin();
   1401         auto curr = it++;
   1402         if (it == str.end()) {
   1403             exit(-1);
   1404         }
   1405         short code = curr->first;
   1406         erase_char(curr_pos, str, alive, pos, curr);
   1407 
   1408         array<int, 2> candidates;
   1409         if (code == 'Y') {
   1410             candidates[0] = encode1('D', 'X');
   1411             candidates[1] = encode1('X', 'D');
   1412         } else if (code == 'X') {
   1413             candidates[0] = encode1('D', 'Y');
   1414             candidates[1] = encode1('Y', 'D');
   1415         } else {
   1416             candidates[0] = encode1('Y', 'X');
   1417             candidates[1] = encode1('X', 'Y');
   1418         }
   1419         bool ok = 0;
   1420         while (!ok) {
   1421             for (auto &c: candidates) {
   1422                 if (!pos[c].size()) {
   1423                     continue;
   1424                 }
   1425                 if (relax(curr_pos, str, alive, pos, code, c)) {
   1426                     ok = 1;
   1427                     res.emplace_back();
   1428                     res.back()[0] = curr_pos[2];
   1429                     res.back()[1] = curr_pos[1];
   1430                     res.back()[2] = curr_pos[0];
   1431                     curr_pos.clear();
   1432                     break;
   1433                 }
   1434                 // A...ABCA, ABC removed
   1435                 res.emplace_back();
   1436                 for (int j = 0; j < 3; ++j) {
   1437                     res.back()[j] = curr_pos.back(); // removed
   1438                     res.back()[j].second += 1;
   1439                     curr_pos.pop_back();
   1440                 }
   1441                 break;
   1442             }
   1443         }
   1444     }
   1445     reverse(res.begin(), res.end());
   1446     return res;
   1447 }
   1448 
   1449 bool check(const string& s) {
   1450     array<int, 3> cnt{};
   1451     char prev = -1;
   1452     for (auto &e: s) {
   1453         if (e == '?') {
   1454             return false;
   1455         }
   1456         if (e != 'Y' && e != 'D' && e != 'X') {
   1457             return false;
   1458         }
   1459         if (e == prev) return false;
   1460         prev = e;
   1461         ++cnt[idx[e]];
   1462     }
   1463     return cnt[0] == s.size() / 3 && cnt[1] == s.size() / 3 && cnt[2] == s.size() / 3;
   1464 }
   1465 
   1466 optional<string> solve_fast1(string v) {
   1467     auto sv = v;
   1468     int N = v.size() / 3;
   1469     array<int, 3> rem{N, N, N};
   1470     for (auto &e: v) {
   1471         if (e == '?') continue;
   1472         --rem[idx[e]];
   1473     }
   1474     if (rem[0] < 0 || rem[1] < 0 || rem[2] < 0) return {};
   1475     vector<co> mink;
   1476     vector<pair<int, int>> segs;
   1477     for (int i = 0; i < v.size(); ++i) {
   1478         if (v[i] != '?') continue;
   1479         int j = i + 1;
   1480         while (j < v.size() && v[j] == '?') ++j;
   1481         mink.emplace_back(j - i, i > 0 ? idx[v[i - 1]] : 3, j < v.size() ? idx[v[j]] : 3);
   1482         segs.emplace_back(i, j - 1);
   1483         i = j - 1;
   1484     }
   1485     reverse(mink.begin(), mink.end());
   1486     reverse(segs.begin(), segs.end());
   1487     for (int i = 1; i < mink.size(); ++i) {
   1488         mink[i] = mink[i - 1] + mink[i];
   1489     }
   1490     if (mink.size()) {
   1491         mink.pop_back();
   1492     }
   1493     while (segs.size()) {
   1494         auto seg = segs.back();
   1495         segs.pop_back();
   1496         auto mk = mink.size() ? mink.back() : co();
   1497         if (mink.size()) {
   1498             mink.pop_back();
   1499         }
   1500         char prev = idx[seg.first ? v[seg.first - 1] : '?'];
   1501         char next_r = idx[seg.second + 1 < v.size() ? v[seg.second + 1] : '?'];
   1502         while (seg.first <= seg.second) {
   1503             char next = seg.first == seg.second ? next_r : -1;
   1504             bool found = 0;
   1505             for (int j = 0; j < 3; ++j) {
   1506                 if (prev == j || next == j || !rem[j]) {
   1507                     continue;
   1508                 }
   1509                 --rem[j];
   1510                 auto cs = co(seg.second - seg.first, j, seg.second + 1 < v.size() ? idx[v[seg.second + 1]] : 3);
   1511                 auto vv = mk + cs;
   1512                 if (!vv.in(rem[0], rem[1], rem[2])) {
   1513                     ++rem[j];
   1514                     continue;
   1515                 }
   1516                 v[seg.first++] = ydx[j];
   1517                 prev = j;
   1518                 found = 1;
   1519                 break;
   1520             }
   1521             if (!found) {
   1522                 return {};
   1523             }
   1524         }
   1525     }
   1526     return v;
   1527 }
   1528 
   1529 optional<pair<vector<array<pair<char, int>, 3>>, string>> solve(string s) {
   1530     auto ww = solve_fast1(s);
   1531     if (!ww || !check(*ww)) {
   1532         return {};
   1533     }
   1534     return pair{solve_str(*ww), *ww};
   1535 }
   1536 
   1537 signed main() {
   1538     ios::sync_with_stdio(0);
   1539     cin.tie(0);
   1540     cout.tie(0);
   1541     idx['Y'] = 0;
   1542     idx['D'] = 1;
   1543     idx['X'] = 2;
   1544     idx['?'] = 99;
   1545     int t;
   1546     cin >> t;
   1547     while (t--) {
   1548         string s;
   1549         cin >> s;
   1550         auto r = solve(s);
   1551         if (r) {
   1552             cout << "YES\n" << r->second << "\n";
   1553             for (auto &x: r->first) {
   1554                 for (auto &e: x) {
   1555                     cout << e.first << " " << e.second << " ";
   1556                 }
   1557                 cout << "\n";
   1558             }
   1559         } else {
   1560             cout << "NO\n";
   1561         }
   1562     }
   1563 }
   1564 ```