codeforces-scrape

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

1819.md (21598B)


      1 Source: https://codeforces.com/blog/entry/115133
      2 
      3 [1820A - Yura's New Name](/contest/1820/problem/A "Codeforces Round 866 (Div. 2)")
      4 
      5 Author: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx")
      6 
      7 Preparation: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx")
      8 
      9 **Editorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21     int t;
     22     cin >> t;
     23     while (t--) {
     24         string s;
     25         cin >> s;
     26         if (s == "^") {
     27             cout << 1 << '\n';
     28             continue;
     29         }
     30         int ans = 0;
     31         if (s[0] == '_')
     32             ++ans;
     33         if (s.back() == '_')
     34             ++ans;
     35         for (int i = 0; i < (int) s.size() - 1; ++i) {
     36             if (s[i] == '_' && s[i + 1] == '_')
     37                 ++ans;
     38         }
     39         cout << ans << '\n';
     40     }
     41 }
     42 ```
     43 
     44 [1820B - JoJo's Incredible Adventures](/contest/1820/problem/B "Codeforces Round 866 (Div. 2)")
     45 
     46 Author: [golikovnik](/profile/golikovnik "Grandmaster golikovnik")
     47 
     48 Preparation: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq")
     49 
     50 **Editorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 using ll = long long;
     61 
     62 int main() {
     63     ios::sync_with_stdio(0); cin.tie(0);
     64 
     65     int t = 1;
     66     cin >> t;
     67     while (t--) {
     68         string s; cin >> s; s += s;
     69         int k = 0, z = 0;
     70         for (char c : s) {
     71             z = c == '1' ? z+1 : 0;
     72             k = max(k, z);
     73         }
     74         const int n = s.size() / 2;
     75 
     76         if (k > n) {
     77             cout << (ll)n*n << '\n';
     78         } else {
     79             const ll side_a = (k+1)/2;
     80             const ll side_b = (k+2)/2;
     81             cout << side_a * side_b << '\n';
     82         }
     83     }
     84 }
     85 ```
     86 
     87 [1819A - Constructive Problem](/contest/1819/problem/A "Codeforces Round 866 (Div. 1)")
     88 
     89 Author: [TeaTime](/profile/TeaTime "Master TeaTime")
     90 
     91 Preparation: [golikovnik](/profile/golikovnik "Grandmaster golikovnik")
     92 
     93 **Editorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 //  Nikita Golikov, 2023
    101 
    102 #include <bits/stdc++.h>
    103 
    104 using namespace std;
    105 
    106 using uint = unsigned int;
    107 using ll = long long;
    108 using ull = unsigned long long;
    109 
    110 #ifdef GOLIKOV
    111     #define debug(x) cerr << (#x) << ":\t" << (x) << endl
    112 #else
    113     #define debug(x) 238;
    114 #endif
    115 
    116 template <class A, class B>
    117 bool smin(A& x, B&& y) {
    118   if (y < x) {
    119     x = y;
    120     return true;
    121   }
    122   return false;
    123 }
    124 
    125 template <class A, class B>
    126 bool smax(A& x, B&& y) {
    127   if (x < y) {
    128     x = y;
    129     return true;
    130   }
    131   return false;
    132 }
    133 
    134 template <class T>
    135 int calcMex(vector<T> v) {
    136   sort(v.begin(), v.end());
    137   v.erase(unique(v.begin(), v.end()), v.end());
    138   int n = int(v.size());
    139   for (int i = 0; i < n; ++i) if (v[i] != i) return i;
    140   return n;
    141 }
    142 
    143 bool solveTest() {
    144   int n; cin >> n;
    145   vector<int> a(n);
    146   map<int, int> leftOcc, rightOcc;
    147   for (int i = 0; i < n; ++i) {
    148     cin >> a[i];
    149     rightOcc[a[i]] = i;
    150     if (!leftOcc.count(a[i])) leftOcc[a[i]] = i;
    151   }
    152   int mex = calcMex(a);
    153   if (leftOcc.count(mex + 1)) {
    154     int L = leftOcc[mex + 1], R = rightOcc[mex + 1];
    155     for (int i = L; i <= R; ++i) {
    156       a[i] = mex;
    157     }
    158     int mx = calcMex(a);
    159     assert(mx <= mex + 1);
    160     return mx == mex + 1;
    161   }
    162   for (int i = 0; i < n; ++i) {
    163     assert(a[i] != mex);
    164     if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {
    165       return true;
    166     }
    167   }
    168   return false;
    169 }
    170 
    171 int main() {
    172 #ifdef GOLIKOV
    173   assert(freopen("in", "rt", stdin));
    174   auto _clock_start = chrono::high_resolution_clock::now();
    175 #endif
    176   ios::sync_with_stdio(false);
    177   cin.tie(nullptr);
    178 
    179   int t; cin >> t;
    180   while (t--) {
    181     cout << (solveTest() ? "Yes" : "No") << '\n';
    182   }
    183 
    184 #ifdef GOLIKOV
    185   cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    186       chrono::high_resolution_clock::now()
    187           - _clock_start).count() << "ms." << endl;
    188 #endif
    189   return 0;
    190 }
    191 ```
    192 
    193 [1819B - The Butcher](/contest/1819/problem/B "Codeforces Round 866 (Div. 1)")
    194 
    195 Author: [Tikhon228](/profile/Tikhon228 "Master Tikhon228")
    196 
    197 Preparation: [Kon567889](/profile/Kon567889 "Master Kon567889")
    198 
    199 **Editorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution**
    204 
    205 ```
    206 //#pragma GCC target("trapv")
    207 #include <iostream>
    208 #include <vector>
    209 #include <algorithm>
    210 #include <set>
    211 #include <string>
    212 #include <cmath>
    213 #include <map>
    214 #include <iostream>
    215 #include <list>
    216 #include <stack>
    217 #include <cassert>
    218 using namespace std;
    219 
    220 typedef long long ll;
    221 typedef long double ld;
    222 
    223 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    224 
    225 const ll INF = 1e9 * 1e9 + 100, SZ = 1100;
    226 
    227 ll n;
    228 vector<pair<ll, ll>> vec;
    229 map<ll, pair<ll, ll>> blocks;
    230 
    231 pair<ll, ll> solve() {
    232 	set<pair<ll, ll>> widest, longest;
    233 
    234 	for (size_t i = 0; i < vec.size(); i++) {
    235 		widest.insert({ vec[i].first, i });
    236 		longest.insert({ vec[i].second, i });
    237 
    238 		blocks[i] = vec[i];
    239 	}
    240 
    241 	pair<ll, ll> ans = { -1, -1 };
    242 	bool mode = 0;
    243 	ll prevw = INF, prevh = INF, prv = -1;
    244 	bool cringe = 0;
    245 	while (widest.size() != 0) {
    246 		if (mode == 0) {
    247 			ll cur = (*widest.rbegin()).first, sum = 0;
    248 			if (ans.second == -1) ans.second = cur;
    249 			prv = blocks[(*widest.rbegin()).second].second;
    250 
    251 			while (widest.size() > 0 && (*widest.rbegin()).first == cur) {
    252 				auto it = (--widest.end());
    253 				longest.erase({blocks[it->second].second, it->second });
    254 				sum += blocks[it->second].second;
    255 				widest.erase(it);
    256 			}
    257 
    258 			if (!cringe) ans.first = sum;
    259 			prv = sum;
    260 			if (prevw == INF) {
    261 				prevh = cur;
    262 			} else {
    263 				prevw -= sum;
    264 				if (prevh != cur) return { -1, -1 };
    265 			}
    266 		} else {
    267 			ll cur = (*longest.rbegin()).first, sum = 0;
    268 			if (!cringe) {
    269 				ans.first = cur + prv;
    270 				cringe = 1;
    271 			}
    272 
    273 			while (longest.size() > 0 && (*longest.rbegin()).first == cur) {
    274 				auto it = (--longest.end());
    275 				widest.erase({ blocks[it->second].first, it->second });
    276 				sum += blocks[it->second].first;
    277 				longest.erase(it);
    278 			}
    279 
    280 			if (prevw == INF) {
    281 				prevw = cur;
    282 				prevh -= sum;
    283 				if (prevw != cur) return { -1, -1 };
    284 			} else {
    285 				prevh -= sum;
    286 				if (prevw != cur) return { -1, -1 };
    287 			}
    288 		}
    289 
    290 		mode ^= 1;
    291 	}
    292 
    293 	if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) {
    294 		return ans;
    295 	} else {
    296 		return { -1, -1 };
    297 	}
    298 }
    299 
    300 signed main() {
    301 	fastInp;
    302 
    303     ll t;
    304     cin >> t;
    305     
    306     while (t--) {
    307         vec.clear();
    308         blocks.clear();
    309     	cin >> n;
    310     
    311     	vec.resize(n);
    312     	for (auto& c : vec) cin >> c.first >> c.second;
    313     
    314     	vector<pair<ll, ll>> ans;
    315     
    316     	ans.push_back(solve());
    317     	swap(ans.back().first, ans.back().second);
    318     	if (ans.back().first == -1) ans.pop_back();
    319     
    320     	for (auto& c : vec) swap(c.first, c.second);
    321     
    322     	ans.push_back(solve());
    323     	if (ans.back().first == -1) ans.pop_back();
    324     
    325     	if (ans.size() == 2 && ans[0] == ans[1]) {
    326     		ans.pop_back();
    327     	}
    328     	cout << ans.size() << "\n";
    329     
    330     	for (auto c : ans) cout << c.first << " " << c.second << "\n";
    331     }
    332     
    333 	return 0;
    334 }
    335 ```
    336 
    337 [1819C - The Fox and the Complete Tree Traversal](/contest/1819/problem/C "Codeforces Round 866 (Div. 1)")
    338 
    339 Author: [golikovnik](/profile/golikovnik "Grandmaster golikovnik")
    340 
    341 Preparation: [DishonoredRighteous](/profile/DishonoredRighteous "Grandmaster DishonoredRighteous")
    342 
    343 **Editorial**
    344 
    345 Tutorial is loading...
    346 
    347 **Solution**
    348 
    349 ```
    350 // #pragma comment(linker, "/stack:200000000")
    351 // #pragma GCC optimize("Ofast,no-stack-protector")
    352 // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
    353 // #pragma GCC optimize("unroll-loops")
    354 
    355 #include <stdio.h>
    356 #include <bits/stdc++.h>
    357 
    358 #ifdef PERVEEVM_LOCAL
    359     #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
    360 #else
    361     #define debug(x) 238
    362 #endif
    363 
    364 #define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
    365 #define NAME "File"
    366 
    367 using ll = long long;
    368 using ld = long double;
    369 
    370 #ifdef PERVEEVM_LOCAL
    371     std::mt19937 rnd(238);
    372 #else
    373     std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    374 #endif
    375 
    376 template<typename T>
    377 bool smin(T& a, const T& b) {
    378     if (b < a) {
    379         a = b;
    380         return true;
    381     }
    382     return false;
    383 }
    384 
    385 template<typename T>
    386 bool smax(T& a, const T& b) {
    387     if (a < b) {
    388         a = b;
    389         return true;
    390     }
    391     return false;
    392 }
    393 
    394 const double PI = atan2(0.0, -1.0);
    395 const int INF = 0x3f3f3f3f;
    396 const ll LINF = (ll)2e18;
    397 const int N = 200100;
    398 
    399 std::vector<int> g[N];
    400 int d[N], par[N];
    401 bool onDiameter[N];
    402 
    403 void dfs(int v, int p, int depth) {
    404 	d[v] = depth;
    405 	par[v] = p;
    406 
    407 	for (auto to : g[v]) {
    408 		if (to != p) {
    409 			dfs(to, v, depth + 1);
    410 		}
    411 	}
    412 }
    413 
    414 void run() {
    415 	int n;
    416 	scanf("%d", &n);
    417 
    418 	for (int i = 0; i < n - 1; ++i) {
    419 		int from, to;
    420 		scanf("%d%d", &from, &to);
    421 		g[from - 1].push_back(to - 1);
    422 		g[to - 1].push_back(from - 1);
    423 	}    
    424 
    425 	dfs(0, 0, 0);
    426 	int v1 = 0;
    427 	for (int i = 0; i < n; ++i) {
    428 		if (d[i] > d[v1]) {
    429 			v1 = i;
    430 		}
    431 	}
    432 
    433 	dfs(v1, v1, 0);
    434 	int v2 = v1;
    435 	for (int i = 0; i < n; ++i) {
    436 		if (d[i] > d[v2]) {
    437 			v2 = i;
    438 		}
    439 	}
    440 
    441 	std::vector<int> diameter;
    442 	for (int v = v2; v != v1; v = par[v]) {
    443 		onDiameter[v] = true;
    444 		diameter.push_back(v);
    445 	}
    446 	onDiameter[v1] = true;
    447 	diameter.push_back(v1);
    448 	std::reverse(diameter.begin(), diameter.end());
    449 
    450 	for (int i = 0; i < n; ++i) {
    451 		if (onDiameter[i]) {
    452 			continue;
    453 		}
    454 		if (!onDiameter[par[i]]) {
    455 			printf("No\n");
    456 			return;
    457 		}
    458 	}
    459 
    460 	printf("Yes\n");
    461 	std::vector<int> ans;
    462 	for (int i = 0; i < (int)diameter.size(); i += 2) {
    463 		ans.push_back(diameter[i]);
    464 		if (i + 1 != (int)diameter.size()) {
    465 			for (auto to : g[diameter[i + 1]]) {
    466 				if (!onDiameter[to]) {
    467 					ans.push_back(to);
    468 				}
    469 			}
    470 		}
    471 	}
    472 
    473 	if (diameter.size() % 2 == 0) {
    474 		for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
    475 			ans.push_back(diameter[i]);
    476 			if (i - 1 >= 0) {
    477 				for (auto to : g[diameter[i - 1]]) {
    478 					if (!onDiameter[to]) {
    479 						ans.push_back(to);
    480 					}
    481 				}
    482 			}
    483 		}
    484 	} else {
    485 		for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {
    486 			ans.push_back(diameter[i - 1]);
    487 			if (i - 2 >= 0) {
    488 				for (auto to : g[diameter[i - 2]]) {
    489 					if (!onDiameter[to]) {
    490 						ans.push_back(to);
    491 					}
    492 				}
    493 			}
    494 		}
    495 	}
    496 
    497 	assert((int)ans.size() == n);
    498 	for (auto i : ans) {
    499 		printf("%d ", i + 1);
    500 	}
    501 	printf("\n");
    502 }
    503 
    504 int main(void) {
    505     // freopen(NAME".in", "r", stdin);
    506     // freopen(NAME".out", "w", stdout);
    507 
    508     #ifdef PERVEEVM_LOCAL
    509         auto start = std::chrono::high_resolution_clock::now();
    510     #endif
    511 
    512     run();
    513 
    514     #ifdef PERVEEVM_LOCAL
    515         auto end = std::chrono::high_resolution_clock::now();
    516         std::cerr << "Execution time: "
    517                   << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
    518                   << " ms" << std::endl;
    519     #endif
    520 
    521     return 0;
    522 }
    523 ```
    524 
    525 [1819D - Misha and Apples](/contest/1819/problem/D "Codeforces Round 866 (Div. 1)")
    526 
    527 Author: [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik")
    528 
    529 Preparation: [dshindov](/profile/dshindov "Candidate Master dshindov")
    530 
    531 **Editorial**
    532 
    533 Tutorial is loading...
    534 
    535 **Solution**
    536 
    537 ```
    538 #include <bits/stdc++.h>
    539 
    540 #include <exception>
    541 
    542 using namespace std;
    543 using ll = long long;
    544 
    545 void solve() {
    546     int n, m;
    547     cin >> n >> m;
    548     vector<vector<int>> apples(n);
    549     for (int i = 0; i < n; ++i) {
    550         int k;
    551         cin >> k;
    552         for (int j = 0; j < k; ++j) {
    553             int x;
    554             cin >> x;
    555             apples[i].push_back(x);
    556         }
    557     }
    558     // vector<int> last(m + 1, -1);
    559     unordered_map<int, int> last;
    560     auto get_last = [&](int i) {
    561         if (!last.count(i)) {
    562             return -1;
    563         } else {
    564             return last[i];
    565         }
    566     };
    567     vector<char> can_zero(n + 1, false);
    568     vector<int> prev(n + 1, 0);
    569     can_zero[0] = true;
    570     int oops = -1;
    571     for (int i = 0; i < n; ++i) {
    572         if (apples[i].empty()) {
    573             can_zero[i + 1] = true;
    574             last[0] = i;
    575         } else {
    576             int nearest_pair = get_last(0);
    577             int new_oops = oops;
    578             for (int x : apples[i]) {
    579                 nearest_pair = max(nearest_pair, get_last(x));
    580                 new_oops = max(new_oops, get_last(x));
    581                 last[x] = i;
    582             }
    583             if (nearest_pair != -1) {
    584                 int nearest_zero = prev[nearest_pair];
    585                 if (oops < nearest_zero) {
    586                     can_zero[i + 1] = true;
    587                 }
    588             }
    589             oops = new_oops;
    590         }
    591         if (can_zero[i + 1]) {
    592             prev[i + 1] = i + 1;
    593         } else {
    594             prev[i + 1] = prev[i];
    595         }
    596     }
    597     // vector<char> used(m + 1, false);
    598     unordered_set<int> used;
    599     vector<int> max_cnt(n + 1, 0);
    600     int current_cnt = 0;
    601     for (int i = n - 1; i >= 0; --i) {
    602         bool fail = false;
    603         if (apples[i].empty()) {
    604             used.insert(0);
    605         }
    606         for (int x : apples[i]) {
    607             if (used.count(x)) {
    608                 fail = true;
    609                 break;
    610             }
    611             used.insert(x);
    612             ++current_cnt;
    613         }
    614         if (fail) {
    615             break;
    616         }
    617         if (used.count(0)) {
    618             max_cnt[i] = m;
    619         } else {
    620             max_cnt[i] = current_cnt;
    621         }
    622     }
    623     int ans = 0;
    624     for (int i = 0; i <= n; ++i) {
    625         if (can_zero[i]) {
    626             ans = max(ans, max_cnt[i]);
    627         }
    628     }
    629     cout << ans << '\n';
    630 }
    631 
    632 int main() {
    633     cin.tie(nullptr)->sync_with_stdio(false);
    634     int t = 1;
    635     cin >> t;
    636     while (t--) solve();
    637 }
    638 ```
    639 
    640 [1819E - Roads in E City](/contest/1819/problem/E "Codeforces Round 866 (Div. 1)")
    641 
    642 Author: [Tikhon228](/profile/Tikhon228 "Master Tikhon228")
    643 
    644 Preparation: [grphil](/profile/grphil "Master grphil")
    645 
    646 **Editorial**
    647 
    648 Tutorial is loading...
    649 
    650 **Solution**
    651 
    652 ```
    653 #include <bits/stdc++.h>
    654 
    655 #define x first
    656 #define y second
    657 
    658 using namespace std;
    659 
    660 mt19937 rnd;
    661 
    662 struct solve {
    663 
    664 vector<pair<int, int>> r;
    665 
    666 vector<vector<pair<int, int>>> s;
    667 
    668 vector<int> ans;
    669 
    670 int n, m;
    671 
    672 static constexpr int rep = 45;
    673 
    674 int dfs(int a, int p, int b) {
    675 	for (auto i : s[a]) {
    676 		if (i.x == b) {
    677 			return i.y;
    678 		}
    679 		if (i.x == p) {
    680 			continue;
    681 		}
    682 
    683 		int x = dfs(i.x, a, b);
    684 
    685 		if (x != -1) {
    686 			return x;
    687 		}
    688 	}
    689 	return -1;
    690 }
    691 
    692 solve() {
    693 	cin >> n >> m;
    694 	r.resize(m);
    695 	for (int i = 0; i < m; i++) {
    696 		cin >> r[i].x >> r[i].y;
    697 		r[i].x--;
    698 		r[i].y--;
    699 	}
    700 
    701 	s.resize(n);
    702 	ans.resize(m, -1);
    703 	int cnt = 0;
    704 	for (int i = 0; i < m; i++) {
    705 		rem(i);
    706 		for (int j = 0; j < rep; j++) {
    707 			if (!ask_end(i)) {
    708 				ans[i] = 1;
    709 				break;
    710 			}
    711 		}
    712 		if (ans[i] == 1) {
    713 			add(i);
    714 			cnt++;
    715 			s[r[i].x].emplace_back(r[i].y, i);
    716 			s[r[i].y].emplace_back(r[i].x, i);
    717 		}
    718 	}
    719 
    720 	assert(cnt == n - 1);
    721 
    722 	for (int i = 0; i < m; i++) {
    723 		if (ans[i] != -1) continue;
    724 		ans[i] = 1;
    725 
    726 		int c = dfs(r[i].x, -1, r[i].y);
    727 		rem(c);
    728 		add(i);
    729 		for (int j = 0; j < rep; j++) {
    730 			if (!ask_end(i)) {
    731 				ans[i] = 0;
    732 				break;
    733 			}
    734 		}
    735 		rem(i);
    736 		add(c);
    737 	}
    738 	cout << "!";
    739 	for (int i = 0; i < m; i++) {
    740 		cout << ' ' << ans[i];
    741 	}
    742 	cout << endl;
    743 	int x;
    744 	cin >> x;
    745 	if (x != 1) {
    746 		exit(1);
    747 	}
    748 }
    749 
    750 void rem(int x) {
    751 	cout << "- " << x + 1 << endl;
    752 }
    753 
    754 void add(int x) {
    755 	cout << "+ " << x + 1 << endl;
    756 }
    757 
    758 bool ask(int a) {
    759 	cout << "? " << a + 1 << endl;
    760 	// cerr << "? " << a + 1 << endl;
    761 	int x;
    762 	cin >> x;
    763 	return x == 1;
    764 }
    765 
    766 bool ask_end(int i) {
    767 	// cerr << "ask_end " << i << endl;
    768 	int a = r[i].x;
    769 	if (rnd() % 2) {
    770 		a = r[i].y;
    771 	}
    772 	return ask(a);
    773 }
    774 
    775 };
    776 
    777 int main() {
    778 	int t;
    779 	cin >> t;
    780 	for (int i = 0; i < t; i++) {
    781 		solve();
    782 	}
    783 }
    784 ```
    785 
    786 [1819F - Willy-nilly, Crack, Into Release!](/contest/1819/problem/F "Codeforces Round 866 (Div. 1)")
    787 
    788 Author: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq")
    789 
    790 Preparation: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq")
    791 
    792 **Editorial**
    793 
    794 Tutorial is loading...
    795 
    796 **Solution**
    797 
    798 ```
    799 #include <bits/stdc++.h>
    800 
    801 using namespace std;
    802 using pi = pair<int, int>;
    803 using ll = long long;
    804 
    805 const int Q = 1e5;
    806 const int N = 20;
    807 const int V = N*Q;
    808 
    809 const ll LINF = 1e18;
    810 
    811 struct MinMaxValue {
    812     ll min_value;
    813     ll max_value;
    814 
    815     MinMaxValue operator * (const MinMaxValue& x) const {
    816         if (x.max_value < 0 || max_value < 0) {
    817             return MinMaxValue { 0, -1 };
    818         }
    819 
    820         return MinMaxValue {
    821             .min_value = x.min_value + min_value,
    822             .max_value = x.max_value + max_value
    823         };
    824     }
    825 
    826     MinMaxValue operator + (const MinMaxValue& x) const {
    827         if (x.max_value == -1) return *this;
    828         if (max_value == -1) return x;
    829 
    830         return MinMaxValue {
    831             .min_value = min(x.min_value, min_value),
    832             .max_value = max(x.max_value, max_value)
    833         };
    834     }
    835 
    836     MinMaxValue& operator += (const MinMaxValue& x) {
    837         return *this = *this + x;
    838     }
    839 
    840     void Reset() {
    841         min_value = 0;
    842         max_value = -1;
    843     }
    844 };
    845 
    846 struct {
    847     MinMaxValue dig, ver, hor;
    848     int cnt;
    849     int go[4];
    850 } nd[V];
    851 int vc = 0;
    852 MinMaxValue dig[N+1], ver[N+1], hor[N+1];
    853 
    854 std::set<ll> words;
    855 
    856 int NewVertex(int h) {
    857     int* go = nd[vc].go;
    858     go[0] = go[1] = go[2] = go[3] = -1;
    859     nd[vc].dig = dig[h];
    860     nd[vc].hor = hor[h];
    861     nd[vc].ver = ver[h];
    862     nd[vc].cnt = 0;
    863     return vc++;
    864 }
    865 
    866 tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {
    867     return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)
    868                    : make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);
    869 }
    870 
    871 void Calculate(int v, int h, int corner) {
    872     auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);
    873     auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);
    874     auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);
    875     auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);
    876 
    877     nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;
    878 
    879     nd[v].dig.Reset();
    880     if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;
    881     if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;
    882 
    883     nd[v].hor = ver0 * dig2 * dig3 * ver1;
    884     if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;
    885 
    886     nd[v].ver = hor0 * dig1 * dig3 * hor2;
    887     if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;
    888 }
    889 
    890 void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {
    891     if (h == 0) {
    892         if (nd[v].cnt == 0) {
    893             words.insert(msk_save);
    894         } else {
    895             words.erase(msk_save);
    896         }
    897         nd[v].cnt ^= 1;
    898     } else {
    899         UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);
    900         Calculate(v, h, corner);
    901     }
    902 }
    903 
    904 bool near_symbols[256][256];
    905 
    906 MinMaxValue GetAnswer(int h) {
    907     int v = 0;
    908 
    909     if (nd[v].cnt == 0) {
    910         return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };
    911     }
    912 
    913     MinMaxValue res; res.Reset();
    914 
    915     bool cycle_len2 = false;
    916     if (nd[v].cnt <= 1) cycle_len2 = true;
    917     if (nd[v].cnt == 2) {
    918         string s, t;
    919 
    920         for (ll msk =       *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);
    921         for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);
    922         auto flag = near_symbols[s.back()][t.back()];
    923 
    924         if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {
    925             cycle_len2 = true;
    926         }
    927 
    928         int s_suf = 0, t_suf = 0;
    929         while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;
    930         while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;
    931 
    932         if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)
    933                 && s.back() == t[h - s_suf - 1]
    934                 && t.back() == s[h - t_suf - 1]) cycle_len2 = true;
    935     }
    936 
    937     if (cycle_len2) {
    938         res.min_value = 2;
    939         res.max_value = 2;
    940     }
    941 
    942     while (h != 0) {
    943         const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];
    944         const auto& dig0 = get<0>(GetState(v0, h-1));
    945         const auto& dig1 = get<0>(GetState(v1, h-1));
    946         const auto& dig2 = get<0>(GetState(v2, h-1));
    947         const auto& dig3 = get<0>(GetState(v3, h-1));
    948 
    949         if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {
    950             res += dig0 * dig1 * dig2 * dig3;
    951         }
    952 
    953         --h;
    954         if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }
    955         if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }
    956         if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }
    957         if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }
    958         break;
    959     }
    960     return res;
    961 }
    962 
    963 int main() {
    964     ios::sync_with_stdio(0); cin.tie(0);
    965 
    966     int n, q; cin >> n >> q;
    967     vector<ll> v(q);
    968 
    969     for (int i = 0; i < 4; ++i) {
    970         int j = (i + 1) % 4;
    971         near_symbols['a' + i]['a' + j] = true;
    972         near_symbols['a' + j]['a' + i] = true;
    973     }
    974 
    975     dig[0] = ver[0] = hor[0] = { 1, 1 };
    976     for (int i = 1; i <= n; ++i) {
    977         dig[i] = hor[i-1] * dig[i-1] * ver[i-1];
    978         hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];
    979     }
    980 
    981     int m_root = NewVertex(n); // make_root
    982     assert(m_root == 0);
    983 
    984     for (int i = 0; i < q; ++i) {
    985         string s; cin >> s;
    986         for (int j = 0; j < n; ++j) {
    987             v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);
    988             v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);
    989         }
    990 
    991         int w = 0;
    992         for (int j = 0; j < n; ++j) {
    993             int& next = nd[w].go[(v[i] >> (2*j)) & 3];
    994             if (next == -1) next = NewVertex(n-j-1);
    995             w = next;
    996         }
    997     }
    998 
    999     for (ll msk : v) {
   1000         UpdateCount(0, n, 0, msk, msk);
   1001         auto [a, b] = GetAnswer(n);
   1002 
   1003         if (a > b) {
   1004             cout << -1 << '\n';
   1005         } else {
   1006             cout << a << " " << b << '\n';
   1007         }
   1008     }
   1009 }
   1010 ```