apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive integer $$$n$$$. Please find an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

A perfect array $$$a_1, a_2, \ldots, a_n$$$ satisfies the following criteria:

- $$$1 \le a_i \le 1000$$$ for all $$$1 \le i \le n$$$.
- $$$a_i$$$ is divisible by $$$i$$$ for all $$$1 \le i \le n$$$.
- $$$a_1 + a_2 + \ldots + a_n$$$ is divisible by $$$n$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The only line of each test case contains a single positive integer $$$n$$$ ($$$1 \le n \le 200$$$) — the length of the array $$$a$$$.

## Output Format
For each test case, output an array $$$a_1, a_2, \ldots, a_n$$$ that is perfect.

We can show that an answer always exists. If there are multiple solutions, print any.

## Examples
```input
7
1
2
3
4
5
6
7
```
```output
1
2 4
1 2 3
2 8 6 4
3 4 9 4 5
1 10 18 8 5 36
3 6 21 24 10 6 14
```

## Note
In the third test case:

- $$$a_1 = 1$$$ is divisible by $$$1$$$.
- $$$a_2 = 2$$$ is divisible by $$$2$$$.
- $$$a_3 = 3$$$ is divisible by $$$3$$$.
- $$$a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$$$ is divisible by $$$3$$$.

In the fifth test case:

- $$$a_1 = 3$$$ is divisible by $$$1$$$.
- $$$a_2 = 4$$$ is divisible by $$$2$$$.
- $$$a_3 = 9$$$ is divisible by $$$3$$$.
- $$$a_4 = 4$$$ is divisible by $$$4$$$.
- $$$a_5 = 5$$$ is divisible by $$$5$$$.
- $$$a_1 + a_2 + a_3 + a_4 + a_5 = 3 + 4 + 9 + 4 + 5 = 25$$$ is divisible by $$$5$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an unsorted permutation $$$p_1, p_2, \ldots, p_n$$$. To sort the permutation, you choose a constant $$$k$$$ ($$$k \ge 1$$$) and do some operations on the permutation. In one operation, you can choose two integers $$$i$$$, $$$j$$$ ($$$1 \le j < i \le n$$$) such that $$$i - j = k$$$, then swap $$$p_i$$$ and $$$p_j$$$.

What is the maximum value of $$$k$$$ that you can choose to sort the given permutation?

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1, 3, 4]$$$ is also not a permutation ($$$n = 3$$$ but there is $$$4$$$ in the array).

An unsorted permutation $$$p$$$ is a permutation such that there is at least one position $$$i$$$ that satisfies $$$p_i \ne i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^{5}$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$. It is guaranteed that the given numbers form a permutation of length $$$n$$$ and the given permutation is unsorted.

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

## Output Format
For each test case, output the maximum value of $$$k$$$ that you can choose to sort the given permutation.

We can show that an answer always exists.

## Examples
```input
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2
```
```output
1
2
3
4
3
2
3
```

## Note
In the first test case, the maximum value of $$$k$$$ you can choose is $$$1$$$. The operations used to sort the permutation are:

- Swap $$$p_2$$$ and $$$p_1$$$ ($$$2 - 1 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 3, 2]$$$
- Swap $$$p_2$$$ and $$$p_3$$$ ($$$3 - 2 = 1$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3]$$$

In the second test case, the maximum value of $$$k$$$ you can choose is $$$2$$$. The operations used to sort the permutation are:

- Swap $$$p_3$$$ and $$$p_1$$$ ($$$3 - 1 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 4, 3, 2]$$$
- Swap $$$p_4$$$ and $$$p_2$$$ ($$$4 - 2 = 2$$$) $$$\rightarrow$$$ $$$p = [1, 2, 3, 4]$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
On a permutation $$$p$$$ of length $$$n$$$, we define a bully swap as follows:

- Let $$$i$$$ be the index of the largest element $$$p_i$$$ such that $$$p_i \neq i$$$.
- Let $$$j$$$ be the index of the smallest element $$$p_j$$$ such that $$$i < j$$$.
- Swap $$$p_i$$$ and $$$p_j$$$.

We define $$$f(p)$$$ as the number of bully swaps we need to perform until $$$p$$$ becomes sorted. Note that if $$$p$$$ is the identity permutation, $$$f(p)=0$$$.

You are given $$$n$$$ and a permutation $$$p$$$ of length $$$n$$$. You need to process the following $$$q$$$ updates.

In each update, you are given two integers $$$x$$$ and $$$y$$$. You will swap $$$p_x$$$ and $$$p_y$$$ and then find the value of $$$f(p)$$$.

Note that the updates are persistent. Changes made to the permutation $$$p$$$ will apply when processing future updates.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^4$$$) — the length of the permutation and the number of updates.

The second line of input contains $$$n$$$ integer $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$. All elements of $$$p$$$ are distinct.

The $$$i$$$-th of the next $$$q$$$ lines of input contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$) — describing the $$$i$$$-th update.

## Output Format
After each update, output $$$f(p)$$$.

## Examples
```input
8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6
```
```output
5
6
9
8
7
```

## Note
After the first update, we have $$$f(p)=5$$$. The $$$5$$$ bully swaps are illustrated below.

- $$$[\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6]$$$,
- $$$[1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6]$$$,
- $$$[1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6]$$$,
- $$$[1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}]$$$,
- $$$[1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Given an array $$$a$$$ of length $$$n$$$, which elements are equal to $$$-1$$$ and $$$1$$$. Let's call the array $$$a$$$ good if the following conditions are held at the same time:

- $$$a_1 + a_2 + \ldots + a_n \ge 0$$$;
- $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1$$$.

In one operation, you can select an arbitrary element of the array $$$a_i$$$ and change its value to the opposite. In other words, if $$$a_i = -1$$$, you can assign the value to $$$a_i := 1$$$, and if $$$a_i = 1$$$, then assign the value to $$$a_i := -1$$$.

Determine the minimum number of operations you need to perform to make the array $$$a$$$ good. It can be shown that this is always possible.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = \pm 1$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations that need to be done to make the $$$a$$$ array good.

## Examples
```input
7
4
-1 -1 1 -1
5
-1 -1 -1 1 1
4
-1 1 -1 1
3
-1 -1 -1
5
1 1 1 1 1
1
-1
2
-1 -1
```
```output
1
1
0
3
0
1
2
```

## Note
In the first test case, we can assign the value $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$$$. Thus, we performed $$$1$$$ operation.

In the second test case, we can assign $$$a_1 := 1$$$. Then $$$a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$1$$$ operation.

In the third test case, $$$a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$$$. Thus, all conditions are already satisfied and no operations are needed.

In the fourth test case, we can assign the values $$$a_1 := 1, a_2 := 1, a_3 := 1$$$. Then $$$a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$$$ and $$$a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$$$. Thus, we performed $$$3$$$ operations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Zinaida Viktorovna has $$$n$$$ students in her history class. The homework for today included $$$m$$$ topics, but the students had little time to prepare, so $$$i$$$-th student learned only topics from $$$l_i$$$ to $$$r_i$$$ inclusive.

At the beginning of the lesson, each student holds their hand at $$$0$$$. The teacher wants to ask some topics. It goes like this:

- The teacher asks the topic $$$k$$$.
- If the student has learned topic $$$k$$$, then he raises his hand by $$$1$$$, otherwise he lower it by $$$1$$$.

Each topic Zinaida Viktorovna can ask no more than one time.

Find the maximum difference of the heights of the highest and the lowest hand that can be in class after the survey.

Note that the student's hand can go below $$$0$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^9$$$) — the number of students and the number of topics, respectively.

Each of the next $$$n$$$ lines of each test case contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the endpoints of the segment of topics that $$$i$$$-th student has learned.

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

## Output Format
For each test case, print one integer — the maximum difference of the heights of the highest and the lowest hand that can be in the class after the survey.

## Examples
```input
6
4 8
2 6
4 8
2 7
1 5
3 3
1 3
2 3
2 2
3 5
1 5
1 5
1 5
3 5
1 1
3 3
5 5
4 7
1 7
1 3
3 3
4 5
2 4
1 3
2 4
```
```output
6
4
0
2
12
2
```

## Note
In the first test case, Zinaida Viktorovna can ask the topics $$$5, 6, 7, 8$$$. Then the hand of the $$$2$$$-nd student will be at the height of $$$4$$$, and the hand of the $$$4$$$-th will be at the height of $$$-2$$$, that is, the difference will be equal to $$$6$$$.

In the second test case, you can ask about the topics $$$1$$$ and $$$3$$$. Then the hand of the $$$1$$$-st student will be at the height of $$$2$$$ and the hand of the $$$3$$$-rd student will be at the height of $$$-2$$$. So the difference will be $$$4$$$.

In the third test case, the difference between the highest and lowest hand will be $$$0$$$ for any set of topics asked.

In the fifth test case, you can ask all topics. Then the difference between the heights of the $$$1$$$-st and $$$3$$$-rd students' hands will be $$$12$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$. A positive integer $$$x$$$ is called good if it is impossible to find a subsegment$$$^{\dagger}$$$ of the array such that the least common multiple of all its elements is equal to $$$x$$$.

You need to find the smallest good integer.

A subsegment$$$^{\dagger}$$$ of the array $$$a$$$ is a set of elements $$$a_l, a_{l + 1}, \ldots, a_r$$$ for some $$$1 \le l \le r \le n$$$. We will denote such subsegment as $$$[l, r]$$$.

## Input Format
Each test consists of multiple test cases. The first line of each test case contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 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 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

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

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

## Output Format
For each test case, output a single integer — the smallest good integer.

## Examples
```input
6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9
```
```output
4
7
1
1
16
13
```

## Note
In the first test case, $$$4$$$ is a good integer, and it is the smallest one, since the integers $$$1,2,3$$$ appear in the array, which means that there are subsegments of the array of length $$$1$$$ with least common multiples of $$$1,2,3$$$. However, it is impossible to find a subsegment of the array with a least common multiple equal to $$$4$$$.

In the second test case, $$$7$$$ is a good integer. The integers $$$1,2,3,4,5$$$ appear explicitly in the array, and the integer $$$6$$$ is the least common multiple of the subsegments $$$[2, 3]$$$ and $$$[1, 3]$$$.

In the third test case, $$$1$$$ is a good integer, since the least common multiples for the integer in the subsegments $$$[1, 1], [1, 2], [2, 2]$$$ are $$$2,6,3$$$, respectively.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array consisting of $$$n$$$ integers. Your task is to determine whether it is possible to color all its elements in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored.

For example, if the array is [$$$1,2,4,3,2,3,5,4$$$], we can color it as follows: [$$$\color{blue}{1},\color{blue}{2},\color{red}{4},\color{blue}{3},\color{red}{2},\color{red}{3},\color{red}{5},\color{red}{4}$$$], where the sum of the blue elements is $$$6$$$ and the sum of the red elements is $$$18$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case begins with a line containing an integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ ($$$1 \le a_i \le 50$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, output "YES" (without quotes) if it is possible to color the array in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored, and "NO" otherwise.

You can output "Yes" and "No" in any case (for example, the strings "yES", "yes", and "Yes" will be recognized as correct answers).

## Examples
```input
7
8
1 2 4 3 2 3 5 4
2
4 7
3
3 9 8
2
1 7
5
5 4 3 2 1
4
4 3 4 5
2
50 48
```
```output
YES
NO
YES
YES
NO
YES
YES
```

## Note
The first sample is described in the statement.

In the second sample, there are only two colorings $$$[\color{blue}{4},\color{red}{7}]$$$ and $$$[\color{red}{4},\color{blue}{7}]$$$ , but in both cases the parity of sums is different.

In the third sample, you can color $$$[\color{blue}{3},\color{blue}{9},\color{red}{8}]$$$ and $$$12$$$ and $$$8$$$ are both even.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Sasha has an array $$$a$$$ of $$$n$$$ integers. He got bored and for all $$$i$$$, $$$j$$$ ($$$i < j$$$), he wrote down the minimum value of $$$a_i$$$ and $$$a_j$$$. He obtained a new array $$$b$$$ of size $$$\frac{n\cdot (n-1)}{2}$$$.

For example, if $$$a=$$$ [$$$2,3,5,1$$$], he would write [$$$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$$$] $$$=$$$ [$$$2, 2, 1, 3, 1, 1$$$].

Then, he randomly shuffled all the elements of the array $$$b$$$.

Unfortunately, he forgot the array $$$a$$$, and your task is to restore any possible array $$$a$$$ from which the array $$$b$$$ could have been obtained.

The elements of array $$$a$$$ should be in the range $$$[-10^9,10^9]$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 200$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 10^3$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$\frac{n\cdot (n-1)}{2}$$$ integers $$$b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$$$ ($$$−10^9\le b_i\le 10^9$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$10^3$$$ and for each array $$$b$$$ in the test, there exists an original array.

## Output Format
For each test case, output any possible array $$$a$$$ of length $$$n$$$.

## Examples
```input
5
3
1 3 1
2
10
4
7 5 3 5 3 3
5
2 2 2 2 2 2 2 2 2 2
5
3 0 0 -2 0 -2 0 0 -2 -2
```
```output
1 3 3
10 10
7 5 3 12
2 2 2 2 2
0 -2 0 3 5
```

## Note
In the first sample, Sasha chose the array $$$[1,3,3]$$$, then the array $$$b$$$ will look like $$$[\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]$$$, after shuffling its elements, the array can look like $$$[1,3,1]$$$.

In the second sample, there is only one pair, so the array $$$[10,10]$$$ is suitable. Another suitable array could be $$$[15,10]$$$.

Now solve the problem and return the code.