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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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.
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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Today Hayato came home from school with homework.

In the assignment, Hayato was given an array $$$a$$$ of length $$$n$$$. The task was to find $$$3$$$ numbers in this array whose sum is odd. At school, he claimed that there are such $$$3$$$ numbers, but Hayato was not sure, so he asked you for help.

Answer if there are such three numbers, and if so, output indices $$$i$$$, $$$j$$$, and $$$k$$$ such that $$$a_i + a_j + a_k$$$ is odd.

The odd numbers are integers that are not divisible by $$$2$$$: $$$1$$$, $$$3$$$, $$$5$$$, and so on.

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

For each test case, the first line contains one integer $$$n$$$ ($$$3 \le n \le 300$$$) — the length of $$$a$$$.

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

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

## Output Format
For each test case, in the first line print one word "YES" (without quotes) if there are $$$3$$$ numbers with an odd sum or "NO" (without quotes) if there are no such $$$3$$$ numbers.

If the answer exists, then on the second line print $$$3$$$ distinct integers $$$i, j, k$$$ ($$$1 \le i, j, k \le n$$$) — the indices of the numbers. If there are several answers, output any.

## Examples
```input
6
3
1 1 1
4
1 1 2 2
3
1 2 3
5
1 4 5 1 2
4
2 6 2 4
5
5 6 3 2 1
```
```output
YES
1 2 3
YES
3 4 1
NO
YES
1 3 4
NO
YES
1 3 5
```

## Note
In the first test case, there is one way to choose $$$3$$$ numbers, and since $$$1 + 1 + 1 = 3$$$, this triple is fine for us.

In the second test case, you need to choose the numbers $$$1, 2, 2$$$, since $$$1 + 2 + 2 = 5$$$.

In the third test case, there is one way to choose three numbers, but $$$1 + 2 + 3 = 6$$$ is an even number, so the required triple does not exist.

In the fifth test case, no matter what three numbers we choose, their sum is 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
While at Kira's house, Josuke saw a piece of paper on the table with a task written on it.

The task sounded as follows. There is an array $$$a$$$ of length $$$n$$$. On this array, do the following:

- select an integer $$$k > 1$$$;
- split the array into $$$k$$$ subsegments $$$^\dagger$$$;
- calculate the sum in each of $$$k$$$ subsegments and write these sums to another array $$$b$$$ (where the sum of the subsegment $$$(l, r)$$$ is $$${\sum_{j = l}^{r}a_j}$$$);
- the final score of such a split will be $$$\gcd(b_1, b_2, \ldots, b_k)^\ddagger$$$.

The task is to find such a partition that the score is maximum possible. Josuke is interested in this task but is not strong in computer science. Help him to find the maximum possible score.

$$$^\dagger$$$ A division of an array into $$$k$$$ subsegments is $$$k$$$ pairs of numbers $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ such that $$$l_i \le r_i$$$ and for every $$$1 \le j \le k - 1$$$ $$$l_{j + 1} = r_j + 1$$$, also $$$l_1 = 1$$$ and $$$r_k = n$$$. These pairs represent the subsegments.

$$$^\ddagger$$$ $$$\gcd(b_1, b_2, \ldots, b_k)$$$ stands for the greatest common divisor (GCD) of the array $$$b$$$.

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

For each test case, the first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9 $$$) — the array $$$a$$$ itself.

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 print a single integer — the maximum score for the optimal partition.

## Examples
```input
6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7
```
```output
4
1
5
3
1
21
```

## Note
In the first test case, you can choose $$$k = 2$$$ and split the array into subsegments $$$(1, 2)$$$ and $$$(3, 4)$$$.

Then the score of such a partition will be equal to $$$\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$$$.

In the fourth test case, you can choose $$$k = 3$$$ and split the array into subsegments $$$(1, 2), (3, 5), (6, 6)$$$.

The split score is $$$\gcd(1 + 2, 1 + 1 + 1, 3) = 3$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Josuke received a huge undirected weighted complete$$$^\dagger$$$ graph $$$G$$$ as a gift from his grandfather. The graph contains $$$10^{18}$$$ vertices. The peculiarity of the gift is that the weight of the edge between the different vertices $$$u$$$ and $$$v$$$ is equal to $$$\gcd(u, v)^\ddagger$$$. Josuke decided to experiment and make a new graph $$$G'$$$. To do this, he chooses two integers $$$l \le r$$$ and deletes all vertices except such vertices $$$v$$$ that $$$l \le v \le r$$$, and also deletes all the edges except between the remaining vertices.

Now Josuke is wondering how many different weights are there in $$$G'$$$. Since their count turned out to be huge, he asks for your help.

$$$^\dagger$$$ A complete graph is a simple undirected graph in which every pair of distinct vertices is adjacent.

$$$^\ddagger$$$ $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of the numbers $$$x$$$ and $$$y$$$.

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

The first line of each test case contains two numbers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$).

## Output Format
For each test case print a single number — the number of different weights among the remaining edges.

## Examples
```input
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090
```
```output
2
6
3
5
0
5
50045
```

## Note
The graph $$$G'$$$ for the first test case.

The picture above shows that the graph has $$$2$$$ different weights.

In the fifth test case, there is only one vertex from which no edges originate, so the answer is $$$0$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Today is an important day for chef Tonio — an auditor has arrived in his hometown of Morioh. He has also arrived at Tonio's restaurant and ordered dessert. Tonio has not been prepared for this turn of events.

As you know, dessert is a string of lowercase English letters. Tonio remembered the rule of desserts — a string $$$s$$$ of length $$$n$$$. Any dessert $$$t$$$ is delicious if the number of occurrences of $$$t$$$ in $$$s$$$ as a substring is divisible by the length of $$$t$$$.

Now Tonio wants to know the number of delicious substrings of $$$s$$$. If the substring occurs several times in the string $$$s$$$, then all occurrences must be taken into account.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the rule $$$s$$$.

The second line contains the string $$$s$$$ of length $$$n$$$ — the rule. The rule consists only of lowercase English letters.

## Output Format
In a single line print the number of delicious substrings of $$$s$$$.

## Examples
```input
7
abacaba
```
```output
11
```
-----
```input
8
abaababa
```
```output
11
```
-----
```input
10
deadinside
```
```output
12
```
-----
```input
5
aaaaa
```
```output
12
```

## Note
In the first sample, there are many delicious substrings. $$$7$$$ of them are substrings of length $$$1$$$ (because any number is divisible by $$$1$$$). Consider other delicious substrings:

- "ab" occurs in $$$s$$$ $$$2$$$ times, which is divisible by the length of the substring.
- "ba" also occurs $$$2$$$ times.

Therefore, the answer is $$$7 + 2 + 2 = 11$$$.

Note that the answer includes both occurrences of "ab" and "ba".

Now solve the problem and return the code.