codeforces-scrape

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

1043.md (33285B)


      1 Source: https://codeforces.com/blog/entry/62797
      2 
      3 #### [1043A — Elections](//codeforces.com/contest/1043/problem/A)
      4 
      5 **Tutorial**
      6 
      7 We can observe that result cannot exceed 201 — Awruk gets at least 101 votes from one person and Elodreip cannot get more than 100 votes from one person. So we can iterate over every possible integer from 1 to 201 and check if Awruk wins with *k* set to this integer. We have to remember that *k* — *a**i* is always at least 0, so we have to check this condition too. Complexity *O*(*n* * *M*), where *M* denotes maximum possible value of *a**i*. Try to solve it in *O*(*n*).
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int n;
     17 int mx = 0, sum = 0;
     18 
     19 int main(){
     20 	scanf("%d", &n);
     21 	for(int i = 1; i <= n; ++i){
     22 		int a;	scanf("%d", &a);
     23 		mx = max(mx, a);
     24 		sum += a;
     25 	}
     26 	
     27 	sum *= 2;
     28 	sum += n;
     29 	sum /= n;
     30 	
     31 	printf("%d", max(sum, mx));
     32 	return 0;
     33 }
     34 ```
     35 
     36 Author: [Anadi](/profile/Anadi "Grandmaster Anadi")
     37 
     38 #### [1043B — Lost Array](//codeforces.com/contest/1043/problem/B)
     39 
     40 **Tutorial**
     41 
     42 First, let's observe that we can replace array *a**i* with array *b**i* = *a**i*  -  *a**i* - 1, because all we care about are differences between neighboring elements. Now, we can see that our lost array can have length *d* if and only if for every *j* such that *j*  +  *d*  ≤  *n*, *b**j*  =  *b**j* + *d*. So we can iterate over every possible *d* from 1 to *n* and check if it is correct in *O*(*n*). Complexity of whole algorithm is *O*(*n*2).
     43 
     44 **Solution**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 const int N = 1007;
     52 
     53 int n;
     54 int in[N];
     55 
     56 bool ok(int d){
     57 	for(int i = 0; i + d < n; ++i)
     58 		if(in[i + 1] - in[i] != in[i + d + 1] - in[i + d])
     59 			return false;
     60 	return true;
     61 }
     62 
     63 int main(){
     64 	scanf("%d", &n);
     65 	for(int i = 1; i <= n; ++i)
     66 		scanf("%d", &in[i]);
     67 	
     68 	vector <int> res;
     69 	for(int i = 1; i <= n; ++i)
     70 		if(ok(i))
     71 			res.push_back(i);
     72 	
     73 	printf("%d\n", res.size());
     74 	for(int v: res)
     75 		printf("%d ", v);
     76 	return 0;
     77 }
     78 ```
     79 
     80 Author: [Anadi](/profile/Anadi "Grandmaster Anadi")
     81 
     82 #### [1043C — Smallest Word](//codeforces.com/contest/1043/problem/C)
     83 
     84 **Tutorial**
     85 
     86 Basically in problem we are given a word in which for every *i* we can reverse prefix of first *i* elements and we want to get the smallest lexicographically word. We will show that we can always achieve word in form *a**j**b**n* - *j*.
     87 
     88 Let's say that we solved our problem for prefix of length *i* and for this prefix we have word *a**j**b**i* - *j* (at the beginning it's just empty word). If our next letter is *b* then we do nothing, because we will get word *a**j**b**i* - *j* + 1 which is still the smallest lexicographically word. Otherwise we want to reverse prefix of length *i*, add letter *a* and reverse prefix of length *i*  +  1, so we get a word *a**j* + 1*b**i* - *j*, which is still fine for us.
     89 
     90 There is still a problem — what if we have already reversed prefix *i* and we just said that we will reverse it second time. But instead of reversing it second time, we can deny it's first reverse.
     91 
     92 Final complexity is *O*(*n*).
     93 
     94 **Solution**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 
     99 using namespace std;
    100 
    101 const int N = 1007;
    102 
    103 string s;
    104 bool write[N];
    105 
    106 int main(){
    107 	cin >> s;
    108 	for(int i = 1; i < s.size(); ++i)
    109 		if(s[i] == 'a'){
    110 			write[i - 1] ^= 1;
    111 			write[i] = 1;
    112 		}
    113 	
    114 	for(int i = 0; i < s.size(); ++i)
    115 		printf("%d%c", write[i], i + 1 == (int)s.size() ? '\n' : ' ');
    116 	return 0;
    117 }
    118 ```
    119 
    120 Author: [Anadi](/profile/Anadi "Grandmaster Anadi")
    121 
    122 #### [1043D — Mysterious Crime](//codeforces.com/contest/1043/problem/D)
    123 
    124 **Tutorial**
    125 
    126 Deleting prefix and suffix is nothing more than taking a subarray. If subarray is common for all permutations then it has to appear in first permutation. We renumber all permutations such that first permutation is 1, 2, ..., *n*  -  1, *n*.
    127 
    128 Now for every *i* in every permutation we count how long is subarray starting at *i* which looks like *i*, *i*  +  1, ..., *i*  +  *k*. It can be easily done in *O*(*n*) for one permutation with two pointers technique.
    129 
    130 Now for every element *i* we compute *reach*[*i*] equal the longest subarray starting in *i* which looks like *i*, *i*  +  1, ..., *i*  +  *k* and it apears in all subarrays. It is just minimum over previously calculated values for all permutations.
    131 
    132 Now we can see that our result is ![](https://espresso.codeforces.com/9f35a7d84286b4af4385390739e74f7b2e293533.png). Final complexity *O*(*nm*).
    133 
    134 **Solution**
    135 
    136 ```
    137 #include <bits/stdc++.h>
    138 
    139 using namespace std;
    140 
    141 typedef long long int LL;
    142 
    143 const int N = 1e5 + 7;
    144 
    145 int n, m;
    146 int mn[N];
    147 int ren[N];
    148 int perm[15][N];
    149 
    150 int main(){
    151 	scanf("%d %d", &n, &m);
    152 	for(int i = 1; i <= m; ++i)
    153 		for(int j = 1; j <= n; ++j)
    154 			scanf("%d", &perm[i][j]);
    155 	
    156 	for(int i = 1; i <= n; ++i)
    157 		ren[perm[1][i]] = i;
    158 	
    159 	for(int i = 1; i <= m; ++i)
    160 		for(int j = 1; j <= n; ++j)
    161 			perm[i][j] = ren[perm[i][j]];
    162 		
    163 	for(int i = 1; i <= n; ++i)
    164 		mn[i] = n;
    165 		
    166 	for(int i = 1; i <= m; ++i){
    167 		int cur = 1;
    168 		for(int j = 1; j <= n; ++j){
    169 			if(cur < j)
    170 				++cur;
    171 
    172 			while(cur < n && perm[i][cur + 1] == perm[i][cur] + 1)
    173 				++cur;
    174 			mn[perm[i][j]] = min(mn[perm[i][j]], perm[i][cur]);
    175 		}
    176 	}
    177 	
    178 	LL res = 0;
    179 	int now = 1;
    180 	while(now <= n){
    181 		int cur = mn[now] - now + 1;
    182 		res += 1LL * (cur + 1) * cur / 2LL;
    183 		now = mn[now] + 1;
    184 	}
    185 	
    186 	printf("%lld\n", res);
    187 	return 0;
    188 }
    189 ```
    190 
    191 Author: [Anadi](/profile/Anadi "Grandmaster Anadi")
    192 
    193 #### [1043E — Train Hard, Win Easy](//codeforces.com/contest/1043/problem/E)
    194 
    195 **Tutorial**
    196 
    197 Let's compute result if there are no edges, we can add them later. If there are no edges then result for pair (*i*, *j*) is min(*x**i*  +  *y**j*, *x**j*  +  *y**i*). First let's fix *i* for which we want to compute result. Then calculate result with all pairs *j* such that *x**i*  +  *y**j*  ≤  *x**j*  +  *y**i*. After some transformations we get that *x**i*  -  *y**i*  ≤  *x**j*  -  *y**j*. Similarly we have that *y**i*  +  *x**j*  <  *x**i*  +  *y**j* if *x**i*  -  *y**i*  >  *y**j*  -  *x**j*.
    198 
    199 So let's sort over differences of *x**i*  -  *y**i* and compute prefix sums of *x**i* and suffix sums of *y**i*. Now we can compute for every *i* result in *O*(1). Then we can iterate over every edge (*u*, *v*) and subtract min(*x**u*  +  *y**v*, *x**v*  +  *y**u*) from result of *u* and *v*.
    200 
    201 Complexity *O*(*nlogn*).
    202 
    203 **Solution**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 
    208 using namespace std;
    209 
    210 typedef long long int LL;
    211 
    212 #define st first
    213 #define nd second
    214 #define PII pair <int, int>
    215 
    216 const int N = 3e5 + 7;
    217 
    218 int n, m;
    219 PII diff[N];
    220 int place[N];
    221 vector <int> G[N];
    222 
    223 LL ans[N];
    224 int x[N], y[N];
    225 LL pref[N], suf[N];
    226 
    227 int main(){
    228 	scanf("%d %d", &n, &m);
    229 	for(int i = 1; i <= n; ++i){
    230 		scanf("%d %d", &x[i], &y[i]);
    231 		diff[i] = {y[i] - x[i], i};
    232 	}
    233 	
    234 	for(int i = 1; i <= m; ++i){
    235 		int u, v;
    236 		scanf("%d %d", &u, &v);
    237 
    238 		G[u].push_back(v);
    239 		G[v].push_back(u);
    240 	}
    241 	
    242 	sort(diff + 1, diff + n + 1);
    243 	for(int i = 1; i <= n; ++i)
    244 		place[diff[i].nd] = i;
    245 	
    246 	for(int i = 1; i <= n; ++i)
    247 		pref[i] = pref[i - 1] + y[diff[i].nd];
    248 	
    249 	for(int i = n; i >= 1; --i)
    250 		suf[i] = suf[i + 1] + x[diff[i].nd];
    251 	
    252 	for(int i = 1; i <= n; ++i){
    253 		int u = diff[i].nd;
    254 		LL res = pref[i - 1] + suf[i + 1] + 1LL * (i - 1) * x[u] + 1LL * (n - i) * y[u];
    255 		
    256 		for(int v: G[u])
    257 			res -= min(x[u] + y[v], x[v] + y[u]);
    258 		ans[u] = res;
    259 	}
    260 	
    261 	for(int i = 1; i <= n; ++i)
    262 		printf("%lld ", ans[i]);
    263 	return 0;
    264 }
    265 ```
    266 
    267 Author: [Rzepa](/profile/Rzepa "International Master Rzepa")
    268 
    269 #### [1043F — Make It One](//codeforces.com/contest/1043/problem/F)
    270 
    271 **Tutorial**
    272 
    273 First let's observe that if there exists valid subset then it's size is at most 7 (because product of 7 smallest primes is bigger then 3 * 105). Let's define *dp*[*i*][*j*] — number of ways to pick *i* different elements such that their gcd is equal to *j*. We can use inclusion--exclusion principle to calculate it. Then *dp*[*i*][*j*] = ![](https://espresso.codeforces.com/ba6272e17ff708d93c577b3369416ceb3038253e.png) — ![](https://espresso.codeforces.com/caa830cac0d32cf827067555c38e23aa2e7c3fa7.png), where *cnt**j* denotes number of *a**i* such that *j* | *a**i*. Because for *k* * *j*  >  3 * 105, *dp*[*i*][*k* * *j*]  =  0 we have to check only *k* * *j*  ≤  3 * 105.
    274 
    275 Our answer is the smallest *i* such that *dp*[*i*][1] is non-zero. Since *dp*[*i*][*j*] can be quite big we should compute it modulo some big prime.
    276 
    277 Final complexity is *O*(*logM* * (*n* + *M*)), where M is equal to maximum of *a**i*.
    278 
    279 **Solution 1**
    280 
    281 ```
    282 #include <bits/stdc++.h>
    283 
    284 using namespace std;
    285 
    286 const int N = 3e5 + 7;
    287 const int MX = 1e9 + 7;
    288 
    289 int n;
    290 int cnt[N];
    291 int sil[N];
    292 int odw[N];
    293 int dp[20][N];
    294 
    295 int fast(int a, int b){
    296 	int ret = 1;
    297 	while(b){
    298 		if(b & 1)
    299 			ret = (1LL * ret * a)%MX;
    300 		
    301 		b >>= 1;
    302 		a = (1LL * a * a)%MX;
    303 	}
    304 	
    305 	return ret;
    306 }
    307 
    308 int newton(int a, int b){
    309 	if(b < 0 || a < b)	return 0;
    310 	return (((1LL * sil[a] * odw[b])%MX) * odw[a - b])%MX;
    311 }
    312 
    313 void sub(int &a, int b){
    314 	a -= b;
    315 	if(a < 0)
    316 		a += MX;
    317 }
    318 
    319 int main(){
    320 	sil[0] = 1;
    321 	for(int i = 1; i < N; ++i)
    322 		sil[i] = (1LL * sil[i - 1] * i)%MX;
    323 	
    324 	odw[N - 1] = fast(sil[N - 1], MX - 2);
    325 	for(int i = N - 1; i >= 1; --i)
    326 		odw[i - 1] = (1LL * odw[i] * i)%MX;
    327 
    328 	scanf("%d", &n);
    329 	for(int i = 1; i <= n; ++i){
    330 		int a;
    331 		scanf("%d", &a);
    332 		cnt[a]++;
    333 	}
    334 	
    335 	for(int i = 1; i < N; ++i)
    336 		for(int j = i + i; j < N; j += i)
    337 			cnt[i] += cnt[j];
    338 	
    339 	for(int i = 1; i < 20; ++i){
    340 		for(int j = N - 1; j >= 1; --j){
    341 			dp[i][j] = newton(cnt[j], i);
    342 			for(int k = j + j; k < N; k += j)
    343 				sub(dp[i][j], dp[i][k]);
    344 		}
    345 		
    346 		if(dp[i][1] > 0){
    347 			printf("%d\n", i);
    348 			return 0;
    349 		}
    350 	}
    351 	
    352 	puts("-1");
    353 	return 0;
    354 }
    355 ```
    356 
    357 **Solution 2**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361 
    362 using namespace std;
    363 
    364 const int N = 3e5 + 7;
    365 
    366 int n;
    367 int cnt[N];
    368 int roz[N];
    369 int dist[N];
    370 queue <int> Q;
    371 vector <int> dv[N];
    372 
    373 int base(int a){
    374 	int ret = 1;
    375 	while(a > 1){
    376 		if(ret%roz[a] != 0)
    377 			ret *= roz[a];
    378 		a /= roz[a];
    379 	}
    380 	
    381 	return ret;
    382 }
    383 
    384 void getEdges(int u, int d){
    385 	vector <int> cur;
    386 	vector <int> val;
    387 	
    388 	while(u > 1){
    389 		cur.push_back(roz[u]);
    390 		u /= roz[u];
    391 	}
    392 	
    393 	for(int v: cur)
    394 		u *= v;
    395 	
    396 	int T = 1 << (int)cur.size();
    397 	val.resize(T);
    398 	
    399 	for(int i = 0; i < T; ++i){
    400 		val[i] = u;
    401 		for(int j = 0; j < (int)cur.size(); ++j)
    402 			if(i & (1 << j))
    403 				val[i] /= cur[j];
    404 	}
    405 	
    406 	for(int i = 0; i < T; ++i){
    407 		int s = 0;
    408 		for(int j = i; true; j = (j - 1) & i){
    409 			if(__builtin_popcount(i ^ j) & 1)
    410 				s -= cnt[val[j]];
    411 			else
    412 				s += cnt[val[j]];
    413 			
    414 			if(j == 0)
    415 				break;
    416 		}
    417 		
    418 		assert(s >= 0);
    419 		if(s && dist[val[i]] == -1){
    420 			dist[val[i]] = d;
    421 			Q.push(val[i]);
    422 		}
    423 	}
    424 }
    425 
    426 int main(){
    427 	scanf("%d", &n);
    428 	for(int i = 2; i < N; ++i){
    429 		if(roz[i] != 0)
    430 			continue;
    431 
    432 		for(int j = i; j < N; j += i)
    433 			roz[j] = i;
    434 	}
    435 	
    436 	for(int i = 1; i < N; ++i)
    437 		for(int j = i; j < N; j += i)
    438 			dv[j].push_back(i);
    439 	
    440 	for(int i = 1; i < N; ++i)
    441 		dist[i] = -1;
    442 	
    443 	for(int i = 1; i <= n; ++i){
    444 		int a;
    445 		scanf("%d", &a);
    446 		a = base(a);
    447 		
    448 		if(dist[a] != -1)
    449 			continue;
    450 
    451 		dist[a] = 1;
    452 		Q.push(a);
    453 		
    454 		for(int v: dv[a])
    455 			cnt[v]++;
    456 	}
    457 	
    458 	while(!Q.empty()){
    459 		int u = Q.front();
    460 		Q.pop();
    461 		getEdges(u, dist[u] + 1);
    462 	}
    463 	
    464 	printf("%d\n", dist[1]);
    465 	return 0;
    466 }
    467 ```
    468 
    469 Author: [Anadi](/profile/Anadi "Grandmaster Anadi")
    470 
    471 #### [1043G — Speckled Band](//codeforces.com/contest/1043/problem/G)
    472 
    473 **Tutorial**
    474 
    475 Let's solve the problem for some string *s* for any time.
    476 
    477 Let's say, that partition of string *s* into *k* strings *s*1*s*2... *s**i*1, *s**i*1 + 1... *s**i*2, ..., {*s**i**k* - 1 + 1}... *s**i**k* is good if at least one pair of this strings are equal. We want to find a minimal possible number of different strings in all good partitions.
    478 
    479 It's easy to see, that the answer is  - 1 if and only if all symbols in *s* are different. And if we have two equal symbols *s**i* = *s**j* (*i* < *j*) we can cut a string into strings *s*1... *s**i* - 1, *s**i*, *s**i* + 1... *s**j* - 1, *s**j*, *s**j* + 1... *s**n* and it is a good partition. In this partition there is at most 4 different strings.
    480 
    481 So the answer can be  - 1, 1, 2, 3, 4.
    482 
    483 The answer is  - 1 if all symbols in *s* are different (case 0).
    484 
    485 The answer is 1 if the string *s* = *aaa*... *a*, for some string *a* (case 1).
    486 
    487 The answer is 2 if the string *s* is *aab*, *aba* or *baa* for some strings *a* and *b* (case 2).
    488 
    489 The answer is 3 if the string *s* is *baac*, *bcaa* or *aabc* for some strings *a*, *b*, *c*. In two last cases it's easy to see, that |*a*| = 1 (case 3).
    490 
    491 To solve our problem let's build suffix array with lcp for string *s*. And let's find *lt**i*~--- minimal possible number *r*, such that *s**is**i* + 1... *s**r* is a tandem (the string, that can be presented as *aa* for some string *a*) and *rt**i*~--- maximal possible number *l* such that *s**ls**l* + 1... *s**i* is a tandem. This numbers can be found using Main and Lorentz algorithm for finding tandem repetitions in the string.
    492 
    493 Now we can solve query for segment [*l*, *r*]: \begin{itemize} \item Case 0: if *r* - *l* ≥ 26, there exists equal symbols, otherwise we can check it by *O*(*r* - *l*); \item Case 1: to check that *s*[*l*... *r*] = *aa*... *a* we can see that |*a*| is a divisor of (*r* - *l* + 1) and (*r* - *l* + 1) / |*a*| is a prime number (if we take a longest possible string *a*). So we should check only *O*(*log*(*n*)) lenghts of string *a*; \item Case 2: *s* = *aab* ![](https://espresso.codeforces.com/a0c29c1e7b0d02c52cb1ab0f5e8357ee1e42253b.png) *lt**l* ≤ *r*, *s* = *baa* ![](https://espresso.codeforces.com/a0c29c1e7b0d02c52cb1ab0f5e8357ee1e42253b.png) *rt**r* ≥ *l*. In the last case we should check, that *s*[*l*... *r*] has a border. It's the most interesting part of the problem, let's solve it in the end; \item Case 3: *s* = *abac* ![](https://espresso.codeforces.com/a0c29c1e7b0d02c52cb1ab0f5e8357ee1e42253b.png) *s**l* exists on *s**l* + 1... *s**r* (can be done using prefix sums), *s* = *baca* ![](https://espresso.codeforces.com/a0c29c1e7b0d02c52cb1ab0f5e8357ee1e42253b.png) *s**r* exists on *s**l*... *s**r* - 1 (can be done using prefix sums). To check *s* = *baac* we can check, that *lt**i* ≤ *r* for some *l* ≤ *i* ≤ *r*, that can be done using minimum on segment in the array *lt*. \end{itemize}
    494 
    495 Now we should the hardest part of this problem~--- we have some segments [*l*, *r*]. For all of them, we should check that the border of *s*[*l*... *r*] exists. Here I know two methods, that uses only suffix array. Easiest of them:
    496 
    497 We have segment [*l*, *r*]. Let's check for all lengths ![](https://espresso.codeforces.com/cb0af4bf2b002f9b60513cd16994698327d63ee2.png), that *s*[*l*... (*l* + *b* - 1)] = *s*[(*r* - *b* + 1)... *r*]. If we don't find border, if it exists, it's length ![](https://espresso.codeforces.com/0b41722e4cb27e9562ef257c0c8384d5448f5b79.png). Let's define *i*~--- maximal index *i* such that *lcp*(*l*, *i*) ≥ *r* - *i* + 1, and string *s*[*i*... *r*] is a border of *s*[*l*... *r*]. So ![](https://espresso.codeforces.com/f2c2099aebbb81c82d9334d47b9c1533f5f237a8.png). But it's easy to see, that the distance between *l* and *i* in suffix array ![](https://espresso.codeforces.com/c3d7ab675f5f8ac3a9adf05ea0debb585352a7ab.png) , so we need to check only ![](https://espresso.codeforces.com/5a41da22acdba46e7c8eeeaddbc58625f49cbfe5.png) variants of *i*.
    498 
    499 Another method can check that border exists for all segments [*l*, *r*] using offline algorithm by *O*(*q*·*log*(*n*)2) time.
    500 
    501 So the total complexity will be ![](https://espresso.codeforces.com/ca39dc3b93e11c2ba6dd7fc8594af6a038a5642d.png) or *O*((*n* + *q*)·*log*(*n*)2).
    502 
    503 **Solution 1**
    504 
    505 ```
    506 #include <bits/stdc++.h>
    507 
    508 using namespace std;
    509 
    510 const int BIG = 1e9 + 239;
    511 const int M = 2 * 1e5 + 239;
    512 const int L = 19;
    513 const int A = 30;
    514 const int T = (1 << 19);
    515 const int two = 2;
    516 
    517 int flm[two][M];
    518 
    519 inline void z_function(string &s, int c)
    520 {
    521 	int n = s.length();
    522 	flm[c][0] = 0;
    523 	int l = 0;
    524 	int r = 0;
    525 	for (int i = 1; i < n; i++)
    526 	{
    527 		flm[c][i] = min(flm[c][i - l], r - i);
    528 		if (flm[c][i] < 0) flm[c][i] = 0;
    529 		while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++;
    530 		if (i + flm[c][i] > r)
    531 		{
    532 			l = i;
    533 			r = i + flm[c][i];
    534 		}
    535 	}        
    536 }
    537 
    538 int a[M], lcp[M], pos[M];
    539 
    540 inline void suffix_array(string s)
    541 {
    542 	s += (char)(31);
    543 	int n = s.length();
    544 	vector<pair<char, int> > v;
    545 	for (int i = 0; i < n; i++)
    546 		v.push_back(make_pair(s[i], i));
    547 	sort(v.begin(), v.end());
    548 	vector<pair<int, int> > num;
    549 	int last = 0;
    550 	for (int i = 0; i < n - 1; i++)
    551 	{
    552 		num.push_back(make_pair(last, v[i].second));
    553 		if (v[i].first != v[i + 1].first) last++;
    554 	}
    555 	num.push_back(make_pair(last, v.back().second));
    556 	vector<int> u(n);
    557 	for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
    558 	int d = 1;
    559 	vector<pair<pair<int, int>, int> > t;
    560 	vector<vector<pair<int, int> > > h;
    561 	while (d < n)
    562 	{
    563 		t.clear();
    564 		h.clear();
    565 		h.resize(n);
    566 		for (int i = 0; i < n; i++)
    567 		{
    568 			int l = num[i].second - d;
    569 			if (l < 0) l += n;
    570 			h[u[l]].push_back(make_pair(num[i].first, l));
    571 		}
    572 		for (int i = 0; i < n; i++)
    573 			for (pair<int, int> r : h[i])
    574 				t.push_back(make_pair(make_pair(i, r.first), r.second));
    575 		last = 0;
    576 		num.clear();
    577 		for (int i = 0; i < n - 1; i++)
    578 		{
    579 			num.push_back(make_pair(last, t[i].second));
    580 			if (t[i].first != t[i + 1].first) last++;
    581 		}
    582 		num.push_back(make_pair(last, t.back().second));
    583 		for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
    584 		d <<= 1;
    585 	}                           
    586 	for (int i = 1; i < n; i++) a[i - 1] = num[i].second;
    587 }
    588 
    589 string s;                 
    590 
    591 inline void kasai()
    592 {
    593 	int n = s.size();
    594 	suffix_array(s); 
    595 	for (int i = 0; i < n; i++)
    596 		pos[a[i]] = i;
    597 	int k = 0;
    598 	for (int i = 0; i < n; i++)
    599 	{
    600 		if (pos[i] == n - 1) continue;
    601 		while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++;
    602 		lcp[pos[i]] = k;
    603 		k = max(0, k - 1);
    604 	}
    605 }
    606 
    607 int n, lw[M], rw[M]; 
    608 string prr, rvl;                     
    609 vector<int> open_l[M], close_l[M];   
    610 vector<int> open_r[M], close_r[M];
    611 multiset<int> nw;
    612 
    613 inline void func(int l, int r)
    614 {
    615 	if (r - l == 1) return;
    616 	int mid = (l + r) >> 1;
    617 	func(l, mid);
    618 	func(mid, r);
    619 	rvl = "";
    620 	for (int i = mid - 1; i >= l; i--) rvl += s[i];
    621 	z_function(rvl, 0);
    622 	prr = "";
    623 	for (int i = mid; i < r; i++) prr += s[i];
    624 	prr += '#';
    625 	for (int i = l; i < mid; i++) prr += s[i];
    626 	z_function(prr, 1);	
    627 	for (int c = l; c < mid; c++)
    628 	{
    629 		int k1 = 0;
    630 		if (c > l) k1 = flm[0][mid - c];
    631 		int k2 = flm[1][r - mid + 1 + c - l];
    632 		int len = mid - c;
    633 		int lg = max(len - k2, 0);
    634 		int rg = min(len - 1, k1);
    635 		if (rg >= lg)
    636 		{
    637 			open_l[c - rg].push_back((2 * len));
    638 			close_l[c - lg].push_back((2 * len));
    639 			open_r[c - rg + 2 * len - 1].push_back((2 * len));
    640 			close_r[c - lg + 2 * len - 1].push_back((2 * len));
    641 		}	
    642 	}
    643 	rvl = "";
    644 	for (int i = mid; i < r; i++) rvl += s[i];
    645 	z_function(rvl, 0);
    646 	prr = "";
    647 	for (int i = mid - 1; i >= l; i--) prr += s[i];
    648 	prr += '#';
    649 	for (int i = r - 1; i >= mid; i--) prr += s[i];
    650 	z_function(prr, 1); 
    651 	for (int c = mid; c < r; c++)
    652 	{
    653 		int k1 = 0;
    654 		if (c != r - 1) k1 = flm[0][c + 1 - mid];
    655 		int k2 = flm[1][r - c + mid - l];
    656 		int len = c - mid + 1;
    657 		int lg = max(len - k2, 0);
    658 		int rg = min(len - 1, k1);
    659 		if (rg >= lg)
    660 		{                                            
    661 			open_l[c + lg - 2 * len + 1].push_back((2 * len));
    662 			close_l[c + rg - 2 * len + 1].push_back((2 * len));
    663 			open_r[c + lg].push_back((2 * len));
    664 			close_r[c + rg].push_back((2 * len));
    665 		}	
    666 	}
    667 	for (int i = l; i < r; i++)
    668 	{
    669 		for (int len : open_l[i]) nw.insert(len);
    670 		if (!nw.empty()) lw[i] = min(lw[i], *nw.begin());
    671 		for (int len : close_l[i]) nw.erase(nw.lower_bound(len));
    672 		open_l[i].clear();
    673 		close_l[i].clear();
    674 	}          
    675 	for (int i = l; i < r; i++)
    676 	{
    677 		for (int len : open_r[i]) nw.insert(len);
    678 		if (!nw.empty()) rw[i] = min(rw[i], *nw.begin());
    679 		for (int len : close_r[i]) nw.erase(nw.lower_bound(len));
    680 		open_r[i].clear();
    681 		close_r[i].clear();
    682 	}
    683 }
    684 
    685 int mn[L][M], st2[M], lc[L][M], kol[A][M];
    686 
    687 inline int getmin(int l, int r)
    688 {
    689 	int u = st2[r - l + 1];
    690 	return min(mn[u][l], mn[u][r - (1 << u) + 1]);
    691 }
    692 
    693 inline int gett(int l, int r)
    694 {
    695 	if (l == r) return (n - l);
    696 	l = pos[l];
    697 	r = pos[r];
    698 	if (l > r) swap(l, r);
    699 	r--;
    700 	int u = st2[r - l + 1];
    701 	return min(lc[u][l], lc[u][r - (1 << u) + 1]);
    702 }
    703 
    704 int q, la[M], ra[M], has[M], mnp[M];
    705 
    706 inline void init()
    707 {
    708 	for (int i = 0; i < n; i++) mn[0][i] = lw[i];
    709 	for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i];
    710 	for (int i = 1; i < L; i++)
    711 		for (int j = 0; j < n; j++)
    712 		{
    713 			int r = (j + (1 << (i - 1)));
    714 			if (r >= n)
    715 			{
    716 				mn[i][j] = mn[i - 1][j];
    717 				continue;
    718 			}
    719 			mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]);
    720 		}
    721 	for (int i = 1; i < L; i++)
    722 		for (int j = 0; j < n - 1; j++)
    723 		{
    724 			int r = (j + (1 << (i - 1)));
    725 			if (r >= n - 1)
    726 			{
    727 				lc[i][j] = lc[i - 1][j];
    728 				continue;
    729 			}                                          
    730 			lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]);
    731 		}	
    732 	st2[1] = 0;
    733 	for (int i = 2; i <= n; i++)
    734 	{
    735 		st2[i] = st2[i - 1];
    736 		if ((1 << (st2[i] + 1)) <= i) st2[i]++;
    737 	}	
    738 }
    739 
    740 int in[L][M], gl[T];
    741 
    742 inline void build(int i, int l, int r)
    743 {
    744 	if (i == 0) gl[i] = 0;
    745 	else gl[i] = gl[(i - 1) / 2] + 1;
    746 	if (r - l == 1)
    747 	{
    748 		in[gl[i]][l] = a[l];
    749 		return;
    750 	}
    751 	int mid = (l + r) >> 1;
    752 	build(2 * i + 1, l, mid);
    753 	build(2 * i + 2, mid, r);
    754 	merge(in[gl[i] + 1] + l, in[gl[i] + 1] + mid, in[gl[i] + 1] + mid, in[gl[i] + 1] + r, in[gl[i]] + l);
    755 }
    756 
    757 inline bool is_on(int i, int l, int r, int ql, int qr, int xl, int xr)
    758 {
    759 	if (r <= ql || qr <= l) return false;
    760 	if (ql <= l && r <= qr)
    761 	{
    762 		int it = upper_bound(in[gl[i]] + l, in[gl[i]] + r, xl) - in[gl[i]] - l;
    763 		if (it == r - l) return false;
    764 		return (in[gl[i]][it + l] <= xr);	
    765 	}
    766 	int mid = (l + r) >> 1;
    767 	if (is_on(2 * i + 1, l, mid, ql, qr, xl, xr)) return true;
    768 	return is_on(2 * i + 2, mid, r, ql, qr, xl, xr);
    769 }
    770 
    771 inline bool check_all(int l, int r)
    772 {
    773 	int len = (r - l + 1);
    774 	int pl = pos[l];
    775 	int lf = pl;
    776 	int rf = n;
    777 	while (rf - lf > 1)
    778 	{
    779 		int h = (lf + rf) / 2;
    780 		if (gett(a[h], l) >= len) lf = h;
    781 		else rf = h;
    782 	}
    783 	int rg = lf + 1;
    784 	lf = -1;
    785 	rf = pl;
    786 	while (rf - lf > 1)
    787 	{
    788 		int h = (lf + rf) / 2;
    789 		if (gett(a[h], l) >= len) rf = h;
    790 		else lf = h;
    791 	}
    792 	int lg = rf;
    793 	return is_on(0, 0, n, lg, rg, l, r);
    794 }
    795 
    796 int par[M];
    797 set<int> cmp[M];
    798 set<pair<int, int> > sc[M];
    799 vector<int> ok[M];
    800 vector<pair<int, int> > mg[M];
    801 
    802 inline void border_check()
    803 {
    804 	for (int i = 0; i < q; i++) has[i] = false;
    805 	for (int i = 0; i < q; i++) ok[ra[i] - la[i]].push_back(i);
    806 	for (int i = 0; i < n - 1; i++) mg[lcp[i]].push_back(make_pair(a[i], a[i + 1]));
    807 	for (int i = 0; i < n; i++)
    808 	{
    809 		par[i] = i;
    810 		cmp[i].insert(i);
    811 	}
    812 	for (int c = n; c >= 1; c--)
    813 	{
    814 		for (int i : ok[c - 1])
    815 			sc[par[la[i]]].insert(make_pair(ra[i], i));   
    816 		for (pair<int, int> t : mg[c])
    817 		{
    818 			int l = par[t.first];
    819 			int r = par[t.second];
    820 			if (cmp[l].size() > cmp[r].size()) swap(l, r);
    821 			for (int x : cmp[l])
    822 				while (true)
    823 				{
    824 					auto it = sc[r].lower_bound(make_pair(x, 0));
    825 					if (it == sc[r].end() || it->first > x + c - 1) break;
    826 					has[it->second] = true;
    827 					sc[r].erase(it);
    828 				}
    829 			for (pair<int, int> u : sc[l])
    830 			{
    831 				int id = u.second;
    832 				auto uk = cmp[r].lower_bound(ra[id] - c + 1);
    833 				if (uk != cmp[r].end() && (*uk) <= ra[id]) 
    834 					has[id] = true;
    835 				else 
    836 				    sc[r].insert(u);
    837 			}
    838 			for (int x : cmp[l])
    839 			{
    840 				par[x] = r;
    841 				cmp[r].insert(x);
    842 			}
    843 		}		
    844 	}	
    845     for (int i = 0; i < q; i++)
    846 	    if (!has[i] && check_all(la[i], ra[i]))
    847 		{
    848 			has[i] = true;
    849 			continue;
    850 		}
    851 }
    852 
    853 inline bool checkno(int l, int r)
    854 {
    855 	if (r - l + 1 > 26) return false;
    856 	vector<int> kol(26, 0);
    857 	for (int x = l; x <= r; x++)
    858 	{
    859 		if (kol[s[x] - 'a'] > 0) return false;
    860 		kol[s[x] - 'a']++;
    861 	}	
    862 	return true;
    863 }
    864 
    865 inline bool try_kol(int l, int r, int p)
    866 {
    867 	int len = (r - l + 1) / p;
    868 	return (gett(l, l + len) >= (r - l + 1 - len));
    869 }
    870 
    871 inline bool ison(int l, int r, char x)
    872 {
    873 	return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]);	
    874 }
    875 
    876 inline int query(int l, int r, int id)
    877 {         
    878 	if (checkno(l, r)) return -1;
    879 	int len = (r - l + 1);
    880 	while (len > 1)
    881 	{
    882 		int p = mnp[len];
    883 		if (try_kol(l, r, p)) return 1;
    884 		while ((len % p) == 0) len /= p;
    885 	}
    886 	if (lw[l] <= r) return 2;
    887 	if (rw[r] >= l) return 2;
    888 	if (has[id]) return 2;
    889 	if (ison(l + 1, r, s[l])) return 3;
    890 	if (ison(l, r - 1, s[r])) return 3;
    891 	if (getmin(l, r) <= r) return 3;	
    892 	return 4;
    893 }
    894 
    895 int main()
    896 {
    897 	cin.sync_with_stdio(0); 
    898 	cin >> n >> s;
    899 	memset(mnp, -1, sizeof(mnp));
    900 	for (int i = 2; i <= n; i++)
    901 		if (mnp[i] == -1)
    902 			for (int j = i; j <= n; j += i)
    903 				if (mnp[j] == -1)
    904 					mnp[j] = i;
    905 	memset(kol[0], 0, sizeof(kol[0]));
    906 	for (int i = 0; i < n; i++)
    907 	{
    908 		for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i];
    909 		kol[s[i] - 'a'][i + 1]++;
    910 	}
    911 	for (int i = 0; i < n; i++)
    912 	{
    913 		lw[i] = n + 1;
    914 		rw[i] = n + 1;
    915 	}
    916 	func(0, n);  
    917 	for (int i = 0; i < n; i++)
    918 	{
    919 		if (lw[i] == n + 1) lw[i] = n;
    920 		else lw[i] += (i - 1);  
    921 		if (rw[i] == n + 1) rw[i] = -1;
    922 		else rw[i] = (i - rw[i] + 1);
    923 	}
    924 	kasai();                                                                        
    925 	init();  
    926 	build(0, 0, n);                                                                       
    927 	cin >> q;
    928 	for (int i = 0; i < q; i++)
    929 	{
    930 		cin >> la[i] >> ra[i];
    931 		la[i]--, ra[i]--;                       
    932 	}
    933 	border_check();
    934 	for (int i = 0; i < q; i++) cout << query(la[i], ra[i], i) << "\n";
    935 	return 0;
    936 }
    937 ```
    938 
    939 **Solution 2**
    940 
    941 ```
    942 #include <bits/stdc++.h>
    943 
    944 using namespace std;
    945 
    946 #define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
    947 
    948 const int BIG = 1e9 + 239;
    949 const int M = 2 * 1e5 + 239;
    950 const int L = 19;
    951 const int A = 30;
    952 const int T = (1 << 19);
    953 const int two = 2;
    954 
    955 int flm[two][M];
    956 
    957 inline void z_function(string &s, int c)
    958 {
    959 	int n = s.length();
    960 	flm[c][0] = 0;
    961 	int l = 0;
    962 	int r = 0;
    963 	for (int i = 1; i < n; i++)
    964 	{
    965 		flm[c][i] = min(flm[c][i - l], r - i);
    966 		if (flm[c][i] < 0) flm[c][i] = 0;
    967 		while (i + flm[c][i] < n && s[flm[c][i]] == s[i + flm[c][i]]) flm[c][i]++;
    968 		if (i + flm[c][i] > r)
    969 		{
    970 			l = i;
    971 			r = i + flm[c][i];
    972 		}
    973 	}        
    974 }
    975 
    976 int a[M], lcp[M], pos[M];
    977 
    978 inline void suffix_array(string s)
    979 {
    980 	s += (char)(31);
    981 	int n = s.length();
    982 	vector<pair<char, int> > v;
    983 	for (int i = 0; i < n; i++)
    984 		v.push_back(make_pair(s[i], i));
    985 	sort(v.begin(), v.end());
    986 	vector<pair<int, int> > num;
    987 	int last = 0;
    988 	for (int i = 0; i < n - 1; i++)
    989 	{
    990 		num.push_back(make_pair(last, v[i].second));
    991 		if (v[i].first != v[i + 1].first) last++;
    992 	}
    993 	num.push_back(make_pair(last, v.back().second));
    994 	vector<int> u(n);
    995 	for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
    996 	int d = 1;
    997 	vector<pair<pair<int, int>, int> > t;
    998 	vector<vector<pair<int, int> > > h;
    999 	while (d < n)
   1000 	{
   1001 		t.clear();
   1002 		h.clear();
   1003 		h.resize(n);
   1004 		for (int i = 0; i < n; i++)
   1005 		{
   1006 			int l = num[i].second - d;
   1007 			if (l < 0) l += n;
   1008 			h[u[l]].push_back(make_pair(num[i].first, l));
   1009 		}
   1010 		for (int i = 0; i < n; i++)
   1011 			for (pair<int, int> r : h[i])
   1012 				t.push_back(make_pair(make_pair(i, r.first), r.second));
   1013 		last = 0;
   1014 		num.clear();
   1015 		for (int i = 0; i < n - 1; i++)
   1016 		{
   1017 			num.push_back(make_pair(last, t[i].second));
   1018 			if (t[i].first != t[i + 1].first) last++;
   1019 		}
   1020 		num.push_back(make_pair(last, t.back().second));
   1021 		for (int i = 0; i < n; i++) u[num[i].second] = num[i].first;
   1022 		d <<= 1;
   1023 	}                           
   1024 	for (int i = 1; i < n; i++) a[i - 1] = num[i].second;
   1025 }
   1026 
   1027 string s;                 
   1028 
   1029 inline void kasai()
   1030 {
   1031 	int n = s.size();
   1032 	suffix_array(s); 
   1033 	for (int i = 0; i < n; i++)
   1034 		pos[a[i]] = i;
   1035 	int k = 0;
   1036 	for (int i = 0; i < n; i++)
   1037 	{
   1038 		if (pos[i] == n - 1) continue;
   1039 		while (s[i + k] == s[a[pos[i] + 1] + k] && a[pos[i] + 1] + k < n && i + k < n) k++;
   1040 		lcp[pos[i]] = k;
   1041 		k = max(0, k - 1);
   1042 	}
   1043 }
   1044 
   1045 int n, lw[M], rw[M]; 
   1046 string prr, rvl;                     
   1047 vector<int> open_l[M], close_l[M];   
   1048 vector<int> open_r[M], close_r[M];
   1049 multiset<int> nw;
   1050 
   1051 inline void func(int l, int r)
   1052 {
   1053 	if (r - l == 1) return;
   1054 	int mid = (l + r) >> 1;
   1055 	func(l, mid);
   1056 	func(mid, r);
   1057 	rvl = "";
   1058 	for (int i = mid - 1; i >= l; i--) rvl += s[i];
   1059 	z_function(rvl, 0);
   1060 	prr = "";
   1061 	for (int i = mid; i < r; i++) prr += s[i];
   1062 	prr += '#';
   1063 	for (int i = l; i < mid; i++) prr += s[i];
   1064 	z_function(prr, 1);	
   1065 	for (int c = l; c < mid; c++)
   1066 	{
   1067 		int k1 = 0;
   1068 		if (c > l) k1 = flm[0][mid - c];
   1069 		int k2 = flm[1][r - mid + 1 + c - l];
   1070 		int len = mid - c;
   1071 		int lg = max(len - k2, 0);
   1072 		int rg = min(len - 1, k1);
   1073 		if (rg >= lg)
   1074 		{
   1075 			open_l[c - rg].push_back((2 * len));
   1076 			close_l[c - lg].push_back((2 * len));
   1077 			open_r[c - rg + 2 * len - 1].push_back((2 * len));
   1078 			close_r[c - lg + 2 * len - 1].push_back((2 * len));
   1079 		}	
   1080 	}
   1081 	rvl = "";
   1082 	for (int i = mid; i < r; i++) rvl += s[i];
   1083 	z_function(rvl, 0);
   1084 	prr = "";
   1085 	for (int i = mid - 1; i >= l; i--) prr += s[i];
   1086 	prr += '#';
   1087 	for (int i = r - 1; i >= mid; i--) prr += s[i];
   1088 	z_function(prr, 1); 
   1089 	for (int c = mid; c < r; c++)
   1090 	{
   1091 		int k1 = 0;
   1092 		if (c != r - 1) k1 = flm[0][c + 1 - mid];
   1093 		int k2 = flm[1][r - c + mid - l];
   1094 		int len = c - mid + 1;
   1095 		int lg = max(len - k2, 0);
   1096 		int rg = min(len - 1, k1);
   1097 		if (rg >= lg)
   1098 		{                                            
   1099 			open_l[c + lg - 2 * len + 1].push_back((2 * len));
   1100 			close_l[c + rg - 2 * len + 1].push_back((2 * len));
   1101 			open_r[c + lg].push_back((2 * len));
   1102 			close_r[c + rg].push_back((2 * len));
   1103 		}	
   1104 	}
   1105 	for (int i = l; i < r; i++)
   1106 	{
   1107 		for (int len : open_l[i]) nw.insert(len);
   1108 		if (!nw.empty()) lw[i] = min(lw[i], *nw.begin());
   1109 		for (int len : close_l[i]) nw.erase(nw.lower_bound(len));
   1110 		open_l[i].clear();
   1111 		close_l[i].clear();
   1112 	}          
   1113 	for (int i = l; i < r; i++)
   1114 	{
   1115 		for (int len : open_r[i]) nw.insert(len);
   1116 		if (!nw.empty()) rw[i] = min(rw[i], *nw.begin());
   1117 		for (int len : close_r[i]) nw.erase(nw.lower_bound(len));
   1118 		open_r[i].clear();
   1119 		close_r[i].clear();
   1120 	}
   1121 }
   1122 
   1123 int mn[L][M], st2[M], lc[L][M], kol[A][M];
   1124 
   1125 inline int getmin(int l, int r)
   1126 {
   1127 	int u = st2[r - l + 1];
   1128 	return min(mn[u][l], mn[u][r - (1 << u) + 1]);
   1129 }
   1130 
   1131 inline int gett(int l, int r)
   1132 {
   1133 	if (l == r) return (n - l);
   1134 	l = pos[l];
   1135 	r = pos[r];
   1136 	if (l > r) swap(l, r);
   1137 	r--;
   1138 	int u = st2[r - l + 1];
   1139 	return min(lc[u][l], lc[u][r - (1 << u) + 1]);
   1140 }
   1141 
   1142 int q, mnp[M];
   1143 
   1144 inline void init()
   1145 {
   1146 	for (int i = 0; i < n; i++) mn[0][i] = lw[i];
   1147 	for (int i = 0; i < n - 1; i++) lc[0][i] = lcp[i];
   1148 	for (int i = 1; i < L; i++)
   1149 		for (int j = 0; j < n; j++)
   1150 		{
   1151 			int r = (j + (1 << (i - 1)));
   1152 			if (r >= n)
   1153 			{
   1154 				mn[i][j] = mn[i - 1][j];
   1155 				continue;
   1156 			}
   1157 			mn[i][j] = min(mn[i - 1][j], mn[i - 1][r]);
   1158 		}
   1159 	for (int i = 1; i < L; i++)
   1160 		for (int j = 0; j < n - 1; j++)
   1161 		{
   1162 			int r = (j + (1 << (i - 1)));
   1163 			if (r >= n - 1)
   1164 			{
   1165 				lc[i][j] = lc[i - 1][j];
   1166 				continue;
   1167 			}                                          
   1168 			lc[i][j] = min(lc[i - 1][j], lc[i - 1][r]);
   1169 		}	
   1170 	st2[1] = 0;
   1171 	for (int i = 2; i <= n; i++)
   1172 	{
   1173 		st2[i] = st2[i - 1];
   1174 		if ((1 << (st2[i] + 1)) <= i) st2[i]++;
   1175 	}	
   1176 }
   1177 
   1178 int u, len;
   1179 
   1180 inline bool check(int l, int r)
   1181 {
   1182 	for (int t = 1; t <= min(len, ((r - l + 1) / 2)); t++)
   1183 		if (gett(l, r - t + 1) >= t)
   1184 			return true;
   1185 	for (int i = max(0, pos[l] - len); i <= min(n - 1, pos[l] + len); i++)
   1186 		if (l < a[i] && a[i] <= r && gett(l, a[i]) >= r - a[i] + 1) 
   1187 			return true;
   1188 	return false;
   1189 }
   1190 
   1191 inline bool checkno(int l, int r)
   1192 {
   1193 	if (r - l + 1 > 26) return false;
   1194 	vector<int> kol(26, 0);
   1195 	for (int x = l; x <= r; x++)
   1196 	{
   1197 		if (kol[s[x] - 'a'] > 0) return false;
   1198 		kol[s[x] - 'a']++;
   1199 	}	
   1200 	return true;
   1201 }
   1202 
   1203 inline bool try_kol(int l, int r, int p)
   1204 {
   1205 	int len = (r - l + 1) / p;
   1206 	return (gett(l, l + len) >= (r - l + 1 - len));
   1207 }
   1208 
   1209 inline bool ison(int l, int r, char x)
   1210 {
   1211 	return (kol[x - 'a'][r + 1] > kol[x - 'a'][l]);	
   1212 }
   1213 
   1214 inline int query(int l, int r)
   1215 {         
   1216 	if (checkno(l, r)) return -1;
   1217 	int len = (r - l + 1);
   1218 	while (len > 1)
   1219 	{
   1220 		int p = mnp[len];
   1221 		if (try_kol(l, r, p)) return 1;
   1222 		while ((len % p) == 0) len /= p;
   1223 	}
   1224 	if (lw[l] <= r) return 2;
   1225 	if (rw[r] >= l) return 2;
   1226 	if (check(l, r)) return 2;
   1227 	if (ison(l + 1, r, s[l])) return 3;
   1228 	if (ison(l, r - 1, s[r])) return 3;
   1229 	if (getmin(l, r) <= r) return 3;	
   1230 	return 4;
   1231 }
   1232 
   1233 int main()
   1234 {
   1235 	cin.sync_with_stdio(0); 
   1236 	cin >> n >> s;
   1237 	memset(mnp, -1, sizeof(mnp));
   1238 	for (int i = 2; i <= n; i++)
   1239 		if (mnp[i] == -1)
   1240 			for (int j = i; j <= n; j += i)
   1241 				if (mnp[j] == -1)
   1242 					mnp[j] = i;
   1243 	memset(kol[0], 0, sizeof(kol[0]));
   1244 	for (int i = 0; i < n; i++)
   1245 	{
   1246 		for (int x = 0; x < 26; x++) kol[x][i + 1] = kol[x][i];
   1247 		kol[s[i] - 'a'][i + 1]++;
   1248 	}
   1249 	for (int i = 0; i < n; i++)
   1250 	{
   1251 		lw[i] = n + 1;
   1252 		rw[i] = n + 1;
   1253 	}
   1254 	func(0, n);  
   1255 	for (int i = 0; i < n; i++)
   1256 	{
   1257 		if (lw[i] == n + 1) lw[i] = n;
   1258 		else lw[i] += (i - 1);  
   1259 		if (rw[i] == n + 1) rw[i] = -1;
   1260 		else rw[i] = (i - rw[i] + 1);
   1261 	}
   1262 	kasai();                                                                        
   1263 	init();  
   1264 	cin >> q;
   1265 	for (int i = 0; i < n; i++)
   1266 		if (i * i >= n)
   1267 		{
   1268 			len = i + 3;
   1269 			break;
   1270 		}
   1271 	for (int i = 0; i < q; i++)
   1272 	{
   1273 		int l, r;
   1274 		cin >> l >> r;
   1275 		l--, r--;
   1276 		cout << query(l, r) << "\n";                       
   1277 	}
   1278 	return 0;
   1279 }
   1280 ```
   1281 
   1282 Author: [isaf27](/profile/isaf27 "Grandmaster isaf27")