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
Vlad found two positive numbers $$$a$$$ and $$$b$$$ ($$$a,b>0$$$). He discovered that $$$a \oplus b = \frac{a + b}{2}$$$, where $$$\oplus$$$ means the bitwise exclusive OR , and division is performed without rounding..

Since it is easier to remember one number than two, Vlad remembered only $$$a\oplus b$$$, let's denote this number as $$$x$$$. Help him find any suitable $$$a$$$ and $$$b$$$ or tell him that they do not exist.

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

Each test case is described by a single integer $$$x$$$ ($$$1 \le x \le 2^{29}$$$) — the number that Vlad remembered.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As the answer, output $$$a$$$ and $$$b$$$ ($$$0 < a,b \le 2^{32}$$$), such that $$$x = a \oplus b = \frac{a + b}{2}$$$. If there are several answers, output any of them. If there are no matching pairs, output -1.

## Examples
```input
6
2
5
10
6
18
36
```
```output
3 1
-1
13 7
-1
25 11
50 22
```

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
Marcos loves strings a lot, so he has a favorite string $$$s$$$ consisting of lowercase English letters. For this string, he wrote down all its non-empty prefixes and suffixes (except for $$$s$$$) on a piece of paper in arbitrary order. You see all these strings and wonder if Marcos' favorite string is a palindrome or not. So, your task is to decide whether $$$s$$$ is a palindrome by just looking at the piece of paper.

A string $$$a$$$ is a prefix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the end.

A string $$$a$$$ is a suffix of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning.

A palindrome is a string that reads the same backward as forward, for example, strings "gg", "ioi", "abba", "icpci" are palindromes, but strings "codeforces", "abcd", "alt" are not.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n \le 20$$$) — the length of the string $$$s$$$.

The second line of each test case contains $$$2n-2$$$ strings $$$a_1, a_2, \cdots, a_{2n-2}$$$ — all non-empty prefixes and suffixes of $$$s$$$, not including itself, in arbitrary order.

It is guaranteed that these strings are all the non-empty prefixes and suffixes of some string consisting of lowercase English letters.

## Output Format
For each test case, output "YES" if $$$s$$$ is a palindrome, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
5
4
bcd cd a d abc ab
3
i io i oi
2
g g
3
t al lt a
4
bba a ab a abb ba
```
```output
NO
YES
YES
NO
YES
```

## Note
In the first test case, $$$s$$$ is "abcd". Its prefixes are "a", "ab" and "abc", and its suffixes are "d", "cd" and "bcd". As the string "abcd" is not a palindrome, the answer is NO.

In the second test case, $$$s$$$ is "ioi". Its prefixes are "i" and "io", and its suffixes are "i" and "oi". As the string "ioi" is a palindrome, the answer is YES.

In the third test case, $$$s$$$ is "gg" which is a palindrome.

In the fourth test case, $$$s$$$ is "alt" which is not a palindrome.

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 an array of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you can choose any number of the array and add $$$1$$$ to it.

Make at most $$$2n$$$ operations so that the array satisfies the following property: $$$a_{i+1}$$$ is not divisible by $$$a_i$$$, for each $$$i = 1, 2, \ldots, n-1$$$.

You do not need to minimize the number of operations.

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

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the length of the given array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq 10^9$$$) — the given array.

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

## Output Format
For each test case, print the answer on a separate line.

In the only line, print $$$n$$$ integers — the resulting array $$$a$$$ after applying at most $$$2n$$$ operations.

We can show that an answer always exists under the given constraints. If there are multiple answers, print any of them.

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

## Note
In the first test case, the array $$$[4, 5, 6, 7]$$$ can be achieved by applying $$$2$$$ operations to the first element, $$$1$$$ operation to the second element, $$$3$$$ operations to the third element, and $$$1$$$ operation to the last element. The total number of operations performed is $$$7$$$, which is less than the allowed $$$8$$$ operations in this case.

In the second test case, the array $$$[3, 2, 3]$$$ can be achieved by applying two operations to the first element. Another possible resulting array could be $$$[2, 3, 5]$$$, because the total number of operations does not need to be minimum.

In the third test case, not applying any operations results in an array that satisfies the statement's property. Observe that it is not mandatory to make operations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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.5 seconds
Memory limit: 256.0 MB

# Problem
The score of a sequence $$$[s_1, s_2, \ldots, s_d]$$$ is defined as $$$\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$$$, where $$$d!=1\cdot 2\cdot \ldots \cdot d$$$. In particular, the score of an empty sequence is $$$1$$$.

For a sequence $$$[s_1, s_2, \ldots, s_d]$$$, let $$$m$$$ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $$$m$$$.

You are given a non-decreasing sequence $$$[a_1, a_2, \ldots, a_n]$$$ of integers of length $$$n$$$. In other words, the condition $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$ is satisfied. For each $$$k=1, 2, \ldots , n$$$, find the cost of the sequence $$$[a_1, a_2, \ldots , a_k]$$$.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements.

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

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the length of the given sequence.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\leq n$$$) — the given sequence. It is guaranteed that its elements are in non-decreasing order.

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

## Output Format
For each test case, output $$$n$$$ integers — the costs of sequences $$$[a_1, a_2, \ldots , a_k]$$$ in ascending order of $$$k$$$.

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

## Note
In the first test case:

- The maximum score among the subsequences of $$$[1]$$$ is $$$1$$$. The subsequences $$$[1]$$$ and $$$[]$$$ (the empty sequence) are the only ones with this score. Thus, the cost of $$$[1]$$$ is $$$1$$$.
- The maximum score among the subsequences of $$$[1, 2]$$$ is $$$2$$$. The only subsequence with this score is $$$[2]$$$. Thus, the cost of $$$[1, 2]$$$ is $$$1$$$.
- The maximum score among the subsequences of $$$[1, 2, 3]$$$ is $$$3$$$. The subsequences $$$[2, 3]$$$ and $$$[3]$$$ are the only ones with this score. Thus, the cost of $$$[1, 2, 3]$$$ is $$$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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
The prime factorization of a positive integer $$$m$$$ is the unique way to write it as $$$\displaystyle m=p_1^{e_1}\cdot p_2^{e_2}\cdot \ldots \cdot p_k^{e_k}$$$, where $$$p_1, p_2, \ldots, p_k$$$ are prime numbers, $$$p_1 < p_2 < \ldots < p_k$$$ and $$$e_1, e_2, \ldots, e_k$$$ are positive integers.

For each positive integer $$$m$$$, $$$f(m)$$$ is defined as the multiset of all numbers in its prime factorization, that is $$$f(m)=\{p_1,e_1,p_2,e_2,\ldots,p_k,e_k\}$$$.

For example, $$$f(24)=\{2,3,3,1\}$$$, $$$f(5)=\{1,5\}$$$ and $$$f(1)=\{\}$$$.

You are given a list consisting of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$. Count how many positive integers $$$m$$$ satisfy that $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$. Since this value may be large, print it modulo $$$998\,244\,353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1\le n \le 2022$$$).

The second line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1\le a_i\le 10^6$$$)  — the given list.

## Output Format
Print one integer, the number of positive integers $$$m$$$ satisfying $$$f(m)=\{a_1, a_2, \ldots, a_{2n}\}$$$ modulo $$$998\,244\,353$$$.

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

## Note
In the first sample, the two values of $$$m$$$ such that $$$f(m)=\{1,2,3,3\}$$$ are $$$m=24$$$ and $$$m=54$$$. Their prime factorizations are $$$24=2^3\cdot 3^1$$$ and $$$54=2^1\cdot 3^3$$$.

In the second sample, the five values of $$$m$$$ such that $$$f(m)=\{2,2,3,5\}$$$ are $$$200, 225, 288, 500$$$ and $$$972$$$.

In the third sample, there is no value of $$$m$$$ such that $$$f(m)=\{1,4\}$$$. Neither $$$1^4$$$ nor $$$4^1$$$ are prime factorizations because $$$1$$$ and $$$4$$$ are not primes.

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
You are given an unweighted tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and a list of $$$n-1$$$ integers $$$a_1, a_2, \ldots, a_{n-1}$$$. A tree is a connected undirected graph without cycles. You will use each element of the list to label one vertex. No vertex should be labeled twice. You can label the only remaining unlabeled vertex with any integer.

A vertex $$$x$$$ is called good if it is possible to do this labeling so that for each vertex $$$i$$$, its label is the distance between $$$x$$$ and $$$i$$$. The distance between two vertices $$$s$$$ and $$$t$$$ on a tree is the minimum number of edges on a path that starts at vertex $$$s$$$ and ends at vertex $$$t$$$.

Find all good vertices.

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

The second line contains $$$n - 1$$$ integers $$$a_1,a_2,\ldots,a_{n-1}$$$ ($$$0\le a_i < n$$$) — the given list.

Then, $$$n−1$$$ lines follow. Each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$) denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.

## Output Format
In the first line print the number of good vertices.

In the second line, print the indices of all good vertices in ascending order.

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

## Note
This is the tree for the first example:

And these are two possible labelings with the elements on the list so that $$$2$$$ is a good vertex (left) and $$$4$$$ is a good vertex (right).

The square below each vertex represents its label. The black squares contain the numbers which were on the given list and the only white square contains the only number which was not on the given list.

In the second example, the only good vertex is vertex $$$3$$$.

In the third example, there are no good vertices.

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
The Berland capital is shaken with three bold crimes committed by the Pihsters, a notorious criminal gang.

The Berland capital's map is represented by an n × m rectangular table. Each cell of the table on the map represents some districts of the capital.

The capital's main detective Polycarpus took a map and marked there the districts where the first three robberies had been committed as asterisks. Deduction tells Polycarpus that the fourth robbery will be committed in such district, that all four robbed districts will form the vertices of some rectangle, parallel to the sides of the map.

Polycarpus is good at deduction but he's hopeless at math. So he asked you to find the district where the fourth robbery will be committed.

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n, m ≤ 100) — the number of rows and columns in the table, correspondingly.

Each of the next n lines contains m characters — the description of the capital's map. Each character can either be a "." (dot), or an "*" (asterisk). A character equals "*" if the corresponding district has been robbed. Otherwise, it equals ".".

It is guaranteed that the map has exactly three characters "*" and we can always find the fourth district that meets the problem requirements.

## Output Format
Print two integers — the number of the row and the number of the column of the city district that is the fourth one to be robbed. The rows are numbered starting from one from top to bottom and the columns are numbered starting from one from left to right.

## Examples
```input
3 2
.*
..
**
```
```output
1 1
```
-----
```input
3 3
*.*
*..
...
```
```output
2 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You're given a multiset of non-negative integers $$$\{a_1, a_2, \dots, a_n\}$$$.

In one step you take two elements $$$x$$$ and $$$y$$$ of the multiset, remove them and insert their mean value $$$\frac{x + y}{2}$$$ back into the multiset.

You repeat the step described above until you are left with only two numbers $$$A$$$ and $$$B$$$. What is the maximum possible value of their absolute difference $$$|A-B|$$$?

Since the answer is not an integer number, output it modulo $$$10^9+7$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the size of the multiset.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the multiset.

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

## Output Format
For each test case, output a single integer, the answer to the problem modulo $$$10^9+7$$$.

Formally, let $$$M = 10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1
```
```output
4
9
500000005
59
0
```

## Note
In the first case, you can't do any operations, so the answer is $$$|7-3|=4$$$.

In the second case, one of the optimal sequence of operations:

1. Substitute $$$1$$$ and $$$2$$$ with $$$1.5$$$;
2. Substitute $$$10$$$ and $$$11$$$ with $$$10.5$$$;
3. The difference between $$$1.5$$$ and $$$10.5$$$ is $$$9$$$.

In the third case, the exact answer is $$$\frac{3}{2}$$$, and $$$500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$$$.

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 a string $$$s$$$. A pair of its non-empty substrings $$$(a, b)$$$ is called entangled if there is a (possibly empty) link string $$$c$$$ such that:

- Every occurrence of $$$a$$$ in $$$s$$$ is immediately followed by $$$cb$$$;
- Every occurrence of $$$b$$$ in $$$s$$$ is immediately preceded by $$$ac$$$.

In other words, $$$a$$$ and $$$b$$$ occur in $$$s$$$ only as substrings of $$$acb$$$. Compute the total number of entangled pairs of substrings of $$$s$$$.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

## Input Format
The first and only line contains a string $$$s$$$ of lowercase English letters ($$$1 \leq |s| \leq 10^5$$$) — the string for which you should count pairs of entangled substrings.

## Output Format
Output a single integer, the number of entangled pairs of substrings of $$$s$$$.

## Examples
```input
abba
```
```output
1
```
-----
```input
abacaba
```
```output
0
```
-----
```input
abcabcabcabc
```
```output
5
```
-----
```input
adamant
```
```output
82
```

## Note
In the first example, the only entangled pair is (ab,ba). For this pair, the corresponding link string $$$c$$$ is empty, as they only occur as substrings of the whole string abba, which doesn't have any characters between ab and ba.

In the second example, there are no entangled pairs.

In the third example, the entangled pairs are (a,b), (b,c), (a,c), (a,bc), and (ab,c). For most pairs, the corresponding link string $$$c$$$ is empty, except for the pair (a,c), for which the link string $$$c$$$ is b, as a and c only occur as substrings of the string abc.

Now solve the problem and return the code.