## A - Bestie

You are given an array $$a$$ consisting of $$n$$ integers $$a_1, a_2, \ldots, a_n$$. Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to $$1$$. In one operation, you can do the following:

• Select an arbitrary index in the array $$1 \leq i \leq n$$;
• Make $$a_i = \gcd(a_i, i)$$, where $$\gcd(x, y)$$ denotes the GCD of integers $$x$$ and $$y$$. The cost of such an operation is $$n - i + 1$$.

You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to $$1$$.

### Input

Each test consists of multiple test cases. The first line contains an integer $$t$$ ($$1 \leq t \leq 5\,000$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$n$$ ($$1 \leq n \leq 20$$) — the length of the array.

The second line of each test case contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$ ($$1 \leq a_i \leq 10^9$$) — the elements of the array.

### Output

For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to $$1$$.

We can show that it's always possible to do so.

### Note

In the first test case, the GCD of the entire array is already equal to $$1$$, so there is no need to perform operations.

In the second test case, select $$i = 1$$. After this operation, $$a_1 = \gcd(2, 1) = 1$$. The cost of this operation is $$1$$.

In the third test case, you can select $$i = 1$$, after that the array $$a$$ will be equal to $$[1, 4]$$. The GCD of this array is $$1$$, and the total cost is $$2$$.

In the fourth test case, you can select $$i = 2$$, after that the array $$a$$ will be equal to $$[3, 2, 9]$$. The GCD of this array is $$1$$, and the total cost is $$2$$.

In the sixth test case, you can select $$i = 4$$ and $$i = 5$$, after that the array $$a$$ will be equal to $$[120, 60, 80, 4, 5]$$. The GCD of this array is $$1$$, and the total cost is $$3$$.

Show code

## B - Ugu

A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $$s_1 s_2 \ldots s_n$$. It is necessary to make this string non-decreasing in the least number of operations. In other words, each character should be not less than the previous. In one operation, you can do the following:

• Select an arbitrary index $$1 \leq i \leq n$$ in the string;
• For all $$j \geq i$$, change the value in the $$j$$-th position to the opposite, that is, if $$s_j = 1$$, then make $$s_j = 0$$, and vice versa.

What is the minimum number of operations needed to make the string non-decreasing?

### Input

Each test consists of multiple test cases. The first line contains an integer $$t$$ ($$1 \leq t \leq 10^4$$) — the number of test cases. The description of test cases follows.

The first line of each test cases a single integer $$n$$ ($$1 \leq n \leq 10^5$$) — the length of the string.

The second line of each test case contains a binary string $$s$$ of length $$n$$.

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$2 \cdot 10^5$$.

### Output

For each test case, output a single integer — the minimum number of operations that are needed to make the string non-decreasing.

### Note

In the first test case, the string is already non-decreasing.

In the second test case, you can select $$i = 1$$ and then $$s = \mathtt{01}$$.

In the third test case, you can select $$i = 1$$ and get $$s = \mathtt{010}$$, and then select $$i = 2$$. As a result, we get $$s = \mathtt{001}$$, that is, a non-decreasing string.

In the sixth test case, you can select $$i = 5$$ at the first iteration and get $$s = \mathtt{100001}$$. Then choose $$i = 2$$, then $$s = \mathtt{111110}$$. Then we select $$i = 1$$, getting the non-decreasing string $$s = \mathtt{000001}$$.

Show code

## C1 - Sheikh (Easy version)

This is the easy version of the problem. The only difference is that in this version $$q = 1$$.

You are given an array of integers $$a_1, a_2, \ldots, a_n$$.

The cost of a subsegment of the array $$[l, r]$$, $$1 \leq l \leq r \leq n$$, is the value $$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$, where $$\operatorname{sum}(l, r) = a*l + a*{l+1} + \ldots + a*r$$, and $$\operatorname{xor}(l, r) = a_l \oplus a*{l+1} \oplus \ldots \oplus a_r$$ ($$\oplus$$ stands for bitwise XOR).

You will have $$q = 1$$ query. Each query is given by a pair of numbers $$L_i$$, $$R_i$$, where $$1 \leq L_i \leq R_i \leq n$$. You need to find the subsegment $$[l, r]$$, $$L_i \leq l \leq r \leq R_i$$, with maximum value $$f(l, r)$$. If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of $$r - l + 1$$.

### Input

Each test consists of multiple test cases. The first line contains an integer $$t$$ ($$1 \leq t \leq 10^4$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$n$$ and $$q$$ ($$1 \leq n \leq 10^5$$, $$q = 1$$) — the length of the array and the number of queries.

The second line of each test case contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$ ($$0 \leq a_i \leq 10^9$$) — array elements.

$$i$$-th of the next $$q$$ lines of each test case contains two integers $$L_i$$ and $$R_i$$ ($$1 \leq L_i \leq R_i \leq n$$) — the boundaries in which we need to find the segment.

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$2 \cdot 10^5$$.

It is guaranteed that $$L_1 = 1$$ and $$R_1 = n$$.

### Output

For each test case print $$q$$ pairs of numbers $$L_i \leq l \leq r \leq R_i$$ such that the value $$f(l, r)$$ is maximum and among such the length $$r - l + 1$$ is minimum. If there are several correct answers, print any of them.

### Note

In the first test case, $$f(1, 1) = 0 - 0 = 0$$.

In the second test case, $$f(1, 1) = 5 - 5 = 0$$, $$f(2, 2) = 10 - 10 = 0$$. Note that $$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$, but we need to find a subsegment with the minimum length among the maximum values of $$f(l, r)$$. So, only segments $$[1, 1]$$ and $$[2, 2]$$ are the correct answers.

In the fourth test case, $$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$.

There are two correct answers in the fifth test case, since $$f(2, 3) = f(3, 4)$$ and their lengths are equal.

Show code

## C2 - Sheikh (Hard Version)

This is the hard version of the problem. The only difference is that in this version $$q = n$$.

You are given an array of integers $$a_1, a_2, \ldots, a_n$$.

The cost of a subsegment of the array $$[l, r]$$, $$1 \leq l \leq r \leq n$$, is the value $$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$, where $$\operatorname{sum}(l, r) = a*l + a*{l+1} + \ldots + a*r$$, and $$\operatorname{xor}(l, r) = a_l \oplus a*{l+1} \oplus \ldots \oplus a_r$$ ($$\oplus$$ stands for bitwise XOR).

You will have $$q$$ queries. Each query is given by a pair of numbers $$L_i$$, $$R_i$$, where $$1 \leq L_i \leq R_i \leq n$$. You need to find the subsegment $$[l, r]$$, $$L_i \leq l \leq r \leq R_i$$, with maximum value $$f(l, r)$$. If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of $$r - l + 1$$.

### Input

Each test consists of multiple test cases. The first line contains an integer $$t$$ ($$1 \leq t \leq 10^4$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$n$$ and $$q$$ ($$1 \leq n \leq 10^5$$, $$q = n$$) — the length of the array and the number of queries.

The second line of each test case contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$ ($$0 \leq a_i \leq 10^9$$) — array elements.

$$i$$-th of the next $$q$$ lines of each test case contains two integers $$L_i$$ and $$R_i$$ ($$1 \leq L_i \leq R_i \leq n$$) — the boundaries in which we need to find the segment.

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$2 \cdot 10^5$$.

It is guaranteed that $$L_1 = 1$$ and $$R_1 = n$$.

### Output

For each test case print $$q$$ pairs of numbers $$L_i \leq l \leq r \leq R_i$$ such that the value $$f(l, r)$$ is maximum and among such the length $$r - l + 1$$ is minimum. If there are several correct answers, print any of them.

### Note

In all test cases, the first query is considered.

In the first test case, $$f(1, 1) = 0 - 0 = 0$$.

In the second test case, $$f(1, 1) = 5 - 5 = 0$$, $$f(2, 2) = 10 - 10 = 0$$. Note that $$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$, but we need to find a subsegment with the minimum length among the maximum values of $$f(l, r)$$. So, only segments $$[1, 1]$$ and $$[2, 2]$$ are the correct answers.

In the fourth test case, $$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$.

There are two correct answers in the fifth test case, since $$f(2, 3) = f(3, 4)$$ and their lengths are equal.

Show code

## D1 - Balance (Easy version)

This is the easy version of the problem. The only difference is that in this version there are no "remove" queries.

Initially you have a set containing one element — $$0$$. You need to handle $$q$$ queries of the following types:

• + $$x$$ — add the integer $$x$$ to the set. It is guaranteed that this integer is not contained in the set;
• ? $$k$$ — find the $$k\text{-mex}$$ of the set.

In our problem, we define the $$k\text{-mex}$$ of a set of integers as the smallest non-negative integer $$x$$ that is divisible by $$k$$ and which is not contained in the set.

### Input

The first line contains an integer $$q$$ ($$1 \leq q \leq 2 \cdot 10^5$$) — the number of queries.

The following $$q$$ lines describe the queries.

An addition query of integer $$x$$ is given in the format + $$x$$ ($$1 \leq x \leq 10^{18}$$). It is guaranteed that $$x$$ was not contained in the set.

A search query of $$k\text{-mex}$$ is given in the format ? $$k$$ ($$1 \leq k \leq 10^{18}$$).

It is guaranteed that there will be at least one query of type ?.

### Output

For each query of type ? output a single integer — the $$k\text{-mex}$$ of the set.

### Note

In the first example:

After the first and second queries, the set will contain elements $$\{0, 1, 2\}$$. The smallest non-negative number that is divisible by $$1$$ and is not contained in the set is $$3$$.

After the fourth query, the set will contain the elements $$\{0, 1, 2, 4\}$$. The smallest non-negative number that is divisible by $$2$$ and is not contained in the set is $$6$$.

In the second example:

• Initially, the set contains only the element $$\{0\}$$.
• After adding an integer $$100$$ the set contains elements $$\{0, 100\}$$.
• $$100\text{-mex}$$ of the set is $$200$$.
• After adding an integer $$200$$ the set contains elements $$\{0, 100, 200\}$$.
• $$100\text{-mex}$$ of the set is $$300$$.
• After adding an integer $$50$$ the set contains elements $$\{0, 50, 100, 200\}$$.
• $$50\text{-mex}$$ of the set is $$150$$.

### 思路与做法

D1 和 D2 基本都是暴力优化然后均摊复杂度能过，很神奇

Show code

## D2 - Balance (Hard version)

This is the hard version of the problem. The only difference is that in this version there are remove queries.

Initially you have a set containing one element — $$0$$. You need to handle $$q$$ queries of the following types:

• + $$x$$ — add the integer $$x$$ to the set. It is guaranteed that this integer is not contained in the set;
• - $$x$$ — remove the integer $$x$$ from the set. It is guaranteed that this integer is contained in the set;
• ? $$k$$ — find the $$k\text{-mex}$$ of the set.

In our problem, we define the $$k\text{-mex}$$ of a set of integers as the smallest non-negative integer $$x$$ that is divisible by $$k$$ and which is not contained in the set.

### Input

The first line contains an integer $$q$$ ($$1 \leq q \leq 2 \cdot 10^5$$) — the number of queries.

The following $$q$$ lines describe the queries.

An addition query of integer $$x$$ is given in the format + $$x$$ ($$1 \leq x \leq 10^{18}$$). It is guaranteed that $$x$$ is not contained in the set.

A remove query of integer $$x$$ is given in the format - $$x$$ ($$1 \leq x \leq 10^{18}$$). It is guaranteed that $$x$$ is contained in the set.

A search query of $$k\text{-mex}$$ is given in the format ? $$k$$ ($$1 \leq k \leq 10^{18}$$).

It is guaranteed that there is at least one query of type ?.

### Output

For each query of type ? output a single integer — the $$k\text{-mex}$$ of the set.

### Note

In the first example:

After the first and second queries, the set will contain elements $$\{0, 1, 2\}$$. The smallest non-negative number that is divisible by $$1$$ and is not in the set is $$3$$.

After the fourth query, the set will contain the elements $$\{0, 1, 2, 4\}$$. The smallest non-negative number that is divisible by $$2$$ and is not in the set is $$6$$.

In the second example:

• Initially, the set contains only the element $$\{0\}$$.
• After adding an integer $$100$$ the set contains elements $$\{0, 100\}$$.
• $$100\text{-mex}$$ of the set is $$200$$.
• After adding an integer $$200$$ the set contains elements $$\{0, 100, 200\}$$.
• $$100\text{-mex}$$ of the set $$300$$.
• After removing an integer $$100$$ the set contains elements $$\{0, 200\}$$.
• $$100\text{-mex}$$ of the set is $$100$$.
• After adding an integer $$50$$ the set contains elements $$\{0, 50, 200\}$$.
• $$50\text{-mex}$$ of the set is $$100$$.
• After removing an integer $$50$$ the set contains elements $$\{0, 200\}$$.
• $$100\text{-mex}$$ of the set is $$50$$.

### 思路与做法

D2 加了删除，这样单纯一个 std::map<int, int> res 就不够用了

• std::map<int, std::vector<int>> changed 记录一下答案都可以从哪个 k 转移过来，即 changed[x] 里的元素都是之前查询时枚举到 x 时对应的所有 k
• std::map<int, std::set<int>> del 记录两次查询 k 之间都删除了哪些会影响答案的数

Show code

## E - Location

You are given two arrays of integers $$a_1, a_2, \ldots, a_n$$ and $$b_1, b_2, \ldots, b_n$$. You need to handle $$q$$ queries of the following two types:

• $$1$$ $$l$$ $$r$$ $$x$$: assign $$a_i := x$$ for all $$l \leq i \leq r$$;

• $$2$$ $$l$$ $$r$$: find the minimum value of the following expression among all $$l \leq i \leq r$$:

$\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}.$

In this problem $$\gcd(x, y)$$ denotes the greatest common divisor of $$x$$ and $$y$$, and $$\operatorname{lcm}(x, y)$$ denotes the least common multiple of $$x$$ and $$y$$.

### Input

The first line contains two integers $$n$$ and $$q$$ ($$1 \leq n, q \leq 5 \cdot 10^4$$) — the number of numbers in the arrays $$a$$ and $$b$$ and the number of queries.

The second line contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$ ($$1 \leq a_i \leq 5 \cdot 10^4$$) — the elements of the array $$a$$.

The third line contains $$n$$ integers $$b_1, b_2, \ldots, b_n$$ ($$1 \leq b_i \leq 5 \cdot 10^4$$) — the elements of the array $$b$$.

Then $$q$$ lines follow, $$j$$-th of which starts with an integer $$t_j$$ ($$1 \leq t_j \leq 2$$) and means that the $$j$$-th query has type $$t_j$$.

If $$t_j = 1$$, it is followed by three integers $$l_j$$, $$r_j$$, and $$x_j$$ ($$1 \leq l_j \leq r_j \leq n$$, $$1 \leq x_j \leq 5 \cdot 10^4$$).

If $$t_j = 2$$, it is followed by two integers $$l_j$$ and $$r_j$$ ($$1 \leq l_j \leq r_j \leq n$$).

It is guaranteed that there is at least one query of type $$2$$.

### Output

For each query of the second type, output the minimum value of the expression.

### Note

In the first example:

• For the first query we can choose $$i = 4$$. So the value is $$\frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1$$.
• After the second query the array $$a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9]$$.
• For the third query we can choose $$i = 9$$. So the value is $$\frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2$$.

In the second:

• For the first query we can choose $$i = 4$$. So the value is $$\frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5$$.
• After the second query the array $$a = [10, 18, 18, 5]$$.
• After the third query the array $$a = [10, 10, 18, 5]$$.
• For the fourth query we can choose $$i = 2$$. So the value is $$\frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 30$$.

### 思路与做法

$B'=\min_{f\mid x}\left\{B,\frac{xv_f}{f^2}\right\}$

Show code