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
Consider the set of all nonnegative integers: $$${0, 1, 2, \dots}$$$. Given two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^4$$$). We paint all the numbers in increasing number first we paint $$$0$$$, then we paint $$$1$$$, then $$$2$$$ and so on.

Each number is painted white or black. We paint a number $$$i$$$ according to the following rules:

- if $$$i = 0$$$, it is colored white;
- if $$$i \ge a$$$ and $$$i - a$$$ is colored white, $$$i$$$ is also colored white;
- if $$$i \ge b$$$ and $$$i - b$$$ is colored white, $$$i$$$ is also colored white;
- if $$$i$$$ is still not colored white, it is colored black.

In this way, each nonnegative integer gets one of two colors.

For example, if $$$a=3$$$, $$$b=5$$$, then the colors of the numbers (in the order from $$$0$$$) are: white ($$$0$$$), black ($$$1$$$), black ($$$2$$$), white ($$$3$$$), black ($$$4$$$), white ($$$5$$$), white ($$$6$$$), black ($$$7$$$), white ($$$8$$$), white ($$$9$$$), ...

Note that:

- It is possible that there are infinitely many nonnegative integers colored black. For example, if $$$a = 10$$$ and $$$b = 10$$$, then only $$$0, 10, 20, 30$$$ and any other nonnegative integers that end in $$$0$$$ when written in base 10 are white. The other integers are colored black.
- It is also possible that there are only finitely many nonnegative integers colored black. For example, when $$$a = 1$$$ and $$$b = 10$$$, then there is no nonnegative integer colored black at all.

Your task is to determine whether or not the number of nonnegative integers colored black is infinite.

If there are infinitely many nonnegative integers colored black, simply print a line containing "Infinite" (without the quotes). Otherwise, print "Finite" (without the quotes).

## Input Format
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the input. Then $$$t$$$ lines follow, each line contains two space-separated integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^4$$$).

## Output Format
For each test case, print one line containing either "Infinite" or "Finite" (without the quotes). Output is case-insensitive (i.e. "infinite", "inFiNite" or "finiTE" are all valid answers).

## Examples
```input
4
10 10
1 10
6 9
7 3
```
```output
Infinite
Finite
Infinite
Finite
```

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
Constanze is the smartest girl in her village but she has bad eyesight.

One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.

However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.

The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.

The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.

But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.

But since this number can be quite large, tell me instead its remainder when divided by $$$10^9+7$$$.

If there are no strings that Constanze's machine would've turned into the message I got, then print $$$0$$$.

## Input Format
Input consists of a single line containing a string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$) — the received message. $$$s$$$ contains only lowercase Latin letters.

## Output Format
Print a single integer — the number of strings that Constanze's machine would've turned into the message $$$s$$$, modulo $$$10^9+7$$$.

## Examples
```input
ouuokarinn
```
```output
4
```
-----
```input
banana
```
```output
1
```
-----
```input
nnn
```
```output
3
```
-----
```input
amanda
```
```output
0
```

## Note
For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".

For the second example, there is only one: "banana".

For the third example, the candidate strings are the following: "nm", "mn" and "nnn".

For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.

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
While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute $$$1 + 3$$$ using the calculator, he gets $$$2$$$ instead of $$$4$$$. But when he tries computing $$$1 + 4$$$, he gets the correct answer, $$$5$$$. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders!

So, when he tries to compute the sum $$$a + b$$$ using the calculator, he instead gets the xorsum $$$a \oplus b$$$ (read the definition by the link: https://en.wikipedia.org/wiki/Exclusive_or).

As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers $$$l$$$ and $$$r$$$, how many pairs of integers $$$(a, b)$$$ satisfy the following conditions: $$$$$$a + b = a \oplus b$$$$$$ $$$$$$l \leq a \leq r$$$$$$ $$$$$$l \leq b \leq r$$$$$$

However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

Then, $$$t$$$ lines follow, each containing two space-separated integers $$$l$$$ and $$$r$$$ ($$$0 \le l \le r \le 10^9$$$).

## Output Format
Print $$$t$$$ integers, the $$$i$$$-th integer should be the answer to the $$$i$$$-th testcase.

## Examples
```input
3
1 4
323 323
1 1000000
```
```output
8
0
3439863766
```

## Note
$$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$.

For the first testcase, the pairs are: $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 1)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 1)$$$, $$$(4, 2)$$$, and $$$(4, 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: 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 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
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 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
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 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
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 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: 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 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 $$$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.