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

# Problem
Omkar is creating a mosaic using colored square tiles, which he places in an $$$n \times n$$$ grid. When the mosaic is complete, each cell in the grid will have either a glaucous or sinoper tile. However, currently he has only placed tiles in some cells.

A completed mosaic will be a mastapeece if and only if each tile is adjacent to exactly $$$2$$$ tiles of the same color ($$$2$$$ tiles are adjacent if they share a side.) Omkar wants to fill the rest of the tiles so that the mosaic becomes a mastapeece. Now he is wondering, is the way to do this unique, and if it is, what is it?

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2000$$$).

Then follow $$$n$$$ lines with $$$n$$$ characters in each line. The $$$i$$$-th character in the $$$j$$$-th line corresponds to the cell in row $$$i$$$ and column $$$j$$$ of the grid, and will be $$$S$$$ if Omkar has placed a sinoper tile in this cell, $$$G$$$ if Omkar has placed a glaucous tile, $$$.$$$ if it's empty.

## Output Format
On the first line, print UNIQUE if there is a unique way to get a mastapeece, NONE if Omkar cannot create any, and MULTIPLE if there is more than one way to do so. All letters must be uppercase.

If you print UNIQUE, then print $$$n$$$ additional lines with $$$n$$$ characters in each line, such that the $$$i$$$-th character in the $$$j^{\text{th}}$$$ line is $$$S$$$ if the tile in row $$$i$$$ and column $$$j$$$ of the mastapeece is sinoper, and $$$G$$$ if it is glaucous.

## Examples
```input
4
S...
..G.
....
...S
```
```output
MULTIPLE
```
-----
```input
6
S.....
....G.
..S...
.....S
....G.
G.....
```
```output
NONE
```
-----
```input
10
.S....S...
..........
...SSS....
..........
..........
...GS.....
....G...G.
..........
......G...
..........
```
```output
UNIQUE
SSSSSSSSSS
SGGGGGGGGS
SGSSSSSSGS
SGSGGGGSGS
SGSGSSGSGS
SGSGSSGSGS
SGSGGGGSGS
SGSSSSSSGS
SGGGGGGGGS
SSSSSSSSSS
```
-----
```input
1
.
```
```output
NONE
```

## Note
For the first test case, Omkar can make the mastapeeces

SSSS

SGGS

SGGS

SSSS

and

SSGG

SSGG

GGSS

GGSS.

For the second test case, it can be proven that it is impossible for Omkar to add tiles to create a mastapeece.

For the third case, it can be proven that the given mastapeece is the only mastapeece Omkar can create by adding tiles.

For the fourth test case, it's clearly impossible for the only tile in any mosaic Omkar creates to be adjacent to two tiles of the same color, as it will be adjacent to $$$0$$$ tiles total.

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
A sequence of integers $$$b_1, b_2, \ldots, b_m$$$ is called good if $$$max(b_1, b_2, \ldots, b_m) \cdot min(b_1, b_2, \ldots, b_m) \ge b_1 + b_2 + \ldots + b_m$$$.

A sequence of integers $$$a_1, a_2, \ldots, a_n$$$ is called perfect if every non-empty subsequence of $$$a$$$ is good.

YouKn0wWho has two integers $$$n$$$ and $$$M$$$, $$$M$$$ is prime. Help him find the number, modulo $$$M$$$, of perfect sequences $$$a_1, a_2, \ldots, a_n$$$ such that $$$1 \le a_i \le n + 1$$$ for each integer $$$i$$$ from $$$1$$$ to $$$n$$$.

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

## Input Format
The first and only line of the input contains two space-separated integers $$$n$$$ and $$$M$$$ ($$$1 \le n \le 200$$$; $$$10^8 \le M \le 10^9$$$). It is guaranteed that $$$M$$$ is prime.

## Output Format
Print a single integer  — the number of perfect sequences modulo $$$M$$$.

## Examples
```input
2 998244353
```
```output
4
```
-----
```input
4 100000007
```
```output
32
```
-----
```input
69 999999937
```
```output
456886663
```

## Note
In the first test case, the perfect sequences are $$$[2, 2]$$$, $$$[2, 3]$$$, $$$[3, 2]$$$ and $$$[3, 3]$$$.

In the second test case, some of the perfect sequences are $$$[3, 4, 3, 5]$$$, $$$[4, 5, 4, 4]$$$, $$$[4, 5, 5, 5]$$$ etc. One example of a sequence which is not perfect is $$$[2, 3, 3, 4]$$$, because, for example, the subsequence $$$[2, 3, 4]$$$ is not an good as $$$2 \cdot 4 < 2 + 3 + 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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
It was October 18, 2017. Shohag, a melancholic soul, made a strong determination that he will pursue Competitive Programming seriously, by heart, because he found it fascinating. Fast forward to 4 years, he is happy that he took this road. He is now creating a contest on Codeforces. He found an astounding problem but has no idea how to solve this. Help him to solve the final problem of the round.

You are given three integers $$$n$$$, $$$k$$$ and $$$x$$$. Find the number, modulo $$$998\,244\,353$$$, of integer sequences $$$a_1, a_2, \ldots, a_n$$$ such that the following conditions are satisfied:

- $$$0 \le a_i \lt 2^k$$$ for each integer $$$i$$$ from $$$1$$$ to $$$n$$$.
- There is no non-empty subsequence in $$$a$$$ such that the bitwise XOR of the elements of the subsequence is $$$x$$$.

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

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

The first and only line of each test case contains three space-separated integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^7$$$, $$$0 \le x \lt 2^{\operatorname{min}(20, k)}$$$).

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

## Output Format
For each test case, print a single integer — the answer to the problem.

## Examples
```input
6
2 2 0
2 1 1
3 2 3
69 69 69
2017 10 18
5 7 0
```
```output
6
1
15
699496932
892852568
713939942
```

## Note
In the first test case, the valid sequences are $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$ and $$$[3, 2]$$$.

In the second test case, the only valid sequence is $$$[0, 0]$$$.

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
Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string $$$s$$$ as input. However, they soon found out that if some substring $$$t$$$ of $$$s$$$ is a palindrome of length greater than 1, the algorithm will work incorrectly. Can the students somehow reorder the characters of $$$s$$$ so that the algorithm will work correctly on the string?

A binary string is a string where each character is either 0 or 1.

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.

A palindrome is a string that reads the same backwards as forwards.

## 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$$$ ($$$1 \le n \le 100$$$) — the length of the string $$$s$$$.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$ consisting only of the characters 0 and 1.

## Output Format
For each test case, print YES (case-insensitive) if it is possible to reorder the characters of $$$s$$$ so that there are no substrings that are a palindrome of length greater than 1, or NO (case-insensitive) otherwise.

## Examples
```input
4
1
1
2
10
2
01
4
1010
```
```output
YES
YES
YES
NO
```

## Note
In the first three test cases, the given strings do not contain palindromes of length greater than 1, so the answers are YES.

In the last test case, it is impossible to reorder the characters so that the string does not contain palindromes of length greater than 1, so the answer is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Igor is in 11th grade. Tomorrow he will have to write an informatics test by the strictest teacher in the school, Pavel Denisovich.

Igor knows how the test will be conducted: first of all, the teacher will give each student two positive integers $$$a$$$ and $$$b$$$ ($$$a < b$$$). After that, the student can apply any of the following operations any number of times:

- $$$a := a + 1$$$ (increase $$$a$$$ by $$$1$$$),
- $$$b := b + 1$$$ (increase $$$b$$$ by $$$1$$$),
- $$$a := a \ | \ b$$$ (replace $$$a$$$ with the bitwise OR of $$$a$$$ and $$$b$$$).

To get full marks on the test, the student has to tell the teacher the minimum required number of operations to make $$$a$$$ and $$$b$$$ equal.

Igor already knows which numbers the teacher will give him. Help him figure out what is the minimum number of operations needed to make $$$a$$$ equal to $$$b$$$.

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

The only line for each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a < b \le 10^6$$$).

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

## Output Format
For each test case print one integer — the minimum required number of operations to make $$$a$$$ and $$$b$$$ equal.

## Examples
```input
5
1 3
5 8
2 5
3 19
56678 164422
```
```output
1
3
2
1
23329
```

## Note
In the first test case, it is optimal to apply the third operation.

In the second test case, it is optimal to apply the first operation three times.

In the third test case, it is optimal to apply the second operation and then the third operation.

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
New Year is just around the corner, which means that in School 179, preparations for the concert are in full swing.

There are $$$n$$$ classes in the school, numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th class has prepared a scene of length $$$a_i$$$ minutes.

As the main one responsible for holding the concert, Idnar knows that if a concert has $$$k$$$ scenes of lengths $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_k$$$ minutes, then the audience will get bored if there exist two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le k$$$ and $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1$$$, where $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)$$$ is equal to the greatest common divisor (GCD) of the numbers $$$b_l$$$, $$$b_{l + 1}$$$, $$$\ldots$$$, $$$b_{r - 1}$$$, $$$b_r$$$.

To avoid boring the audience, Idnar can ask any number of times (possibly zero) for the $$$t$$$-th class ($$$1 \le t \le k$$$) to make a new scene $$$d$$$ minutes in length, where $$$d$$$ can be any positive integer. Thus, after this operation, $$$b_t$$$ is equal to $$$d$$$. Note that $$$t$$$ and $$$d$$$ can be different for each operation.

For a sequence of scene lengths $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_{k}$$$, let $$$f(b)$$$ be the minimum number of classes Idnar has to ask to change their scene if he wants to avoid boring the audience.

Idnar hasn't decided which scenes will be allowed for the concert, so he wants to know the value of $$$f$$$ for each non-empty prefix of $$$a$$$. In other words, Idnar wants to know the values of $$$f(a_1)$$$, $$$f(a_1$$$,$$$a_2)$$$, $$$\ldots$$$, $$$f(a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n)$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of classes in the school.

The second line contains $$$n$$$ positive integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the lengths of the class scenes.

## Output Format
Print a sequence of $$$n$$$ integers in a single line — $$$f(a_1)$$$, $$$f(a_1$$$,$$$a_2)$$$, $$$\ldots$$$, $$$f(a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n)$$$.

## Examples
```input
1
1
```
```output
1
```
-----
```input
3
1 4 2
```
```output
1 1 2
```
-----
```input
7
2 12 4 8 18 3 6
```
```output
0 1 1 1 2 2 2
```

## Note
In the first test we can change $$$1$$$ to $$$2$$$, so the answer is $$$1$$$.

In the second test:

- $$$[1]$$$ can be changed into $$$[2]$$$,
- $$$[1, 4]$$$ can be changed into $$$[3, 4]$$$,
- $$$[1, 4, 2]$$$ can be changed into $$$[2, 3, 2]$$$.

Now solve the problem and return the code.