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 an integer $$$n$$$. Find a sequence of $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ such that $$$1 \leq a_i \leq 10^9$$$ for all $$$i$$$ and $$$$$$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)= \sqrt{a_1 + a_2 + \dots + a_n}.$$$$$$

It can be proven that there exists a sequence of distinct integers that satisfies all the conditions above.

## Input Format
The first line of input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first and only line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the length of the sequence you have to find.

The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output $$$n$$$ space-separated distinct integers $$$a_1, a_2, \dots, a_n$$$ satisfying the conditions in the statement.

If there are several possible answers, you can output any of them. Please remember that your integers must be distinct!

## Examples
```input
3
2
5
4
```
```output
3 1
20 29 18 26 28
25 21 23 31
```

## Note
In the first test case, the maximum is $$$3$$$, the minimum is $$$1$$$, the sum is $$$4$$$, and $$$3 - 1 = \sqrt{4}$$$.

In the second test case, the maximum is $$$29$$$, the minimum is $$$18$$$, the sum is $$$121$$$, and $$$29-18 = \sqrt{121}$$$.

For each test case, the integers are all distinct.

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
Колонна из $$$n$$$ самокатов едет по узкой односторонней дороге в пункт Б. Самокаты пронумерованы от $$$1$$$ до $$$n$$$. Для каждого самоката $$$i$$$ известно, что текущее расстояние от него до пункта Б равно $$$a_i$$$ метров. При этом $$$a_1 < a_2 < \ldots < a_n$$$, в частности, самокат $$$1$$$ находится ближе всего к пункту Б, а самокат $$$n$$$ — дальше всего.

Самокат с номером $$$i$$$ движется в сторону пункта Б со скоростью $$$i$$$ метров в секунду (то есть чем ближе самокат в колонне к пункту Б, тем медленнее он едет). Так как дорога узкая, самокаты не могут обгонять друг друга. Более того, соседние самокаты в колонне должны соблюдать дистанцию хотя бы в $$$1$$$ метр. Поэтому когда более быстрый самокат догоняет более медленный, более быстрому приходится дальше ехать со скоростью более медленного, причём на расстоянии в $$$1$$$ метр от него.

Определите, на каком расстоянии до пункта Б будет каждый самокат ровно через одну секунду.

## Input Format
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число самокатов в колонне.

В $$$i$$$-й из следующих $$$n$$$ строк задано одно целое число $$$a_i$$$ ($$$1 \le a_i \le 1000$$$; $$$a_1 < a_2 < \ldots < a_n$$$) — текущее расстояние от самоката $$$i$$$ до пункта Б в метрах.

## Output Format
Выведите $$$n$$$ целых чисел — расстояния от самокатов $$$1, 2, \ldots, n$$$ до пункта Б в метрах через одну секунду.

## Examples
```input
4
20
30
50
100
```
```output
19
28
47
96
```
-----
```input
5
1
2
3
4
5
```
```output
0
1
2
3
4
```
-----
```input
8
5
9
10
15
17
18
19
22
```
```output
4
7
8
11
12
13
14
15
```

## Note
В первом тесте самокаты пока не мешают друг другу ехать, поэтому каждый самокат $$$i$$$ продвигается на $$$i$$$ метров в сторону пункта Б.

Во втором тесте самокаты уже выстроились в колонне на расстоянии $$$1$$$ метр друг от друга и вынуждены ехать со скоростью самого медленного самоката с номером $$$1$$$.

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
В этой версии задачи размеры копируемых файлов не превышают $$$1000$$$ байт.

Вы копируете с одного сервера на другой $$$n$$$ файлов размером $$$a_1, a_2, \ldots, a_n$$$ байт. Файлы копируются последовательно в заданном порядке.

При копировании вы видите два прогресс-бара: первый показывает процент скопированных данных в текущем файле, а второй — общий процент скопированных данных по всем $$$n$$$ файлам. Оба процента отображаются округлёнными вниз до целого числа. Значения на прогресс-барах обновляются после копирования каждого байта.

Формально, после копирования байта номер $$$x$$$ из файла номер $$$i$$$ первый прогресс-бар показывает $$$\lfloor \frac{100 \cdot x}{a_i} \rfloor$$$ процентов, а второй — $$$\lfloor \frac{100 \cdot (a_1 + a_2 + \ldots + a_{i - 1} + x)}{a_1 + a_2 + \ldots + a_n} \rfloor$$$ процентов. В самом начале копирования оба прогресс-бара показывают $$$0$$$ процентов.

Найдите все такие целые числа от $$$0$$$ до $$$100$$$ включительно, что существует момент времени, в который оба прогресс-бара одновременно показывают это число. Выведите эти числа в порядке возрастания.

## Input Format
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число копируемых файлов.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — размеры файлов в байтах в том порядке, в котором они будут копироваться.

## Output Format
Выведите в возрастающем порядке все числа от $$$0$$$ до $$$100$$$ включительно такие, что существует момент времени, в который на обоих прогресс-барах одновременно показывается это число.

## Examples
```input
1
6
```
```output
0
16
33
50
66
83
100
```
-----
```input
2
100 500
```
```output
0
95
96
97
98
99
100
```
-----
```input
4
1000 2 2 998
```
```output
0
50
99
100
```
-----
```input
6
170 130 400 256 30 100
```
```output
0
17
43
44
84
90
99
100
```

## Note
В первом тесте копируется всего один файл, поэтому оба прогресс-бара всегда показывают одинаковые значения.

Во втором тесте первый прогресс-бар сразу же уйдёт вперёд, потом сбросится в ноль и начнёт догонять второй прогресс-бар заново. В конце копирования прогресс-бары некоторое время будут показывать одно и то же число.

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
В этой версии задачи размеры копируемых файлов не превышают $$$10^{10}$$$ байт.

Вы копируете с одного сервера на другой $$$n$$$ файлов размером $$$a_1, a_2, \ldots, a_n$$$ байт. Файлы копируются последовательно в заданном порядке.

При копировании вы видите два прогресс-бара: первый показывает процент скопированных данных в текущем файле, а второй — общий процент скопированных данных по всем $$$n$$$ файлам. Оба процента отображаются округлёнными вниз до целого числа. Значения на прогресс-барах обновляются после копирования каждого байта.

Формально, после копирования байта номер $$$x$$$ из файла номер $$$i$$$ первый прогресс-бар показывает $$$\lfloor \frac{100 \cdot x}{a_i} \rfloor$$$ процентов, а второй — $$$\lfloor \frac{100 \cdot (a_1 + a_2 + \ldots + a_{i - 1} + x)}{a_1 + a_2 + \ldots + a_n} \rfloor$$$ процентов. В самом начале копирования оба прогресс-бара показывают $$$0$$$ процентов.

Найдите все такие целые числа от $$$0$$$ до $$$100$$$ включительно, что существует момент времени, в который оба прогресс-бара одновременно показывают это число. Выведите эти числа в порядке возрастания.

## Input Format
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число копируемых файлов.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{10}$$$) — размеры файлов в байтах в том порядке, в котором они будут копироваться.

## Output Format
Выведите в возрастающем порядке все числа от $$$0$$$ до $$$100$$$ включительно такие, что существует момент времени, в который на обоих прогресс-барах одновременно показывается это число.

## Examples
```input
1
6
```
```output
0
16
33
50
66
83
100
```
-----
```input
2
100 500
```
```output
0
95
96
97
98
99
100
```
-----
```input
4
10000000000 2 2 9999999998
```
```output
0
50
99
100
```
-----
```input
6
170 130 400 256 30 100
```
```output
0
17
43
44
84
90
99
100
```

## Note
В первом тесте копируется всего один файл, поэтому оба прогресс-бара всегда показывают одинаковые значения.

Во втором тесте первый прогресс-бар сразу же уйдёт вперёд, потом сбросится в ноль и начнёт догонять второй прогресс-бар заново. В конце копирования прогресс-бары некоторое время будут показывать одно и то же число.

Обратите внимание, что третий тест в этой версии задачи отличается от третьего теста в предыдущей версии задачи.

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
Hossam woke up bored, so he decided to create an interesting array with his friend Hazem.

Now, they have an array $$$a$$$ of $$$n$$$ positive integers, Hossam will choose a number $$$a_i$$$ and Hazem will choose a number $$$a_j$$$.

Count the number of interesting pairs $$$(a_i, a_j)$$$ that meet all the following conditions:

- $$$1 \le i, j \le n$$$;
- $$$i \neq j$$$;
- The absolute difference $$$|a_i - a_j|$$$ must be equal to the maximum absolute difference over all the pairs in the array. More formally, $$$|a_i - a_j| = \max_{1 \le p, q \le n} |a_p - a_q|$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$), which denotes the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

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

## Output Format
For each test case print an integer — the number of interesting pairs $$$(a_i, a_j)$$$.

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

## Note
In the first example, the two ways are:

- Hossam chooses the fourth number $$$8$$$ and Hazem chooses the fifth number $$$1$$$.
- Hossam chooses the fifth number $$$1$$$ and Hazem chooses the fourth number $$$8$$$.

In the second example, the four ways are:

- Hossam chooses the second number $$$2$$$ and Hazem chooses the sixth number $$$10$$$.
- Hossam chooses the sixth number $$$10$$$ and Hazem chooses the second number $$$2$$$.
- Hossam chooses the fifth number $$$2$$$ and Hazem chooses the sixth number $$$10$$$.
- Hossam chooses the sixth number $$$10$$$ and Hazem chooses the fifth number $$$2$$$.

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
Hossam makes a big party, and he will invite his friends to the party.

He has $$$n$$$ friends numbered from $$$1$$$ to $$$n$$$. They will be arranged in a queue as follows: $$$1, 2, 3, \ldots, n$$$.

Hossam has a list of $$$m$$$ pairs of his friends that don't know each other. Any pair not present in this list are friends.

A subsegment of the queue starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is $$$[a, a + 1, a + 2, \ldots, b]$$$. A subsegment of the queue is called good when all pairs of that segment are friends.

Hossam wants to know how many pairs $$$(a, b)$$$ there are ($$$1 \le a \le b \le n$$$), such that the subsegment starting from the friend $$$a$$$ and ending at the friend $$$b$$$ is good.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$), the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) representing the number of friends and the number of pairs, respectively.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i\le n$$$, $$$x_i \neq y_i$$$) representing a pair of Hossam's friends that don't know each other.

Note that pairs can be repeated.

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

## Output Format
For each test case print an integer — the number of good subsegments.

## Examples
```input
2
3 2
1 3
2 3
4 2
1 2
2 3
```
```output
4
5
```

## Note
In the first example, the answer is $$$4$$$.

The good subsegments are:

[1]

[2]

[3]

[1, 2]

In the second example, the answer is $$$5$$$.

The good subsegments are:

[1]

[2]

[3]

[4]

[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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Hossam has $$$n$$$ trainees. He assigned a number $$$a_i$$$ for the $$$i$$$-th trainee.

A pair of the $$$i$$$-th and $$$j$$$-th ($$$i \neq j$$$) trainees is called successful if there is an integer $$$x$$$ ($$$x \geq 2$$$), such that $$$x$$$ divides $$$a_i$$$, and $$$x$$$ divides $$$a_j$$$.

Hossam wants to know if there is a successful pair of trainees.

Hossam is very tired now, so he asks you for your help!

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. A description of the test cases follows.

The first line of each test case contains an integer number $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers, the number of each trainee $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case.

## Examples
```input
2
3
32 48 7
3
14 5 9
```
```output
YES
NO
```

## Note
In the first example, the first trainee and the second trainee make up a successful pair:

$$$a_1 = 32, a_2 = 48$$$, you can choose $$$x = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Hossam bought a new piece of ground with length $$$n$$$ and width $$$m$$$, he divided it into an $$$n \cdot m$$$ grid, each cell being of size $$$1\times1$$$.

Since Hossam's name starts with the letter 'H', he decided to draw the capital letter 'H' by building walls of size $$$1\times1$$$ on some squares of the ground. Each square $$$1\times1$$$ on the ground is assigned a quality degree: perfect, medium, or bad.

The process of building walls to form up letter 'H' has the following constraints:

- The letter must consist of one horizontal and two vertical lines.
- The vertical lines must not be in the same or neighboring columns.
- The vertical lines must start in the same row and end in the same row (and thus have the same length).
- The horizontal line should connect the vertical lines, but must not cross them.
- The horizontal line can be in any row between the vertical lines (not only in the middle), except the top and the bottom one. (With the horizontal line in the top row the letter looks like 'n', and in the bottom row like 'U'.)
- It is forbidden to build walls in cells of bad quality.
- You can use at most one square of medium quality.
- You can use any number of squares of perfect quality.

Find the maximum number of walls that can be used to draw the letter 'H'.

Check the note for more clarification.

## Input Format
The first line of the input contains two integer numbers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 400$$$).

The next $$$n$$$ lines of the input contain $$$m$$$ characters each, describing the grid. The character '.' stands for a perfect square, the character 'm' stands for a medium square, and the character '#' stands for a bad square.

## Output Format
Print a single integer — the maximum number of walls that form a capital letter 'H'.

If it is not possible to draw any letter 'H', print $$$0$$$.

## Examples
```input
2 3
#m.
.#.
```
```output
0
```
-----
```input
7 8
...#.m..
..m...m.
.#..#.m#
...m..m.
m.......
..#.m.mm
......m.
```
```output
16
```

## Note
In the first test case, we can't build the letter 'H'.

For the second test case, the figure below represents the grid and some of the valid letters 'H'. Perfect, medium, and bad squares are represented with white, yellow, and black colors 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.5 seconds
Memory limit: 256.0 MB

# Problem
Hossam gives you a sequence of integers $$$a_1, \, a_2, \, \dots, \, a_n$$$ of length $$$n$$$. Moreover, he will give you $$$q$$$ queries of type $$$(l, \, r)$$$. For each query, consider the elements $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$. Hossam wants to know the smallest number in this sequence, such that it occurs in this sequence an odd number of times.

You need to compute the answer for each query before process the next query.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, \, b \le 2 \cdot 10^9$$$), the numbers used to encode the queries.

Let $$$\mathrm{ans}_i$$$ be the answer on the $$$i$$$-th query, and $$$\mathrm{ans}_0$$$ be zero. Then $$$$$$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$$$$$ $$$$$$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$$$$$ where $$$l_i, \, r_i$$$ are parameters of the $$$i$$$-th query and $$$\oplus$$$ means the bitwise exclusive or operation. It is guaranteed that $$$1 \le l \le r \le n$$$.

## Output Format
For each query, print the smallest number that occurs an odd number of times on the given segment of the sequence.

If there is no such number, print $$$0$$$.

## Examples
```input
5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7
```
```output
1
2
1
0
2
2
```
-----
```input
10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61
```
```output
51
55
19
48
76
19
23
19
55
19
```

## Note
In the example,

$$$$$$l_1 = 1, \, r_1 = 2,$$$$$$ $$$$$$l_2 = 1, \, r_2 = 3,$$$$$$ $$$$$$l_3 = 2, \, r_3 = 4,$$$$$$ $$$$$$l_4 = 1, \, r_4 = 4,$$$$$$ $$$$$$l_5 = 2, \, r_5 = 2,$$$$$$ $$$$$$l_6 = 1, \, r_6 = 5.$$$$$$

Now solve the problem and return the code.