codeforces-scrape

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

2130.md (51640B)


      1 Source: https://codeforces.com/blog/entry/145152
      2 
      3 Thank you for participation and we hope you enjoy this round :)
      4 
      5 **How did you find the contest?**
      6 
      7 * Great:
      8 * Good:
      9 * Average:
     10 * Bad:
     11 * Trash:
     12 
     13 **Which problem is your most favourite?**
     14 
     15 * D2A:
     16 * D2B:
     17 * D1A:
     18 * D1B:
     19 * D1C1:
     20 * D1C2:
     21 * D1C3:
     22 * D1D:
     23 * D1E:
     24 * D1F1:
     25 * D1F2:
     26 
     27 **Which problem you hate the most?**
     28 
     29 * D2A:
     30 * D2B:
     31 * D1A:
     32 * D1B:
     33 * D1C1:
     34 * D1C2:
     35 * D1C3:
     36 * D1D:
     37 * D1E:
     38 * D1F1:
     39 * D1F2:
     40 
     41 #### [D2A Submission is All You Need](https://codeforces.com/contest/2130/problem/A)
     42 
     43 **Fun**
     44 
     45 Do you know the source of the title?
     46 
     47 **Hint 1**
     48 
     49 Assuming that choosing $\text{mex(S')}$ is optimal, what conditions does $S'$ need to satisfy?
     50 
     51 **Hint 2**
     52 
     53 Are there duplicate numbers in $S'$? Is there a number greater than $\text{mex(S')}$ in $S'$?
     54 
     55 **Tutorial**
     56 
     57 Assuming that choosing $\text{mex(S')}$ is optimal, there are no duplicate numbers in $S'$. And thers is not a number greater than $\text{mex(S')}$. Otherwise, we can easily construct a better answer.
     58 
     59 Consider $\text{S={0,1,...,x}}$. We can see $\text{mex(S')} \gt \text{max(S')}$ when $x$ is $0$ or $1$. And $\text{mex({0,1})}=\text{mex({0})}+\text{sum({1})}$. Thus, we only use $\text{mex}$ operation for each single $0$.
     60 
     61 The answer is $\text{sum(S)}$ add the number of $0$ in $S$.
     62 
     63 **solution**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 using namespace std;
     68 
     69 void solve(){
     70     int n, tmp, ans = 0;
     71     cin >> n;
     72     for(int i=0; i<n; i++){cin >> tmp; ans += tmp + (tmp == 0);}
     73     cout << ans << '\n';
     74 }
     75 
     76 int main(){
     77     ios::sync_with_stdio(false);
     78     cin.tie(NULL);
     79     int t;
     80     cin >> t;
     81     while(t--) solve();
     82 }
     83 ```
     84 
     85 **Rate the Problem**
     86 
     87 Amazing problem:
     88 
     89 Good problem:
     90 
     91 Average problem:
     92 
     93 Bad problem:
     94 
     95 Didn't solve:
     96 
     97 #### [D2B Pathless](https://codeforces.com/contest/2130/problem/B)
     98 
     99 **Hint1**
    100 
    101 Casework. Consider two easy cases first: $\Sigma a \gt s$ and $\Sigma a=s$.
    102 
    103 **Hint2**
    104 
    105 What if there is an index $i$ such that $a_i+a_{i+1}=1$?
    106 
    107 **Hint3**
    108 
    109 To "block" $a_i+a_{i+1}=1$, what should Bob do?
    110 
    111 **Hint4**
    112 
    113 Consider cases of $\Sigma a=s+1$ and $\Sigma a \gt s+1$.
    114 
    115 **Tutorial**
    116 
    117 The minimum path sum is the sum of the simple path from $1$ to $n$ (i.e., $1 \rightarrow 2 \rightarrow \dots \rightarrow n$), denoted as $\text{base_sum} = \sum_{i=1}^{n} a_i$.
    118 
    119 The path can include back-and-forth movements (e.g., from $i$ to $i+1$ and back to $i$), which increases the path length and the path sum. Specifically, each back-and-forth movement between adjacent positions $(i, i+1)$ adds $a_i + a_{i+1}$ to the path sum.
    120 
    121 Thus, the total path sum can be expressed as $\text{base_sum} + d$, where $d$ is the additional sum contributed by zero or more back-and-forth movements. Here, $d$ can be represented as a non-negative integer linear combination of the sums of adjacent pairs.
    122 
    123 Casework:
    124 
    125 * If $s \lt \text{base_sum}$, no path sum can equal $s$ (since the base sum already exceeds $k$, and any additional movements will further increase the sum).
    126 * If $s = \text{base_sum}$, the simple path ($1 \rightarrow 2 \rightarrow \dots \rightarrow n$) already satisfies the condition, so Alice cannot be stopped.
    127 * If $s \gt \text{base_sum}$, let $d = s - \text{base_sum}$:
    128 
    129   + If $d = 1$, we can rearrange the array to avoid adjacent pairs summing to $1$ (i.e., avoid $0$ and $1$ being adjacent). Specifically, place all $0$s first, followed by all $2$s, and then all $1$s (e.g., $[0, 0, \dots, 0, 2, 2, \dots, 2, 1, 1, \dots, 1]$). This ensures no adjacent pair sums to $1$, making $d = 1$ unachievable.
    130   + If $d \neq 1$, no rearrangement can prevent Alice from achieving the path sum $s$ (since sums of adjacent pairs can cover all $T \geq 2$ through linear combinations).
    131 
    132 **solution**
    133 
    134 ```
    135 #include <bits/stdc++.h>
    136 using namespace std;
    137 
    138 void solve(){
    139     int n, k, tmp;
    140     cin >> n >> k;
    141     vector<int> a(3);
    142     for(int i=0; i<n; i++){cin >> tmp; a[tmp]++;}
    143     if(k == a[1] + 2*a[2] || k >= a[1] + 2*a[2] + 2){cout << -1 << '\n'; return;}
    144     for(int i=0; i<a[0]; i++) cout << 0 << ' ';
    145     for(int i=0; i<a[2]; i++) cout << 2 << ' ';
    146     for(int i=0; i<a[1]; i++) cout << 1 << ' ';
    147     cout << '\n';
    148 }
    149 
    150 int main(){
    151     ios::sync_with_stdio(false);
    152     cin.tie(NULL);
    153     int t;
    154     cin >> t;
    155     while(t--) solve();
    156 }
    157 ```
    158 
    159 **Rate the Problem**
    160 
    161 Amazing problem:
    162 
    163 Good problem:
    164 
    165 Average problem:
    166 
    167 Bad problem:
    168 
    169 Didn't solve:
    170 
    171 #### [D1A Double Perspective](https://codeforces.com/contest/2129/problem/A)
    172 
    173 **Hint1**
    174 
    175 Assuming that choosing $S$ is optimal, what is the value of $g(S)$?
    176 
    177 **Hint2**
    178 
    179 In the case of $g(S)=0$, make $f(S)$ the length of the union of the entire set.
    180 
    181 **Tutorial**
    182 
    183 Assuming that choosing $S$ is optimal, $g(S)$ must be $0$ because removing an edge on the cycle will not change $f(S)$.
    184 
    185 In the case of $g(S)=0$, we need to make $f(S)$ the length of the union of the entire set. There are many approaches.
    186 
    187 An easiest $O(n^2)$ approach is to remove all segments contained by other segments. Afterwards, it can be proven that there are no cycles with a length greater than or equal to $3$ in the graph. If there is a cycle, note it as $x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow ... \rightarrow x_1$, we can always find $x_{i-1} \lt x_i \gt x_{i+1}$, where either $[x_{i-1},x_i] \subseteq [x_i,x_{i+1}]$ or $[x_i,x_{i+1}] \subseteq [x_{i-1},x_i]$. At this point, we have deduced the contradiction, so there are no cycles with a length greater than or equal to $3$ in the graph.
    188 
    189 Another approach is to use DSU to maintain the generate forest.
    190 
    191 **solution**
    192 
    193 ```
    194 #include <map>
    195 #include <set>
    196 #include <cmath>
    197 #include <ctime>
    198 #include <queue>
    199 #include <stack>
    200 #include <cstdio>
    201 #include <cstdlib>
    202 #include <vector>
    203 #include <cstring>
    204 #include <algorithm>
    205 #include <iostream>
    206 #include <bitset>
    207 #include <unordered_map>
    208 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    209 using namespace std;
    210 typedef double db;
    211 typedef long long ll;
    212 typedef unsigned long long ull;
    213 const int N=1000010;
    214 int T,n;
    215 int a[N],b[N];
    216 
    217 void init()
    218 {
    219     cin>>n;
    220     for(int i=1;i<=n;i++)
    221         cin>>a[i]>>b[i];
    222 }
    223 
    224 void solve()
    225 {
    226     vector<int> tag(n+4,1),ans;
    227     for(int i=1;i<=n;i++)
    228     {
    229         for(int j=1;j<=n;j++)
    230         {
    231             if(i==j) continue;
    232             if(a[j]<=a[i]&&b[i]<=b[j]) tag[i]=0;
    233         }
    234         if(tag[i]) ans.push_back(i);
    235     }
    236     cout<<ans.size()<<"\n";
    237     for(int i=0;i<ans.size();i++)
    238         cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
    239 }
    240 
    241 int main()
    242 {
    243     fastio;
    244 
    245     cin>>T;
    246 	while(T--)
    247 	{
    248 		init();
    249 		solve();
    250 	}
    251 
    252 	return 0;
    253 }
    254 ```
    255 
    256 **Rate the Problem**
    257 
    258 Amazing problem:
    259 
    260 Good problem:
    261 
    262 Average problem:
    263 
    264 Bad problem:
    265 
    266 Didn't solve:
    267 
    268 #### [D1B Stay or Mirror](https://codeforces.com/contest/2129/problem/B)
    269 
    270 **Hint1**
    271 
    272 Consider $p_i=1$. If $a_i=1$, what are inversions containing $i$? If $a_i=2n-1$, what are inversions containing $i$?
    273 
    274 **Hint2**
    275 
    276 Attempt to generalize the conclusion to any pair $(i, j)$.
    277 
    278 **Tutorial**
    279 
    280 Consider $p_i=1$ and inversions containing $i$. If $a_i=1$, it is the minimum value, and the inversions containing $i$ are $(1, i), (2, i),... (i-1, i)$; If $a_i=2n-1$, it is the maximum value, and the inversions containing $i$ are $(i, i+1),... (i, n)$. The key observation is the number of inversions containing $i$ is only related to $a_i$, and completely unrelated to other elements.
    281 
    282 At this point, the problem has actually been solved. We can greedily choose $\min(i-1,n-i)$ and remove $1$ from $p$, and the remaining part is a completely identical subproblem with a size of $n-1$.
    283 
    284 It can be implemented as follows: for each index $i$, calculate the number of elements to the left that are bigger than $p_i$ (note it as $lbigger$), and the number of elements to the right that are bigger than $p_i$ (note it as $rbigger$). Then greedily add $\min(lbigger,rbigger)$ to the answer.
    285 
    286 **solution**
    287 
    288 ```
    289 #include <bits/stdc++.h>
    290 using namespace std;
    291 
    292 void solve(){
    293     int n, ans = 0;
    294     cin >> n;
    295     vector<int> p(n);
    296     for(int i=0; i<n; i++) cin >> p[i];
    297     for(int i=0; i<n; i++){
    298         int left = 0, right = 0;
    299         for(int j=0; j<i; j++) if(p[j] > p[i]) left++;
    300         for(int j=i+1; j<n; j++) if(p[j] > p[i]) right++;
    301         ans += min(left, right);
    302     }
    303     cout << ans << '\n';
    304 }
    305 
    306 int main(){
    307     ios::sync_with_stdio(false);
    308     cin.tie(NULL);
    309     int t;
    310     cin >> t;
    311     while(t--) solve();
    312 }
    313 ```
    314 
    315 **Rate the Problem**
    316 
    317 Amazing problem:
    318 
    319 Good problem:
    320 
    321 Average problem:
    322 
    323 Bad problem:
    324 
    325 Didn't solve:
    326 
    327 #### [D1C1 Interactive RBS (Easy Version)](https://codeforces.com/contest/2129/problem/C1), [D1C2 Interactive RBS (Medium Version)](https://codeforces.com/contest/2129/problem/C2) and [D1C3 Interactive RBS (Hard Version)](https://codeforces.com/contest/2129/problem/C3)
    328 
    329 **Hint1**
    330 
    331 Try to Perform binary search to find a $\texttt{'('}$ and a $\texttt{')'}$ using $O(\log n)$ queries. It is best to complete it within $10$ operations (to pass the hard version).
    332 
    333 **Hint2**
    334 
    335 Consider the easy version. Constraint implies that we use one query to determine $2$ characters.
    336 
    337 **Hint3**
    338 
    339 Construct a string $x$, insert $s_i$ and $s_j$ into certain positions of $x$ to obtain string $y$, so that $f(y)$ can produce $4$ different values.
    340 
    341 **Hint4**
    342 
    343 Consider the medium version. Effectively utilizing the conditions of $k \le 1000$.
    344 
    345 **Hint5**
    346 
    347 Consider binary code.
    348 
    349 **Hint6**
    350 
    351 Consider the hard version. The number of substrings in a string of length $l$ is $O(l ^ 2)$. How to utilize this?
    352 
    353 **Tutorial (easy version)**
    354 
    355 At first, we need to find $s_x=\texttt{’(’}$ and $s_y=\texttt{’)’}$. Do binary search to find the smallest $i$ such that $f(s_1s_2...s_i) \gt 0$. Then we get $s_{i-1}=\texttt{’(’}$ and $s_i=\texttt{’)’}$. A corner case is $f(s)=0$. In this case, $s_n=\texttt{’(’}$ and $s_1=\texttt{’)’}$.
    356 
    357 Ask $f(\texttt{"s1)s2)()"})$:
    358 
    359 * If $f(\texttt{"s1)s2)()"})=6$, $s_1=$ $\texttt{'('}$ and $s_2=$ $\texttt{'('}$.
    360 * If $f(\texttt{"s1)s2)()"})=2$, $s_1=$ $\texttt{'('}$ and $s_2=$ $\texttt{')'}$.
    361 * If $f(\texttt{"s1)s2)()"})=3$, $s_1=$ $\texttt{')'}$ and $s_2=$ $\texttt{'('}$.
    362 * If $f(\texttt{"s1)s2)()"})=1$, $s_1=$ $\texttt{')'}$ and $s_2=$ $\texttt{')'}$.
    363 
    364 In this way, we can determine two characters with one query.
    365 
    366 **Tutorial (medium version)**
    367 
    368 Read the tutorial in easy version first.
    369 
    370 Note $f_0$ as the $f$ value of the following string:
    371 
    372 $\underbrace{()()\ldots()}_{128 pairs}$ $)$ $\underbrace{()()\ldots()}_{64 pairs}$ $)$ $\dots$ $)()$
    373 
    374 Then ask for the $f$ value of the following string (note it as $f_1$):
    375 
    376 $\underbrace{s_8)()\ldots()}_{128 pairs}$ $)$ $\underbrace{s_7)()\ldots()}_{64 pairs}$ $)$ $\dots$ $)s_1)$
    377 
    378 By checking the binary bits of $f_0-f_1$, we can determine $8$ positions with one query. For example, if $f_0-f_1=(10000101)_2$, we can get $s_1=s_3=s_8=')'$.
    379 
    380 **Tutorial (hard version)**
    381 
    382 Read the tutorial of the medium version first.
    383 
    384 We can optimize
    385 
    386 $\underbrace{s_i)()\ldots()}_{2^k pairs}$
    387 
    388 to
    389 
    390 $\underbrace{()()\ldots()}_{2^{\lfloor \frac{k}{2} \rfloor}-1\ pairs}$ $s_i)$ $\underbrace{()()\ldots()}_{2^{\lceil \frac{k}{2} \rceil}-1\ pairs}$
    391 
    392 With this optimization, we can determine $12$ locations in one query.
    393 
    394 Another construction also works:
    395 
    396 $\underbrace{s_1)s_1)\ldots s_1)}_{g(1)\ pairs}$ $)$ $\underbrace{s_2)s_2)\ldots s_2)}_{g(2)\ pairs}$ $)$ $\underbrace{s_3)s_3)\ldots s_3)}_{g(3)\ pairs}$ $)$ $\ldots$ $\underbrace{s_{12})s_{12})\ldots s_{12})}_{g(12)\ pairs}$
    397 
    398 where $g(1)=1$ and $\frac{g(i+1) \cdot (g(i+1)+1)}{2} \gt \frac{g(1) \cdot (g(1)+1)}{2}+\frac{g(2) \cdot (g(2)+1)}{2}+\ldots+\frac{g(i) \cdot (g(i)+1)}{2}$.
    399 
    400 **solution (easy version)**
    401 
    402 ```
    403 #include <bits/stdc++.h>
    404 using namespace std;
    405 
    406 typedef long long ll;
    407 
    408 typedef long long       ll;
    409 typedef long double     ld;
    410 typedef pair<ll, ll>   pll;
    411 typedef pair<int, int> pii;
    412 typedef vector<int> vi;
    413 typedef vector<ll> vll;
    414 
    415 const long long kk = 1000;
    416 const long long ml = kk * kk;
    417 const long long mod = ml * kk + 7;
    418 const long long inf = ml * ml * ml + 7;
    419 
    420 #define T(x, i) get<i>(x)
    421 #define F first
    422 #define S second
    423 #define all(v) v.begin(), v.end()
    424 #define forn(i, n) for (int i = 0; i < n; i++)
    425 
    426 template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.F >> p.S; }
    427 template<class T, class U> inline ostream& operator<<(ostream& str, const pair<T, U> &p) { str << p.F << ' ' << p.S << ' '; return str; }
    428 template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
    429 template<class T> inline ostream& operator<<(ostream& str, const vector<T> &a) { for (auto &i : a) str << i << ' '; return str; }
    430 
    431 void flush() { cout << flush; }
    432 void flushln() { cout << endl; }
    433 template<class T> void read(T &x) { cin >> x; }
    434 template<class T, class ...U> void read(T &x, U&... u) { read(x); read(u...); }
    435 template<class T> void print(const T &x) { cout << x; }
    436 template<class T, class ...U> void print(const T &x, const U&... u) { print(x); print(u...); }
    437 template<class ...T> void println(const T&... u) { print(u..., '\n'); }
    438 template<class T> void eprint(const T &x) { cerr << x; }
    439 template<class T, class ...U> void eprint(const T &x, const U&... u) { eprint(x); eprint(u...); }
    440 template<class ...T> void eprintln(const T&... u) { eprint(u..., '\n'); }
    441 
    442 #ifdef DEBUG
    443 	mt19937 rng(1033);
    444 	#define var(x) cerr << #x << ": " << x << '\n';
    445 	#define range(a, b) cerr << #a << ", " << #b << ": "; for (auto _it = a; _it != b; ++_it) cerr << *_it << ' '; cerr << '\n';
    446 #else
    447 	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    448 	#define cerr if (false) cerr
    449 	#define var(x)
    450 	#define range(a, b)
    451 	#define eprintln if(false)eprintln
    452 	#define eprint if(false)eprint
    453 #endif
    454 int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
    455 
    456 int n;
    457 
    458 map<vector<int>, int> mem;
    459 
    460 int ask(vector<int> ind) {
    461 	if (!mem.count(ind)) {
    462 		cout << "? ";
    463 		cout << ind.size() << ' ';
    464 		for (auto i : ind)
    465 			cout << i + 1 << ' ';
    466 		cout << endl;
    467 
    468 		int res;
    469 		cin >> res;
    470 		mem[ind] = res;
    471 	}
    472 
    473 	return mem[ind];
    474 }
    475 
    476 bool same(vector<int> ind) {
    477 	if (ask(ind))
    478 		return false;
    479 	ind.push_back(ind[0]);
    480 	ind.erase(ind.begin());
    481 	if (ask(ind))
    482 		return false;
    483 	return true;
    484 }
    485 
    486 pii search(vector<int> ind) {
    487 	if (ind.size() == 2) {
    488 		if (ask(ind))
    489 			return {ind[0], ind[1]};
    490 		return {ind[1], ind[0]};
    491 	}
    492 
    493 	vector<int> inda, indb;
    494 	int sz = (ind.size() + 1) / 2;
    495 	for (int i = 0; i < sz; i++) {
    496 		inda.push_back(ind[i]);
    497 		indb.push_back(ind[ind.size() - 1 - i]);
    498 	}
    499 
    500 	if (!same(inda))
    501 		return search(inda);
    502 	if (!same(indb))
    503 		return search(indb);
    504 	inda.push_back(indb[0]);
    505 	return search(inda);
    506 }
    507 
    508 pii find_reg2() {
    509 	vector<int> ind(n);
    510 	iota(all(ind), 0);
    511 	shuffle(all(ind), rng);
    512 	return search(ind);
    513 }
    514 
    515 void solve() {
    516 	mem.clear();
    517 	auto [po, pc] = find_reg2();
    518 
    519 	vector<int> to_ask(n);
    520 	iota(all(to_ask), 0);
    521 	if (to_ask.size() & 1)
    522 		to_ask.push_back(0);
    523 
    524 	string ans = string(n, '.');
    525 	ans[po] = '(';
    526 	ans[pc] = ')';
    527 		
    528 	for (int i = 0; i < to_ask.size(); i += 2) {
    529 		int a = to_ask[i], b = to_ask[i + 1];
    530 
    531 		vector<int> q = {po, pc, po, a, b, pc};
    532 		int res = ask(q);
    533 
    534 		// ()(ab) - x ab
    535 		// ()(()) - 4 ()
    536 		// ()((() - 2 ((
    537 		// ()())) - 3 ))
    538 		// ()()() - 6 )(
    539 		map<int, pair<char, char>> results = {
    540 			{4, {'(', ')'}},
    541 			{2, {'(', '('}},
    542 			{3, {')', ')'}},
    543 			{6, {')', '('}},
    544 		};
    545 
    546 		assert(results.count(res));
    547 		auto [resa, resb] = results[res];
    548 		ans[a] = resa;
    549 		ans[b] = resb;
    550 	}
    551 
    552 	cout << "! " << ans << endl;
    553 }
    554 
    555 signed main() {
    556 	#ifdef DEBUG
    557 	// freopen("input.txt", "r", stdin);
    558 	// freopen("output.txt", "w", stdout);
    559 	#endif
    560 	ios_base::sync_with_stdio(0); cin.tie(0);
    561 	cout << fixed << setprecision(20);
    562 	int t = 1;
    563 	cin >> t;
    564 	for (int i = 0; i < t; i++) {
    565 		cin >> n;
    566 		solve();
    567 	}
    568 	#ifdef DEBUG
    569 		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
    570 	#endif
    571 }
    572 
    573 /*
    574 
    575 ()(ab)
    576 ()(()) - 4 ()
    577 ()((() - 2 ((
    578 ()())) - 3 ))
    579 ()()() - 6 )(
    580 
    581 2
    582 3
    583 )((
    584 2
    585 ()
    586 
    587 */
    588 ```
    589 
    590 **solution (medium version)**
    591 
    592 ```
    593 #include <vector>
    594 #include <list>
    595 #include <map>
    596 #include <set>
    597 #include <deque>
    598 #include <vector>
    599 #include <list>
    600 #include <map>
    601 #include <set>
    602 #include <deque>
    603 #include <queue>
    604 #include <stack>
    605 #include <bitset>
    606 #include <algorithm>
    607 #include <functional>
    608 #include <numeric>
    609 #include <utility>
    610 #include <sstream>
    611 #include <iostream>
    612 #include <iomanip>
    613 #include <cstdio>
    614 #include <cmath>
    615 #include <cstdlib>
    616 #include <cctype>
    617 #include <string>
    618 #include <cstring>
    619 #include <ctime>
    620 #include <random>
    621 #include <chrono>
    622  
    623 using namespace std;
    624  
    625 #define _int64 long long
    626 #define mo 998244353
    627 
    628 char tar[110000];
    629 int cnt;
    630 
    631 int doask(vector<int>& a)
    632 {
    633 	int i,ret;
    634 	/*
    635 	{
    636 		int v,tmp,j;
    637 		string ss;
    638 		cnt++;
    639 		ss="";
    640 		for (i=0;i<a.size();i++)
    641 		{
    642 			ss.push_back(tar[a[i]]);
    643 		}
    644 		tmp=0;
    645 		for (i=0;i<ss.length();i++)
    646 		{
    647 			v=0;
    648 			for (j=i;j<ss.length();j++)
    649 			{
    650 				if (ss[j]=='(') v++;
    651 				else v--;
    652 				if (v<0) break;
    653 				if (v==0) tmp++;
    654 			}
    655 		}
    656 		return tmp;
    657 	}
    658 	*/
    659 	
    660 	printf("? %d",(int)a.size());
    661 	for (i=0;i<a.size();i++)
    662 		printf(" %d",a[i]+1);
    663 	printf("\n");
    664 	fflush(stdout);
    665 	scanf("%d",&ret);
    666 	return ret;
    667 	
    668 }
    669 
    670 char ans[1100];
    671 
    672 void doanswer()
    673 {
    674 	printf("! %s\n",ans);
    675 	cerr<<"T "<<tar<<endl;
    676 	cerr<<"cnt:"<<cnt<<endl;
    677 	if (string(ans)==string(tar))
    678 	{
    679 		cerr<<"good"<<endl;
    680 	}
    681 	else cerr<<"bad"<<endl;
    682 	fflush(stdout);
    683 }
    684 
    685 int main()
    686 {
    687 	int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st;
    688 	vector<int> a;
    689 	scanf("%d",&t);
    690 	for (l=0;l<t;l++)
    691 	{
    692 		scanf("%d",&n);
    693 		for (i=0;i<n;i++)
    694 		{
    695 			x=rand()%2;
    696 			if (x==0) tar[i]='(';
    697 			else tar[i]=')';
    698 		}
    699 		tar[n]='\0';
    700 		cnt=0;
    701 		st=0;ans[n]='\0';
    702 		indl=-1;
    703 		indr=-1;
    704 		// while (st<n)
    705 		// {
    706 			ll=st;rr=n;
    707 			while (rr-ll>1)
    708 			{
    709 				mid=(ll+rr)/2;
    710 				a.clear();
    711 				for (i=st;i<=mid;i++)
    712 					a.push_back(i);
    713 				tmp=doask(a);
    714 				if (tmp==0) ll=mid;
    715 				else rr=mid;
    716 			}
    717 			if (rr==n)
    718 			{
    719 				indr=st;
    720 				/*
    721 				if ((indl==-1)&&(indr==-1))
    722 				{
    723 					indr=st;
    724 				}
    725 				ll=st-1;rr=n;
    726 				while (rr-ll>1)
    727 				{
    728 					mid=(ll+rr)/2;
    729 					a.clear();
    730 					a.push_back(mid);
    731 					a.push_back(indr);
    732 					tmp=doask(a);
    733 					if (tmp==0) ll=mid;
    734 					else rr=mid;
    735 				}
    736 				for (i=st;i<=ll;i++)
    737 					ans[i]=')';
    738 				for (i=rr;i<n;i++)
    739 					ans[i]='(';
    740 				st=n;
    741 				break;
    742 				*/
    743 			}
    744 			else
    745 			{
    746 				indr=rr;
    747 				/*
    748 				v=rr;
    749 				ans[v]=')';
    750 				ll=st-1;rr=v-1;
    751 				while (rr-ll>1)
    752 				{
    753 					mid=(ll+rr)/2;
    754 					a.clear();
    755 					a.push_back(mid);
    756 					a.push_back(v);
    757 					tmp=doask(a);
    758 					if (tmp==0) ll=mid;
    759 					else rr=mid;
    760 				}
    761 				for (i=st;i<=ll;i++)
    762 					ans[i]=')';
    763 				for (i=rr;i<v;i++)
    764 					ans[i]='(';
    765 				st=v+1;
    766 				indl=v-1;
    767 				indr=v;
    768 				*/
    769 			}
    770 		// }
    771 		//cerr<<"indr:"<<indr<<endl;
    772 		for (i=0;i<n;i+=8)
    773 		{
    774 			a.clear();
    775 			for (j=0;j<8;j++)
    776 			{
    777 				if (i+j>=n) break;
    778 				for (k=0;k<(1<<j);k++)
    779 				{
    780 					a.push_back(i+j);
    781 					a.push_back(indr);
    782 					a.push_back(indr);
    783 				}
    784 			}
    785 			tmp=doask(a);
    786 			for (j=0;j<8;j++)
    787 			{
    788 				if (i+j>=n) break;
    789 				if (((1<<j)&tmp)!=0) ans[i+j]='(';
    790 				else ans[i+j]=')';
    791 			}
    792 		}
    793 
    794 		doanswer();
    795 	}
    796 }
    797 ```
    798 
    799 **solution (hard version)**
    800 
    801 ```
    802 #include <vector>
    803 #include <list>
    804 #include <map>
    805 #include <set>
    806 #include <deque>
    807 #include <vector>
    808 #include <list>
    809 #include <map>
    810 #include <set>
    811 #include <deque>
    812 #include <queue>
    813 #include <stack>
    814 #include <bitset>
    815 #include <algorithm>
    816 #include <functional>
    817 #include <numeric>
    818 #include <utility>
    819 #include <sstream>
    820 #include <iostream>
    821 #include <iomanip>
    822 #include <cstdio>
    823 #include <cmath>
    824 #include <cstdlib>
    825 #include <cctype>
    826 #include <string>
    827 #include <cstring>
    828 #include <ctime>
    829 #include <random>
    830 #include <chrono>
    831  
    832 using namespace std;
    833  
    834 #define _int64 long long
    835 #define mo 998244353
    836 
    837 char tar[110000];
    838 int cnt;
    839 
    840 int doask(vector<int>& a)
    841 {
    842 	int i,ret;
    843 	/*
    844 	{
    845 		int v,tmp,j;
    846 		string ss;
    847 		cnt++;
    848 		ss="";
    849 		for (i=0;i<a.size();i++)
    850 		{
    851 			ss.push_back(tar[a[i]]);
    852 		}
    853 		tmp=0;
    854 		for (i=0;i<ss.length();i++)
    855 		{
    856 			v=0;
    857 			for (j=i;j<ss.length();j++)
    858 			{
    859 				if (ss[j]=='(') v++;
    860 				else v--;
    861 				if (v<0) break;
    862 				if (v==0) tmp++;
    863 			}
    864 		}
    865 		return tmp;
    866 	}
    867 	*/
    868 	
    869 	printf("? %d",(int)a.size());
    870 	for (i=0;i<a.size();i++)
    871 		printf(" %d",a[i]+1);
    872 	printf("\n");
    873 	fflush(stdout);
    874 	scanf("%d",&ret);
    875 	return ret;
    876 	
    877 }
    878 
    879 char ans[1100];
    880 
    881 void doanswer()
    882 {
    883 	printf("! %s\n",ans);
    884 	cerr<<"T "<<tar<<endl;
    885 	cerr<<"cnt:"<<cnt<<endl;
    886 	if (string(ans)==string(tar))
    887 	{
    888 		cerr<<"good"<<endl;
    889 	}
    890 	else cerr<<"bad"<<endl;
    891 	fflush(stdout);
    892 }
    893 
    894 int main()
    895 {
    896 	int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st,sum,len;
    897 	vector<int> a;
    898 	vector<int> p;
    899 	sum=0;len=0;
    900 	for (i=1;i<=130;i++)
    901 	{
    902 		tmp=i*(i+1)/2;
    903 		if (tmp>sum)
    904 		{
    905 			p.push_back(i);
    906 			//cerr<<"i:"<<i<<endl;
    907 			sum+=tmp;
    908 			len+=i+i;
    909 		}
    910 	}
    911 	//cerr<<"p.sz:"<<p.size()<<" "<<len<<endl;
    912 	scanf("%d",&t);
    913 	for (l=0;l<t;l++)
    914 	{
    915 		scanf("%d",&n);
    916 		for (i=0;i<n;i++)
    917 		{
    918 			x=rand()%2;
    919 			if (x==0) tar[i]='(';
    920 			else tar[i]=')';
    921 		}
    922 		tar[n]='\0';
    923 		cnt=0;
    924 		st=0;ans[n]='\0';
    925 		indl=-1;
    926 		indr=-1;
    927 		// while (st<n)
    928 		// {
    929 			ll=st;rr=n;
    930 			while (rr-ll>1)
    931 			{
    932 				mid=(ll+rr)/2;
    933 				a.clear();
    934 				for (i=st;i<=mid;i++)
    935 					a.push_back(i);
    936 				tmp=doask(a);
    937 				if (tmp==0) ll=mid;
    938 				else rr=mid;
    939 			}
    940 			if (rr==n)
    941 			{
    942 				indr=st;
    943 				/*
    944 				if ((indl==-1)&&(indr==-1))
    945 				{
    946 					indr=st;
    947 				}
    948 				ll=st-1;rr=n;
    949 				while (rr-ll>1)
    950 				{
    951 					mid=(ll+rr)/2;
    952 					a.clear();
    953 					a.push_back(mid);
    954 					a.push_back(indr);
    955 					tmp=doask(a);
    956 					if (tmp==0) ll=mid;
    957 					else rr=mid;
    958 				}
    959 				for (i=st;i<=ll;i++)
    960 					ans[i]=')';
    961 				for (i=rr;i<n;i++)
    962 					ans[i]='(';
    963 				st=n;
    964 				break;
    965 				*/
    966 			}
    967 			else
    968 			{
    969 				indr=rr;
    970 				/*
    971 				v=rr;
    972 				ans[v]=')';
    973 				ll=st-1;rr=v-1;
    974 				while (rr-ll>1)
    975 				{
    976 					mid=(ll+rr)/2;
    977 					a.clear();
    978 					a.push_back(mid);
    979 					a.push_back(v);
    980 					tmp=doask(a);
    981 					if (tmp==0) ll=mid;
    982 					else rr=mid;
    983 				}
    984 				for (i=st;i<=ll;i++)
    985 					ans[i]=')';
    986 				for (i=rr;i<v;i++)
    987 					ans[i]='(';
    988 				st=v+1;
    989 				indl=v-1;
    990 				indr=v;
    991 				*/
    992 			}
    993 		// }
    994 		//cerr<<"indr:"<<indr<<endl;
    995 		for (i=0;i<n;i+=p.size())
    996 		{
    997 			a.clear();
    998 			for (j=0;j<p.size();j++)
    999 			{
   1000 				if (i+j>=n) break;
   1001 				for (k=0;k<p[j];k++)
   1002 				{
   1003 					a.push_back(i+j);
   1004 					a.push_back(indr);
   1005 				}
   1006 				a.push_back(indr);
   1007 			}
   1008 			tmp=doask(a);
   1009 			for (j=p.size()-1;j>=0;j--)
   1010 			{
   1011 				if (i+j>=n) continue;
   1012 				v=p[j]*(p[j]+1)/2;
   1013 				if (tmp>=v)
   1014 				{
   1015 					tmp-=v;ans[i+j]='(';
   1016 				}
   1017 				else ans[i+j]=')';
   1018 			}
   1019 		}
   1020 
   1021 		doanswer();
   1022 	}
   1023 }
   1024 ```
   1025 
   1026 **Rate the Problem**
   1027 
   1028 Amazing problem:
   1029 
   1030 Good problem:
   1031 
   1032 Average problem:
   1033 
   1034 Bad problem:
   1035 
   1036 Didn't solve:
   1037 
   1038 #### [D1D Permutation Blackhole](https://codeforces.com/contest/2129/problem/D)
   1039 
   1040 **Hint1**
   1041 
   1042 Consider enumerating $p_i = 1$. After that, will the cells to the left of $p_i$ affect the cells to the right of $p_i$?
   1043 
   1044 **Hint2**
   1045 
   1046 Consider range DP.
   1047 
   1048 **Hint3**
   1049 
   1050 Can you find the upper bound of $s_i$?
   1051 
   1052 **Tutorial**
   1053 
   1054 Consider range DP.
   1055 
   1056 Note $dp[l][r][x][y]$ as the number of scheme ensureing $s[l-1]+=x$ and $s[r+1]+=y$.
   1057 
   1058 Transform:
   1059 
   1060 $  
   1061   
   1062 dp[l][r][x][y] = \left\{ \begin{array}{l} \Sigma_{\text{i is nearer to l}} \binom{r-l}{i-l} \cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{\text{i is nearer to r}} \binom{r-l}{i-l} \cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i = -1) \\ \Sigma_{\text{i is nearer to l},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{ \text{i is nearer to r},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i \neq -1) \end{array} \right.   
   1063   
   1064 $
   1065 
   1066 For simplicity, this formula omits some edge cases. Readers are encouraged to fill in the details themselves.
   1067 
   1068 The complexity seems high, but the problem can be solved with one key observation: the upper bound of $s_i$ is $O( \log n)$.
   1069 
   1070 Proof: let's fix a position $i$ and only consider the cells $c_1, c_2, ..., c_k$ $(c_1 \lt c_2 \lt ... \lt c_k)$ to the left of $i$ that cause $s_i$ to increase. We can see that $i - c_j \gt 2(i - c_{j+1})$. Otherwise, $c_{j+1}$ would cause $s_{c_j}$ to increase by $1$ instead of $s_i$. Thus, We can get $k$ is $O( \log n)$.
   1071 
   1072 Complexity: $O(n^3 \log^3n)$.
   1073 
   1074 **solution**
   1075 
   1076 ```
   1077 #include <map>
   1078 #include <set>
   1079 #include <cmath>
   1080 #include <ctime>
   1081 #include <queue>
   1082 #include <stack>
   1083 #include <cstdio>
   1084 #include <cstdlib>
   1085 #include <vector>
   1086 #include <cstring>
   1087 #include <algorithm>
   1088 #include <iostream>
   1089 #include <bitset>
   1090 #include <unordered_map>
   1091 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   1092 using namespace std;
   1093 typedef double db;
   1094 typedef long long ll;
   1095 typedef unsigned long long ull;
   1096 const int N=110;
   1097 const int LOGN=10;
   1098 const ll  TMD=998244353;
   1099 const ll  INF=2147483647;
   1100 int T,n;
   1101 ll s[N],fac[N],inv[N];
   1102 ll dp[N][N][LOGN][LOGN];
   1103 
   1104 void init_C()
   1105 {
   1106 	fac[0]=1;
   1107 	for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
   1108 	inv[N-1]=pw(fac[N-1],TMD-2);
   1109  	for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%TMD;
   1110 }
   1111 
   1112 ll C(int n,int m)
   1113 {
   1114 	if(n<m||n<0||m<0) return 0;
   1115 	return fac[n]*inv[m]%TMD*inv[n-m]%TMD;
   1116 }
   1117 
   1118 void init()
   1119 {
   1120     cin>>n;
   1121     for(int i=1;i<=n;i++) cin>>s[i];
   1122     for(int i=1;i<=n+4;i++)
   1123         for(int j=1;j<=n+4;j++)
   1124             for(int ii=0;ii<LOGN;ii++)
   1125                 for(int jj=0;jj<LOGN;jj++)
   1126                     dp[i][j][ii][jj]=0;
   1127     dp[1][1][0][1]=(s[1]<1);
   1128     for(int i=2;i<=n;i++)
   1129         dp[i][i][1][0]=(s[i]<1);
   1130     for(int i=1;i<=n;i++)   //auxiliary value
   1131         dp[i][i-1][0][0]=dp[i+1][i][0][0]=1;
   1132 }
   1133 
   1134 int ABS(int x)
   1135 {
   1136     return x<0?-x:x;
   1137 }
   1138 
   1139 void solve()
   1140 {
   1141     for(int i=2;i<=n;i++)
   1142     {
   1143         for(int j=1;j+i-1<=n;j++)
   1144         {
   1145             for(int ii=0;ii<LOGN;ii++)
   1146             {
   1147                 for(int jj=0;jj<LOGN;jj++)
   1148                 {
   1149                      int l=j,r=j+i-1;
   1150                      for(int k=l;k<=r;k++)
   1151                      {
   1152                          int tagl=0,tagr=0;
   1153                          if(l==1&&r==n) tagl=tagr=0;
   1154                          else if(l==1) tagr=1;
   1155                          else if(r==n) tagl=1;
   1156                          else
   1157                          {
   1158                              if(ABS(l-1-k)<=ABS(k-(r+1))) tagl=1;
   1159                              else tagr=1;
   1160                          }
   1161                          if(ii-tagl<0||jj-tagr<0) continue;
   1162                          if(s[k]==-1)
   1163                          {
   1164                              ll suml=0,sumr=0;
   1165                              for(int kk=0;kk<LOGN;kk++) suml=(suml+dp[l][k-1][ii-tagl][kk])%TMD;
   1166                              for(int kk=0;kk<LOGN;kk++) sumr=(sumr+dp[k+1][r][kk][jj-tagr])%TMD;
   1167                             dp[l][r][ii][jj]=(dp[l][r][ii][jj]+suml*sumr%TMD*C(r-l,k-l))%TMD;
   1168                         }
   1169                          else
   1170                          {
   1171                              for(int kk=0;kk<LOGN;kk++)
   1172                              {
   1173                                  if(s[k]-kk<0||s[k]-kk>=LOGN) continue;
   1174                                  dp[l][r][ii][jj]=(dp[l][r][ii][jj]+dp[l][k-1][ii-tagl][kk]*dp[k+1][r][s[k]-kk][jj-tagr]%TMD*C(r-l,k-l))%TMD;
   1175                              }
   1176                          }
   1177                      }
   1178                 }
   1179             }
   1180         }
   1181     }
   1182     cout<<dp[1][n][0][0]<<'\n';
   1183 }
   1184 
   1185 int main()
   1186 {
   1187     fastio;
   1188 
   1189     init_C();
   1190 
   1191     cin>>T;
   1192 	while(T--)
   1193 	{
   1194 		init();
   1195 		solve();
   1196 	}
   1197 
   1198 	return 0;
   1199 }
   1200 ```
   1201 
   1202 **Rate the Problem**
   1203 
   1204 Amazing problem:
   1205 
   1206 Good problem:
   1207 
   1208 Average problem:
   1209 
   1210 Bad problem:
   1211 
   1212 Didn't solve:
   1213 
   1214 #### [D1E Induced Graph Queries](https://codeforces.com/contest/2129/problem/E)
   1215 
   1216 **Fun**
   1217 
   1218 Come up with an O(n log^4 n) solution using a persistent multidimensional segment tree with Trie that supports rectangle update XOR.
   1219 
   1220 **Hint1**
   1221 
   1222 Find the nature of the problem and recall the data structures and algorithms learned. What can we utilize?
   1223 
   1224 **Hint2**
   1225 
   1226 Consider a standard Mo's algorithm. Why it doesn't work in this problem?
   1227 
   1228 **Hint3**
   1229 
   1230 Recalling the Handshake Theorem: $\Sigma_{i=1}^n degree_i=2m$.
   1231 
   1232 **Hint4**
   1233 
   1234 Consider a variation of Mo's algorithm.
   1235 
   1236 **Hint5**
   1237 
   1238 How to find the $k$-th smallest value without $O( \log n)$ complexity?
   1239 
   1240 **Tutorial**
   1241 
   1242 We found that merging the $f$ values of two intervals is a bit difficult. However, if we want to add a single node to the graph, it is relatively easy to update the $f$ value using brute force. This inspires us to use the Mo's algorithm.
   1243 
   1244 If we use the standard Mo's Algorithm, when expanding the interval from $[l, r]$ to $[l, r+1]$, we need to examine all edges connected to $r+1$ and update the node degrees accordingly. We define a cost array: $cost_i=degree_i+1$. The cost of update node $r+1$ is $cost_{r+1}$.
   1245 
   1246 However, if a node has a high degree, repeatedly processing it in Mo's Algorithm could lead to big time complexity.
   1247 
   1248 We leverage the Handshaking Lemma to use modified Mo's Algorithm to efficiently handle the queries.
   1249 
   1250 Recall that the Mo's algorithm relatively evenly divides array indices into blocks according to array length and assigns block numbers. Here, our dividinging strategy is different: we "relatively evenly" divide the array into blocks based on the prefix sum value of the $cost$ array. Specifically, we calculate the prefix sum of the cost array $precost$, using $\frac{precost_i}{B}$ as the block number of node $i$, where $B$ is the block length parameter.
   1251 
   1252 Assuming we have a data structure that can maintain the value of $k$-th smallest value in $O(1)$, using the same analysis method as standard Mo's algorithm, we can get the complexity is $O((n+m+q)\sqrt{n+m})$.
   1253 
   1254 To find the $k$-th smallest value without $O( \log n)$ complexity, we only need to maintain two arrays $cnt$ and $sum$, where $cnt_i$ is the occurrence of value $i$, and $sum_i=\Sigma_{j=(i-1)B+1}^{iB}cnt_j$ ($B$ is the block length parameter). We can perform modification in $O(1)$ and query in $O(\sqrt{n})$. The complexity is $O((n+q)\sqrt{n})$.
   1255 
   1256 Regarding implementation, you need to pay attention to two common pitfalls:
   1257 
   1258 * If you use $cost_i=degree_i$ instead of $cost_i=degree_i+1$, the dividing algorithm doesn't work for the graph with many nodes with degree $0$.
   1259 * Similarly, you can not set $B=\sqrt{m}$.
   1260 
   1261 **solution**
   1262 
   1263 ```
   1264 #include<bits/stdc++.h>
   1265 using namespace std;
   1266 
   1267 #define all(a) a.begin(),a.end()
   1268 #define pb push_back
   1269 #define sz(a) ((int)a.size())
   1270 
   1271 using ll=long long;
   1272 using u32=unsigned int;
   1273 using u64=unsigned long long;
   1274 using i128=__int128;
   1275 using u128=unsigned __int128;
   1276 using f128=__float128;
   1277 
   1278 using pii=pair<int,int>;
   1279 using pll=pair<ll,ll>;
   1280 
   1281 template<typename T> using vc=vector<T>;
   1282 template<typename T> using vvc=vc<vc<T>>;
   1283 template<typename T> using vvvc=vc<vvc<T>>;
   1284 
   1285 using vi=vc<int>;
   1286 using vll=vc<ll>;
   1287 using vvi=vc<vi>;
   1288 using vvll=vc<vll>;
   1289 
   1290 #define vv(type,name,n,...) \
   1291     vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
   1292 #define vvv(type,name,n,m,...) \
   1293     vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
   1294 
   1295 template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
   1296 template<typename T> using max_heap=priority_queue<T>;
   1297 
   1298 // https://trap.jp/post/1224/
   1299 #define rep1(n) for(ll i=0; i<(ll)(n); ++i)
   1300 #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
   1301 #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
   1302 #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
   1303 #define cut4(a,b,c,d,e,...) e
   1304 #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
   1305 #define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
   1306 #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
   1307 #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
   1308 #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
   1309 #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
   1310 #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
   1311 
   1312 template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
   1313 template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}
   1314 
   1315 template<typename T>
   1316 void sort_unique(vector<T> &vec){
   1317     sort(vec.begin(),vec.end());
   1318     vec.resize(unique(vec.begin(),vec.end())-vec.begin());
   1319 }
   1320 
   1321 template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
   1322 template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}
   1323 
   1324 template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
   1325 template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}
   1326 
   1327 #ifdef i_am_noob
   1328 #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
   1329 template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
   1330 template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
   1331 template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
   1332 template<typename T> void _do(T && x) {cerr << x << endl;}
   1333 template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
   1334 #else
   1335 #define bug(...) 777771449
   1336 #endif
   1337 
   1338 template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
   1339 template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
   1340 template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
   1341 template<typename T> void print(T && x) {cout << x << "\n";}
   1342 template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}
   1343 
   1344 template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}
   1345 
   1346 vvi read_graph(int n, int m, int base=1){
   1347     vvi adj(n);
   1348     for(int i=0,u,v; i<m; ++i){
   1349         cin >> u >> v,u-=base,v-=base;
   1350         adj[u].pb(v),adj[v].pb(u);
   1351     }
   1352     return adj;
   1353 }
   1354 
   1355 vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}
   1356 
   1357 template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}
   1358 
   1359 template<typename T> constexpr T inf=0;
   1360 template<> constexpr int inf<int> = 0x3f3f3f3f;
   1361 template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;
   1362 
   1363 template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}
   1364 
   1365 template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}
   1366 
   1367 #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
   1368 
   1369 //#include<atcoder/all>
   1370 //using namespace atcoder;
   1371 
   1372 //using mint=modint998244353;
   1373 //using mint=modint1000000007;
   1374 
   1375 const int N=1<<18,K=1<<10;
   1376 
   1377 struct DS{
   1378     int big[N/K],small[N];
   1379     void ins(int x){
   1380         small[x]++;
   1381         big[x>>10]++;
   1382     }
   1383     void del(int x){
   1384         small[x]--;
   1385         big[x>>10]--;
   1386     }
   1387     int kth(int k){
   1388         k--;
   1389         int cur=0;
   1390         while(big[cur]<=k) k-=big[cur++];
   1391         cur<<=10;
   1392         while(small[cur]<=k) k-=small[cur++];
   1393         return cur;
   1394     }
   1395 }ds;
   1396 
   1397 void ahcorz(){
   1398     int n,m; cin >> n >> m;
   1399     vvi adj=read_graph(n,m);
   1400     vi block(n);
   1401     int cur=0;
   1402     rep(n){
   1403         if(cur>=n) break;
   1404         int tot=0;
   1405         while(cur<n&&tot<K){
   1406             tot+=sz(adj[cur])+1;
   1407             block[cur++]=i;
   1408         }
   1409     }
   1410     int q; cin >> q;
   1411     vc<array<int,4>> qq(q);
   1412     vi res(q);
   1413     rep(q){
   1414         int l,r,k; cin >> l >> r >> k; l--,r--;
   1415         qq[i]={l,r,k,i};
   1416     }
   1417     sort(all(qq),[&](array<int,4> arr1, array<int,4> arr2){
   1418         if(block[arr1[0]]!=block[arr2[0]]) return block[arr1[0]]<block[arr2[0]];
   1419         if(block[arr1[0]]&1) return arr1[1]>arr2[1];
   1420         else return arr1[1]<arr2[1];
   1421     });
   1422     vi val(n);
   1423     int l=0,r=0;
   1424     ds.ins(0);
   1425     auto ins=[&](int i){
   1426         for(auto j: adj[i]){
   1427             if(j>=l&&j<=r){
   1428                 ds.del(val[j]);
   1429                 val[j]^=i+1,val[i]^=j+1;
   1430                 ds.ins(val[j]);
   1431             }
   1432         }
   1433         ds.ins(val[i]);
   1434     };
   1435     auto del=[&](int i){
   1436         ds.del(val[i]);
   1437         for(auto j: adj[i]){
   1438             if(j>=l&&j<=r){
   1439                 ds.del(val[j]);
   1440                 val[j]^=i+1,val[i]^=j+1;
   1441                 ds.ins(val[j]);
   1442             }
   1443         }
   1444     };
   1445     auto gogo=[&](int l2, int r2){
   1446         while(l>l2){
   1447             ins(l-1);
   1448             l--;
   1449         }
   1450         while(r<r2){
   1451             ins(r+1);
   1452             r++;
   1453         }
   1454         while(l<l2){
   1455             l++;
   1456             del(l-1);
   1457         }
   1458         while(r>r2){
   1459             r--;
   1460             del(r+1);
   1461         }
   1462     };
   1463     for(auto [l2,r2,k,i]: qq){
   1464         gogo(l2,r2);
   1465         res[i]=ds.kth(k);
   1466     }
   1467     rep(i,l,r+1) ds.del(val[i]);
   1468     rep(q) print(res[i]);
   1469 }
   1470 
   1471 signed main(){
   1472     ios_base::sync_with_stdio(0),cin.tie(0);
   1473     cout << fixed << setprecision(20);
   1474     int t=1;
   1475     cin >> t;
   1476     while(t--) ahcorz();
   1477 }
   1478 ```
   1479 
   1480 **Rate the Problem**
   1481 
   1482 Amazing problem:
   1483 
   1484 Good problem:
   1485 
   1486 Average problem:
   1487 
   1488 Bad problem:
   1489 
   1490 Didn't solve:
   1491 
   1492 #### [D1F1 Top-K Tracker (Easy Version)](https://codeforces.com/contest/2129/problem/F1) and [D1F2 Top-K Tracker (Hard Version)](https://codeforces.com/contest/2129/problem/F2)
   1493 
   1494 **Fun**
   1495 
   1496 Did you notice the double meaning of the title?
   1497 
   1498 **Hint1**
   1499 
   1500 Consider easy version. Try to use only operation $1$ and $3$ (Due to symmetry, using operation $2$ and $4$ is the same), and only use $m=30$ in operation $1$ and $m=300$ in operation $3$.
   1501 
   1502 **Hint2**
   1503 
   1504 Let $S_i$ represent the set in which queries element $i$ is accessed. Make all $S_i$ different to distinguish all elements.
   1505 
   1506 **Hint3**
   1507 
   1508 Greedily choose all $S_i$ such that $|S_i| \lt 3$. Afterwards, carefully construct a set of size $3$ to reach the upper bound.
   1509 
   1510 **Hint4**
   1511 
   1512 Suppose there are $30$ numbers $1, 2, …, 30$, and each number can be used up to $30$ times. Can you construct $900$ distinct triplets?
   1513 
   1514 **Hint5**
   1515 
   1516 Consider hard version. How to efficiently utilize the four operations, and the condition $m \gt k$?
   1517 
   1518 **Hint6**
   1519 
   1520 Using operation $1$ and operation $4$ is enough. Due to symmetry, using operation $2$ and $3$ is the same.
   1521 
   1522 **Hint7**
   1523 
   1524 Recall the bottleneck of the easy version. We used too many sets of size $3$. Let’s say it another way — too many elements were determined at the cost of $3$. How to optimize it?
   1525 
   1526 **Hint8**
   1527 
   1528 Consider $S_i=S_j$. This actually provides an unordered pair. In other words, we know unordered pair $(p_i,p_j)=(x,y)$, but we can not determine whether $p_i=x$ or $p_j=x$. To determine it, we can add one of $x$ or $y$ to the query of type $4$.
   1529 
   1530 **Hint9**
   1531 
   1532 Suppose there are $300$ unordered pairs $(x_1, y_1), (x_2, y_2), …, (x_{300}, y_{300})$. We can add one element of $(x_i, y_i)$ into query $4$, then query to determine all unordered pairs. However, the average cost is still near to $3$, which is no better than the easy version.
   1533 
   1534 **Hint10**
   1535 
   1536 Try to determine $435$ unordered pairs using single query $4$.
   1537 
   1538 **Tutorial (easy version)**
   1539 
   1540 Use only operation $1$ and $3$, with $m=30$ in operation $1$ and $m=300$ in operation $3$.
   1541 
   1542 Let $S_i$ represent the set accessed by query element $i$. To distinguish all elements, we need to ensure that all $S_i$ ($1 \le i \le n$) are distinct.
   1543 
   1544 After selecting all $S_i$ such that $|S_i| \lt 3$, we must also construct a set of size $3$ to reach the upper bound.
   1545 
   1546 Another way to phrase this: We have $30$ numbers $1, 2, \ldots, 30$, where $1$ through $29$ can each be used $30$ times, and $30$ can be used $270$ times. The goal is to construct as many distinct triplets as possible to maximize the count.
   1547 
   1548 A natural approach is to prioritize consuming the usage count of $30$. Since $29$ is prime, the sequence $x = [1, k \mod 29 + 1, 2k \mod 29 + 1, \ldots, 28k \mod 29 + 1]$ ensures all elements are distinct. For $1 \le k \le 9$, we can construct triplets $(x_1, x_2, 30), (x_2, x_3, 30), \ldots, (x_{29}, x_1, 30)$.
   1549 
   1550 After this, $1$ through $29$ will each have $12$ remaining uses, and $30$ will have $9$ remaining uses. This distribution is not ideal. Instead, we can use $(1, 2, 3)$ and $(4, 5, 6)$ in place of $(1, 2, 30), (3, 4, 30),$ and $(5, 6, 30)$. This adjustment ensures that $1$ through $30$ each have $12$ remaining uses.
   1551 
   1552 Define a **perfect set** $S_x$ as a set of triplets where each number from $1$ to $x$ appears exactly once.
   1553 
   1554 For numbers $1, 2, \ldots, 3l$, define:
   1555 
   1556 * $al = [1, 2, \ldots, l]$,
   1557 * $am = [l+1, l+2, \ldots, 2l]$,
   1558 * $ar = [2l+1, 2l+2, \ldots, 3l]$.
   1559 
   1560 Let $\text{lshift}(a, i) = [a_{1+i}, a_{2+i}, \ldots, a_{(n+i-1) \mod n + 1}]$. Then, define:
   1561 
   1562 $ S_l(\text{al}, \text{am}, \text{ar}) = \{(\text{al}_1, \text{am}_1, \text{ar}_1), (\text{al}_2, \text{am}_2, \text{ar}_2), \ldots, (\text{al}_l, \text{am}_l, \text{ar}_l)\} $
   1563 
   1564 We can generate $l^2$ distinct perfect sets of the form $S_l(al, \text{lshift}(am, i), \text{lshift}(ar, j))$ for $0 \le i, j \le l$.
   1565 
   1566 Now that all numbers have equal remaining usage counts, we can apply the above construction.
   1567 
   1568 Using the above construction, there are many different approaches.
   1569 
   1570 Overall, we can construct a total of $846$ distinct sets, which is sufficient to pass the easy version.
   1571 
   1572 **Tutorial (hard version)**
   1573 
   1574 The hard version differs significantly from the easy version in its approach, particularly in utilizing the concept of distinguishing elements through $S_i$.
   1575 
   1576 We need to efficiently utilize the four operations, and the condition $m \gt k$.
   1577 
   1578 In this solution, use operation $2$ $29$ times and operation $3$ once.
   1579 
   1580 Consider all sets $S_i$ with $|S_i| \lt 3$ and elements in $[1,29]$, assigning each to exactly two indices, yielding $2×(1+29+\frac{29×28}{2})=872$ sets forming 436 unordered pairs where $S_i=S_j$, where we cannot initially determine whether $pos_i = x$ or $pos_j = x$.
   1581 
   1582 Consider $S_i = S_j$. This actually provides an unordered pair $(pos_i, pos_j) = (x, y)$, where we know the pair of positions but cannot determine whether $pos_i = x$ and $pos_j = y$, or $pos_i = y$ and $pos_j = x$.
   1583 
   1584 Let these $\frac{872}{2} = 436$ pairs be denoted as $(pos_1, pos_n), (pos_2, pos_{n-1}), \ldots, (pos_{436}, pos_{n-435})$ (for convenience, we assume $n = 890$). Then, randomly select exactly one $pos$ from each of these pairs, and query the maximum value (considering only one maximum for now) among $p[pos_1 \text{ or } pos_n], p[pos_2 \text{ or } pos_{n-1}], \ldots$.
   1585 
   1586 Let us analyze what will happen:
   1587 
   1588 | Return Value | Pairs Determined | Probability |
   1589 | --- | --- | --- |
   1590 | $n$ | $1$ | $\frac{1}{2}$ |
   1591 | $n-1$ | $2$ | $\frac{1}{4}$ |
   1592 | $n-2$ | $3$ | $\frac{1}{8}$ |
   1593 | ... | ... | ... |
   1594 
   1595 We can see ehe expected number of resolved pairs per query:
   1596 
   1597 $1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{8} + \dots \approx 2$
   1598 
   1599 With an expectation value of $2$, we can estimate that performing $\text{max}$ query $300$ times yields a high probability $P \approx 1$ of determining all $436$ unordered pairs $(pos_i, pos_j)$. This implies that a single application of operation $3$ suffices to resolve all such pairs.
   1600 
   1601 Through this methodology, we successfully determine $872$ elements of the permutation $p$. At this stage, $29$ query operations remain available (with exactly $2$ uses permitted), and the determination of all $n=890$ elements becomes computationally tractable.
   1602 
   1603 **Failure probability analysis**
   1604 
   1605 Mathematically, this follows a geometric distribution with success probability $p = \frac{1}{2}$ where $\mathbb{P}(X = i) = 2^{-i}$, and the sum of such geometric random variables yields a negative binomial distribution $\text{NB}(r,p)$. For large $n$, this can be approximated by a normal distribution $\mathcal{N}(\mu, \sigma^2)$ via the Central Limit Theorem, where $\mu = \frac{1}{p} = 2$ and $\sigma^2 = \frac{1-p}{p^2} = 2$.
   1606 
   1607 ## Probability that $\sum_{i=1}^{300} X_i \le 435$
   1608 
   1609 **Given.** $X$ is discrete with $ \mathbb{P}(X=k)=2^{-k},\; k=1,2,\dots$. Thus $X\sim\mathrm{Geom}(p=\tfrac12)$ on ${1,2,\dots}$ with mean $1/p=2$.
   1610 
   1611 ### 1) Sum–negative-binomial connection
   1612 
   1613 Let $S=\sum_{i=1}^{300} X_i$. The sum of i.i.d. $\mathrm{Geom}(p)$ variables is negative binomial:
   1614 
   1615 $ S \sim \mathrm{NB}(r=300,\;p=\tfrac12), $
   1616 
   1617 i.e., $S$ is the number of Bernoulli$(\tfrac12)
   1618 
   1619 Unable to parse markup [type=CF_MATHJAX]
   1620 
   1621 successes.
   1622 
   1623 ### 2) Convert to a binomial tail
   1624 
   1625 $ \mathbb{P}(S \le 435) = \mathbb{P}\big(\text{300th success occurs by time }435\big) = \mathbb{P}\big(\mathrm{Bin}(n=435,p=\tfrac12)\ge 300\big). $
   1626 
   1627 ### 3) Exact expression
   1628 
   1629 By symmetry of the binomial with $p=\tfrac12$,
   1630 
   1631 $ \mathbb{P}\big(\mathrm{Bin}(435,\tfrac12)\ge 300\big) = \sum_{k=300}^{435} \binom{435}{k} 2^{-435} = \sum_{k=0}^{135} \binom{435}{k} 2^{-435}. $
   1632 
   1633 ### 4) Numerical value
   1634 
   1635 $ \boxed{\;\mathbb{P}\!\left(\sum_{i=1}^{300} X_i \le 435\right) \;\approx\; 8.61\times 10^{-16}\;} $
   1636 
   1637 ### 5) Sanity check (normal approximation to the binomial)
   1638 
   1639 With $\mu = np = 217.5$, $\sigma=\sqrt{np(1-p)}=\sqrt{108.75}\approx 10.428$, and continuity correction,
   1640 
   1641 $ z=\frac{299.5-\mu}{\sigma}\approx 7.86 \quad\Rightarrow\quad \mathbb{P}(Z\ge z)\approx 1.87\times 10^{-15}, $
   1642 
   1643 which is of the same (tiny) order as the exact value above.
   1644 
   1645 **solution (easy version)**
   1646 
   1647 ```
   1648 #include <map>
   1649 #include <set>
   1650 #include <cmath>
   1651 #include <ctime>
   1652 #include <queue>
   1653 #include <stack>
   1654 #include <cstdio>
   1655 #include <cstdlib>
   1656 #include <vector>
   1657 #include <cstring>
   1658 #include <algorithm>
   1659 #include <iostream>
   1660 #include <bitset>
   1661 #include <unordered_map>
   1662 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   1663 using namespace std;
   1664 typedef double db;
   1665 typedef long long ll;
   1666 typedef unsigned long long ull;
   1667 const int N=1010;
   1668 int T,n;
   1669 vector<int> Sv[N],Sp[N];
   1670 
   1671 void init()
   1672 {
   1673     cin>>n;
   1674     for(int i=1;i<N;i++)
   1675         Sv[i].clear(),Sp[i].clear();
   1676 }
   1677 
   1678 vector<int> ask(int ty,vector<int> &v)
   1679 {
   1680     cout<<ty<<" "<<v.size();
   1681     for(int i=0;i<v.size();i++)
   1682         cout<<" "<<v[i];
   1683     cout<<"\n"<<flush;
   1684     int k;
   1685     if(ty<3) k=min(60,(int)v.size());
   1686     else k=min(300,(int)v.size());
   1687     vector<int> res;
   1688     for(int i=1;i<=k;i++)
   1689     {
   1690         int t;
   1691         cin>>t;
   1692         res.push_back(t);
   1693     }
   1694     return res;
   1695 }
   1696 
   1697 void solve()
   1698 {
   1699     int cnt=0;
   1700     vector<int> p(n+4);
   1701     for(int i=1;i<=30;i++)
   1702         Sv[++cnt].push_back(i);
   1703     for(int i=1;i<=30;i++)
   1704     {
   1705         for(int j=i+1;j<=30;j++)
   1706         {
   1707             cnt++;
   1708             Sv[cnt].push_back(i),Sv[cnt].push_back(j);
   1709         }
   1710     }
   1711     for(int i=1;i<=9;i++)
   1712     {
   1713         int cur=1;
   1714         while(1)
   1715         {
   1716             int nxt=cur+i;
   1717             if(nxt>29) nxt-=29;
   1718             cnt++;
   1719             Sv[cnt].push_back(30);
   1720             Sv[cnt].push_back(cur);
   1721             Sv[cnt].push_back(nxt);
   1722             cur=nxt;
   1723             if(nxt==1) break;
   1724         }
   1725     }
   1726     vector<int> vl(11),vm(11),vr(11);
   1727     for(int i=1;i<=10;i++)
   1728         vl[i]=i,vm[i]=10+i,vr[i]=20+i;
   1729     for(int i=1;i<=9;i++)
   1730     {
   1731         for(int j=1;j<=10;j++)
   1732         {
   1733             cnt++;
   1734             Sv[cnt].push_back(vl[j]);
   1735             Sv[cnt].push_back(vm[j]);
   1736             Sv[cnt].push_back(vr[j]);
   1737         }
   1738         for(int j=0;j<10;j++)
   1739             vr[j]=vr[j+1];
   1740         vr[10]=vr[0];
   1741     }
   1742     for(int i=1,cur=1;i<=29;i++)
   1743     {
   1744         int x=cur,y=cur+1,z=cur+2;
   1745         while(x>29) x-=29;
   1746         while(y>29) y-=29;
   1747         while(z>29) z-=29;
   1748         cnt++;
   1749         Sv[cnt].push_back(x);
   1750         Sv[cnt].push_back(y);
   1751         Sv[cnt].push_back(z);
   1752         cur+=3;
   1753     }
   1754     for(int i=1;i<=30;i++)
   1755     {
   1756         vector<int> v,t;
   1757         for(int j=1;j<=n;j++)
   1758             if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
   1759                 v.push_back(j);
   1760         if(v.empty()) continue;
   1761         if(i<30) t=ask(2,v);
   1762         else t=ask(4,v);
   1763         for(int j=0;j<t.size();j++)
   1764             Sp[t[j]].push_back(i);
   1765     }
   1766     for(int i=1;i<=n;i++)
   1767          sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
   1768     for(int i=1;i<=n;i++)
   1769         for(int j=1;j<=n;j++)
   1770             if((!Sp[i].empty())&&Sp[i]==Sv[j]) p[i]=j;
   1771     cout<<"! ";
   1772     for(int i=1;i<=n;i++)
   1773         cout<<p[i]<<(i==n?'\n':' ');
   1774     cout<<flush;
   1775 }
   1776 
   1777 int main()
   1778 {
   1779     fastio;
   1780 
   1781     cin>>T;
   1782 	while(T--)
   1783 	{
   1784 		init();
   1785 		solve();
   1786 	}
   1787 
   1788 	return 0;
   1789 }
   1790 ```
   1791 
   1792 **solution (hard version)**
   1793 
   1794 ```
   1795 #include <map>
   1796 #include <set>
   1797 #include <cmath>
   1798 #include <ctime>
   1799 #include <queue>
   1800 #include <stack>
   1801 #include <cstdio>
   1802 #include <cstdlib>
   1803 #include <vector>
   1804 #include <cstring>
   1805 #include <algorithm>
   1806 #include <iostream>
   1807 #include <bitset>
   1808 #include <unordered_map>
   1809 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   1810 using namespace std;
   1811 typedef double db;
   1812 typedef long long ll;
   1813 typedef unsigned long long ull;
   1814 const int N=1010;
   1815 int T,n;
   1816 vector<int> Sv[N],Sp[N],prv[N],prp[N];
   1817 
   1818 void init()
   1819 {
   1820     srand(time(0));
   1821     cin>>n;
   1822     for(int i=1;i<N;i++)
   1823         Sv[i].clear(),Sp[i].clear(),prv[i].clear(),prp[i].clear();
   1824 }
   1825 
   1826 vector<int> ask(int ty,vector<int> &v)
   1827 {
   1828     cout<<ty<<" "<<v.size();
   1829     for(int i=0;i<v.size();i++)
   1830         cout<<" "<<v[i];
   1831     cout<<"\n"<<flush;
   1832     int k;
   1833     if(ty<3) k=min(60,(int)v.size());
   1834     else k=min(300,(int)v.size());
   1835     vector<int> res;
   1836     for(int i=1;i<=k;i++)
   1837     {
   1838         int t;
   1839         cin>>t;
   1840         res.push_back(t);
   1841     }
   1842     return res;
   1843 }
   1844 
   1845 void solve()
   1846 {
   1847     int cnt=0,cntr=871,cntpr=30;
   1848     vector<int> p(n+4);
   1849     for(int i=1;i<=29;i++)
   1850     {
   1851         cnt++;
   1852         Sv[cnt].push_back(i);
   1853         cntr--;
   1854         Sv[cntr].push_back(i);
   1855     }
   1856     for(int i=1;i<=29;i++)
   1857     {
   1858         for(int j=i+1;j<=29;j++)
   1859         {
   1860             cnt++;
   1861             Sv[cnt].push_back(i),Sv[cnt].push_back(j);
   1862             cntr--;
   1863             Sv[cntr].push_back(i),Sv[cntr].push_back(j);
   1864         }
   1865     }
   1866     for(int i=871,hd=1;i<890;i++,hd+=3)
   1867     {
   1868         int x=hd,y=hd+1,z=hd+2;
   1869         if(x>29) x-=29;
   1870         if(y>29) y-=29;
   1871         if(z>29) z-=29;
   1872         Sv[i].push_back(x),Sv[i].push_back(y),Sv[i].push_back(z);
   1873     }
   1874     for(int i=1;i<=29;i++)
   1875     {
   1876         vector<int> v,t;
   1877         for(int j=1;j<=n;j++)
   1878             if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
   1879                 v.push_back(j);
   1880         if(v.empty()) continue;
   1881         t=ask(2,v);
   1882         for(int j=0;j<t.size();j++)
   1883             Sp[t[j]].push_back(i);
   1884     }
   1885     for(int i=1;i<=n;i++)
   1886          sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
   1887     for(int i=1;i<=n;i++)
   1888     {
   1889         for(int j=871;j<=n;j++)
   1890             if(Sp[i]==Sv[j]) p[i]=j;
   1891     }
   1892     for(int i=1;i<=n;i++)
   1893     {
   1894         if(Sp[i].size()==1) prp[Sp[i][0]].push_back(i);
   1895         else if(Sp[i].size()==2) prp[30*Sp[i][0]+Sp[i][1]].push_back(i);    //hash the set
   1896         //|S|>2 and empty set are ignored
   1897     }
   1898     for(int i=1;i<=n;i++)
   1899     {
   1900         if(Sv[i].size()==1) prv[Sv[i][0]].push_back(i);
   1901         else if(Sv[i].size()==2) prv[30*Sv[i][0]+Sv[i][1]].push_back(i);    //hash the set
   1902     }
   1903     //necessary shuffle
   1904     for(int i=1;i<N;i++)
   1905     {
   1906         if(prp[i].size()<2) continue;
   1907         if(rand()&1) swap(prp[i][0],prp[i][1]);
   1908     }
   1909     for(int i=1;i<=1;i++)
   1910     {
   1911         vector<int> v,t;
   1912         for(int j=1;j<N;j++)
   1913         {
   1914             if(prp[j].empty()) continue;
   1915             else if(prp[j].size()==1)
   1916             {
   1917                 p[prp[j][0]]=prv[j][0];
   1918                 prp[j].clear();
   1919                 prv[j].clear();
   1920                 continue;
   1921             }
   1922             v.push_back(prp[j][0]);
   1923         }
   1924         if(v.empty()) continue;
   1925         t=ask(3,v);
   1926         for(int j=1;j<N;j++)
   1927         {
   1928             if(prp[j].empty()) continue;
   1929             if(t.empty()) break;
   1930             if(prv[j][1]==t.back())
   1931             {
   1932                 t.pop_back();
   1933                 p[prp[j][0]]=prv[j][1];
   1934                 p[prp[j][1]]=prv[j][0];
   1935             }
   1936             else
   1937             {
   1938                 p[prp[j][0]]=prv[j][0];
   1939                 p[prp[j][1]]=prv[j][1];
   1940             }
   1941             prp[j].clear();
   1942             prv[j].clear();
   1943         }
   1944     }
   1945     cout<<"! ";
   1946     for(int i=1;i<=n;i++)
   1947         cout<<p[i]<<(i==n?'\n':' ');
   1948     cout<<flush;
   1949 }
   1950 
   1951 int main()
   1952 {
   1953     fastio;
   1954 
   1955     cin>>T;
   1956 	while(T--)
   1957 	{
   1958 		init();
   1959 		solve();
   1960 	}
   1961 
   1962 	return 0;
   1963 }
   1964 ```
   1965 
   1966 **Rate the Problem**
   1967 
   1968 Amazing problem:
   1969 
   1970 Good problem:
   1971 
   1972 Average problem:
   1973 
   1974 Bad problem:
   1975 
   1976 Didn't solve: