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: 9.0 seconds
Memory limit: 1024.0 MB

# Problem
To defeat Lord Voldemort, Harry needs to destroy all horcruxes first. The last horcrux is an array $$$a$$$ of $$$n$$$ integers, which also needs to be destroyed. The array is considered destroyed if all its elements are zeroes. To destroy the array, Harry can perform two types of operations:

1. choose an index $$$i$$$ ($$$1 \le i \le n$$$), an integer $$$x$$$, and subtract $$$x$$$ from $$$a_i$$$.
2. choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n; i \ne j$$$), an integer $$$x$$$, and subtract $$$x$$$ from $$$a_i$$$ and $$$x + 1$$$ from $$$a_j$$$.

Note that $$$x$$$ does not have to be positive.

Harry is in a hurry, please help him to find the minimum number of operations required to destroy the array and exterminate Lord Voldemort.

## Input Format
The first line contains a single integer $$$n$$$ — the size of the array $$$a$$$ ($$$1 \le n \le 20$$$).

The following line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — array elements ($$$-10^{15} \le a_i \le 10^{15}$$$).

## Output Format
Output a single integer — the minimum number of operations required to destroy the array $$$a$$$.

## Examples
```input
3
1 10 100
```
```output
3
```
-----
```input
3
5 3 -2
```
```output
2
```
-----
```input
1
0
```
```output
0
```

## Note
In the first example one can just apply the operation of the first kind three times.

In the second example, one can apply the operation of the second kind two times: first, choose $$$i = 2, j = 1, x = 4$$$, it transforms the array into $$$(0, -1, -2)$$$, and then choose $$$i = 3, j = 2, x = -2$$$ to destroy the array.

In the third example, there is nothing to be done, since the array is already destroyed.

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
Tired of boring office work, Denis decided to open a fast food restaurant.

On the first day he made $$$a$$$ portions of dumplings, $$$b$$$ portions of cranberry juice and $$$c$$$ pancakes with condensed milk.

The peculiarity of Denis's restaurant is the procedure of ordering food. For each visitor Denis himself chooses a set of dishes that this visitor will receive. When doing so, Denis is guided by the following rules:

- every visitor should receive at least one dish (dumplings, cranberry juice, pancakes with condensed milk are all considered to be dishes);
- each visitor should receive no more than one portion of dumplings, no more than one portion of cranberry juice and no more than one pancake with condensed milk;
- all visitors should receive different sets of dishes.

What is the maximum number of visitors Denis can feed?

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

Each of the remaining $$$t$$$ lines contains integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$0 \leq a, b, c \leq 10$$$) — the number of portions of dumplings, the number of portions of cranberry juice and the number of condensed milk pancakes Denis made.

## Output Format
For each test case print a single integer — the maximum number of visitors Denis can feed.

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

## Note
In the first test case of the example, Denis can feed the first visitor with dumplings, give the second a portion of cranberry juice, and give the third visitor a portion of cranberry juice and a pancake with a condensed milk.

In the second test case of the example, the restaurant Denis is not very promising: he can serve no customers.

In the third test case of the example, Denise can serve four visitors. The first guest will receive a full lunch of dumplings, a portion of cranberry juice and a pancake with condensed milk. The second visitor will get only dumplings. The third guest will receive a pancake with condensed milk, and the fourth guest will receive a pancake and a portion of dumplings. Please note that Denis hasn't used all of the prepared products, but is unable to serve more visitors.

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
Nikolay has only recently started in competitive programming, but already qualified to the finals of one prestigious olympiad. There going to be $$$n$$$ participants, one of whom is Nikolay. Like any good olympiad, it consists of two rounds. Tired of the traditional rules, in which the participant who solved the largest number of problems wins, the organizers came up with different rules.

Suppose in the first round participant A took $$$x$$$-th place and in the second round — $$$y$$$-th place. Then the total score of the participant A is sum $$$x + y$$$. The overall place of the participant A is the number of participants (including A) having their total score less than or equal to the total score of A. Note, that some participants may end up having a common overall place. It is also important to note, that in both the first and the second round there were no two participants tying at a common place. In other words, for every $$$i$$$ from $$$1$$$ to $$$n$$$ exactly one participant took $$$i$$$-th place in first round and exactly one participant took $$$i$$$-th place in second round.

Right after the end of the Olympiad, Nikolay was informed that he got $$$x$$$-th place in first round and $$$y$$$-th place in the second round. Nikolay doesn't know the results of other participants, yet he wonders what is the minimum and maximum place he can take, if we consider the most favorable and unfavorable outcome for him. Please help Nikolay to find the answer to this question.

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

Each of the following $$$t$$$ lines contains integers $$$n$$$, $$$x$$$, $$$y$$$ ($$$1 \leq n \leq 10^9$$$, $$$1 \le x, y \le n$$$) — the number of participants in the olympiad, the place that Nikolay took in the first round and the place that Nikolay took in the second round.

## Output Format
Print two integers — the minimum and maximum possible overall place Nikolay could take.

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

## Note
Explanation for the first example:

Suppose there were 5 participants A-E. Let's denote Nikolay as A. The the most favorable results for Nikolay could look as follows:

However, the results of the Olympiad could also look like this:

In the first case Nikolay would have taken first place, and in the second — third place.

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
Alicia has an array, $$$a_1, a_2, \ldots, a_n$$$, of non-negative integers. For each $$$1 \leq i \leq n$$$, she has found a non-negative integer $$$x_i = max(0, a_1, \ldots, a_{i-1})$$$. Note that for $$$i=1$$$, $$$x_i = 0$$$.

For example, if Alicia had the array $$$a = \{0, 1, 2, 0, 3\}$$$, then $$$x = \{0, 0, 1, 2, 2\}$$$.

Then, she calculated an array, $$$b_1, b_2, \ldots, b_n$$$: $$$b_i = a_i - x_i$$$.

For example, if Alicia had the array $$$a = \{0, 1, 2, 0, 3\}$$$, $$$b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\}$$$.

Alicia gives you the values $$$b_1, b_2, \ldots, b_n$$$ and asks you to restore the values $$$a_1, a_2, \ldots, a_n$$$. Can you help her solve the problem?

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \leq n \leq 200\,000$$$) – the number of elements in Alicia's array.

The next line contains $$$n$$$ integers, $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

It is guaranteed that for the given array $$$b$$$ there is a solution $$$a_1, a_2, \ldots, a_n$$$, for all elements of which the following is true: $$$0 \leq a_i \leq 10^9$$$.

## Output Format
Print $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$), such that if you calculate $$$x$$$ according to the statement, $$$b_1$$$ will be equal to $$$a_1 - x_1$$$, $$$b_2$$$ will be equal to $$$a_2 - x_2$$$, ..., and $$$b_n$$$ will be equal to $$$a_n - x_n$$$.

It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

## Examples
```input
5
0 1 1 -2 1
```
```output
0 1 2 0 3
```
-----
```input
3
1000 999999000 -1000000000
```
```output
1000 1000000000 0
```
-----
```input
5
2 1 2 2 3
```
```output
2 3 5 7 10
```

## Note
The first test was described in the problem statement.

In the second test, if Alicia had an array $$$a = \{1000, 1000000000, 0\}$$$, then $$$x = \{0, 1000, 1000000000\}$$$ and $$$b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}$$$.

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
This is the easy version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $$$s$$$, consisting of lowercase English letters. Find the longest string, $$$t$$$, which satisfies the following conditions:

- The length of $$$t$$$ does not exceed the length of $$$s$$$.
- $$$t$$$ is a palindrome.
- There exists two strings $$$a$$$ and $$$b$$$ (possibly empty), such that $$$t = a + b$$$ ( "$$$+$$$" represents concatenation), and $$$a$$$ is prefix of $$$s$$$ while $$$b$$$ is suffix of $$$s$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$), the number of test cases. The next $$$t$$$ lines each describe a test case.

Each test case is a non-empty string $$$s$$$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $$$5000$$$.

## Output Format
For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

## Examples
```input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
```
```output
a
abcdfdcba
xyzyx
c
abba
```

## Note
In the first test, the string $$$s = $$$"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

- Its length is $$$9$$$, which does not exceed the length of the string $$$s$$$, which equals $$$11$$$.
- It is a palindrome.
- "abcdfdcba" $$$=$$$ "abcdfdc" $$$+$$$ "ba", and "abcdfdc" is a prefix of $$$s$$$ while "ba" is a suffix of $$$s$$$.

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $$$=$$$ "c" $$$+$$$ "" and $$$a$$$ or $$$b$$$ can be empty. The other possible solution for this test is "s".

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
This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $$$s$$$, consisting of lowercase English letters. Find the longest string, $$$t$$$, which satisfies the following conditions:

- The length of $$$t$$$ does not exceed the length of $$$s$$$.
- $$$t$$$ is a palindrome.
- There exists two strings $$$a$$$ and $$$b$$$ (possibly empty), such that $$$t = a + b$$$ ( "$$$+$$$" represents concatenation), and $$$a$$$ is prefix of $$$s$$$ while $$$b$$$ is suffix of $$$s$$$.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases. The next $$$t$$$ lines each describe a test case.

Each test case is a non-empty string $$$s$$$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

## Examples
```input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
```
```output
a
abcdfdcba
xyzyx
c
abba
```

## Note
In the first test, the string $$$s = $$$"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

- Its length is $$$9$$$, which does not exceed the length of the string $$$s$$$, which equals $$$11$$$.
- It is a palindrome.
- "abcdfdcba" $$$=$$$ "abcdfdc" $$$+$$$ "ba", and "abcdfdc" is a prefix of $$$s$$$ while "ba" is a suffix of $$$s$$$.

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $$$=$$$ "c" $$$+$$$ "" and $$$a$$$ or $$$b$$$ can be empty. The other possible solution for this test is "s".

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: 512.0 MB

# Problem
This is the easy version of the problem. The difference is constraints on the number of wise men and the time limit. You can make hacks only if all versions of this task are solved.

$$$n$$$ wise men live in a beautiful city. Some of them know each other.

For each of the $$$n!$$$ possible permutations $$$p_1, p_2, \ldots, p_n$$$ of the wise men, let's generate a binary string of length $$$n-1$$$: for each $$$1 \leq i < n$$$ set $$$s_i=1$$$ if $$$p_i$$$ and $$$p_{i+1}$$$ know each other, and $$$s_i=0$$$ otherwise.

For all possible $$$2^{n-1}$$$ binary strings, find the number of permutations that produce this binary string.

## Input Format
The first line of input contains one integer $$$n$$$ ($$$2 \leq n \leq 14)$$$  — the number of wise men in the city.

The next $$$n$$$ lines contain a binary string of length $$$n$$$ each, such that the $$$j$$$-th character of the $$$i$$$-th string is equal to '1' if wise man $$$i$$$ knows wise man $$$j$$$, and equals '0' otherwise.

It is guaranteed that if the $$$i$$$-th man knows the $$$j$$$-th man, then the $$$j$$$-th man knows $$$i$$$-th man and no man knows himself.

## Output Format
Print $$$2^{n-1}$$$ space-separated integers. For each $$$0 \leq x < 2^{n-1}$$$:

- Let's consider a string $$$s$$$ of length $$$n-1$$$, such that $$$s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$$$ for all $$$1 \leq i \leq n - 1$$$.
- The $$$(x+1)$$$-th number should be equal to the required answer for $$$s$$$.

## Examples
```input
3
011
101
110
```
```output
0 0 0 6
```
-----
```input
4
0101
1000
0001
1010
```
```output
2 2 6 2 2 6 2 2
```

## Note
In the first test, each wise man knows each other, so every permutation will produce the string $$$11$$$.

In the second test:

- If $$$p = \{1, 2, 3, 4\}$$$, the produced string is $$$101$$$, because wise men $$$1$$$ and $$$2$$$ know each other, $$$2$$$ and $$$3$$$ don't know each other, and $$$3$$$ and $$$4$$$ know each other;
- If $$$p = \{4, 1, 2, 3\}$$$, the produced string is $$$110$$$, because wise men $$$1$$$ and $$$4$$$ know each other, $$$1$$$ and $$$2$$$ know each other and $$$2$$$, and $$$3$$$ don't know each other;
- If $$$p = \{1, 3, 2, 4\}$$$, the produced string is $$$000$$$, because wise men $$$1$$$ and $$$3$$$ don't know each other, $$$3$$$ and $$$2$$$ don't know each other, and $$$2$$$ and $$$4$$$ don't know each other.

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: 512.0 MB

# Problem
This is the hard version of the problem. The difference is constraints on the number of wise men and the time limit. You can make hacks only if all versions of this task are solved.

$$$n$$$ wise men live in a beautiful city. Some of them know each other.

For each of the $$$n!$$$ possible permutations $$$p_1, p_2, \ldots, p_n$$$ of the wise men, let's generate a binary string of length $$$n-1$$$: for each $$$1 \leq i < n$$$ set $$$s_i=1$$$ if $$$p_i$$$ and $$$p_{i+1}$$$ know each other, and $$$s_i=0$$$ otherwise.

For all possible $$$2^{n-1}$$$ binary strings, find the number of permutations that produce this binary string.

## Input Format
The first line of input contains one integer $$$n$$$ ($$$2 \leq n \leq 18)$$$  — the number of wise men in the city.

The next $$$n$$$ lines contain a binary string of length $$$n$$$ each, such that the $$$j$$$-th character of the $$$i$$$-th string is equal to '1' if wise man $$$i$$$ knows wise man $$$j$$$, and equals '0' otherwise.

It is guaranteed that if the $$$i$$$-th man knows the $$$j$$$-th man, then the $$$j$$$-th man knows $$$i$$$-th man and no man knows himself.

## Output Format
Print $$$2^{n-1}$$$ space-separated integers. For each $$$0 \leq x < 2^{n-1}$$$:

- Let's consider a string $$$s$$$ of length $$$n-1$$$, such that $$$s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2$$$ for all $$$1 \leq i \leq n - 1$$$.
- The $$$(x+1)$$$-th number should be equal to the required answer for $$$s$$$.

## Examples
```input
3
011
101
110
```
```output
0 0 0 6
```
-----
```input
4
0101
1000
0001
1010
```
```output
2 2 6 2 2 6 2 2
```

## Note
In the first test, each wise man knows each other, so every permutation will produce the string $$$11$$$.

In the second test:

- If $$$p = \{1, 2, 3, 4\}$$$, the produced string is $$$101$$$, because wise men $$$1$$$ and $$$2$$$ know each other, $$$2$$$ and $$$3$$$ don't know each other, and $$$3$$$ and $$$4$$$ know each other;
- If $$$p = \{4, 1, 2, 3\}$$$, the produced string is $$$110$$$, because wise men $$$1$$$ and $$$4$$$ know each other, $$$1$$$ and $$$2$$$ know each other and $$$2$$$, and $$$3$$$ don't know each other;
- If $$$p = \{1, 3, 2, 4\}$$$, the produced string is $$$000$$$, because wise men $$$1$$$ and $$$3$$$ don't know each other, $$$3$$$ and $$$2$$$ don't know each other, and $$$2$$$ and $$$4$$$ don't know each other.

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
Lee is going to fashionably decorate his house for a party, using some regular convex polygons...

Lee thinks a regular $$$n$$$-sided (convex) polygon is beautiful if and only if he can rotate it in such a way that at least one of its edges is parallel to the $$$OX$$$-axis and at least one of its edges is parallel to the $$$OY$$$-axis at the same time.

Recall that a regular $$$n$$$-sided polygon is a convex polygon with $$$n$$$ vertices such that all the edges and angles are equal.

Now he is shopping: the market has $$$t$$$ regular polygons. For each of them print YES if it is beautiful and NO otherwise.

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

Each of the next $$$t$$$ lines contains a single integer $$$n_i$$$ ($$$3 \le n_i \le 10^9$$$): it means that the $$$i$$$-th polygon is a regular $$$n_i$$$-sided polygon.

## Output Format
For each polygon, print YES if it's beautiful or NO otherwise (case insensitive).

## Examples
```input
4
3
4
12
1000000000
```
```output
NO
YES
YES
YES
```

## Note
In the example, there are $$$4$$$ polygons in the market. It's easy to see that an equilateral triangle (a regular $$$3$$$-sided polygon) is not beautiful, a square (a regular $$$4$$$-sided polygon) is beautiful and a regular $$$12$$$-sided polygon (is shown below) is beautiful as well.

Now solve the problem and return the code.