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

# Problem
Let's call (yet again) a string good if its length is even, and every character in odd position of this string is different from the next character (the first character is different from the second, the third is different from the fourth, and so on). For example, the strings good, string and xyyx are good strings, and the strings bad, aa and aabc are not good. Note that the empty string is considered good.

You are given a string $$$s$$$, you have to delete minimum number of characters from this string so that it becomes good.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of characters in $$$s$$$.

The second line contains the string $$$s$$$, consisting of exactly $$$n$$$ lowercase Latin letters.

## Output Format
In the first line, print one integer $$$k$$$ ($$$0 \le k \le n$$$) — the minimum number of characters you have to delete from $$$s$$$ to make it good.

In the second line, print the resulting string $$$s$$$. If it is empty, you may leave the second line blank, or not print it at all.

## Examples
```input
4
good
```
```output
0
good
```
-----
```input
4
aabc
```
```output
2
ab
```
-----
```input
3
aaa
```
```output
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
We guessed some integer number $$$x$$$. You are given a list of almost all its divisors. Almost all means that there are all divisors except $$$1$$$ and $$$x$$$ in the list.

Your task is to find the minimum possible integer $$$x$$$ that can be the guessed number, or say that the input data is contradictory and it is impossible to find such number.

You have to answer $$$t$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 25$$$) — the number of queries. Then $$$t$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 300$$$) — the number of divisors in the list.

The second line of the query contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$2 \le d_i \le 10^6$$$), where $$$d_i$$$ is the $$$i$$$-th divisor of the guessed number. It is guaranteed that all values $$$d_i$$$ are distinct.

## Output Format
For each query print the answer to it.

If the input data in the query is contradictory and it is impossible to find such number $$$x$$$ that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible $$$x$$$.

## Examples
```input
2
8
8 2 12 6 4 24 16 3
1
2
```
```output
48
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
You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.

Let's define a function $$$f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$$$.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array $$$b$$$ to minimize the value of $$$\sum\limits_{1 \le l \le r \le n} f(l, r)$$$. Since the answer can be very large, you have to print it modulo $$$998244353$$$. Note that you should minimize the answer but not its remainder.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$ and $$$b$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_j \le 10^6$$$), where $$$b_j$$$ is the $$$j$$$-th element of $$$b$$$.

## Output Format
Print one integer — the minimum possible value of $$$\sum\limits_{1 \le l \le r \le n} f(l, r)$$$ after rearranging elements of $$$b$$$, taken modulo $$$998244353$$$. Note that you should minimize the answer but not its remainder.

## Examples
```input
5
1 8 7 2 4
9 7 2 9 3
```
```output
646
```
-----
```input
1
1000000
1000000
```
```output
757402647
```
-----
```input
2
1 3
4 2
```
```output
20
```

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
Toad Ivan has $$$m$$$ pairs of integers, each integer is between $$$1$$$ and $$$n$$$, inclusive. The pairs are $$$(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)$$$.

He asks you to check if there exist two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x < y \leq n$$$) such that in each given pair at least one integer is equal to $$$x$$$ or $$$y$$$.

## Input Format
The first line contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq m \leq 300\,000$$$) — the upper bound on the values of integers in the pairs, and the number of given pairs.

The next $$$m$$$ lines contain two integers each, the $$$i$$$-th of them contains two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) — the integers in the $$$i$$$-th pair.

## Output Format
Output "YES" if there exist two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x < y \leq n$$$) such that in each given pair at least one integer is equal to $$$x$$$ or $$$y$$$. Otherwise, print "NO". You can print each letter in any case (upper or lower).

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

## Note
In the first example, you can't choose any $$$x$$$, $$$y$$$ because for each such pair you can find a given pair where both numbers are different from chosen integers.

In the second example, you can choose $$$x=2$$$ and $$$y=4$$$.

In the third example, you can choose $$$x=1$$$ and $$$y=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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
While playing with geometric figures Alex has accidentally invented a concept of a $$$n$$$-th order rhombus in a cell grid.

A $$$1$$$-st order rhombus is just a square $$$1 \times 1$$$ (i.e just a cell).

A $$$n$$$-th order rhombus for all $$$n \geq 2$$$ one obtains from a $$$n-1$$$-th order rhombus adding all cells which have a common side with it to it (look at the picture to understand it better).

Alex asks you to compute the number of cells in a $$$n$$$-th order rhombus.

## Input Format
The first and only input line contains integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — order of a rhombus whose numbers of cells should be computed.

## Output Format
Print exactly one integer — the number of cells in a $$$n$$$-th order rhombus.

## Examples
```input
1
```
```output
1
```
-----
```input
2
```
```output
5
```
-----
```input
3
```
```output
13
```

## Note
Images of rhombus corresponding to the examples are given in the statement.

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
Nick had received an awesome array of integers $$$a=[a_1, a_2, \dots, a_n]$$$ as a gift for his $$$5$$$ birthday from his mother. He was already going to explore its various properties but after unpacking he was disappointed a lot because the product $$$a_1 \cdot a_2 \cdot \dots a_n$$$ of its elements seemed to him not large enough.

He was ready to throw out the array, but his mother reassured him. She told him, that array would not be spoiled after the following operation: choose any index $$$i$$$ ($$$1 \le i \le n$$$) and do $$$a_i := -a_i - 1$$$.

For example, he can change array $$$[3, -1, -4, 1]$$$ to an array $$$[-4, -1, 3, 1]$$$ after applying this operation to elements with indices $$$i=1$$$ and $$$i=3$$$.

Kolya had immediately understood that sometimes it's possible to increase the product of integers of the array a lot. Now he has decided that he wants to get an array with the maximal possible product of integers using only this operation with its elements (possibly zero, one or more times, as many as he wants), it is not forbidden to do this operation several times for the same index.

Help Kolya and print the array with the maximal possible product of elements $$$a_1 \cdot a_2 \cdot \dots a_n$$$ which can be received using only this operation in some order.

If there are multiple answers, print any of them.

## Input Format
The first line contains integer $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$) — number of integers in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{6} \leq a_i \leq 10^{6}$$$) — elements of the array

## Output Format
Print $$$n$$$ numbers — elements of the array with the maximal possible product of elements which can be received using only this operation in some order from the given array.

If there are multiple answers, print any of them.

## Examples
```input
4
2 2 2 2
```
```output
-3 -3 -3 -3
```
-----
```input
1
0
```
```output
0
```
-----
```input
3
-3 -3 2
```
```output
-3 -3 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Melody Pond was stolen from her parents as a newborn baby by Madame Kovarian, to become a weapon of the Silence in their crusade against the Doctor. Madame Kovarian changed Melody's name to River Song, giving her a new identity that allowed her to kill the Eleventh Doctor.

Heidi figured out that Madame Kovarian uses a very complicated hashing function in order to change the names of the babies she steals. In order to prevent this from happening to future Doctors, Heidi decided to prepare herself by learning some basic hashing techniques.

The first hashing function she designed is as follows.

Given two positive integers $$$(x, y)$$$ she defines $$$H(x,y):=x^2+2xy+x+1$$$.

Now, Heidi wonders if the function is reversible. That is, given a positive integer $$$r$$$, can you find a pair $$$(x, y)$$$ (of positive integers) such that $$$H(x, y) = r$$$?

If multiple such pairs exist, output the one with smallest possible $$$x$$$. If there is no such pair, output "NO".

## Input Format
The first and only line contains an integer $$$r$$$ ($$$1 \le r \le 10^{12}$$$).

## Output Format
Output integers $$$x, y$$$ such that $$$H(x,y) = r$$$ and $$$x$$$ is smallest possible, or "NO" if no such pair exists.

## Examples
```input
19
```
```output
1 8
```
-----
```input
16
```
```output
NO
```

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
After learning about polynomial hashing, Heidi decided to learn about shift-xor hashing. In particular, she came across this interesting problem.

Given a bitstring $$$y \in \{0,1\}^n$$$ find out the number of different $$$k$$$ ($$$0 \leq k < n$$$) such that there exists $$$x \in \{0,1\}^n$$$ for which $$$y = x \oplus \mbox{shift}^k(x).$$$

In the above, $$$\oplus$$$ is the xor operation and $$$\mbox{shift}^k$$$ is the operation of shifting a bitstring cyclically to the right $$$k$$$ times. For example, $$$001 \oplus 111 = 110$$$ and $$$\mbox{shift}^3(00010010111000) = 00000010010111$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the bitstring $$$y$$$.

The second line contains the bitstring $$$y$$$.

## Output Format
Output a single integer: the number of suitable values of $$$k$$$.

## Examples
```input
4
1010
```
```output
3
```

## Note
In the first example:

- $$$1100\oplus \mbox{shift}^1(1100) = 1010$$$
- $$$1000\oplus \mbox{shift}^2(1000) = 1010$$$
- $$$0110\oplus \mbox{shift}^3(0110) = 1010$$$

There is no $$$x$$$ such that $$$x \oplus x = 1010$$$, hence the answer is $$$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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Now Heidi is ready to crack Madame Kovarian's hashing function.

Madame Kovarian has a very strict set of rules for name changes. Two names can be interchanged only if using the following hashing function on them results in a collision. However, the hashing function is parametrized, so one can always find a set of parameters that causes such a collision. Heidi decided to exploit this to her advantage.

Given two strings $$$w_1$$$, $$$w_2$$$ of equal length $$$n$$$ consisting of lowercase English letters and an integer $$$m$$$.

Consider the standard polynomial hashing function:

$$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)$$$

where $$$p$$$ is some prime, and $$$r$$$ is some number such that $$$2\leq r \leq p-2$$$.

The goal is to find $$$r$$$ and a prime $$$p$$$ ($$$m \leq p \leq 10^9$$$) such that $$$H_p(w_1) = H_p(w_2)$$$.

Strings $$$w_1$$$ and $$$w_2$$$ are sampled independently at random from all strings of length $$$n$$$ over lowercase English letters.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$10 \le n \le 10^5$$$, $$$2 \le m \le 10^5$$$).

The second and the third line, respectively, contain the words $$$w_1$$$, $$$w_2$$$ that were sampled independently at random from all strings of length $$$n$$$ over lowercase English letters.

## Output Format
Output integers $$$p, r$$$.

$$$p$$$ should be a prime in the range $$$[m, 10^9]$$$ and $$$r$$$ should be an integer satisfying $$$r\in [2,p-2]$$$.

At least one solution is guaranteed to exist. In case multiple solutions exist, print any of them.

## Examples
```input
10 5
bgcbaaaaaa
cccaaaaaaa
```
```output
5 2
```
-----
```input
10 100
melodypond
riversongg
```
```output
118219 79724
```

## Note
In the first example, note that even though $$$p=3$$$ and $$$r=2$$$ also causes a colision of hashes, it is not a correct solution, since $$$m$$$ is $$$5$$$ and thus we want $$$p\geq 5$$$.

In the second example, we are aware of the extra 'g' at the end. We just didn't realize that "River Song" and "Melody Pond" have different lengths...

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

# Problem
Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $$$s$$$ spaceships, each with a certain attacking power $$$a$$$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $$$b$$$ bases, each with a certain defensive power $$$d$$$, and a certain amount of gold $$$g$$$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.

## Input Format
The first line contains integers $$$s$$$ and $$$b$$$ ($$$1 \leq s, b \leq 10^5$$$), the number of spaceships and the number of bases, respectively.

The second line contains $$$s$$$ integers $$$a$$$ ($$$0 \leq a \leq 10^9$$$), the attacking power of each spaceship.

The next $$$b$$$ lines contain integers $$$d, g$$$ ($$$0 \leq d \leq 10^9$$$, $$$0 \leq g \leq 10^4$$$), the defensive power and the gold of each base, respectively.

## Output Format
Print $$$s$$$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.

## Examples
```input
5 4
1 3 5 2 4
0 1
4 2
2 8
9 4
```
```output
1 9 11 9 11
```

## Note
The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

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
The Cybermen and the Daleks have long been the Doctor's main enemies. Everyone knows that both these species enjoy destroying everything they encounter. However, a little-known fact about them is that they both also love taking Turing tests!

Heidi designed a series of increasingly difficult tasks for them to spend their time on, which would allow the Doctor enough time to save innocent lives!

The funny part is that these tasks would be very easy for a human to solve.

The first task is as follows. There are some points on the plane. All but one of them are on the boundary of an axis-aligned square (its sides are parallel to the axes). Identify that point.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 10$$$).

Each of the following $$$4n + 1$$$ lines contains two integers $$$x_i, y_i$$$ ($$$0 \leq x_i, y_i \leq 50$$$), describing the coordinates of the next point.

It is guaranteed that there are at least $$$n$$$ points on each side of the square and all $$$4n + 1$$$ points are distinct.

## Output Format
Print two integers — the coordinates of the point that is not on the boundary of the square.

## Examples
```input
2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
```
```output
1 1
```
-----
```input
2
0 0
0 1
0 2
0 3
1 0
1 2
2 0
2 1
2 2
```
```output
0 3
```

## Note
In both examples, the square has four sides $$$x=0$$$, $$$x=2$$$, $$$y=0$$$, $$$y=2$$$.

Now solve the problem and return the code.