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
Bob is playing with $$$6$$$-sided dice. A net of such standard cube is shown below.

He has an unlimited supply of these dice and wants to build a tower by stacking multiple dice on top of each other, while choosing the orientation of each dice. Then he counts the number of visible pips on the faces of the dice.

For example, the number of visible pips on the tower below is $$$29$$$ — the number visible on the top is $$$1$$$, from the south $$$5$$$ and $$$3$$$, from the west $$$4$$$ and $$$2$$$, from the north $$$2$$$ and $$$4$$$ and from the east $$$3$$$ and $$$5$$$.

The one at the bottom and the two sixes by which the dice are touching are not visible, so they are not counted towards total.

Bob also has $$$t$$$ favourite integers $$$x_i$$$, and for every such integer his goal is to build such a tower that the number of visible pips is exactly $$$x_i$$$. For each of Bob's favourite integers determine whether it is possible to build a tower that has exactly that many visible pips.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of favourite integers of Bob.

The second line contains $$$t$$$ space-separated integers $$$x_i$$$ ($$$1 \leq x_i \leq 10^{18}$$$) — Bob's favourite integers.

## Output Format
For each of Bob's favourite integers, output "YES" if it is possible to build the tower, or "NO" otherwise (quotes for clarity).

## Examples
```input
4
29 34 19 38
```
```output
YES
YES
YES
NO
```

## Note
The first example is mentioned in the problem statement.

In the second example, one can build the tower by flipping the top dice from the previous tower.

In the third example, one can use a single die that has $$$5$$$ on top.

The fourth example is impossible.

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
Let $$$G$$$ be a simple graph. Let $$$W$$$ be a non-empty subset of vertices. Then $$$W$$$ is almost-$$$k$$$-uniform if for each pair of distinct vertices $$$u,v \in W$$$ the distance between $$$u$$$ and $$$v$$$ is either $$$k$$$ or $$$k+1$$$.

You are given a tree on $$$n$$$ vertices. For each $$$i$$$ between $$$1$$$ and $$$n$$$, find the maximum size of an almost-$$$i$$$-uniform set.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) – the number of vertices of the tree.

Then $$$n-1$$$ lines follows, the $$$i$$$-th of which consisting of two space separated integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) meaning that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the given graph is tree.

## Output Format
Output a single line containing $$$n$$$ space separated integers $$$a_i$$$, where $$$a_i$$$ is the maximum size of an almost-$$$i$$$-uniform set.

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

## Note
Consider the first example.

- The only maximum almost-$$$1$$$-uniform set is $$$\{1, 2, 3, 4\}$$$.
- One of the maximum almost-$$$2$$$-uniform sets is or $$$\{2, 3, 5\}$$$, another one is $$$\{2, 3, 4\}$$$.
- A maximum almost-$$$3$$$-uniform set is any pair of vertices on distance $$$3$$$.
- Any single vertex is an almost-$$$k$$$-uniform set for $$$k \geq 1$$$.

In the second sample there is an almost-$$$2$$$-uniform set of size $$$4$$$, and that is $$$\{2, 3, 5, 6\}$$$.

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
Let $$$n$$$ be an integer. Consider all permutations on integers $$$1$$$ to $$$n$$$ in lexicographic order, and concatenate them into one big sequence $$$P$$$. For example, if $$$n = 3$$$, then $$$P = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]$$$. The length of this sequence is $$$n \cdot n!$$$.

Let $$$1 \leq i \leq j \leq n \cdot n!$$$ be a pair of indices. We call the sequence $$$(P_i, P_{i+1}, \dots, P_{j-1}, P_j)$$$ a subarray of $$$P$$$.

You are given $$$n$$$. Find the number of distinct subarrays of $$$P$$$. Since this number may be large, output it modulo $$$998244353$$$ (a prime number).

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$), as described in the problem statement.

## Output Format
Output a single integer — the number of distinct subarrays, modulo $$$998244353$$$.

## Examples
```input
2
```
```output
8
```
-----
```input
10
```
```output
19210869
```

## Note
In the first example, the sequence $$$P = [1, 2, 2, 1]$$$. It has eight distinct subarrays: $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$, $$$[1, 2, 2]$$$, $$$[2, 2, 1]$$$ and $$$[1, 2, 2, 1]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tournament — complete directed graph.

In one operation you can pick any vertex $$$v$$$ and change the direction of all edges with $$$v$$$ on one of the ends (i.e all edges $$$u \to v$$$ change their orientation to $$$v \to u$$$ and vice versa).

You want to make the tournament strongly connected with the smallest possible number of such operations if it is possible.

Also, if it is possible, you need to find the number of ways to make this number of operations to make graph strongly connected (two ways are different if for some $$$i$$$ vertex that we chose on $$$i$$$-th operation in one way is different from vertex that we chose on $$$i$$$-th operation in another way). You only need to find this value modulo $$$998\,244\,353$$$.

## Input Format
The first line of input contains one integer $$$n$$$ ($$$3 \leq n \leq 2000$$$): the number of vertices in the tournament.

Following $$$n$$$ lines contain a description of the given tournament, each of them contains a binary string of length $$$n$$$. If $$$j$$$-th character of $$$i$$$-th string is equal to '1', then the graph has an edge $$$i \to j$$$.

It is guaranteed that there are no edges $$$i \to i$$$ and the graph has exactly one edge among $$$i \to j$$$ and $$$j \to i$$$ for different $$$i$$$ and $$$j$$$.

## Output Format
If it is not possible to convert tournament to strongly connected with the given operations, output "-1".

Otherwise, output two integers: the smallest number of operations that you need to make the given graph strongly connected and the number of ways to do this number of operations to make graph strongly connected, modulo $$$998\,244\,353$$$.

## Examples
```input
3
010
001
100
```
```output
0 1
```
-----
```input
4
0010
1000
0100
1110
```
```output
-1
```
-----
```input
6
010000
001000
100000
111001
111100
111010
```
```output
2 18
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
For an array $$$a$$$ of integers let's denote its maximal element as $$$\max(a)$$$, and minimal as $$$\min(a)$$$. We will call an array $$$a$$$ of $$$k$$$ integers interesting if $$$\max(a) - \min(a) \ge k$$$. For example, array $$$[1, 3, 4, 3]$$$ isn't interesting as $$$\max(a) - \min(a) = 4 - 1 = 3 < 4$$$ while array $$$[7, 3, 0, 4, 3]$$$ is as $$$\max(a) - \min(a) = 7 - 0 = 7 \ge 5$$$.

You are given an array $$$a$$$ of $$$n$$$ integers. Find some interesting nonempty subarray of $$$a$$$, or tell that it doesn't exist.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

## Input Format
The first line contains integer number $$$t$$$ ($$$1 \le t \le 10\,000$$$). Then $$$t$$$ test cases follow.

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 10^9$$$) — the elements of the array.

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, output "NO" in a separate line if there is no interesting nonempty subarray in $$$a$$$.

Otherwise, output "YES" in a separate line. In the next line, output two integers $$$l$$$ and $$$r$$$ ($$$1\le l \le r \le n$$$) — bounds of the chosen subarray. If there are multiple answers, print any.

You can print each letter in any case (upper or lower).

## Examples
```input
3
5
1 2 3 4 5
4
2 0 1 9
2
2019 2020
```
```output
NO
YES
1 4
NO
```

## Note
In the second test case of the example, one of the interesting subarrays is $$$a = [2, 0, 1, 9]$$$: $$$\max(a) - \min(a) = 9 - 0 = 9 \ge 4$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call an array $$$a_1, a_2, \dots, a_m$$$ of nonnegative integer numbers good if $$$a_1 + a_2 + \dots + a_m = 2\cdot(a_1 \oplus a_2 \oplus \dots \oplus a_m)$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

For example, array $$$[1, 2, 3, 6]$$$ is good, as $$$1 + 2 + 3 + 6 = 12 = 2\cdot 6 = 2\cdot (1\oplus 2 \oplus 3 \oplus 6)$$$. At the same time, array $$$[1, 2, 1, 3]$$$ isn't good, as $$$1 + 2 + 1 + 3 = 7 \neq 2\cdot 1 = 2\cdot(1\oplus 2 \oplus 1 \oplus 3)$$$.

You are given an array of length $$$n$$$: $$$a_1, a_2, \dots, a_n$$$. Append at most $$$3$$$ elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements!. So, if an array is good already you are allowed to not append elements.

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

The first line of each test case contains a single integer $$$n$$$ $$$(1\le n \le 10^5)$$$ — the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0\le a_i \le 10^9$$$) — the elements of the array.

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

## Output Format
For each test case, output two lines.

In the first line, output a single integer $$$s$$$ ($$$0\le s\le 3$$$) — the number of elements you want to append.

In the second line, output $$$s$$$ integers $$$b_1, \dots, b_s$$$ ($$$0\le b_i \le 10^{18}$$$) — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

## Examples
```input
3
4
1 2 3 6
1
8
2
1 1
```
```output
0

2
4 4
3
2 6 2
```

## Note
In the first test case of the example, the sum of all numbers is $$$12$$$, and their $$$\oplus$$$ is $$$6$$$, so the condition is already satisfied.

In the second test case of the example, after adding $$$4, 4$$$, the array becomes $$$[8, 4, 4]$$$. The sum of numbers in it is $$$16$$$, $$$\oplus$$$ of numbers in it is $$$8$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a set of $$$n\ge 2$$$ pairwise different points with integer coordinates. Your task is to partition these points into two nonempty groups $$$A$$$ and $$$B$$$, such that the following condition holds:

For every two points $$$P$$$ and $$$Q$$$, write the Euclidean distance between them on the blackboard: if they belong to the same group — with a yellow pen, and if they belong to different groups — with a blue pen. Then no yellow number is equal to any blue number.

It is guaranteed that such a partition exists for any possible input. If there exist multiple partitions, you are allowed to output any of them.

## Input Format
The first line contains one integer $$$n$$$ $$$(2 \le n \le 10^3)$$$ — the number of points.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — the coordinates of the $$$i$$$-th point.

It is guaranteed that all $$$n$$$ points are pairwise different.

## Output Format
In the first line, output $$$a$$$ ($$$1 \le a \le n-1$$$) — the number of points in a group $$$A$$$.

In the second line, output $$$a$$$ integers — the indexes of points that you include into group $$$A$$$.

If there are multiple answers, print any.

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

## Note
In the first example, we set point $$$(0, 0)$$$ to group $$$A$$$ and points $$$(0, 1)$$$ and $$$(1, 0)$$$ to group $$$B$$$. In this way, we will have $$$1$$$ yellow number $$$\sqrt{2}$$$ and $$$2$$$ blue numbers $$$1$$$ on the blackboard.

In the second example, we set points $$$(0, 1)$$$ and $$$(0, -1)$$$ to group $$$A$$$ and points $$$(-1, 0)$$$ and $$$(1, 0)$$$ to group $$$B$$$. In this way, we will have $$$2$$$ yellow numbers $$$2$$$, $$$4$$$ blue numbers $$$\sqrt{2}$$$ on the blackboard.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 8.0 seconds
Memory limit: 512.0 MB

# Problem
Let's call a binary string $$$s$$$ awesome, if it has at least $$$1$$$ symbol 1 and length of the string is divisible by the number of 1 in it. In particular, 1, 1010, 111 are awesome, but 0, 110, 01010 aren't.

You are given a binary string $$$s$$$. Count the number of its awesome substrings.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by 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 line contains the string $$$s$$$ ($$$1 \leq |s|\le 200\,000$$$) consisting only of zeros and ones.

## Output Format
Output a single number — the number of awesome substrings of $$$s$$$.

## Examples
```input
111
```
```output
6
```
-----
```input
01010
```
```output
10
```
-----
```input
0000
```
```output
0
```
-----
```input
1111100000
```
```output
25
```

## Note
In the first sample, all substrings of $$$s$$$ are awesome.

In the second sample, we have the following awesome substrings of $$$s$$$: 1 ($$$2$$$ times), 01 ($$$2$$$ times), 10 ($$$2$$$ times), 010 ($$$2$$$ times), 1010, 0101

In the third sample, no substring is awesome.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, such that for each $$$1\le i \le n$$$ holds $$$i-n\le a_i\le i-1$$$.

Find some nonempty subset of these integers, whose sum is equal to $$$0$$$. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \le 10^6$$$).

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

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

## Output Format
For each test case, output two lines.

In the first line, output $$$s$$$ ($$$1\le s \le n$$$) — the number of elements in your subset.

In the second line, output $$$s$$$ integers $$$i_1, i_2, \dots, i_s$$$ ($$$1\le i_k \le n$$$). All integers have to be pairwise different, and $$$a_{i_1} + a_{i_2} + \dots + a_{i_s}$$$ has to be equal to $$$0$$$. If there are several possible subsets with zero-sum, you can find any of them.

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

## Note
In the first example, we get sum is $$$a_1 = 0$$$.

In the second example, we get sum is $$$a_1 + a_4 + a_3 + a_2 = 0$$$.

Now solve the problem and return the code.