codeforces-scrape

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

1114.md (37894B)


      1 Source: https://codeforces.com/blog/entry/65136
      2 
      3 *Model solutions are now available.*  
      4 *[GreenGrape](/profile/GreenGrape "Master GreenGrape") and I will write more about problem F, including an alternative data structures (still quite tight on time limit) ;)*
      5 
      6 ## [1114A - Got Any Grapes?](/contest/1114/problem/A "Codeforces Round 538 (Div. 2)")
      7 
      8 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape")  
      9 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa")  
     10 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
     11 
     12 **Tutorial**
     13 
     14 First of all, we can see the grape preference is hierarchically inclusive: the grapes' types Andrew enjoys are some of those that Dmitry does, and Dmitry's favorites are included in Michal's.
     15 
     16 Let's distribute the grapes to satisfy Andrew first, then to Dmitry, then Michal. If any of the following criteria is not satisfied (which means one of our friends is not happy), then we can immediately say that no distributions are available:
     17 
     18 * Andrew must have at least *a* green grapes. So we need, *x* ≤ *a*.
     19 * Dmitry can have purple grapes and/or the remaining green grapes. In other words, *y* ≤ *a* + *b* - *x* (the minus *x* is because *x* green grapes have been given to Andrew already).
     20 * Michal can have grapes of any kinds. In other words, *z* ≤ *a* + *b* + *c* - *x* - *y* (similar explanations like above for both minus *x* and minus *y*).
     21 
     22 If all three criteria are satisfied, then a grape distribution is possible.
     23 
     24 Total complexity: ![](https://espresso.codeforces.com/c49c1b7e387d521abbea6a5b59931c15c56dca9b.png).
     25 
     26 **Solution (Akikaze)**
     27 
     28 Submission link: [49737634](/contest/1114/submission/49737634 "Submission 49737634 by AkiLotus")
     29 
     30 **Source code in plain text**
     31 
     32 ```
     33 #pragma comment(linker, "/stack:247474112")
     34 #pragma GCC optimize("Ofast")
     35 
     36 #include <bits/stdc++.h>
     37 using namespace std;
     38 
     39 #define endl '\n'
     40 
     41 int x, y, z, a, b, c;
     42 
     43 void Input() {
     44 	cin >> x >> y >> z;
     45 	cin >> a >> b >> c;
     46 }
     47 
     48 void Solve() {
     49 	if (x > a) {cout << "NO\n"; return;}
     50 	if (x + y > a + b) {cout << "NO\n"; return;}
     51 	if (x + y + z > a + b + c) {cout << "NO\n"; return;}
     52 	cout << "YES\n";
     53 }
     54 
     55 int main(int argc, char* argv[]) {
     56 	ios_base::sync_with_stdio(0);
     57 	cin.tie(NULL); Input(); Solve();
     58 	return 0;
     59 }
     60 ```
     61 
     62 ## [1114B - Yet Another Array Partitioning Task](/contest/1114/problem/B "Codeforces Round 538 (Div. 2)")
     63 
     64 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
     65 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")  
     66 Editorialist: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa")
     67 
     68 **Tutorial**
     69 
     70 In a perfect scenario, the maximum beauty of the original array is just a sum of *m*·*k* largest elements.
     71 
     72 In fact, such scenario is always available regardless of the elements.
     73 
     74 Let's denote *A* as the set of these *m*·*k* largest elements. The solution for us will be dividing the array into *k* segments, such that each segment contains exactly *m* elements of *A*. Just make a split between corresponding elements in the set *A*.
     75 
     76 Depending on the way we find *m*·*k* largest elements, the time complexity might differ.
     77 
     78 If we simply do so after sorting the entire array by usual means, the time complexity will be ![](https://espresso.codeforces.com/0d8aa761c1935375e54d4ae05c77815a3bc26901.png).
     79 
     80 However, we can use [`std::nth_element` function](http://www.cplusplus.com/reference/algorithm/nth_element/) instead of sorting the entire array. The idea is to sort the array in such a way that, every elements not higher than a value *v* will be stored in the left side, other elements will stay on the right, and this works in linear time (a.k.a. ![](https://espresso.codeforces.com/75c1cc685b678543b1630d9159eed84639cf6a8e.png) time complexity).
     81 
     82 An example implementation of such ordering can be shown [here](https://cp-algorithms.com/sequences/k-th.html).
     83 
     84 **Solution (xuanquang1999)**
     85 
     86 Submission link: [49737896](/contest/1114/submission/49737896 "Submission 49737896 by AkiLotus")
     87 
     88 **Source code in plain text**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 typedef pair<int, int> pii;
     96 typedef long long ll;
     97 
     98 int main() {
     99     ios_base::sync_with_stdio(0); cin.tie(NULL);
    100 
    101     int n, m, k;
    102     cin >> n >> m >> k;
    103 
    104     vector<pii> a(n);
    105     for(int i = 0; i < n; ++i) {
    106         cin >> a[i].first;
    107         a[i].second = i;
    108     }
    109 
    110     sort(a.begin(), a.end(), greater<pii>());
    111 
    112     vector<int> ind(m*k);
    113     ll sumBeauty = 0;
    114     for(int i = 0; i < m*k; ++i) {
    115         sumBeauty += a[i].first;
    116         ind[i] = a[i].second;
    117     }
    118 
    119     sort(ind.begin(), ind.end());
    120 
    121     vector<int> division(k-1);
    122     for(int i = 0; i < k-1; ++i)
    123         division[i] = ind[(i+1)*m - 1];
    124 
    125     cout << sumBeauty << endl;
    126     for(int p: division)
    127         cout << p + 1 << " ";
    128 
    129     return 0;
    130 }
    131 ```
    132 
    133 ## [1114C - Trailing Loves (or L'oeufs?)](/contest/1114/problem/C "Codeforces Round 538 (Div. 2)")
    134 
    135 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    136 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [majk](/profile/majk "International Grandmaster majk"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")  
    137 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus")
    138 
    139 **Tutorial**
    140 
    141 The problem can be reduced to the following: finding the maximum *r* that *n* ! is divisible by *b**r*.
    142 
    143 By prime factorization, we will have the following: *b* = *p*1*y*1·*p*2*y*2·...·*p**m**y**m*.
    144 
    145 In a similar manner, we will also have: *n* ! = *p*1*x*1·*p*2*x*2·...·*p**m**x**m*·*Q* (with *Q* being coprime to any *p**i* presented above).
    146 
    147 The process of finding *p*1, *p*2, ..., *p**m*, *y*1, *y*2, ..., *y**m* can be done by normal prime factorization of the value *b*.
    148 
    149 The process of finding *x*1, *x*2, ..., *x**m* is a little bit more tricky since the integer they were originated (*n* !) is too huge to be factorized manually. Still the factorial properties gave us another approach: for each *p**i*, we can do the following:
    150 
    151 * Initially, denote *x**i* = 0.
    152 * Repeatedly do the following: add ![](https://espresso.codeforces.com/39e8e6da50420d3b2652aaa25427f36b605d55b0.png) to *x**i*, then divide *n* by *p**i*. The loop ends when *n* is zero.
    153 
    154 After all, we can obtain the final value *r* as of following: ![](https://espresso.codeforces.com/49455eb6083bdc6538d540bbfddd0fc734a41fab.png).
    155 
    156 Total complexity: ![](https://espresso.codeforces.com/85fc20c8566b05180d80228077d5747fcabdcc98.png) (as the number of prime factors of an integer *b* will not surpass ![](https://espresso.codeforces.com/a2d5a43faf30159f1fbfedd840fedceb806abedf.png)).
    157 
    158 **Solution (Akikaze)**
    159 
    160 Submission link: [49738076](/contest/1114/submission/49738076 "Submission 49738076 by AkiLotus")
    161 
    162 **Source code in plain text**
    163 
    164 ```
    165 #pragma comment(linker, "/stack:247474112")
    166 #pragma GCC optimize("Ofast")
    167 
    168 #include <bits/stdc++.h>
    169 using namespace std;
    170 
    171 #define endl '\n'
    172 
    173 long long n, b;
    174 
    175 void Input() {
    176 	cin >> n >> b;
    177 }
    178 
    179 void Solve() {
    180 	long long ans = 1000000000000000000LL;
    181 	for (long long i=2; i<=b; i++) {
    182 		if (1LL * i * i > b) i = b;
    183 		int cnt = 0;
    184 		while (b % i == 0) {b /= i; cnt++;}
    185 		if (cnt == 0) continue;
    186 		long long tmp = 0, mul = 1;
    187 		while (mul <= n / i) {mul *= i; tmp += n / mul;}
    188 		ans = min(ans, tmp / cnt);
    189 	}
    190 	cout << ans << endl;
    191 }
    192 
    193 int main(int argc, char* argv[]) {
    194 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    195 	Input(); Solve(); return 0;
    196 }
    197 ```
    198 
    199 ## [1114D - Flood Fill](/contest/1114/problem/D "Codeforces Round 538 (Div. 2)")
    200 
    201 Author: [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa")  
    202 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")  
    203 Editorialist: [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Master neko_nyaaaaaaaaaaaaaaaaa"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")
    204 
    205 **Tutorial**
    206 
    207 This problem was inspired by the game Flood-it. It is apparently NP-hard. You can try out the game here. https://www.chiark.greenend.org.uk/\%7Esgtatham/puzzles/js/flood.html
    208 
    209 **The first solution is rather straightforward.** Suppose squares [*L*, *R*] are flooded, then they are either of color *c**L* or *c**R*. We can define ![](https://espresso.codeforces.com/38d46bdd4bd15e4a14b68f6d804e78ce7c80dc8a.png) as the minimum number of moves required to make the segment [*L*, *R*] monochromic:
    210 
    211 * ![](https://espresso.codeforces.com/f2909ee2b2ff4d0aad96b15b230dc95fcb102d78.png) is the least moves required to make the segment having color *c**L*.
    212 * ![](https://espresso.codeforces.com/fc7d5e0c46176edf5a3d098604a9cf073a6eebca.png) is the least moves required to make the segment having color *c**R*.
    213 
    214 **The second solution, which is the author's intended solution, is less so.** Note that the size of the component doesn't matter, so first "compress" the array so that every adjacent elements are different. We will work on this compressed array instead.
    215 
    216 We want to maximize the number of turns that we can fill two adjacent squares instead of one. From a starting square, this maximum number of "saved" turns is equal to the longest common subsequence (LCS) of the array expanding to the two sides. The answer is the *N* — (maximum LCS over all starting squares)
    217 
    218 This is equivalent to finding the longest odd size palindrome subsequence. In fact, it is the longest palindrome subsequence. For every even-sized palindrome subsequence, since adjacent elements are different, we can just insert an element in the middle and obtain a longer palindrome subsequence.
    219 
    220 To find the longest palindrome subsequence, we can make a reversed copy of the array and find LCS of it with the original array.
    221 
    222 Alternatively, we can also use the first solution on the compressed array, without needing the third parameter.
    223 
    224 Time complexity: ![](https://espresso.codeforces.com/a5c1bdb62f55c836c0ae70ab80c99ad6cdd0bbed.png).
    225 
    226 **Solution 1 (_kun_)**
    227 
    228 Submission link: [49738289](/contest/1114/submission/49738289 "Submission 49738289 by AkiLotus")
    229 
    230 **Source code in plain text**
    231 
    232 ```
    233 // Dmitry _kun_ Sayutin (2019)
    234 
    235 #include <bits/stdc++.h>
    236 
    237 using std::cin;
    238 using std::cout;
    239 using std::cerr;
    240 
    241 using std::vector;
    242 using std::map;
    243 using std::array;
    244 using std::set;
    245 using std::string;
    246 
    247 using std::pair;
    248 using std::make_pair;
    249 
    250 using std::tuple;
    251 using std::make_tuple;
    252 using std::get;
    253 
    254 using std::min;
    255 using std::abs;
    256 using std::max;
    257 using std::swap;
    258 
    259 using std::unique;
    260 using std::sort;
    261 using std::generate;
    262 using std::reverse;
    263 using std::min_element;
    264 using std::max_element;
    265 
    266 #ifdef LOCAL
    267 #define LASSERT(X) assert(X)
    268 #else
    269 #define LASSERT(X) {}
    270 #endif
    271 
    272 template <typename T>
    273 T input() {
    274     T res;
    275     cin >> res;
    276     LASSERT(cin);
    277     return res;
    278 }
    279 
    280 template <typename IT>
    281 void input_seq(IT b, IT e) {
    282     std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
    283 }
    284 
    285 #define SZ(vec)         int((vec).size())
    286 #define ALL(data)       data.begin(),data.end()
    287 #define RALL(data)      data.rbegin(),data.rend()
    288 #define TYPEMAX(type)   std::numeric_limits<type>::max()
    289 #define TYPEMIN(type)   std::numeric_limits<type>::min()
    290 
    291 int dp[5000][5000][2];
    292 
    293 int main() {
    294     std::iostream::sync_with_stdio(false);
    295     cin.tie(nullptr);
    296     cout.tie(nullptr);
    297 
    298     // code here
    299     int n = input<int>();
    300 
    301     vector<int> a(n);
    302     input_seq(ALL(a));
    303 
    304     for (int i = 0; i != n; ++i)
    305         for (int j = 0; j != n; ++j)
    306             dp[i][j][0] = dp[i][j][1] = (i == j ? 0 : TYPEMAX(int) / 2);
    307     
    308 
    309     for (int r = 0; r != n; ++r)
    310         for (int l = r; l >= 0; --l)
    311             for (int it = 0; it != 2; ++it) {
    312                 int c = (it == 0 ? a[l] : a[r]);
    313                 
    314                 if (l)
    315                     dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][it] + int(c != a[l - 1]));
    316 
    317                 if (r + 1 != n)
    318                     dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][it] + int(c != a[r + 1]));
    319             }
    320 
    321     cout << min(dp[0][n - 1][0], dp[0][n - 1][1]) << "\n";
    322     
    323     return 0;
    324 }
    325 ```
    326 
    327 **Solution 2 (neko_nyaa)**
    328 
    329 Submission link: [49738394](/contest/1114/submission/49738394 "Submission 49738394 by AkiLotus")
    330 
    331 **Source code in plain text**
    332 
    333 ```
    334 #include <bits/stdc++.h>
    335 using namespace std;
    336 
    337 const int maxN = 5008;
    338 
    339 int n;
    340 int dp[maxN][maxN];
    341 vector<int> a(1), b;
    342 vector<int> ans;
    343 
    344 void input() {
    345 	cin >> n;
    346 	for (int i = 0; i < n; i++) {
    347 		int x; cin >> x;
    348 		if (x != a.back()) a.push_back(x);
    349 	}
    350 	n = a.size() - 1;
    351 
    352 	b = a;
    353 	reverse(b.begin() + 1, b.end());
    354 }
    355 
    356 void solve() {
    357 	for (int i = 1; i <= n; i++) {
    358 		for (int j = 1; j <= n; j++) {
    359 			if (a[i] == b[j]) {dp[i][j] = dp[i-1][j-1] + 1;}
    360 			else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}
    361 		}
    362 	}
    363 }
    364 
    365 void output() {
    366 	cout << n - (dp[n][n] + 1)/2 << '\n';
    367 }
    368 
    369 int main() {
    370 	
    371 	input();
    372 	solve();
    373 	output();
    374 	
    375 	return 0;
    376 }
    377 ```
    378 
    379 ## [1114E - Arithmetic Progression](/contest/1114/problem/E "Codeforces Round 538 (Div. 2)")
    380 
    381 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus")  
    382 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape")  
    383 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999")
    384 
    385 **Tutorial**
    386 
    387 The `>` query type allows you to find the max value of the array through binary searching, which will cost ![](https://espresso.codeforces.com/bbc77edea90c1ded03bf8dca871e18e39f9d41d2.png) queries.
    388 
    389 The remaining queries will be spent for the queries of the `?` type to get some random elements of the array. *d* will be calculated as greatest common divisors of all difference between all consecutive elements, provided all elements found (yes, including the `max` one) is kept into a list sorted by increasing order.
    390 
    391 Having `d` and `max`, we can easily find the `min` value: *min* = *max* - *d*·(*n* - 1).
    392 
    393 The number of allowed queries seem small (30 queries to be exact), yet it's enough for us to have reasonable probability of passing the problem.
    394 
    395 *By some maths, we can find out the probability of our solution to fail being relatively small — approximately 1.86185·10- 9.*
    396 
    397 **Proof on the probability, written by xuanquang1999**
    398 
    399 For simplicity, assumed that the sequence *a* is [0, 1, 2, ..., *n* - 1]. Suppose that we randomly (and uniformly) select a subsequence *S* containing *k* elements from sequence *a* (when *k* is the number of `?` query asked). Denote *S* = [*s*1, *s*2, ..., *s**k*].
    400 
    401 Let *D* the GCD of all difference between consecutive elements in *S*. In other word, ![](https://espresso.codeforces.com/d4cb33976c0819d88da8c93e6da1e30f0e2a515a.png). Our solution will success if *D* = 1 and will fail otherwise. Let *P* the probability that our solution will pass (*D* = 1). Then the failing probability is 1 - *P*.
    402 
    403 We will apply [Möbius inversion](https://codeforces.com/blog/entry/53925) to calculate *P*: Let *f*(*x*) the probability that *D* is divisible by *x*. Then, ![](https://espresso.codeforces.com/b884f5679f342a3c1d056982bfe2ca11cb49a61b.png) (where μ(*x*) is the Möbius function).
    404 
    405 Now we need to calculate *f*(*x*). It can be shown that *D* is divisible by *x* if and only if ![](https://espresso.codeforces.com/910abdac77ffc5a5e4fd04de8b316d754b17c09e.png) for all 2 ≤ *i* ≤ *k*. In other word, there is some *r* from 0 to *x* - 1 such that ![](https://espresso.codeforces.com/c8f530998ab41edcc70982e671e8f21f16109730.png) for all 1 ≤ *i* ≤ *k*.
    406 
    407 Let *g*(*r*) the number of ways to select a subsequence *S* such that ![](https://espresso.codeforces.com/c8f530998ab41edcc70982e671e8f21f16109730.png) for all 1 ≤ *i* ≤ *k*. Then, according to definition:
    408 
    409 ![](https://espresso.codeforces.com/054f51e4235dca832bcda559601d98e14322ad69.png)
    410 
    411 The denominator is simply ![](https://espresso.codeforces.com/3b6fb2d742f7434e0b1d8be541f1896f7422081e.png). To calculate *g*(*r*), notice that for each *i*, the value of *s**i* can be *x*·*j* + *r* for some integer *j*. In other word, *S* must be a subsequence of the sequence *a**r* = [*r*, *x* + *r*, 2*x* + *r*, ...]. Let ![](https://espresso.codeforces.com/fe3ab82380275a6174833989bf9fd184e68baf54.png).
    412 
    413 * If ![](https://espresso.codeforces.com/f58b4393bc8cfd90f455a0c6b1b0bb818add67c4.png), *a**r* has *q* + 1 elements. Therefore, ![](https://espresso.codeforces.com/23c8043fa8a48cac2637c6da0c60677b211a572a.png)
    414 * If ![](https://espresso.codeforces.com/8bcc22bdfeb738db1736fab5273d438362f7a185.png), *a**r* has *q* elements. Therefore, ![](https://espresso.codeforces.com/4495db96569f8c098827c795817e681dc55765f8.png).
    415 
    416 In summary:
    417 
    418 ![](https://espresso.codeforces.com/878f3296b60cfb91d682e5d338adcb71b850ae4a.png)
    419 
    420 The complexity of this calculating method is *O*(*n*). My implementation of the above method can be found [here](https://ideone.com/IHmndY).
    421 
    422 Keep in mind to use a good random number generator and a seed which is hard to obtain, thus making your solution truly random and not falling into corner cases.
    423 
    424 Some of the tutorials of [neal](/profile/neal "International Grandmaster neal") might be helpful:
    425 
    426 [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587)  
    427 [How randomized solutions can be hacked, and how to make your solution unhackable](https://codeforces.com/blog/entry/61675)
    428 
    429 **Solution (Akikaze)**
    430 
    431 Submission link: [49739271](/contest/1114/submission/49739271 "Submission 49739271 by AkiLotus")
    432 
    433 **Source code in plain text**
    434 
    435 ```
    436 #pragma comment(linker, "/stack:247474112")
    437 #pragma GCC optimize("Ofast")
    438 
    439 #include <bits/stdc++.h>
    440 using namespace std;
    441 
    442 #define endl '\n'
    443 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
    444 
    445 int n, Max = -1000000000, d = 0;
    446 int queryRemaining = 60; vector<int> id;
    447 
    448 void findMax() {
    449 	int top = -1000000000, bot = +1000000000;
    450 	while (top <= bot) {
    451 		int hasHigher;
    452 		int mid = (top + bot) / 2;
    453 		cout << "> " << mid << endl;
    454 		fflush(stdout); cin >> hasHigher;
    455 		queryRemaining--;
    456 		if (hasHigher) top = mid + 1;
    457 		else {bot = mid - 1; Max = mid;}
    458 	}
    459 }
    460 
    461 void findD() {
    462 	vector<int> List; int RandomRange = n;
    463 	while (queryRemaining > 0 && RandomRange > 0) {
    464 		int demandedIndex = rng32() % RandomRange;
    465 		cout << "? " << id[demandedIndex] << endl; fflush(stdout);
    466 		int z; cin >> z; List.push_back(z);
    467 		RandomRange--; queryRemaining--;
    468 		swap(id[demandedIndex], id[RandomRange]);
    469 	}
    470 	sort(List.begin(), List.end());
    471 	if (List.back() != Max) List.push_back(Max);
    472 	for (int i=1; i<List.size(); i++) {
    473 		d = __gcd(d, List[i] - List[i-1]);
    474 	}
    475 }
    476 
    477 void Input() {
    478 	cin >> n; id.resize(n);
    479 	for (int i=0; i<n; i++) id[i] = i+1;
    480 }
    481 
    482 void Solve() {
    483 	findMax(); findD();
    484 	int Min = Max - d * (n - 1);
    485 	cout << "! " << Min << " " << d;
    486 	cout << endl; fflush(stdout);
    487 }
    488 
    489 int main(int argc, char* argv[]) {
    490 	ios_base::sync_with_stdio(0);
    491 	Input(); Solve(); return 0;
    492 }
    493 ```
    494 
    495 ## [1114F - Please, another Queries on Array?](/contest/1114/problem/F "Codeforces Round 538 (Div. 2)")
    496 
    497 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")  
    498 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")  
    499 Editorialist: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [GreenGrape](/profile/GreenGrape "Master GreenGrape"), [cdkrot](/profile/cdkrot "Grandmaster cdkrot")
    500 
    501 **Tutorial**
    502 
    503 There's a few fundamentals about Euler's totient we need to know:
    504 
    505 * φ(*p*) = *p* - 1 and φ(*p**k*) = *p**k* - 1·(*p* - 1), provided *p* is a prime number and *k* is a positive integer. You can easily prove these equations through the definition of the function itself.
    506 * Euler's totient is a **multiplicative function**. *f*(*x*) is considered a multiplicative function when ![](https://espresso.codeforces.com/56be750d1b80485d64aa09138a04c51659bf83f5.png) means *f*(*a*)·*f*(*b*) = *f*(*a*·*b*).
    507 
    508 Keep in mind that we can rewrite φ(*p**k*) as of following: ![](https://espresso.codeforces.com/30c53e477789d35253523b18c801d0c2cad7e540.png).
    509 
    510 Let's denote *P* as the set of prime factors of ![](https://espresso.codeforces.com/66ffde9ad104df54167d646a96e4a566f4279583.png).
    511 
    512 Thus, the answer for each query will simply be: ![](https://espresso.codeforces.com/67dab5c7e4cfa06fe316b76654942075656f4c1d.png).
    513 
    514 So, for each query we'll need to know the product of the elements, and which primes are included in that product.
    515 
    516 There are a few ways to work around with it. One of the most effective way is as following:
    517 
    518 * Create a product segment tree to maintain the segment products.
    519 * Since ![](https://espresso.codeforces.com/d4353050eb004a4cb99885196096a42912ad7c36.png) only depends on the appearance or non-appearance of the primes, and the constraints guaranteed us to have at most 62 prime factors, we can use bitmasks and an or-sum segment tree to maintain this part.
    520 
    521 Also, the bitmasks and range products can be maintained in a sqrt-decomposition fashion (please refer to [GreenGrape](/profile/GreenGrape "Master GreenGrape")'s solution), making each query's complexity to be somewhat around ![](https://espresso.codeforces.com/df2e6b06a1b79c80d0fd56d707697d8c26801437.png). Still, this complexity is quite high and surpassed time limit on a pretty thin margin.
    522 
    523 Complexity for initializing segment trees: ![](https://espresso.codeforces.com/143ad93bdeff80c2f3c41631e7377ab44d9b9caa.png).
    524 
    525 Complexity for each update query: ![](https://espresso.codeforces.com/185d58accd05908ace68200a6dc258d95e1eaa79.png).
    526 
    527 Complexity for each return query: ![](https://espresso.codeforces.com/185d58accd05908ace68200a6dc258d95e1eaa79.png).
    528 
    529 **Solution 1a (_kun_)**
    530 
    531 Submission link: [49739509](/contest/1114/submission/49739509 "Submission 49739509 by AkiLotus")
    532 
    533 **Source code in plain text**
    534 
    535 ```
    536 // Dmitry _kun_ Sayutin (2019)
    537 
    538 #include <bits/stdc++.h>
    539 
    540 using std::cin;
    541 using std::cout;
    542 using std::cerr;
    543 
    544 using std::vector;
    545 using std::map;
    546 using std::array;
    547 using std::set;
    548 using std::string;
    549 
    550 using std::pair;
    551 using std::make_pair;
    552 
    553 using std::tuple;
    554 using std::make_tuple;
    555 using std::get;
    556 
    557 using std::min;
    558 using std::abs;
    559 using std::max;
    560 using std::swap;
    561 
    562 using std::unique;
    563 using std::sort;
    564 using std::generate;
    565 using std::reverse;
    566 using std::min_element;
    567 using std::max_element;
    568 
    569 #ifdef LOCAL
    570 #define LASSERT(X) assert(X)
    571 #else
    572 #define LASSERT(X) {}
    573 #endif
    574 
    575 template <typename T>
    576 T input() {
    577     T res;
    578     cin >> res;
    579     LASSERT(cin);
    580     return res;
    581 }
    582 
    583 template <typename IT>
    584 void input_seq(IT b, IT e) {
    585     std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
    586 }
    587 
    588 #define SZ(vec)         int((vec).size())
    589 #define ALL(data)       data.begin(),data.end()
    590 #define RALL(data)      data.rbegin(),data.rend()
    591 #define TYPEMAX(type)   std::numeric_limits<type>::max()
    592 #define TYPEMIN(type)   std::numeric_limits<type>::min()
    593 
    594 const int mod = 1000 * 1000 * 1000 + 7;
    595 
    596 int add(int a, int b) {
    597     return (a + b >= mod ? a + b - mod : a + b);
    598 }
    599 
    600 int sub(int a, int b) {
    601     return (a >= b ? a - b : mod + a - b);
    602 }
    603 
    604 int mult(int a, int b) {
    605     return (int64_t(a) * b) % mod;
    606 }
    607 
    608 int fpow(int a, int n, int r = 1) {
    609     while (n) {
    610         if (n % 2)
    611             r = mult(r, a);
    612 
    613         n /= 2;
    614         a = mult(a, a);
    615     }
    616 
    617     return r;
    618 }
    619 
    620 const int max_n = 4.1e5;
    621 int tree[4 * max_n];
    622 int modif[4 * max_n];
    623 int64_t pmask[4 * max_n], pushmask[4 * max_n];
    624 
    625 vector<int> primes, revprimes;
    626 
    627 void build(int v, int l, int r, vector<int>& a) {
    628     modif[v] = 1;
    629     
    630     if (l == r - 1) {
    631         tree[v] = a[l];
    632 
    633         for (int i = 0; i != SZ(primes); ++i)
    634             if (a[l] % primes[i] == 0)
    635                 pmask[v] |= (int64_t(1) << int64_t(i));
    636     } else {
    637         int m = l + (r - l) / 2;
    638         build(2 * v + 1, l, m, a);
    639         build(2 * v + 2, m, r, a);
    640 
    641         tree[v] = mult(tree[2 * v + 1], tree[2 * v + 2]);
    642         pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2];
    643     }
    644 }
    645 
    646 void push(int v, int vl, int vr) {
    647     if (modif[v] != 1)
    648         tree[v] = fpow(modif[v], vr - vl, tree[v]);
    649 
    650     pmask[v] |= pushmask[v];
    651     
    652     if (vl != vr - 1) {
    653         modif[2 * v + 1] = mult(modif[2 * v + 1], modif[v]);
    654         modif[2 * v + 2] = mult(modif[2 * v + 2], modif[v]);
    655 
    656         pushmask[2 * v + 1] |= pushmask[v];
    657         pushmask[2 * v + 2] |= pushmask[v];
    658     }
    659 
    660     modif[v] = 1;
    661     pushmask[v] = 0;
    662 }
    663 
    664 pair<int, int64_t> get(int v, int vl, int vr, int l, int r) {
    665     if (vr <= l or r <= vl)
    666         return make_pair<int, int64_t>(1, 0);
    667     
    668     push(v, vl, vr);
    669 
    670     if (l <= vl and vr <= r)
    671         return make_pair(tree[v], pmask[v]);
    672 
    673     int vm = vl + (vr - vl) / 2;
    674     
    675     auto r1 = get(2 * v + 1, vl, vm, l, r);
    676     auto r2 = get(2 * v + 2, vm, vr, l, r);
    677 
    678     return make_pair(mult(r1.first, r2.first), r1.second | r2.second);
    679 }
    680 
    681 void multiply(int v, int vl, int vr, int l, int r, int x, int64_t mask) {
    682     if (vr <= l or r <= vl)
    683         return;
    684 
    685     push(v, vl, vr);
    686     
    687     if (l <= vl and vr <= r) {
    688         pushmask[v] = mask;
    689         modif[v] = x;
    690         return;
    691     }
    692 
    693     int vm = vl + (vr - vl) / 2;
    694     
    695     multiply(2 * v + 1, vl, vm, l, r, x, mask);
    696     multiply(2 * v + 2, vm, vr, l, r, x, mask);
    697 
    698     pmask[v] = pmask[2 * v + 1] | pmask[2 * v + 2] | pushmask[2 * v + 1] | pushmask[2 * v + 2];
    699     tree[v] = fpow(x, min(vr, r) - max(l, vl), tree[v]);
    700 }
    701 
    702 int main() {
    703     std::iostream::sync_with_stdio(false);
    704     cin.tie(nullptr);
    705     cout.tie(nullptr);
    706 
    707     // code here
    708     for (int i = 2; i <= 300; ++i) {
    709         bool ok = true;
    710         for (int j = 2; j * j <= i and ok; ++j)
    711             if (i % j == 0)
    712                 ok = false;
    713 
    714         if (ok) {
    715             primes.push_back(i);
    716             revprimes.push_back(fpow(i, mod - 2));
    717         }
    718     }
    719 
    720     int n = input<int>();
    721     int q = input<int>();
    722 
    723     vector<int> a(n);
    724     input_seq(ALL(a));
    725 
    726     build(0, 0, n, a);
    727 
    728     for (int it = 0; it != q; ++it) {
    729         if (input<string>() == "TOTIENT") {
    730             int l = input<int>() - 1;
    731             int r = input<int>() - 1;
    732             
    733             pair<int, uint64_t> prod = get(0, 0, n, l, r + 1);
    734             for (int i = 0; i != SZ(primes); ++i)
    735                 if (prod.second & (int64_t(1) << int64_t(i)))
    736                     prod.first = mult(mult(prod.first, primes[i] - 1), revprimes[i]);
    737 
    738             cout << prod.first << "\n";
    739         } else {
    740             int l = input<int>() - 1;
    741             int r = input<int>() - 1;
    742             int x = input<int>();
    743 
    744             int64_t msk = 0;
    745             for (int i = 0; i != SZ(primes); ++i)
    746                 if (x % primes[i] == 0)
    747                     msk |= (int64_t(1) << int64_t(i));
    748 
    749             multiply(0, 0, n, l, r + 1, x, msk);
    750         }
    751     }
    752     
    753     return 0;
    754 }
    755 ```
    756 
    757 **Solution 1b (Akikaze) [literally kun's solution, yet shorter, and a bit uglier :P]**
    758 
    759 Submission link: [49740091](/contest/1114/submission/49740091 "Submission 49740091 by AkiLotus")
    760 
    761 **Source code in plain text**
    762 
    763 ```
    764 #pragma comment(linker, "/stack:247474112")
    765 #pragma GCC optimize("Ofast")
    766 
    767 #include <bits/stdc++.h>
    768 using namespace std;
    769 
    770 #define endl '\n'
    771 
    772 const int Mod = 1000000007;
    773 
    774 int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137
    775 ,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293}; // (size = 62)
    776 
    777 int modPow(int a, int b) {
    778     int res = 1;
    779     while (b > 0) {
    780         if (b % 2 == 0) {a = (1LL * a * a) % Mod; b /= 2;}
    781         else {res = (1LL * res * a) % Mod; b -= 1;}
    782     }
    783     return res;
    784 }
    785 
    786 struct ProTree {
    787 	vector<int> Tree, Lazy;
    788 	ProTree() {}
    789 	ProTree(int n) {Tree.resize(n*4, 1); Lazy.resize(n*4, 1);}
    790 	
    791 	void Propagate(int node, int st, int en) {
    792 		if (Lazy[node] == 1) return;
    793 		Tree[node] = (1LL * Tree[node] * modPow(Lazy[node], (en - st + 1))) % Mod;
    794 		if (st != en) {
    795 			Lazy[node*2+1] = (1LL * Lazy[node*2+1] * Lazy[node]) % Mod;
    796 			Lazy[node*2+2] = (1LL * Lazy[node*2+2] * Lazy[node]) % Mod;
    797 		}
    798 		Lazy[node] = 1;
    799 	}
    800 	
    801 	void Multiply(int node, int st, int en, int L, int R, int val) {
    802 		Propagate(node, st, en);
    803 		if (st > en || en < L || R < st) return;
    804 		if (L <= st && en <= R) {
    805 			Lazy[node] = (1LL * Lazy[node] * val) % Mod;
    806 			Propagate(node, st, en); return;
    807 		}
    808 		Multiply(node*2+1, st, (st+en)/2+0, L, R, val);
    809 		Multiply(node*2+2, (st+en)/2+1, en, L, R, val);
    810 		Tree[node] = (1LL * Tree[node*2+1] * Tree[node*2+2]) % Mod;
    811 	}
    812 	
    813 	int Product(int node, int st, int en, int L, int R) {
    814 		Propagate(node, st, en);
    815 		if (st > en || en < L || R < st) return 1;
    816 		if (L <= st && en <= R) return Tree[node];
    817 		int p1 = Product(node*2+1, st, (st+en)/2+0, L, R);
    818 		int p2 = Product(node*2+2, (st+en)/2+1, en, L, R);
    819 		return ((1LL * p1 * p2) % Mod);
    820 	}
    821 };
    822 
    823 struct OrTree {
    824 	vector<long long> Tree, Lazy;
    825 	OrTree() {}
    826 	OrTree(int n) {Tree.resize(n*4); Lazy.resize(n*4);}
    827 	
    828 	void Propagate(int node, int st, int en) {
    829 		if (Lazy[node] == 0) return;
    830 		Tree[node] |= Lazy[node];
    831 		if (st != en) {
    832 			Lazy[node*2+1] |= Lazy[node];
    833 			Lazy[node*2+2] |= Lazy[node];
    834 		}
    835 		Lazy[node] = 0;
    836 	}
    837 	
    838 	void Update(int node, int st, int en, int L, int R, long long val) {
    839 		Propagate(node, st, en);
    840 		if (st > en || en < L || R < st) return;
    841 		if (L <= st && en <= R) {
    842 			Lazy[node] |= val;
    843 			Propagate(node, st, en); return;
    844 		}
    845 		Update(node*2+1, st, (st+en)/2+0, L, R, val);
    846 		Update(node*2+2, (st+en)/2+1, en, L, R, val);
    847 		Tree[node] = (Tree[node*2+1] | Tree[node*2+2]);
    848 	}
    849 	
    850 	long long Or(int node, int st, int en, int L, int R) {
    851 		Propagate(node, st, en);
    852 		if (st > en || en < L || R < st) return 0;
    853 		if (L <= st && en <= R) return Tree[node];
    854 		long long p1 = Or(node*2+1, st, (st+en)/2+0, L, R);
    855 		long long p2 = Or(node*2+2, (st+en)/2+1, en, L, R);
    856 		return (p1 | p2);
    857 	}
    858 };
    859 
    860 int N, Q, l, r, x; string cmd;
    861 vector<int> invPrime(62);
    862 vector<int> A; ProTree PrTree; OrTree OSTree;
    863 vector<long long> Mask(301, 0);
    864 
    865 void PreprocessMask() {
    866 	for (int z=1; z<=300; z++) {
    867 		for (int i=0; i<62; i++) {
    868 			if (z % prime[i] != 0) continue;
    869 			Mask[z] |= (1LL << i);
    870 		}
    871 	}
    872 }
    873 
    874 void Input() {
    875     for (int i=0; i<62; i++) invPrime[i] = modPow(prime[i], Mod-2); PreprocessMask();
    876 	cin >> N >> Q; A.resize(N); PrTree = ProTree(N); OSTree = OrTree(N);
    877 	for (int i=0; i<N; i++) {
    878 		cin >> A[i];
    879 		PrTree.Multiply(0, 0, N-1, i, i, A[i]);
    880 		OSTree.Update(0, 0, N-1, i, i, Mask[A[i]]);
    881 	}
    882 }
    883 
    884 void Solve() {
    885 	while (Q--) {
    886 		cin >> cmd >> l >> r; l--; r--;
    887 		if (cmd == "MULTIPLY") {
    888 			cin >> x;
    889 			PrTree.Multiply(0, 0, N-1, l, r, x);
    890 			OSTree.Update(0, 0, N-1, l, r, Mask[x]);
    891 		}
    892 		else if (cmd == "TOTIENT") {
    893 			int res = PrTree.Product(0, 0, N-1, l, r);
    894 			long long SegMask = OSTree.Or(0, 0, N-1, l, r);
    895 			for (int i=0; i<62; i++) {
    896 			    if ((SegMask & (1LL << i)) == 0) continue;
    897 			    res = (1LL * res * (prime[i] - 1)) % Mod;
    898 			    res = (1LL * res * invPrime[i]) % Mod;
    899 			}
    900 			cout << res << endl;
    901 		}
    902 	}
    903 }
    904 
    905 int main(int argc, char* argv[]) {
    906 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    907 	Input(); Solve(); return 0;
    908 }
    909 ```
    910 
    911 **Solution 2 (GreenGrape)**
    912 
    913 Submission link: [49739611](/contest/1114/submission/49739611 "Submission 49739611 by AkiLotus")
    914 
    915 **Source code in plain text**
    916 
    917 ```
    918 #define _CRT_SECURE_NO_WARNINGS
    919 #pragma GCC optimize("unroll-loops")
    920 #include <iostream>
    921 #include <algorithm>
    922 #include <vector>
    923 #include <ctime>
    924 #include <unordered_set>
    925 #include <string>
    926 #include <map>
    927 #include <unordered_map>
    928 #include <random>
    929 #include <set>
    930 #include <cassert>
    931 #include <functional>
    932 #include <iomanip>
    933 #include <queue>
    934 #include <numeric>
    935 #include <bitset>
    936 #include <iterator>
    937 
    938 using namespace std;
    939 
    940 const int N = 100001;
    941 
    942 mt19937 gen(time(NULL));
    943 #define forn(i, n) for (int i = 0; i < n; i++)
    944 #define ford(i, n) for (int i = n - 1; i >= 0; i--)
    945 #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
    946 #define all(a) (a).begin(), (a).end()
    947 #define pii pair<int, int>
    948 #define mp make_pair
    949 #define endl '\n'
    950 #define vi vector<int>
    951 
    952 typedef long long ll;
    953 
    954 template<typename T = int>
    955 inline T read() {
    956 	T val = 0, sign = 1; char ch;
    957 	for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    958 		if (ch == '-') sign = -1;
    959 	for (; ch >= '0' && ch <= '9'; ch = getchar())
    960 		val = val * 10 + ch - '0';
    961 	return sign * val;
    962 }
    963 
    964 const int mod = 1e9 + 7;
    965 const int phi = 1e9 + 6;
    966 
    967 const int M = 301, B = 500;
    968 int P = 0;
    969 
    970 inline int mul(int a, int b) {
    971 	return (a * 1LL * b) % mod;
    972 }
    973 
    974 int mpow(int u, int p) {
    975 	if (!p) return 1;
    976 	return mul(mpow(mul(u, u), p / 2), (p & 1) ? u : 1);
    977 }
    978 
    979 vector<int> primes;
    980 vector<int> pi;
    981 
    982 int pw[M];
    983 int lg[N];
    984 
    985 bool pr(int x) {
    986 	if (x <= 1) return false;
    987 	for (int i = 2; i * i <= x; i++)
    988 		if (x % i == 0)
    989 			return false;
    990 	return true;
    991 }
    992 
    993 void precalc() {
    994 	forn(i, M)
    995 		if (pr(i)) {
    996 			primes.push_back(i);
    997 			P++;
    998 		}
    999 	pi.resize(P);
   1000 	forn(i, M) {
   1001 		int x = 1;
   1002 		forn(j, B) {
   1003 			x = mul(x, i);
   1004 		}
   1005 		pw[i] = x;
   1006 	}
   1007 
   1008 	forn(i, P)
   1009 		pi[i] = mpow(primes[i], phi - 1);
   1010 }
   1011 
   1012 struct product_tree {
   1013 	vector<int> arr, block_product, block_update, single_update;
   1014 	int n;
   1015 
   1016 	product_tree(vector<int>& a) : n(a.size()) {
   1017 		arr = a;
   1018 		while (n % B) {
   1019 			n++, arr.push_back(1);
   1020 		}
   1021 		block_product.resize(n / B, 1);
   1022 		block_update.resize(n / B, -1);
   1023 		single_update.resize(n / B, -1);
   1024 
   1025 		for (int i = 0; i < n; i += B) {
   1026 			int x = 1;
   1027 			int pos = i / B;
   1028 			forn(j, B)
   1029 				x = mul(x, arr[i + j]);
   1030 			block_product[pos] = x;
   1031 		}
   1032 	}
   1033 
   1034 	inline void add(int& u, int x, int mode) {
   1035 		if (mode) {
   1036 			if (u == -1)
   1037 				u = x;
   1038 			else
   1039 				u = mul(u, x);
   1040 		}
   1041 		else {
   1042 			if (u == -1)
   1043 				u = pw[x];
   1044 			else
   1045 				u = mul(u, pw[x]);
   1046 		}
   1047 	}
   1048 
   1049 	void update(int pos, int x) {
   1050 		add(block_update[pos], x, 0);
   1051 		add(single_update[pos], x, 1);
   1052 	}
   1053 
   1054 	void reconstruct(int pos) {
   1055 		int e = single_update[pos];
   1056 		if (e == -1) return;
   1057 		int x = 1;
   1058 
   1059 		int l = pos * B, r = l + B;
   1060 		for (int i = l; i < r; i++) {
   1061 			arr[i] = mul(arr[i], e);
   1062 			x = mul(x, arr[i]);
   1063 		}
   1064 
   1065 		single_update[pos] = block_update[pos] = -1;
   1066 		block_product[pos] = x;
   1067 	}
   1068 
   1069 	void apply(int l, int r, int x) {
   1070 		int L = l / B, R = r / B;
   1071 		if (L == R) {
   1072 			reconstruct(L);
   1073 			for (int i = l; i <= r; i++) {
   1074 				arr[i] = mul(arr[i], x);
   1075 				block_product[L] = mul(block_product[L], x);
   1076 			}
   1077 			return;
   1078 		}
   1079 		reconstruct(L);
   1080 		for (int i = l; i < (L + 1) * B; i++) {
   1081 			arr[i] = mul(arr[i], x);
   1082 			block_product[L] = mul(block_product[L], x);
   1083 		}
   1084 		reconstruct(R);
   1085 		for (int i = R * B; i <= r; i++) {
   1086 			arr[i] = mul(arr[i], x);
   1087 			block_product[R] = mul(block_product[R], x);
   1088 		}
   1089 		for (int j = L + 1; j < R; j++)
   1090 			update(j, x);
   1091 	}
   1092 
   1093 	int get(int l, int r) {
   1094 		int L = l / B, R = r / B;
   1095 		int ans = 1;
   1096 		if (L == R) {
   1097 			reconstruct(L);
   1098 			for (int i = l; i <= r; i++) {
   1099 				ans = mul(ans, arr[i]);
   1100 			}
   1101 			return ans;
   1102 		}
   1103 		reconstruct(L);
   1104 		for (int i = l; i < (L + 1) * B; i++) {
   1105 			ans = mul(ans, arr[i]);
   1106 		}
   1107 		reconstruct(R);
   1108 		for (int i = R * B; i <= r; i++) {
   1109 			ans = mul(ans, arr[i]);
   1110 		}
   1111 		for (int j = L + 1; j < R; j++) {
   1112 			ans = mul(ans, block_product[j]);
   1113 			if (block_update[j] != -1)
   1114 				ans = mul(ans, block_update[j]);
   1115 		}
   1116 		return ans;
   1117 	}
   1118 };
   1119 
   1120 struct prime_tree {
   1121 	vector<ll> t, d;
   1122 	int n;
   1123 
   1124 	prime_tree(vector<ll>& a) : n(a.size()) {
   1125 		t.resize(4 * n);
   1126 		d.resize(4 * n, -1);
   1127 		build(1, 0, n, a);
   1128 	}
   1129 
   1130 	ll build(int u, int l, int r, vector<ll>& a) {
   1131 		if (l == r - 1) {
   1132 			return t[u] = a[l];
   1133 		}
   1134 		int m = (l + r) / 2;
   1135 		return t[u] = build(u << 1, l, m, a) | build(u << 1 | 1, m, r, a);
   1136 	}
   1137 
   1138 	inline void add(ll& u, ll x) {
   1139 		if (u == -1)
   1140 			u = x;
   1141 		else
   1142 			u |= x;
   1143 	}
   1144 
   1145 	void push(int u, int l, int r) {
   1146 		if (d[u] == -1) return;
   1147 		t[u] |= d[u];
   1148 		if (r - l > 1) {
   1149 			add(d[u << 1], d[u]);
   1150 			add(d[u << 1 | 1], d[u]);
   1151 		}
   1152 		d[u] = -1;
   1153 	}
   1154 
   1155 	void update(int u, int l, int r, int L, int R, ll x) {
   1156 		push(u, l, r);
   1157 		if (L >= R || l > L || r < R) return;
   1158 		if (l == L && r == R) {
   1159 			add(d[u], x);
   1160 			push(u, l, r);
   1161 			return;
   1162 		}
   1163 		int m = (l + r) / 2;
   1164 		update(u << 1, l, m, L, min(m, R), x);
   1165 		update(u << 1 | 1, m, r, max(L, m), R, x);
   1166 
   1167 		t[u] = t[u << 1] | t[u << 1 | 1];
   1168 	}
   1169 
   1170 	ll get(int u, int l, int r, int L, int R) {
   1171 		push(u, l, r);
   1172 		if (L >= R || l > L || r < R) return 0;
   1173 		if (l == L && r == R) {
   1174 			return t[u];
   1175 		}
   1176 		int m = (l + r) / 2;
   1177 		return get(u << 1, l, m, L, min(m, R)) | get(u << 1 | 1, m, r, max(L, m), R);
   1178 	}
   1179 
   1180 	ll get(int l, int r) {
   1181 		return get(1, 0, n, l, r + 1);
   1182 	}
   1183 	void apply(int l, int r, ll x) {
   1184 		update(1, 0, n, l, r + 1, x);
   1185 	}
   1186 };
   1187 
   1188 ll transform(int x) {
   1189 	ll mask = 0;
   1190 	forn(i, P)
   1191 		if (x % primes[i] == 0) {
   1192 			mask |= (1LL << i);
   1193 		}
   1194 	return mask;
   1195 }
   1196 
   1197 void solve() {
   1198 	int n, q; cin >> n >> q;
   1199 
   1200 	vi a(n);
   1201 	vector<ll> _a;
   1202 
   1203 	for (auto& v : a) {
   1204 		cin >> v;
   1205 		_a.push_back(transform(v));
   1206 	}
   1207 
   1208 	auto Ptree = product_tree(a);
   1209 	auto Mtree = prime_tree(_a);
   1210 
   1211 	int l, r, x;
   1212 	forn(i, q) {
   1213 		string s; cin >> s;
   1214 		if (s == "MULTIPLY") {
   1215 			cin >> l >> r >> x;
   1216 			l--, r--;
   1217 			Ptree.apply(l, r, x);
   1218 			Mtree.apply(l, r, transform(x));
   1219 		}
   1220 		else {
   1221 			cin >> l >> r;
   1222 			l--, r--;
   1223 
   1224 			int product = Ptree.get(l, r);
   1225 			ll mask = Mtree.get(l, r);
   1226 
   1227 			forn(j, 63)
   1228 				if (mask >> j & 1) {
   1229 					product = mul(product, primes[j] - 1);
   1230 					product = mul(product, pi[j]);
   1231 				}
   1232 
   1233 			cout << product << endl;
   1234 		}
   1235 	}
   1236 }
   1237 
   1238 signed main() {
   1239 	int t = 1;
   1240 
   1241 	ios_base::sync_with_stdio(0);
   1242 	cin.tie(0);
   1243 
   1244 	precalc();
   1245 
   1246 	while (t--) {
   1247 		clock_t z = clock();
   1248 		solve();
   1249 		debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
   1250 	}
   1251 }
   1252 ```