codeforces-scrape

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

1937.md (63909B)


      1 Source: https://codeforces.com/blog/entry/126513
      2 
      3 Thank you for participation and we hope you enjoy this round :)
      4 
      5 #### [D2A — Shuffle Party](https://codeforces.com/contest/1937/problem/A)
      6 
      7 Idea : [chromate00](/profile/chromate00 "Эксперт chromate00")
      8 
      9 **Hint (for thinkers)**
     10 
     11 If you think in terms of $k$, it might be hard to find the solution. Maybe it will be helpful if you fix $d$ and find the $k$ which will be swapped with $d$.
     12 
     13 **Hint (for observers)**
     14 
     15 Try bruteforcing for, say, $n \le 20$. Do you see a pattern?
     16 
     17 **Tutorial**
     18 
     19 On $n=1$, the answer is trivially $1$.
     20 
     21 On $n=2$, index $1$ and $2$ are swapped. The answer is therefore $2$.
     22 
     23 For $n \gt 2$, let us assume the element $1$ is on index $a$ and it will be swapped with index $k$. Then, $a$ must be $k/2$. We will prove this by contradiction. Let us assume that there is no divisor greater than $a$, and $a$ is lesser than $k/2$. But then, as $a$ is a multiple of $2$ in the base condition, $k$ must be a multiple of $2$, and $k/2$ is a divisor of $k$. This contradicts the assumption. By induction we can see that $a$ is always a multiple of $2$, and this proof will always hold. The element $1$ will move only when $k/2=a$.
     24 
     25 Therefore, we can find the largest value of $v$ such that $2^v \le n$. The answer turns out to be $2^v$.
     26 
     27 **solution**
     28 
     29 ```
     30 #include<bits/stdc++.h>
     31 using namespace std;
     32 using ll=long long;
     33  
     34 int main()
     35 {
     36     cin.tie(0)->sync_with_stdio(0);
     37     ll q;cin>>q;
     38     while(q--)
     39     {
     40         ll n,p=1;cin>>n;
     41         while(p*2<=n)p<<=1;
     42         cout<<p<<"\n";
     43     }
     44 }
     45 ```
     46 
     47 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=lLmVzA49BRM>
     48 
     49 #### [D2B — Binary Path](https://codeforces.com/contest/1937/problem/B)
     50 
     51 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm")
     52 
     53 **Hint1**
     54 
     55 Let’s call path $(1,1) \rightarrow \ldots \rightarrow (1,i)\rightarrow(2,i) \rightarrow \ldots \rightarrow (2,n)$ the $i$-th path. What's the difference between the $i$-th path and the $(i+1)$-th path?
     56 
     57 **Hint2**
     58 
     59 What if $a_{2i}=1$ and $a_{1(i+1)}=0$ ?
     60 
     61 **Hint3**
     62 
     63 What if $a_{2i}=0$ and $a_{1(i+1)}=1$ ?
     64 
     65 **Tutorial**
     66 
     67 * Let the string achieved by moving down on the $i$-th column be $S_i$. Then, for any $1 \le k \lt n$, one can observe that $S_k$ and $S_{k+1}$ can only differ by at most one index, which is index $k+1$. Thus, comparing $S_k$ and $S_{k+1}$ lexicographically can be done in $O(1)$, by comparing this one index.
     68 * After finding the lexicographically smallest string, counting the occurrence of this string can be done straightforwardly in $O(n)$.
     69 * The implementation can differ for each participant, but the following method provides a clean implementation. Let the initial coordinate be $(1,1)$, and maintain a counter which is initially reset to $1$. Then repeat the following until we reach $(2,n)$:
     70 
     71 1. If we are on row $2$, move to the right.
     72 2. If we are on column $n$, move downwards.
     73 3. From here, let the character on the right be $a$, and one below be $b$.
     74 4. If $a \gt b$, move downwards.
     75 5. If $a \lt b$, move to the right and reset the counter to $1$.
     76 6. If $a=b$, move to the right and increment the counter.
     77 
     78 * In the end, the string on the path we passed through will be lexicographically smallest, and the integer on the counter will be the number of occurrences.
     79 
     80 **solution**
     81 
     82 ```
     83 #include <map>
     84 #include <set>
     85 #include <cmath>
     86 #include <ctime>
     87 #include <queue>
     88 #include <stack>
     89 #include <cstdio>
     90 #include <cstdlib>
     91 #include <vector>
     92 #include <cstring>
     93 #include <algorithm>
     94 #include <iostream>
     95 using namespace std;
     96 typedef double db; 
     97 typedef long long ll;
     98 typedef unsigned long long ull;
     99 const int N=1000010;
    100 const int LOGN=28;
    101 const ll  TMD=0;
    102 const ll  INF=2147483647;
    103 int  T,n;
    104 char a[3][N];
    105 
    106 int main()
    107 {
    108 	scanf("%d",&T);
    109 	while(T--)
    110 	{
    111     	        scanf("%d",&n);
    112 		for(int i=1;i<=2;i++)
    113 		{
    114 		    scanf("\n");
    115 			for(int j=1;j<=n;j++)
    116 				scanf("%c",&a[i][j]);
    117 		}
    118 		int max_down=n,min_down=1;
    119 		for(int i=n;i>=2;i--)
    120 			if(a[1][i]=='1'&&a[2][i-1]=='0') max_down=i-1;
    121 		for(int i=1;i<max_down;i++)
    122 			if(a[2][i]=='1'&&a[1][i+1]=='0') min_down=i+1;
    123 		for(int i=1;i<=max_down;i++) printf("%c",a[1][i]);
    124 		for(int i=max_down;i<=n;i++) printf("%c",a[2][i]);
    125 		printf("\n");
    126 		printf("%d\n",max_down-min_down+1);
    127 	}
    128 	
    129 	return 0;
    130 }
    131 ```
    132 
    133 #### [D1A — Bitwise Operation Wizard](https://codeforces.com/contest/1936/problem/A)
    134 
    135 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm")
    136 
    137 **Hint1**
    138 
    139 What's the maximum value of $p_i \oplus p_j$?
    140 
    141 **Hint2**
    142 
    143 How to get $i$, such that $p_i = n-1$?
    144 
    145 **Hint3**
    146 
    147 How to get $j$, such that $p_i \oplus p_j$ reaches the maximum value?
    148 
    149 **Tutorial**
    150 
    151 Step1:do queries $? \ x \ x \ y \ y$ like classic searching for the maximum value among $n$ numbers to get $p_i= n-1$;
    152 
    153 Step2:do queries $? \ x \ i \ y \ i$ to find all index $k$ such that $p_i | p_{k}$ reaches the maximum value. We store all such indexes in a vector $id$ .
    154 
    155 Step3:do queries $? \ id[x] \ id[x] \ id[y] \ id[y]$ to find $j$ in $id$ such that $p_j$ reaches the minimum value.
    156 
    157 **solution**
    158 
    159 ```
    160 #include <map>
    161 #include <set>
    162 #include <cmath>
    163 #include <ctime>
    164 #include <queue>
    165 #include <stack>
    166 #include <cstdio>
    167 #include <cstdlib>
    168 #include <vector>
    169 #include <cstring>
    170 #include <algorithm>
    171 #include <iostream>
    172 using namespace std;
    173 typedef double db; 
    174 typedef long long ll;
    175 typedef unsigned long long ull;
    176 const int N=1000010;
    177 const int LOGN=28;
    178 const ll  TMD=0;
    179 const ll  INF=2147483647;
    180 int T,n;
    181 
    182 char query(int a,int b,int c,int d)
    183 {
    184 	char x;
    185 	printf("? %d %d %d %d\n",a,b,c,d);
    186 	fflush(stdout);
    187 	cin>>x;
    188 	fflush(stdout);
    189 	return x;
    190 }
    191 
    192 int main()
    193 {	
    194 	scanf("%d",&T);
    195 	while(T--)
    196 	{
    197     	        scanf("%d",&n);
    198 		int mx=0,ans1=0,ans2;
    199 		vector<int> v;
    200 		for(int i=1;i<n;i++)
    201 		{
    202 			int c=query(ans1,ans1,i,i);
    203 			if(c=='<') ans1=i;
    204 		}
    205 		v.push_back(0);
    206 		for(int i=1;i<n;i++)
    207 		{
    208 			int c=query(mx,ans1,i,ans1);
    209 			if(c=='<')
    210 			{
    211 			    mx=i;
    212 			    v.clear();
    213 			    v.push_back(i);
    214 			}
    215 			else if(c=='=') v.push_back(i);
    216 		}
    217 		ans2=v[0];
    218 		for(int i=1;i<v.size();i++)
    219 		{
    220 			int c=query(ans2,ans2,v[i],v[i]);
    221 			if(c=='>') ans2=v[i];
    222 		}
    223 		printf("! %d %d\n",ans1,ans2);
    224 		fflush(stdout);
    225 	}
    226 	
    227 	return 0;
    228 }
    229 ```
    230 
    231 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=jfcx1Rs8I28>
    232 
    233 #### [D1B — Pinball](https://codeforces.com/contest/1936/problem/B)
    234 
    235 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm")
    236 
    237 **UPD**: It conflicts with <https://codeforces.com/contest/733/problem/E>. This is a coincidence. There are no excuses. Very sorry for any inconvenience caused to everyone.
    238 
    239 **Hint1**
    240 
    241 Observe: which cells actually change the direction of the pinball placed at position $p$ initially?
    242 
    243 **Hint2**
    244 
    245 These cells are the $ \gt $ to the left of $p$ and the $ \lt $ to the right of $p$. Can you see the trace of the pinball?
    246 
    247 **Hint3**
    248 
    249 How to quickly calculate the time when a pinball leaves the grid?
    250 
    251 **Tutorial**
    252 
    253 We observe that, in fact, only the $ \gt $ to the left of $p$ and the $ \lt $ to the right of $p$ change the direction of the pinball placed at position $p$ initially.
    254 
    255 For convenience, let's assume $s_p$ is $ \gt $, $k=min(countright(1,p),countleft(p+1,n))$, and the pinball leaves from the left boundary(for other situations, we can handle them in a similar way).
    256 
    257 We can obtain $right[1,\ldots,k]$ and $left[1,\ldots,k]$ through prefix sum + binary search, where $right$ represents the indices of $ \gt $ to the left of $p$ (in decreasing order), and $left$ represents the indices of $ \lt $ to the right of $p$ (in increasing order).
    258 
    259 We use $right$ and $left$ to describe the trace of the pinball:
    260 
    261 The first segment: the pinball moves from $right_1$ to $left_1$;
    262 
    263 The second segment: the pinball moves from $left_1$ to $right_2$;
    264 
    265 The third segment: the pinball moves from $right_2$ to $left_3$;
    266 
    267 $\ldots$
    268 
    269 The $2k$-th segment: the pinball moves from $left_k$ to the left boundary.
    270 
    271 It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves.
    272 
    273 **solution**
    274 
    275 ```
    276 #include <map>
    277 #include <set>
    278 #include <cmath>
    279 #include <ctime>
    280 #include <queue>
    281 #include <stack>
    282 #include <cstdio>
    283 #include <cstdlib>
    284 #include <vector>
    285 #include <cstring>
    286 #include <algorithm>
    287 #include <iostream>
    288 using namespace std;
    289 typedef double db; 
    290 typedef long long ll;
    291 typedef unsigned long long ull;
    292 const int N=1000010;
    293 const int LOGN=28;
    294 const ll  TMD=0;
    295 const ll  INF=2147483647;
    296 int  T,n;
    297 ll   Sl[N],Sr[N],IDl[N],IDr[N];
    298 char s[N];
    299 
    300 int findpre(int x)
    301 {
    302 	int L=0,R=n+1,M;
    303 	while(L+1!=R)
    304 	{
    305 		M=(L+R)>>1;
    306 		if(Sr[M]<x) L=M;
    307 		else R=M; 
    308 	}
    309 	return R;
    310 }
    311 
    312 int findsuf(int x)
    313 {
    314 	int L=0,R=n+1,M;
    315 	while(L+1!=R)
    316 	{
    317 		M=(L+R)>>1;
    318 		if(Sl[n]-Sl[M-1]<x) R=M;
    319 		else L=M; 
    320 	}
    321 	return L;
    322 }
    323 
    324 int main()
    325 {
    326 	scanf("%d",&T);
    327 	while(T--)
    328 	{
    329     	        scanf("%d%s",&n,s);
    330 		for(int i=1;i<=n;i++) 
    331 		{
    332 	  	  Sr[i]=Sr[i-1]+(s[i-1]=='>');
    333 	  	  Sl[i]=Sl[i-1]+(s[i-1]=='<');
    334  		  IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); 	
    335  		  IDl[i]=IDl[i-1]+i*(s[i-1]=='<'); 	
    336 		}		
    337 		for(int i=1;i<=n;i++)
    338 		{
    339 			if(s[i-1]=='>')
    340 			{
    341 				if(Sr[i]>Sl[n]-Sl[i])
    342 				{
    343 					int p=findpre(Sr[i]-(Sl[n]-Sl[i]));
    344 					printf("%I64d ",2*((IDl[n]-IDl[i])-(IDr[i]-IDr[p-1]))+i+(n+1));
    345 				}
    346 				else
    347 				{
    348 					int p=findsuf((Sl[n]-Sl[i])-Sr[i]+1);
    349 					printf("%I64d ",2*((IDl[p]-IDl[i])-(IDr[i]-IDr[0]))+i);
    350 				}
    351 			}
    352 			else
    353 			{
    354 				if(Sr[i]>=Sl[n]-Sl[i-1])
    355 				{
    356 					int p=findpre(Sr[i]-(Sl[n]-Sl[i-1])+1);
    357 					printf("%I64d ",2*((IDl[n]-IDl[i-1])-(IDr[i]-IDr[p-1]))-i+(n+1));
    358 				}
    359 				else
    360 				{
    361 					int p=findsuf((Sl[n]-Sl[i-1])-Sr[i]);
    362 					printf("%I64d ",2*((IDl[p]-IDl[i-1])-(IDr[i]-IDr[0]))-i);
    363 				}
    364 			}
    365 		}
    366 		printf("\n");
    367 	}
    368 	
    369 	return 0;
    370 }
    371 ```
    372 
    373 #### [D1C — Pokémon Arena](https://codeforces.com/contest/1936/problem/C)
    374 
    375 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm")
    376 
    377 **Hint1**
    378 
    379 In fact, you don't need to hire the same Pokemon more than once.
    380 
    381 **Hint2**
    382 
    383 Consider graph building.
    384 
    385 **Hint3**
    386 
    387 How to reduce the number of edges in the graph?
    388 
    389 **Tutorial**
    390 
    391 Let's consider $n$ Pokémon as nodes, and defeating Pokémon $u$ by Pokémon $v$ as the edge $u \rightarrow v$. Then the problem is essentially finding the shortest path from $n$ to $1$.
    392 
    393 If we brute force to construct the graph, the time complexity will be $O(n^2m)$, which is unacceptable. How can we find a better way to build the graph?
    394 
    395 Recalling, we need to represent all processes like "Pokémon $u$ increased attribute $x$ by some value and defeated Pokémon $v$" using paths in the graph.
    396 
    397 We will use the following graph building to achieve this. Overall, we consider each attribute separately. For the $x$-th attribute, we construct $2n$ virtual nodes $X_1,...,X_n$ and $Y_1,...,Y_n$, and connect each Pokémon based on the $x$-th attribute.
    398 
    399 For example, $n=3$ and $a_{1,1}=9, a_{2,1}=6, a_{3,1}=1$, we have the following graph building for attribute $1$:
    400 
    401 ![ aaa](/predownloaded/bb/a9/bba913da5f21ee7bbcae6a6d958db29b01006729.png)
    402 
    403 In this graph,for example,"Pokémon $3$ increased attribute $1$ by $8$ and defeated Pokémon $1$" can be represented as path $3 \rightarrow X1 \rightarrow X2 \rightarrow X3 \rightarrow Y3 \rightarrow 1$.
    404 
    405 More generally, our graph building method is :
    406 
    407 * Consider each attribute separately. Assuming we are processing the $i$-th attribute, insert all $a_{1,i} , \ldots ,a_{n,i}$ into $val$ and sort it (for convenience, we assume that they are pairwise different).
    408 * Construct $2n$ virtual nodes $X_1,...,X_n$ and $Y_1,...,Y_n$;
    409 * Add edge $X_i \rightarrow X_{i+1}$ with a value of $(val_{i+1}-val_i)$ for $1 \le i \lt n$;
    410 * Add edge $Y_{i+1} \rightarrow Y_{i}$ with a value of $0$ for $1 \le i \lt n$;
    411 * Add edge $X_i \rightarrow Y_{i}$ with a value of $0$ for $1 \le i \le n$;
    412 * Add edge $i \rightarrow X_{rank_i}$ with a value of $c_i$ for $1 \le i \le n$;
    413 * Add edge $Y_{rank_i} \rightarrow i$ with a value of $0$ for $1 \le i \le n$.
    414 
    415 Then we just run Dijkstra algorithm in this graph. The time complexity is $O(nmlog(nm))$.
    416 
    417 **solution**
    418 
    419 ```
    420 #include <bits/stdc++.h>
    421 #define int long long
    422 #define fi first
    423 #define se second
    424 
    425 using namespace std;
    426 
    427 const int INFF = 1e18;
    428 
    429 int32_t main()
    430 {
    431         ios_base::sync_with_stdio(false);
    432         cin.tie(NULL);
    433         
    434         int t;
    435         cin >> t;
    436 
    437         while (t --> 0) {
    438                 int n, m;
    439                 cin >> n >> m;
    440 
    441                 vector<int> c(n + 1);
    442                 for (int i = 1; i <= n; i++) cin >> c[i];
    443 
    444                 vector<vector<int>> a(n + 1, vector<int>(m + 1));
    445                 vector<vector<pair<int, int>>> b(m + 1);
    446                 for (int i = 1; i <= n; i++) {
    447                         for (int j = 1; j <= m; j++) {
    448                                 cin >> a[i][j];
    449 
    450                                 b[j].push_back({a[i][j], i});
    451                         }
    452                 }
    453 
    454                 vector<vector<int>> rank(n + 1, vector<int>(m + 1));
    455                 vector<vector<int>> dec(n + 1, vector<int>(m + 1));
    456                 for (int j = 1; j <= m; j++) {
    457                         sort(b[j].begin(), b[j].end());
    458 
    459                         for (int i = 0; i < n; i++) {
    460                                 auto [x, id] = b[j][i];
    461                                 rank[id][j] = i + 1;
    462                                 dec[i + 1][j] = id;
    463                         }
    464                 }
    465 
    466                 int ans = INFF;
    467                 vector<int> vis(n + 1, 0);
    468                 vector<vector<int>> dist(n + 1, vector<int>(m + 1, INFF));
    469                 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    470                 vis[1] = 1;
    471                 for (int j = 1; j <= m; j++) dist[1][j] = 0, pq.push({dist[1][j], 1, j});
    472                 while (!pq.empty()) {
    473                         auto [w, x, t] = pq.top();
    474                         pq.pop();
    475 
    476                         if (dist[x][t] < w) continue;
    477 
    478                         if (x == n) ans = min(ans, w + c[n]);
    479 
    480                         if (rank[x][t] < n) {
    481                                 int z = dec[rank[x][t] + 1][t];
    482                                 if (w < dist[z][t]) {
    483                                         dist[z][t] = w;
    484                                         pq.push({dist[z][t], z, t});
    485                                 }
    486                         }
    487 
    488                         if (rank[x][t] > 1) {
    489                                 int z = dec[rank[x][t] - 1][t];
    490                                 if (w + a[x][t] - a[z][t] < dist[z][t]) {
    491                                         dist[z][t] = w + a[x][t] - a[z][t];
    492                                         pq.push({dist[z][t], z, t});
    493                                 }
    494                         }
    495 
    496                         if (!vis[x]) {
    497                                 vis[x] = 1;
    498                                 for (int j = 1; j <= m; j++) {
    499                                         if (w + c[x] < dist[x][j]) {
    500                                                 dist[x][j] = w + c[x];
    501                                                 pq.push({dist[x][j], x, j});
    502                                         }
    503                                 }
    504                         }
    505                 }
    506 
    507                 cout << ans << '\n';
    508         }
    509         
    510         return 0;
    511 }
    512 ```
    513 
    514 Video editorial by [aryanc403](/profile/aryanc403 "Международный мастер aryanc403") <https://www.youtube.com/watch?v=ysdozposXkQ>
    515 
    516 #### [D1D — Bitwise Paradox](https://codeforces.com/contest/1936/problem/D)
    517 
    518 Idea : [Psychotic_D](/profile/Psychotic_D "Международный мастер Psychotic_D"), [MagicalFlower](/profile/MagicalFlower "Легендарный гроссмейстер MagicalFlower")
    519 
    520 **Tutorial**
    521 
    522 First we use the line segment tree to maintain sequence $b$. For the nodes $[l,r]$ on each line segment tree, we maintain the first and last occurrence positions of each binary bit in the interval.
    523 
    524 We need to merge the two intervals, whether it is modification or query. Suppose you want to use the information of $[l, mid], [mid +1, r]$ to merge the information of $[l, r]$. Consider the answer that spans two intervals. If we want to make the $i$-th position of the interval OR $1$, then there are two possibilities
    525 
    526 1. Select the last occurrence position $P$ of the $i$-th bit in $[l,mid].$
    527 2. Select the first occurrence position $Q$ of the $i$-th bit in $[mid+1,r].$
    528 
    529 Let $x = max(a[P], a[P+1],\ldots, a[mid]), y = max(a[mid + 1], a[mid + 2], \ldots, a[Q]).$
    530 
    531 If $x \lt =y,$ we can choose the position $P$ greedily, because his price is smaller. If you choose $Q,$ then you must also choose $P,$ because choosing $P$ does not increase max $a.$ Otherwise, select $Q$ on the contrary.
    532 
    533 With the above greedy, then you can enumerate the first binary bit $i$ that is larger than $v$. The $i$-th bit of the interval OR must be $1$, and the $i$-th bit of $v$ is $0$. For the $j$-th $(j \gt i)$ bit, if the $j$-th bit of $v$ is $1$, then the $j$-th bit must also be $1$. The rest of the bits can be regarded as $0$ or $1$, you only need to deal with these bits that must be selected $1$ greedily, and expand the interval.
    534 
    535 You can use the st table $O(1)$ to find the interval max of $a$, so you can merge the information of the two intervals in the time of $O(log V)$. With the line segment tree, $O(q log n log V + n log V)$ can be done.
    536 
    537 **solution**
    538 
    539 ```
    540 #include <bits/stdc++.h>
    541 using namespace std;
    542 constexpr int N = 5e5 + 10, V = 30, inf = INT_MAX, L = 18;
    543 int n, q, S, a[N], b[N];
    544 struct Rmq
    545 {
    546    int st[L][N];
    547    void init()
    548    {
    549       for (int i = 1; i <= n; i++)
    550          st[0][i] = a[i];
    551       for (int i = 1; i < L; i++)
    552       {
    553          for (int j = 1; j <= n - (1 << i) + 1; j++)
    554          {
    555             st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
    556          }
    557       }
    558    }
    559    int qry(int l, int r)
    560    {
    561       int k = __lg(r - l + 1);
    562       return max(st[k][l], st[k][r - (1 << k) + 1]);
    563    }
    564 } ds;
    565 struct Info
    566 {
    567    int pre[V], suf[V];
    568    int ans, l, r;
    569    Info()
    570    {
    571       memset(pre, 0, sizeof(pre));
    572       memset(suf, 0, sizeof(suf));
    573       ans = inf, l = r = 0;
    574    }
    575    Info(const Info &x, const Info &y)
    576    {
    577       for (int i = 0; i < V; i++)
    578       {
    579          pre[i] = x.pre[i] ? x.pre[i] : y.pre[i];
    580          suf[i] = y.suf[i] ? y.suf[i] : x.suf[i];
    581       }
    582       ans = inf, l = r = 0;
    583    }
    584    friend Info operator+(const Info &x, const Info &y)
    585    {
    586       Info z(x, y);
    587       z.ans = min(x.ans, y.ans), z.l = x.l, z.r = y.r;
    588       int pl = x.r, pr = y.l;
    589       if (!pl)
    590          return z;
    591       for (int i = V - 1; i >= 0; i--)
    592       {
    593          int u = x.suf[i], v = y.pre[i];
    594          if (u)
    595             u = min(u, pl);
    596          if (v)
    597             v = max(v, pr);
    598          int lans = u ? ds.qry(u, pr) : inf;
    599          int rans = v ? ds.qry(pl, v) : inf;
    600          if (lans < rans)
    601          {
    602             if (S >> i & 1)
    603             {
    604                if (lans < z.ans)
    605                   pl = u;
    606                else
    607                   break;
    608             }
    609             else
    610                z.ans = min(z.ans, lans);
    611          }
    612          else
    613          {
    614             if (S >> i & 1)
    615             {
    616                if (rans < z.ans)
    617                   pr = v;
    618                else
    619                   break;
    620             }
    621             else
    622                z.ans = min(z.ans, rans);
    623          }
    624       }
    625       return z;
    626    }
    627    void clear()
    628    {
    629       *this = Info();
    630    }
    631    void upd(int p)
    632    {
    633       l = r = p, ans = b[p] > S ? a[p] : inf;
    634       memset(pre, 0, sizeof(pre));
    635       memset(suf, 0, sizeof(suf));
    636       for (int j = 0; j < V; j++)
    637       {
    638          if (b[p] >> j & 1)
    639          {
    640             suf[j] = p;
    641             pre[j] = p;
    642          }
    643       }
    644    }
    645 } ans;
    646 void reply(const Info &cur)
    647 {
    648    ans = ans + cur;
    649 }
    650 struct Node
    651 {
    652    Node *ls, *rs;
    653    int l, r, mid;
    654    Info info;
    655    void up()
    656    {
    657       info = ls->info + rs->info;
    658    }
    659    void update(int p)
    660    {
    661       if (l == r)
    662          return info.upd(l);
    663       p <= mid ? ls->update(p) : rs->update(p);
    664       up();
    665    }
    666    void query(int ql, int qr)
    667    {
    668       if (l >= ql && r <= qr)
    669          return reply(info);
    670       if (ql <= mid)
    671          ls->query(ql, qr);
    672       if (qr > mid)
    673          rs->query(ql, qr);
    674    }
    675 } mempool[N + 5 << 1], *cnt = mempool, *rt;
    676 Node *build(int l, int r)
    677 {
    678    Node *u = cnt++;
    679    int mid = l + r >> 1;
    680    u->l = l, u->r = r, u->mid = mid;
    681    if (l == r)
    682    {
    683       u->info.upd(l);
    684       return u;
    685    }
    686    u->ls = build(l, mid);
    687    u->rs = build(mid + 1, r);
    688    u->up();
    689    return u;
    690 }
    691  
    692 void solve()
    693 {
    694    cin >> n >> S;
    695    S--;
    696    for (int i = 1; i <= n; i++)
    697       cin >> a[i];
    698    ds.init();
    699    for (int i = 1; i <= n; i++)
    700       cin >> b[i];
    701    rt = build(1, n);
    702    cin >> q;
    703    for (int i = 0; i < q; i++)
    704    {
    705       int opt;
    706       cin >> opt;
    707       if (opt == 1)
    708       {
    709          int p, x;
    710          cin >> p >> x;
    711          b[p] = x;
    712          rt->update(p);
    713       }
    714       else
    715       {
    716          int l, r;
    717          cin >> l >> r;
    718          ans.clear();
    719          rt->query(l, r);
    720          cout << (ans.ans == inf ? -1 : ans.ans) << ' ';
    721       }
    722    }
    723    cout << "\n";
    724 }
    725 int main()
    726 {
    727 #ifndef ONLINE_JUDGE
    728    freopen("input.txt", "r", stdin);
    729    freopen("output.txt", "w", stdout);
    730 #endif
    731    ios_base::sync_with_stdio(0);
    732    cin.tie(0);
    733    cout.tie(0);
    734    ios::sync_with_stdio(false), cin.tie(0);
    735    int t = 0;
    736    cin >> t;
    737    while (t--)
    738    {
    739       solve();
    740    }
    741  
    742    // 	cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
    743    return 0;
    744 }
    745 ```
    746 
    747 #### [D1E — Yet Yet Another Permutation Problem](https://codeforces.com/contest/1936/problem/E)
    748 
    749 Idea : [wuhudsm](/profile/wuhudsm "Кандидат в мастера wuhudsm")
    750 
    751 **Hint1**
    752 
    753 We found it difficult to directly calculate all valid permutations. How about calculating all invalid permutations?
    754 
    755 **Hint2**
    756 
    757 Can you come up with an $O(n^2)$ DP solution?
    758 
    759 **Hint3**
    760 
    761 How to optimize the $O(n^2)$ DP solution?
    762 
    763 **Tutorial**
    764 
    765 We found it difficult to directly calculate all valid permutations. Consider calculating all invalid permutations and subtract it from $n!$.
    766 
    767 Let's first make some notes. We note $P_i=max(p_1,...,p_i),Q_i=max(q_1,...,q_i)$,and $last_i=max(j)(P_j \neq P_i)$.And note the values of all extreme points is $val[1,...,m]$ and positions is $pos[1,...,m]$.
    768 
    769 For example,$p=[3,1,4,2,6,5]$,we get $m=3$, $val=[3,4,6]$ and $pos=[1,3,5]$.
    770 
    771 Let’s call a permutation $q$ “i-invalid” if there’s an index $j$ satisfying $Q_j=P_j=val_i$.
    772 
    773 Note $S_i$ as the set of all “i-invalid” permutations.According to the Inclusion-Exclusion Principle,the answer is $n!-(|S_1|+|S_2|+...)+(|S_1∩S_2|+|S_1∩S_3|+...)-...$
    774 
    775 Consider put $val_i$ in $q$ to make $q$ “i-invalid”.There’re $2$ kinds of ways:
    776 
    777 * $q_j=val_i(1 \le j \lt pos_i)$ and $Q_{pos_i}=val_i$;
    778 * $q_j=val_i(pos_i \le j \lt pos_{i+1})$ and $Q_{pos_i}=val_i$.
    779 
    780 In both cases,we call the first $max(j,pos_i)$ numbers are “determined”. In other words,they’re some numbers in $[1,val_i]$.
    781 
    782 Then we can find an $O(n^2)$ DP. Note $dp_{i,j}$ — $i$ stands for the first $i$ numbers is “determined”,and $j$ stands for $j$ extreme values are “invalid”. In fact we only care about the parity of $j$,so $j=0,1$. Note for the first $i$ numbers are “determined” automatically means $Q_i=P_i$. In addition,$q_i=P_i(P_i=P_{i-1})$ or $q_i \lt P_i(P_i \neq P_{i-1})$.
    783 
    784 We get a DP formula $dp_{i,j}= \Sigma_{k=0}^{last_i} dp_{k,j \oplus 1} \cdot A^{P_i-k-1}_{i-k-1} \cdot (P_i==P_{i+1}?1:i-k)$
    785 
    786 Here is a small trick to reduce the constant. If we note $f_i=dp_{i,0}-dp_{i,1}$, we get a more concise formula $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (P_i==P_{i+1}?1:i-j)$
    787 
    788 We perform the following transformation on the formula.
    789 
    790 ① For $i$ satisfying $P_i=P_{i-1}$, we get
    791 
    792 $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} = -[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)!$
    793 
    794 ② For $i$ satisfying $P_i \neq P_{i-1}$, we get
    795 
    796 $f_{i}= -\Sigma_{j=0}^{last_i} f_{j} \cdot A^{P_i-j-1}_{i-j-1} \cdot (i-j) = -i[(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} f_{j} \cdot (P_i-j-1)! + [(P_i-i)!]^{-1} \Sigma_{j=0}^{last_i} jf_{j} \cdot (P_i-j-1)!$
    797 
    798 After that, we have transformed the formula into a classical form $f(i)= h(i) \Sigma_{j=0}^{i-1} f(j) \cdot g(i-j)$, which can be calculate in $O(n log^2 n)$ by D&C+FFT.
    799 
    800 **solution**
    801 
    802 ```
    803 #include<bits/stdc++.h>
    804 using namespace std;
    805 
    806 #define all(a) a.begin(),a.end()
    807 #define pb push_back
    808 #define sz(a) ((int)a.size())
    809 
    810 using ll=long long;
    811 using u32=unsigned int;
    812 using u64=unsigned long long;
    813 using i128=__int128;
    814 using u128=unsigned __int128;
    815 using f128=__float128;
    816 
    817 using pii=pair<int,int>;
    818 using pll=pair<ll,ll>;
    819 
    820 template<typename T> using vc=vector<T>;
    821 template<typename T> using vvc=vc<vc<T>>;
    822 template<typename T> using vvvc=vc<vvc<T>>;
    823 
    824 using vi=vc<int>;
    825 using vll=vc<ll>;
    826 using vvi=vc<vi>;
    827 using vvll=vc<vll>;
    828 
    829 #define vv(type,name,n,...) \
    830     vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
    831 #define vvv(type,name,n,m,...) \
    832     vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
    833 
    834 template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
    835 template<typename T> using max_heap=priority_queue<T>;
    836 
    837 // https://trap.jp/post/1224/
    838 #define rep1(n) for(ll i=0; i<(ll)(n); ++i)
    839 #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
    840 #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
    841 #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
    842 #define cut4(a,b,c,d,e,...) e
    843 #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
    844 #define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
    845 #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
    846 #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
    847 #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
    848 #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
    849 #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
    850 
    851 template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
    852 template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}
    853 
    854 template<typename T>
    855 void sort_unique(vector<T> &vec){
    856     sort(vec.begin(),vec.end());
    857     vec.resize(unique(vec.begin(),vec.end())-vec.begin());
    858 }
    859 
    860 template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
    861 template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}
    862 
    863 template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
    864 template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}
    865 
    866 #ifdef i_am_noob
    867 #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
    868 template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
    869 template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
    870 template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
    871 template<typename T> void _do(T && x) {cerr << x << endl;}
    872 template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
    873 #else
    874 #define bug(...) 777771449
    875 #endif
    876 
    877 template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
    878 template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
    879 template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
    880 template<typename T> void print(T && x) {cout << x << "\n";}
    881 template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}
    882 
    883 template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}
    884 
    885 vvi read_graph(int n, int m, int base=1){
    886     vvi adj(n);
    887     for(int i=0,u,v; i<m; ++i){
    888         cin >> u >> v,u-=base,v-=base;
    889         adj[u].pb(v),adj[v].pb(u);
    890     }
    891     return adj;
    892 }
    893 
    894 vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}
    895 
    896 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};}
    897 
    898 template<typename T> constexpr T inf=0;
    899 template<> constexpr int inf<int> = 0x3f3f3f3f;
    900 template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;
    901 
    902 template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}
    903 
    904 template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}
    905 
    906 #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
    907 
    908 #include <utility>
    909 
    910 namespace atcoder {
    911 
    912 namespace internal {
    913 
    914 // @param m `1 <= m`
    915 // @return x mod m
    916 constexpr long long safe_mod(long long x, long long m) {
    917     x %= m;
    918     if (x < 0) x += m;
    919     return x;
    920 }
    921 
    922 // Fast modular multiplication by barrett reduction
    923 // Reference: https://en.wikipedia.org/wiki/Barrett_reduction
    924 // NOTE: reconsider after Ice Lake
    925 struct barrett {
    926     unsigned int _m;
    927     unsigned long long im;
    928 
    929     // @param m `1 <= m < 2^31`
    930     barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
    931 
    932     // @return m
    933     unsigned int umod() const { return _m; }
    934 
    935     // @param a `0 <= a < m`
    936     // @param b `0 <= b < m`
    937     // @return `a * b % m`
    938     unsigned int mul(unsigned int a, unsigned int b) const {
    939         // [1] m = 1
    940         // a = b = im = 0, so okay
    941 
    942         // [2] m >= 2
    943         // im = ceil(2^64 / m)
    944         // -> im * m = 2^64 + r (0 <= r < m)
    945         // let z = a*b = c*m + d (0 <= c, d < m)
    946         // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
    947         // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
    948         // ((ab * im) >> 64) == c or c + 1
    949         unsigned long long z = a;
    950         z *= b;
    951 #ifdef _MSC_VER
    952         unsigned long long x;
    953         _umul128(z, im, &x);
    954 #else
    955         unsigned long long x =
    956             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
    957 #endif
    958         unsigned int v = (unsigned int)(z - x * _m);
    959         if (_m <= v) v += _m;
    960         return v;
    961     }
    962 };
    963 
    964 // @param n `0 <= n`
    965 // @param m `1 <= m`
    966 // @return `(x ** n) % m`
    967 constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    968     if (m == 1) return 0;
    969     unsigned int _m = (unsigned int)(m);
    970     unsigned long long r = 1;
    971     unsigned long long y = safe_mod(x, m);
    972     while (n) {
    973         if (n & 1) r = (r * y) % _m;
    974         y = (y * y) % _m;
    975         n >>= 1;
    976     }
    977     return r;
    978 }
    979 
    980 // Reference:
    981 // M. Forisek and J. Jancina,
    982 // Fast Primality Testing for Integers That Fit into a Machine Word
    983 // @param n `0 <= n`
    984 constexpr bool is_prime_constexpr(int n) {
    985     if (n <= 1) return false;
    986     if (n == 2 || n == 7 || n == 61) return true;
    987     if (n % 2 == 0) return false;
    988     long long d = n - 1;
    989     while (d % 2 == 0) d /= 2;
    990     constexpr long long bases[3] = {2, 7, 61};
    991     for (long long a : bases) {
    992         long long t = d;
    993         long long y = pow_mod_constexpr(a, t, n);
    994         while (t != n - 1 && y != 1 && y != n - 1) {
    995             y = y * y % n;
    996             t <<= 1;
    997         }
    998         if (y != n - 1 && t % 2 == 0) {
    999             return false;
   1000         }
   1001     }
   1002     return true;
   1003 }
   1004 template <int n> constexpr bool is_prime = is_prime_constexpr(n);
   1005 
   1006 // @param b `1 <= b`
   1007 // @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
   1008 constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
   1009     a = safe_mod(a, b);
   1010     if (a == 0) return {b, 0};
   1011 
   1012     // Contracts:
   1013     // [1] s - m0 * a = 0 (mod b)
   1014     // [2] t - m1 * a = 0 (mod b)
   1015     // [3] s * |m1| + t * |m0| <= b
   1016     long long s = b, t = a;
   1017     long long m0 = 0, m1 = 1;
   1018 
   1019     while (t) {
   1020         long long u = s / t;
   1021         s -= t * u;
   1022         m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b
   1023 
   1024         // [3]:
   1025         // (s - t * u) * |m1| + t * |m0 - m1 * u|
   1026         // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
   1027         // = s * |m1| + t * |m0| <= b
   1028 
   1029         auto tmp = s;
   1030         s = t;
   1031         t = tmp;
   1032         tmp = m0;
   1033         m0 = m1;
   1034         m1 = tmp;
   1035     }
   1036     // by [3]: |m0| <= b/g
   1037     // by g != b: |m0| < b/g
   1038     if (m0 < 0) m0 += b / s;
   1039     return {s, m0};
   1040 }
   1041 
   1042 // Compile time primitive root
   1043 // @param m must be prime
   1044 // @return primitive root (and minimum in now)
   1045 constexpr int primitive_root_constexpr(int m) {
   1046     if (m == 2) return 1;
   1047     if (m == 167772161) return 3;
   1048     if (m == 469762049) return 3;
   1049     if (m == 754974721) return 11;
   1050     if (m == 998244353) return 3;
   1051     int divs[20] = {};
   1052     divs[0] = 2;
   1053     int cnt = 1;
   1054     int x = (m - 1) / 2;
   1055     while (x % 2 == 0) x /= 2;
   1056     for (int i = 3; (long long)(i)*i <= x; i += 2) {
   1057         if (x % i == 0) {
   1058             divs[cnt++] = i;
   1059             while (x % i == 0) {
   1060                 x /= i;
   1061             }
   1062         }
   1063     }
   1064     if (x > 1) {
   1065         divs[cnt++] = x;
   1066     }
   1067     for (int g = 2;; g++) {
   1068         bool ok = true;
   1069         for (int i = 0; i < cnt; i++) {
   1070             if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
   1071                 ok = false;
   1072                 break;
   1073             }
   1074         }
   1075         if (ok) return g;
   1076     }
   1077 }
   1078 template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
   1079 
   1080 }  // namespace internal
   1081 
   1082 }  // namespace atcoder
   1083 
   1084 #include <cassert>
   1085 #include <numeric>
   1086 #include <type_traits>
   1087 
   1088 namespace atcoder {
   1089 
   1090 namespace internal {
   1091 
   1092 #ifndef _MSC_VER
   1093 template <class T>
   1094 using is_signed_int128 =
   1095     typename std::conditional<std::is_same<T, __int128_t>::value ||
   1096                                   std::is_same<T, __int128>::value,
   1097                               std::true_type,
   1098                               std::false_type>::type;
   1099 
   1100 template <class T>
   1101 using is_unsigned_int128 =
   1102     typename std::conditional<std::is_same<T, __uint128_t>::value ||
   1103                                   std::is_same<T, unsigned __int128>::value,
   1104                               std::true_type,
   1105                               std::false_type>::type;
   1106 
   1107 template <class T>
   1108 using make_unsigned_int128 =
   1109     typename std::conditional<std::is_same<T, __int128_t>::value,
   1110                               __uint128_t,
   1111                               unsigned __int128>;
   1112 
   1113 template <class T>
   1114 using is_integral = typename std::conditional<std::is_integral<T>::value ||
   1115                                                   is_signed_int128<T>::value ||
   1116                                                   is_unsigned_int128<T>::value,
   1117                                               std::true_type,
   1118                                               std::false_type>::type;
   1119 
   1120 template <class T>
   1121 using is_signed_int = typename std::conditional<(is_integral<T>::value &&
   1122                                                  std::is_signed<T>::value) ||
   1123                                                     is_signed_int128<T>::value,
   1124                                                 std::true_type,
   1125                                                 std::false_type>::type;
   1126 
   1127 template <class T>
   1128 using is_unsigned_int =
   1129     typename std::conditional<(is_integral<T>::value &&
   1130                                std::is_unsigned<T>::value) ||
   1131                                   is_unsigned_int128<T>::value,
   1132                               std::true_type,
   1133                               std::false_type>::type;
   1134 
   1135 template <class T>
   1136 using to_unsigned = typename std::conditional<
   1137     is_signed_int128<T>::value,
   1138     make_unsigned_int128<T>,
   1139     typename std::conditional<std::is_signed<T>::value,
   1140                               std::make_unsigned<T>,
   1141                               std::common_type<T>>::type>::type;
   1142 
   1143 #else
   1144 
   1145 template <class T> using is_integral = typename std::is_integral<T>;
   1146 
   1147 template <class T>
   1148 using is_signed_int =
   1149     typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
   1150                               std::true_type,
   1151                               std::false_type>::type;
   1152 
   1153 template <class T>
   1154 using is_unsigned_int =
   1155     typename std::conditional<is_integral<T>::value &&
   1156                                   std::is_unsigned<T>::value,
   1157                               std::true_type,
   1158                               std::false_type>::type;
   1159 
   1160 template <class T>
   1161 using to_unsigned = typename std::conditional<is_signed_int<T>::value,
   1162                                               std::make_unsigned<T>,
   1163                                               std::common_type<T>>::type;
   1164 
   1165 #endif
   1166 
   1167 template <class T>
   1168 using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
   1169 
   1170 template <class T>
   1171 using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
   1172 
   1173 template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
   1174 
   1175 }  // namespace internal
   1176 
   1177 }  // namespace atcoder
   1178 
   1179 #include <cassert>
   1180 #include <numeric>
   1181 #include <type_traits>
   1182 
   1183 #ifdef _MSC_VER
   1184 #include <intrin.h>
   1185 #endif
   1186 
   1187 namespace atcoder {
   1188 
   1189 namespace internal {
   1190 
   1191 struct modint_base {};
   1192 struct static_modint_base : modint_base {};
   1193 
   1194 template <class T> using is_modint = std::is_base_of<modint_base, T>;
   1195 template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
   1196 
   1197 }  // namespace internal
   1198 
   1199 template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
   1200 struct static_modint : internal::static_modint_base {
   1201     using mint = static_modint;
   1202 
   1203   public:
   1204     static constexpr int mod() { return m; }
   1205     static mint raw(int v) {
   1206         mint x;
   1207         x._v = v;
   1208         return x;
   1209     }
   1210 
   1211     static_modint() : _v(0) {}
   1212     template <class T, internal::is_signed_int_t<T>* = nullptr>
   1213     static_modint(T v) {
   1214         long long x = (long long)(v % (long long)(umod()));
   1215         if (x < 0) x += umod();
   1216         _v = (unsigned int)(x);
   1217     }
   1218     template <class T, internal::is_unsigned_int_t<T>* = nullptr>
   1219     static_modint(T v) {
   1220         _v = (unsigned int)(v % umod());
   1221     }
   1222     static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }
   1223 
   1224     unsigned int val() const { return _v; }
   1225 
   1226     mint& operator++() {
   1227         _v++;
   1228         if (_v == umod()) _v = 0;
   1229         return *this;
   1230     }
   1231     mint& operator--() {
   1232         if (_v == 0) _v = umod();
   1233         _v--;
   1234         return *this;
   1235     }
   1236     mint operator++(int) {
   1237         mint result = *this;
   1238         ++*this;
   1239         return result;
   1240     }
   1241     mint operator--(int) {
   1242         mint result = *this;
   1243         --*this;
   1244         return result;
   1245     }
   1246 
   1247     mint& operator+=(const mint& rhs) {
   1248         _v += rhs._v;
   1249         if (_v >= umod()) _v -= umod();
   1250         return *this;
   1251     }
   1252     mint& operator-=(const mint& rhs) {
   1253         _v -= rhs._v;
   1254         if (_v >= umod()) _v += umod();
   1255         return *this;
   1256     }
   1257     mint& operator*=(const mint& rhs) {
   1258         unsigned long long z = _v;
   1259         z *= rhs._v;
   1260         _v = (unsigned int)(z % umod());
   1261         return *this;
   1262     }
   1263     mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
   1264 
   1265     mint operator+() const { return *this; }
   1266     mint operator-() const { return mint() - *this; }
   1267 
   1268     mint pow(long long n) const {
   1269         assert(0 <= n);
   1270         mint x = *this, r = 1;
   1271         while (n) {
   1272             if (n & 1) r *= x;
   1273             x *= x;
   1274             n >>= 1;
   1275         }
   1276         return r;
   1277     }
   1278     mint inv() const {
   1279         if (prime) {
   1280             assert(_v);
   1281             return pow(umod() - 2);
   1282         } else {
   1283             auto eg = internal::inv_gcd(_v, m);
   1284             assert(eg.first == 1);
   1285             return eg.second;
   1286         }
   1287     }
   1288 
   1289     friend mint operator+(const mint& lhs, const mint& rhs) {
   1290         return mint(lhs) += rhs;
   1291     }
   1292     friend mint operator-(const mint& lhs, const mint& rhs) {
   1293         return mint(lhs) -= rhs;
   1294     }
   1295     friend mint operator*(const mint& lhs, const mint& rhs) {
   1296         return mint(lhs) *= rhs;
   1297     }
   1298     friend mint operator/(const mint& lhs, const mint& rhs) {
   1299         return mint(lhs) /= rhs;
   1300     }
   1301     friend bool operator==(const mint& lhs, const mint& rhs) {
   1302         return lhs._v == rhs._v;
   1303     }
   1304     friend bool operator!=(const mint& lhs, const mint& rhs) {
   1305         return lhs._v != rhs._v;
   1306     }
   1307 
   1308   private:
   1309     unsigned int _v;
   1310     static constexpr unsigned int umod() { return m; }
   1311     static constexpr bool prime = internal::is_prime<m>;
   1312 };
   1313 
   1314 template <int id> struct dynamic_modint : internal::modint_base {
   1315     using mint = dynamic_modint;
   1316 
   1317   public:
   1318     static int mod() { return (int)(bt.umod()); }
   1319     static void set_mod(int m) {
   1320         assert(1 <= m);
   1321         bt = internal::barrett(m);
   1322     }
   1323     static mint raw(int v) {
   1324         mint x;
   1325         x._v = v;
   1326         return x;
   1327     }
   1328 
   1329     dynamic_modint() : _v(0) {}
   1330     template <class T, internal::is_signed_int_t<T>* = nullptr>
   1331     dynamic_modint(T v) {
   1332         long long x = (long long)(v % (long long)(mod()));
   1333         if (x < 0) x += mod();
   1334         _v = (unsigned int)(x);
   1335     }
   1336     template <class T, internal::is_unsigned_int_t<T>* = nullptr>
   1337     dynamic_modint(T v) {
   1338         _v = (unsigned int)(v % mod());
   1339     }
   1340     dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }
   1341 
   1342     unsigned int val() const { return _v; }
   1343 
   1344     mint& operator++() {
   1345         _v++;
   1346         if (_v == umod()) _v = 0;
   1347         return *this;
   1348     }
   1349     mint& operator--() {
   1350         if (_v == 0) _v = umod();
   1351         _v--;
   1352         return *this;
   1353     }
   1354     mint operator++(int) {
   1355         mint result = *this;
   1356         ++*this;
   1357         return result;
   1358     }
   1359     mint operator--(int) {
   1360         mint result = *this;
   1361         --*this;
   1362         return result;
   1363     }
   1364 
   1365     mint& operator+=(const mint& rhs) {
   1366         _v += rhs._v;
   1367         if (_v >= umod()) _v -= umod();
   1368         return *this;
   1369     }
   1370     mint& operator-=(const mint& rhs) {
   1371         _v += mod() - rhs._v;
   1372         if (_v >= umod()) _v -= umod();
   1373         return *this;
   1374     }
   1375     mint& operator*=(const mint& rhs) {
   1376         _v = bt.mul(_v, rhs._v);
   1377         return *this;
   1378     }
   1379     mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
   1380 
   1381     mint operator+() const { return *this; }
   1382     mint operator-() const { return mint() - *this; }
   1383 
   1384     mint pow(long long n) const {
   1385         assert(0 <= n);
   1386         mint x = *this, r = 1;
   1387         while (n) {
   1388             if (n & 1) r *= x;
   1389             x *= x;
   1390             n >>= 1;
   1391         }
   1392         return r;
   1393     }
   1394     mint inv() const {
   1395         auto eg = internal::inv_gcd(_v, mod());
   1396         assert(eg.first == 1);
   1397         return eg.second;
   1398     }
   1399 
   1400     friend mint operator+(const mint& lhs, const mint& rhs) {
   1401         return mint(lhs) += rhs;
   1402     }
   1403     friend mint operator-(const mint& lhs, const mint& rhs) {
   1404         return mint(lhs) -= rhs;
   1405     }
   1406     friend mint operator*(const mint& lhs, const mint& rhs) {
   1407         return mint(lhs) *= rhs;
   1408     }
   1409     friend mint operator/(const mint& lhs, const mint& rhs) {
   1410         return mint(lhs) /= rhs;
   1411     }
   1412     friend bool operator==(const mint& lhs, const mint& rhs) {
   1413         return lhs._v == rhs._v;
   1414     }
   1415     friend bool operator!=(const mint& lhs, const mint& rhs) {
   1416         return lhs._v != rhs._v;
   1417     }
   1418 
   1419   private:
   1420     unsigned int _v;
   1421     static internal::barrett bt;
   1422     static unsigned int umod() { return bt.umod(); }
   1423 };
   1424 template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;
   1425 
   1426 using modint998244353 = static_modint<998244353>;
   1427 using modint1000000007 = static_modint<1000000007>;
   1428 using modint = dynamic_modint<-1>;
   1429 
   1430 namespace internal {
   1431 
   1432 template <class T>
   1433 using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
   1434 
   1435 template <class T>
   1436 using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
   1437 
   1438 template <class> struct is_dynamic_modint : public std::false_type {};
   1439 template <int id>
   1440 struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
   1441 
   1442 template <class T>
   1443 using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
   1444 
   1445 }  // namespace internal
   1446 
   1447 }  // namespace atcoder
   1448 
   1449 #include <algorithm>
   1450 #include <array>
   1451 
   1452 #ifdef _MSC_VER
   1453 #include <intrin.h>
   1454 #endif
   1455 
   1456 namespace atcoder {
   1457 
   1458 namespace internal {
   1459 
   1460 // @param n `0 <= n`
   1461 // @return minimum non-negative `x` s.t. `n <= 2**x`
   1462 int ceil_pow2(int n) {
   1463     int x = 0;
   1464     while ((1U << x) < (unsigned int)(n)) x++;
   1465     return x;
   1466 }
   1467 
   1468 // @param n `1 <= n`
   1469 // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
   1470 int bsf(unsigned int n) {
   1471 #ifdef _MSC_VER
   1472     unsigned long index;
   1473     _BitScanForward(&index, n);
   1474     return index;
   1475 #else
   1476     return __builtin_ctz(n);
   1477 #endif
   1478 }
   1479 
   1480 }  // namespace internal
   1481 
   1482 }  // namespace atcoder
   1483 
   1484 #include <cassert>
   1485 #include <type_traits>
   1486 #include <vector>
   1487 
   1488 namespace atcoder {
   1489 
   1490 namespace internal {
   1491 
   1492 template <class mint, internal::is_static_modint_t<mint>* = nullptr>
   1493 void butterfly(std::vector<mint>& a) {
   1494     static constexpr int g = internal::primitive_root<mint::mod()>;
   1495     int n = int(a.size());
   1496     int h = internal::ceil_pow2(n);
   1497 
   1498     static bool first = true;
   1499     static mint sum_e[30];  // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
   1500     if (first) {
   1501         first = false;
   1502         mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
   1503         int cnt2 = bsf(mint::mod() - 1);
   1504         mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
   1505         for (int i = cnt2; i >= 2; i--) {
   1506             // e^(2^i) == 1
   1507             es[i - 2] = e;
   1508             ies[i - 2] = ie;
   1509             e *= e;
   1510             ie *= ie;
   1511         }
   1512         mint now = 1;
   1513         for (int i = 0; i <= cnt2 - 2; i++) {
   1514             sum_e[i] = es[i] * now;
   1515             now *= ies[i];
   1516         }
   1517     }
   1518     for (int ph = 1; ph <= h; ph++) {
   1519         int w = 1 << (ph - 1), p = 1 << (h - ph);
   1520         mint now = 1;
   1521         for (int s = 0; s < w; s++) {
   1522             int offset = s << (h - ph + 1);
   1523             for (int i = 0; i < p; i++) {
   1524                 auto l = a[i + offset];
   1525                 auto r = a[i + offset + p] * now;
   1526                 a[i + offset] = l + r;
   1527                 a[i + offset + p] = l - r;
   1528             }
   1529             now *= sum_e[bsf(~(unsigned int)(s))];
   1530         }
   1531     }
   1532 }
   1533 
   1534 template <class mint, internal::is_static_modint_t<mint>* = nullptr>
   1535 void butterfly_inv(std::vector<mint>& a) {
   1536     static constexpr int g = internal::primitive_root<mint::mod()>;
   1537     int n = int(a.size());
   1538     int h = internal::ceil_pow2(n);
   1539 
   1540     static bool first = true;
   1541     static mint sum_ie[30];  // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
   1542     if (first) {
   1543         first = false;
   1544         mint es[30], ies[30];  // es[i]^(2^(2+i)) == 1
   1545         int cnt2 = bsf(mint::mod() - 1);
   1546         mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
   1547         for (int i = cnt2; i >= 2; i--) {
   1548             // e^(2^i) == 1
   1549             es[i - 2] = e;
   1550             ies[i - 2] = ie;
   1551             e *= e;
   1552             ie *= ie;
   1553         }
   1554         mint now = 1;
   1555         for (int i = 0; i <= cnt2 - 2; i++) {
   1556             sum_ie[i] = ies[i] * now;
   1557             now *= es[i];
   1558         }
   1559     }
   1560 
   1561     for (int ph = h; ph >= 1; ph--) {
   1562         int w = 1 << (ph - 1), p = 1 << (h - ph);
   1563         mint inow = 1;
   1564         for (int s = 0; s < w; s++) {
   1565             int offset = s << (h - ph + 1);
   1566             for (int i = 0; i < p; i++) {
   1567                 auto l = a[i + offset];
   1568                 auto r = a[i + offset + p];
   1569                 a[i + offset] = l + r;
   1570                 a[i + offset + p] =
   1571                     (unsigned long long)(mint::mod() + l.val() - r.val()) *
   1572                     inow.val();
   1573             }
   1574             inow *= sum_ie[bsf(~(unsigned int)(s))];
   1575         }
   1576     }
   1577 }
   1578 
   1579 }  // namespace internal
   1580 
   1581 template <class mint, internal::is_static_modint_t<mint>* = nullptr>
   1582 std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
   1583     int n = int(a.size()), m = int(b.size());
   1584     if (!n || !m) return {};
   1585     if (std::min(n, m) <= 60) {
   1586         if (n < m) {
   1587             std::swap(n, m);
   1588             std::swap(a, b);
   1589         }
   1590         std::vector<mint> ans(n + m - 1);
   1591         for (int i = 0; i < n; i++) {
   1592             for (int j = 0; j < m; j++) {
   1593                 ans[i + j] += a[i] * b[j];
   1594             }
   1595         }
   1596         return ans;
   1597     }
   1598     int z = 1 << internal::ceil_pow2(n + m - 1);
   1599     a.resize(z);
   1600     internal::butterfly(a);
   1601     b.resize(z);
   1602     internal::butterfly(b);
   1603     for (int i = 0; i < z; i++) {
   1604         a[i] *= b[i];
   1605     }
   1606     internal::butterfly_inv(a);
   1607     a.resize(n + m - 1);
   1608     mint iz = mint(z).inv();
   1609     for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
   1610     return a;
   1611 }
   1612 
   1613 template <unsigned int mod = 998244353,
   1614           class T,
   1615           std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
   1616 std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
   1617     int n = int(a.size()), m = int(b.size());
   1618     if (!n || !m) return {};
   1619 
   1620     using mint = static_modint<mod>;
   1621     std::vector<mint> a2(n), b2(m);
   1622     for (int i = 0; i < n; i++) {
   1623         a2[i] = mint(a[i]);
   1624     }
   1625     for (int i = 0; i < m; i++) {
   1626         b2[i] = mint(b[i]);
   1627     }
   1628     auto c2 = convolution(move(a2), move(b2));
   1629     std::vector<T> c(n + m - 1);
   1630     for (int i = 0; i < n + m - 1; i++) {
   1631         c[i] = c2[i].val();
   1632     }
   1633     return c;
   1634 }
   1635 
   1636 std::vector<long long> convolution_ll(const std::vector<long long>& a,
   1637                                       const std::vector<long long>& b) {
   1638     int n = int(a.size()), m = int(b.size());
   1639     if (!n || !m) return {};
   1640 
   1641     static constexpr unsigned long long MOD1 = 754974721;  // 2^24
   1642     static constexpr unsigned long long MOD2 = 167772161;  // 2^25
   1643     static constexpr unsigned long long MOD3 = 469762049;  // 2^26
   1644     static constexpr unsigned long long M2M3 = MOD2 * MOD3;
   1645     static constexpr unsigned long long M1M3 = MOD1 * MOD3;
   1646     static constexpr unsigned long long M1M2 = MOD1 * MOD2;
   1647     static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
   1648 
   1649     static constexpr unsigned long long i1 =
   1650         internal::inv_gcd(MOD2 * MOD3, MOD1).second;
   1651     static constexpr unsigned long long i2 =
   1652         internal::inv_gcd(MOD1 * MOD3, MOD2).second;
   1653     static constexpr unsigned long long i3 =
   1654         internal::inv_gcd(MOD1 * MOD2, MOD3).second;
   1655 
   1656     auto c1 = convolution<MOD1>(a, b);
   1657     auto c2 = convolution<MOD2>(a, b);
   1658     auto c3 = convolution<MOD3>(a, b);
   1659 
   1660     std::vector<long long> c(n + m - 1);
   1661     for (int i = 0; i < n + m - 1; i++) {
   1662         unsigned long long x = 0;
   1663         x += (c1[i] * i1) % MOD1 * M2M3;
   1664         x += (c2[i] * i2) % MOD2 * M1M3;
   1665         x += (c3[i] * i3) % MOD3 * M1M2;
   1666         // B = 2^63, -B <= x, r(real value) < B
   1667         // (x, x - M, x - 2M, or x - 3M) = r (mod 2B)
   1668         // r = c1[i] (mod MOD1)
   1669         // focus on MOD1
   1670         // r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)
   1671         // r = x,
   1672         //     x - M' + (0 or 2B),
   1673         //     x - 2M' + (0, 2B or 4B),
   1674         //     x - 3M' + (0, 2B, 4B or 6B) (without mod!)
   1675         // (r - x) = 0, (0)
   1676         //           - M' + (0 or 2B), (1)
   1677         //           -2M' + (0 or 2B or 4B), (2)
   1678         //           -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)
   1679         // we checked that
   1680         //   ((1) mod MOD1) mod 5 = 2
   1681         //   ((2) mod MOD1) mod 5 = 3
   1682         //   ((3) mod MOD1) mod 5 = 4
   1683         long long diff =
   1684             c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
   1685         if (diff < 0) diff += MOD1;
   1686         static constexpr unsigned long long offset[5] = {
   1687             0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
   1688         x -= offset[diff % 5];
   1689         c[i] = x;
   1690     }
   1691 
   1692     return c;
   1693 }
   1694 
   1695 }  // namespace atcoder
   1696 
   1697 using namespace atcoder;
   1698 
   1699 using mint=modint998244353;
   1700 //using mint=modint1000000007;
   1701 
   1702 template<int mod>
   1703 struct nCr{
   1704     vector<static_modint<mod>> fac,inv,ifac;
   1705     void calc(int n){
   1706         fac.resize(n+1),inv.resize(n+1),ifac.resize(n+1);
   1707         fac[0]=inv[1]=ifac[0]=1;
   1708         for(int i=1; i<=n; ++i) fac[i]=fac[i-1]*static_modint<mod>::raw(i);
   1709         for(int i=2; i<=n; ++i) inv[i]=inv[mod%i]*static_modint<mod>::raw(mod-mod/i);
   1710         for(int i=1; i<=n; ++i) ifac[i]=ifac[i-1]*inv[i];
   1711     }
   1712     static_modint<mod> C(int n, int m){
   1713         if(m<0||m>n) return 0;
   1714         return fac[n]*ifac[m]*ifac[n-m];
   1715     }
   1716 };
   1717 
   1718 nCr<998244353> de;
   1719 
   1720 void ahcorz(){
   1721     // (a_i - j)! / (a_i - i)! (a_i = a_j)
   1722     // (a_i - j - 1)! / (a_i - i)! * (i - j) (a_i != a_j)
   1723     int n; cin >> n;
   1724     de.calc(n+1);
   1725     vi a; a.pb(0);
   1726     rep(n){
   1727         int x; cin >> x;
   1728         a.pb(max(a.back(),x));
   1729     }
   1730     vc<mint> dp(n+1),aux(n+1);
   1731     auto solve=[&](auto &self, int l, int r) -> void{
   1732         if(l+1==r){
   1733             if(l==0) dp[l]=-1;
   1734             else dp[l]+=aux[l]*l;
   1735             dp[l]*=de.ifac[a[l]-l];
   1736             return;
   1737         }
   1738         int mid=l+r>>1;
   1739         self(self,l,mid);
   1740         if(a[mid]==a[mid-1]){
   1741             int x=mid-1,y=mid;
   1742             while(x-1>=l&&a[x-1]==a[mid]) x--;
   1743             while(y+1<r&&a[y+1]==a[mid]) y++;
   1744             mint tot,tot1,tot2;
   1745             rep(i,x,mid) tot+=dp[i]*de.fac[a[mid]-i],tot1+=dp[i]*de.fac[a[mid]-i-1],tot2+=dp[i]*de.fac[a[mid]-i-1]*i;
   1746             rep(i,mid,y+1) dp[i]-=tot-(tot1*i-tot2);
   1747         }
   1748         vc<mint> vec;
   1749         rep(i,a[mid]-mid,a[r-1]-(l+1)+1) vec.pb(de.fac[i]);
   1750         vc<mint> vec1,vec2;
   1751         rep(i,l,mid) vec1.pb(dp[i]),vec2.pb(dp[i]*i);
   1752         auto res1=convolution(vec,vec1),res2=convolution(vec,vec2);
   1753         int base=a[mid]-mid+l+1;
   1754         rep(i,mid,r) if(a[i]-base>=0&&a[i]-base<sz(res1)) aux[i]-=res1[a[i]-base],dp[i]+=res2[a[i]-base];
   1755         self(self,mid,r);
   1756     };
   1757     solve(solve,0,n+1);
   1758     print(dp[n].val());
   1759 }
   1760 
   1761 signed main(){
   1762     ios_base::sync_with_stdio(0),cin.tie(0);
   1763     cout << fixed << setprecision(20);
   1764     int t=1;
   1765     cin >> t;
   1766     while(t--) ahcorz();
   1767 }
   1768 ```
   1769 
   1770 #### [D1F — Grand Finale: Circles](https://codeforces.com/contest/1936/problem/F)
   1771 
   1772 Idea : [chromate00](/profile/chromate00 "Эксперт chromate00")
   1773 
   1774 **UPD**: The TL was a bit too loose, and unintended solutions with $\mathcal{O}(n \log^2 (1/\epsilon))$ complexity passed during the round. For the sake of the problem itself, I suggest that you try to solve assuming a $1$ second time limit.
   1775 
   1776 **Tutorial**
   1777 
   1778 For a given center coordinate $(x,y)$, we can model the objective function $r=f(x,y)$ to maximize as follows.
   1779 
   1780 $f(x,y)=\min_{1 \le i \le n} {\left({r_i-\sqrt{(x_i-x)^2+(y_i-y)^2}}\right)}$
   1781 
   1782 Formally, this can be modeled as follows:
   1783 
   1784 $\begin{split} \max & \ r \\ \text{s.t.} & \ \sqrt{(x_i-x)^2+(y_i-y)^2} \le r_i-r \ \ \forall \ 1 \le i \le n \end{split}$
   1785 
   1786 This is a **second order cone program**. Generally, this is not as simple to solve as linear or quadratic programs. There are multiple solvers out there, but all of them are either commercial or simply unfit for use on Codeforces. And even if we use general approaches to second order cone programming, their time complexity is at least $\mathcal{O}(n^{3.5})$, so they cannot work. Almost all general approaches to convex programming do not help very much for this task also, because of the following reasons.
   1787 
   1788 * Gradient Descent cannot work in this task. The objective function is not smooth.
   1789 * Coordinate Descent also cannot work in this task for the same reason, and it is not hard to find a countercase.
   1790 * Subgradient methods can solve this task, but they take $\mathcal{O}(1/\epsilon^2)$ iterations to converge. This is a very big dependency on the precision, so they take too much time.
   1791 * We do not expect anyone to write Adaptive Coordinate Descent during contest time, but we still tested the PRAXIS algorithm and checked that it does not pass.
   1792 * Using nested ternary searches does not help very much. The time complexity will be $\mathcal{O}(n \log^2 (1/\epsilon))$, but the constants are large due to multiple function calls and floating point operations.
   1793 * Heuristics such as the Nelder-Mead method are not proven to converge. In many cases we found it not converging successfully.
   1794 
   1795 In the editorial, we will explain a solution of expected $\mathcal{O}(n)$ time complexity, with constants depending on the number of dimensions (which is $2$ in our case).
   1796 
   1797 First, we observe that any answer can be described as a "basis" of at most $3$ selected circles. For $k=0,1,2,3$, the basis is as follows.
   1798 
   1799 * Case 1: $k=0$
   1800 
   1801 This is the case of no circles, which can be regarded as an "identity element" of bases. Some very huge circle that will enclose any given circle, for example the circle with $10^{18}$ as radius and $(0,0)$ as center, can represent this case.
   1802 
   1803 * Case 2: $k=1$
   1804 
   1805 This is the case of a single circle. The circle that represents this case is the one selected circle.
   1806 
   1807 * Case 3: $k=2$
   1808 
   1809 This is the case of two circles, for which the basis is the largest circle in the intersection of two circles. We can find this by choosing the center as the midpoint of the two points $A$ and $B$, where $A$ and $B$ are the points where the line segment between circle centers and the circle itself intersect.
   1810 
   1811 * Case 4: $k=3$
   1812 
   1813 This is the case of three circles, and the most tricky of all four cases. It can be found as one solution to the following system of quadratic equations:
   1814 
   1815 $(x_A-x)^2+(y_A-y)^2 = (r_A-r)^2 \\ (x_B-x)^2+(y_B-y)^2 = (r_B-r)^2 \\ (x_C-x)^2+(y_C-y)^2 = (r_C-r)^2$
   1816 
   1817 This can be solved algebraically. If you are used to solving geometry problems in Olympiads, you may know the [''Problem of Apollonius''](https://en.wikipedia.org/wiki/Problem_of_Apollonius). This is one special case of the problem, which is not very often mentioned because often the three circles do not intersect with each other (thus most of the time one solution for $r$ must be negative). Or if one does not know the problem, they can find that the locus of the circle center that meets with two circle edges (as in Case 3) is a conic section, precisely one side of a pair of hyperbola. By finding the intersections of two hyperbola, one can find the center of this circle. Thus, this circle can be found in $\mathcal{O}(1)$ time, with constants based on number of dimensions.
   1818 
   1819 By the system of quadratic equations stated above, we see that there are at most $2$ solutions. It is sufficient to take the one that happens to be inside the intersection. (If there are two such solutions, take the larger one. For the current version of the data this check is not necessary, but it does not hurt to try.) Thus, for some $n \gt 3$, the bases can be represented with some $k \le 3$ circles.
   1820 
   1821 Do note that, already, we have an $\mathcal{O}(n^3)$ solution based on this. We enumerate all possible bases, and find the smallest one out of them (since that one will be the one that satisfies the conditions).
   1822 
   1823 Now, for some basis circle $(x,y,r)$, we can check whether some given circle $(x_i,y_i,r_i)$ is "violated" by this basis (i.e. this basis is not inside this circle) in $\mathcal{O}(1)$ by comparing the distance. We take an incremental approach. We add circles to the basis one by one, up to $3$ circles. We choose to change the basis if only the next added circle is violated by the current basis. Of course, still this takes $\mathcal{O}(n^3)$ time, and sorting the circles based on any argument will not help anyways.
   1824 
   1825 However, adding the circles in **random order** will make it only take expected $\mathcal{O}(n)$ time. This can be analyzed by the probability that a new basis will be added. The precise analysis for the time complexity is left as a practice for the reader.
   1826 
   1827 If you have seen the minimum enclosing circle problem, the Welzl's algorithm to solve that precise problem will seem very similar to this. In fact, the suggested algorithm itself is not very different from Welzl's algorithm. If you want, though, you may take an iterative approach instead of modifying Welzl's algorithm. Using three nested loops will do.
   1828 
   1829 There is only two issues left. The first is the issue of numerical instability. Sometimes, due to numerical instability, the algorithm will return a NaN value. It is not that hard to solve, we can simply shuffle again and rerun the algorithm. The given time limit will be sufficient for doing this unless the constant is too big. The second is more tricky, and it is about hacks.
   1830 
   1831 If you use a fixed seed for randomization (or time-based seeds to some extent), someone may hack you by adding an adversarial test case which makes the time complexity explode back to $\mathcal{O}(n^3)$. This is very bad. How do we solve this? To intervent this, we will make the algorithm halt when the number of iterations exceed a certain limit. Formally, let us choose a constant $c$, and the algorithm will halt and rerun when the number of iterations exceeds $c \cdot n$. Then, if the probability of the algorithm successfully running in this number of iterations is $p$, the expected number of reruns needed is $\mathcal{O}(1/p)$, and hacking is much harder. The algorithm will successfully find the solution in $\mathcal{O}((c/p) \cdot n)$ time. Of course, the probability $p$ depends on $c$, and you must tune the value as needed. Empirically $c=30$ runs very well, almost always taking no longer than $0.4$ seconds under proper optimizations, and $1.5$ seconds without.
   1832 
   1833 **solution**
   1834 
   1835 ```
   1836 #include<bits/stdc++.h>
   1837 using namespace std;
   1838 using ll=long long;
   1839  
   1840 using lf=long double;
   1841 using pt=pair<lf,lf>;
   1842 lf& real(pt& p){return p.first;}
   1843 lf& imag(pt& p){return p.second;}
   1844 pt midp(pt a,pt b){return pt{(real(a)+real(b))/2,(imag(a)+imag(b))/2};}
   1845 pt addi(pt a,pt b){return pt{(real(a)+real(b)),(imag(a)+imag(b))};}
   1846 pt subt(pt a,pt b){return pt{(real(a)-real(b)),(imag(a)-imag(b))};}
   1847 pt mult(pt a,lf b){return pt{real(a)*b,imag(a)*b};}
   1848 lf abs(pt a){return sqrtl(powl(real(a),2)+powl(imag(a),2));}
   1849 lf dist(pt a,pt b){return sqrtl(powl(real(a)-real(b),2)+powl(imag(a)-imag(b),2));}
   1850  
   1851 struct circ{pt p;lf r;};
   1852 const lf inf=1e18;
   1853  
   1854 circ basis0(){return {pt{0,0},inf};}
   1855  
   1856 circ basis1(circ a){return a;}
   1857  
   1858 circ basis2(circ a,circ b)
   1859 {
   1860     pt aa=a.p,bb=b.p;
   1861     pt ab=subt(bb,aa),ba=subt(aa,bb);
   1862     lf aab=abs(ab),aba=abs(ba);
   1863     real(ab)/=aab;
   1864     imag(ab)/=aab;
   1865     real(ba)/=aba;
   1866     imag(ba)/=aba;
   1867     pt ar=addi(aa,mult(ab,a.r)),br=addi(bb,mult(ba,b.r));
   1868     
   1869     return {midp(ar,br),dist(ar,br)/2.0L};
   1870 }
   1871  
   1872 circ basis3(circ a,circ b,circ c)
   1873 {
   1874     lf x1=real(a.p),y1=imag(a.p),r1=a.r;
   1875     lf x2=real(b.p),y2=imag(b.p),r2=b.r;
   1876     lf x3=real(c.p),y3=imag(c.p),r3=c.r;
   1877     lf a2=x1-x2,a3=x1-x3,b2=y1-y2,b3=y1-y3,c2=r2-r1,c3=r3-r1;
   1878     lf d1=x1*x1+y1*y1-r1*r1,d2=d1-x2*x2-y2*y2+r2*r2,d3=d1-x3*x3-y3*y3+r3*r3;
   1879     lf ab=a3*b2-a2*b3;
   1880     lf xa=(b2*d3-b3*d2)/(ab*2)-x1;
   1881     lf xb=(b3*c2-b2*c3)/ab;
   1882     lf ya=(a3*d2-a2*d3)/(ab*2)-y1;
   1883     lf yb=(a2*c3-a3*c2)/ab;
   1884     lf A=xb*xb+yb*yb-1;
   1885     lf B=2*(r1+xa*xb+ya*yb);
   1886     lf C=xa*xa+ya*ya-r1*r1;
   1887     lf r=-(A?(B-sqrtl(B*B-4*A*C))/(2*A):C/B);
   1888     return {pt{x1+xa+xb*r,y1+ya+yb*r},r};
   1889 }
   1890  
   1891 bool viol(circ p,circ a)
   1892 {
   1893     return a.r<p.r+dist(a.p,p.p);
   1894 }
   1895  
   1896 circ solve(vector<circ>&v)
   1897 {
   1898     lf _nan=nan("aaa");
   1899     mt19937_64 mt(1999999);
   1900     //shuffle(begin(v),end(v),mt);
   1901     vector<circ>basis;
   1902     auto trivial=[&]()
   1903     {
   1904         if(size(basis)==0)return basis0();
   1905         if(size(basis)==1)return basis[0];
   1906         if(size(basis)==2)return basis2(basis[0],basis[1]);
   1907         return basis3(basis[0],basis[1],basis[2]);
   1908     };
   1909  
   1910     int counter=0;
   1911     
   1912     auto rec=[&](auto rec,int n)->circ
   1913     {
   1914         if(n==0||size(basis)==3)return trivial();
   1915         counter++;
   1916         if(counter>30*size(v))return {pt{0,0},_nan};
   1917         auto c=rec(rec,n-1);
   1918         auto p=v[n-1];
   1919         if(!viol(c,p)||isnan(c.r))return c;
   1920         basis.push_back(p);
   1921         c=rec(rec,n-1);
   1922         basis.pop_back();
   1923         return c;
   1924     };
   1925     auto c=rec(rec,size(v));
   1926     while(isnan(c.r))
   1927     {
   1928         counter=0;
   1929         shuffle(begin(v),end(v),mt);
   1930         c=rec(rec,size(v));
   1931     }
   1932     return c;
   1933 }
   1934  
   1935 int main()
   1936 {
   1937     cin.tie(0)->sync_with_stdio(0);
   1938     int n;cin>>n;
   1939     vector<circ>v(n);
   1940     for(auto&[p,r]:v)
   1941     {
   1942         ll x,y,rr;cin>>x>>y>>rr;
   1943         p={x,y};r=rr;
   1944     }
   1945     auto ans=solve(v);
   1946     cout<<setprecision(16)<<fixed<<real(ans.p)<<" "<<imag(ans.p)<<" "<<ans.r<<"\n";
   1947 }
   1948 ```