仓库源文，站点原文

title: "题解 - Codeforces Round #830 (Div. 2)" date: 2022-10-27 01:11:30 categories:

算法竞赛 tags:
算法竞赛
Codeforces
暴力
模拟
贪心
思维
构造
二分
数学
组合数学
抽屉原理
数据结构
分块
前缀和
记忆化搜索
均摊复杂度
数论
最大公约数
最小公倍数
位运算
异或

神奇的数据结构场 $\dots$

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.

Example

input

9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125

output

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$.

思路与做法

注意到 $\gcd(x,x+1)=1$, 故答案不超过 3, 简单讨论下就行了

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732A CodeForces/1732A/0.cpp %} </details>

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.

Example

input

output

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}$.

思路与做法

简单扫一遍就行, 注意特判全为 0 的情况

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732B CodeForces/1732B/0.cpp %} </details>

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) = al + a{l+1} + \ldots + ar$, 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.

Example

input

6
1 1
0
1 1
2 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7

output

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.

思路与做法

注意到 $f(l,r)\leq f(l,r+1)$, 所以我们枚举 $l$ 然后二分出最小的 $r$ 即可

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732C1 CodeForces/1732C1/0.cpp %} </details>

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$.

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

Example

input

6
1 1
0
1 1
2 2
5 10
1 2
2 2
3 3
0 2 4
1 3
1 2
2 3
4 4
0 12 8 3
1 4
1 3
2 4
2 3
5 5
21 32 32 32 10
1 5
1 4
1 3
2 5
3 5
7 7
0 1 0 1 0 1 0
1 7
3 6
2 5
1 4
4 7
2 6
2 7

output

Note

In all test cases, the first query is considered.

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

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.

思路与做法

接着 C1 的思路继续

这题最玄幻的一点来了: 实际上我们可以不用二分, 因为由抽屉原理, 我们最多只需要删掉当前区间端点的 $\operatorname{lb} 10^9\approx 31$ 个非零数即可使 $f$ 变小, 所以直接枚举一下即可

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732C2 CodeForces/1732C2/0.cpp %} </details>

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.

Examples

input

15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000

output

3
6
3
3
10
3
2000000000000000000

input

output

200
300
150

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 基本都是暴力优化然后均摊复杂度能过, 很神奇

我们考虑暴力做法: 用 std::set 暴力维护

显然这样插入是 $O(\log n)$ 的, 但是查找是 $O(\frac{K}{k}\log n)$ 的, 其中 $K\leq 2\times 10^{18}$

我们发现若某次查询的 $k$ 之前已经查过了, 那我们不需要从 $x$ 依次枚举, 而直接从上一次的进度继续即可

这样的话我们就相当于把许多查询压缩到了一次, 这样的话 std::set 里元素被访问的次数均摊下来大概只有 $O(\log q)$ 次, 就可以通过本题了

具体来说就是我们开一个 std::map<int, int> res, 其中 res[k] 表示上一次询问 k 时的答案, 则之后再询问 k 的时候只需要从 res[k] 开始搜即可

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732D1 CodeForces/1732D1/1.cpp %} </details>

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.

Examples

input

18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2

output

3
6
3
3
10
3
2000000000000000000
3
4

input

output

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$.

思路与做法

和 D1 一样, 我们考虑优化暴力做法

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 之间都删除了哪些会影响答案的数

这样时间复杂度均摊下来就是比 D1 多了个 std::set 带来的 $O(\log n)$

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732D2 CodeForces/1732D2/0.cpp %} </details>

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.

Examples

input

10 10
6 10 15 4 9 25 2 3 5 30
1 2 3 4 6 9 12 15 18 30
2 1 10
1 7 10 9
2 5 10
1 1 6 14
2 4 7
2 3 9
1 2 9 30
2 1 4
2 3 7
2 5 10

output

input

output

5
30

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$.

思路与做法

显然要上数据结构, 这里参照官方题解写的分块

写分块的话关键在于对每个块怎么维护操作 1

我们先对每个 b[i] 枚举因数 f, 然后每个块上都开个数组 v, v[f] 记录块上含因子 f 的最小的 b 的值

在将某个块上全部的 a 都改成 $x$ 的时候, 我们首先打个懒标记, 因为当需要修改单个元素时候需要首先根据懒标记暴力修改块上的元素来保证正确性. 接着设此时块上的答案为 $B$, 则修改后的答案 $B'$ 满足

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

注意这题要用 uint32_t, 因为 int64_t 会被卡常, 而且结果最大大约为 2.5e9

代码参考

<details open> <summary>Show code</summary> {% icodeweb cpa_cpp title:CodeForces_1732E CodeForces/1732E/0.cpp %} </details>