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 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
In the times of Jason and the Argonauts, it was well known that sirens use the sound of their songs to lure sailors into their demise. Yet only a few knew that every time sirens call a sailor by his name, his will weakens, making him more vulnerable.

For the purpose of this problem, both siren songs and names of the sailors will be represented as strings of lowercase English letters. The more times the sailor's name occurs as a contiguous substring of the song, the greater danger he is in.

Jason found out that sirens can sing one of the $$$n+1$$$ songs, which have the following structure: let $$$s_i$$$ ($$$0 \leq i \leq n$$$) be the $$$i$$$-th song and $$$t$$$ be a string of length $$$n$$$, then for every $$$i < n$$$: $$$s_{i+1} = s_i t_i s_i$$$. In other words $$$i+1$$$-st song is the concatenation of $$$i$$$-th song, $$$i$$$-th letter ($$$0$$$-indexed) of $$$t$$$ and the $$$i$$$-th song.

Fortunately, he also knows $$$s_0$$$ and $$$t$$$. Jason wonders how many times a sailor's name is mentioned in a particular song. Answer $$$q$$$ queries: given the sailor's name ($$$w$$$) and the index of a song ($$$i$$$) output the number of occurrences of $$$w$$$ in $$$s_i$$$ as a substring. As this number can be quite large, output its remainder modulo $$$10^9+7$$$.

## Input Format
In the first line of input there are two integers $$$n$$$, $$$q$$$ ( $$$ 1 \leq n, q \leq 10^5$$$) meaning that there are $$$n+1$$$ songs and $$$q$$$ queries. In the next two lines strings $$$s_0$$$ and $$$t$$$ follow ($$$1 \leq |s_0| \leq 100, |t| = n$$$).

Next $$$q$$$ lines describe the queries; each one contains an integer $$$k$$$ ($$$ 0 \leq k \leq n$$$), the index of the song sung by the sirens, and a non-empty string $$$w$$$, which is the name of a sailor. All strings in this problem consist only of lowercase English letters, and the sum of lengths of sailors' names does not exceed $$$10^6$$$.

## Output Format
Output $$$q$$$ lines, $$$i$$$-th of them should contain the remainder modulo $$$10^9+7$$$ of the number of occurrences of $$$w$$$ in $$$s_k$$$.

## Examples
```input
3 3
aa
bcd
2 aba
3 ca
3 aa
```
```output
2
2
8
```
-----
```input
4 5
aba
bbac
1 a
3 baca
3 ab
2 bab
4 aba
```
```output
4
0
14
6
28
```

## Note
In the first example songs of the sirens are as follows:

- Song $$$0$$$: aa
- Song $$$1$$$: aabaa
- Song $$$2$$$: aabaacaabaa
- Song $$$3$$$: aabaacaabaadaabaacaabaa

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
For the New Year, Polycarp decided to send postcards to all his $$$n$$$ friends. He wants to make postcards with his own hands. For this purpose, he has a sheet of paper of size $$$w \times h$$$, which can be cut into pieces.

Polycarp can cut any sheet of paper $$$w \times h$$$ that he has in only two cases:

- If $$$w$$$ is even, then he can cut the sheet in half and get two sheets of size $$$\frac{w}{2} \times h$$$;
- If $$$h$$$ is even, then he can cut the sheet in half and get two sheets of size $$$w \times \frac{h}{2}$$$;

If $$$w$$$ and $$$h$$$ are even at the same time, then Polycarp can cut the sheet according to any of the rules above.

After cutting a sheet of paper, the total number of sheets of paper is increased by $$$1$$$.

Help Polycarp to find out if he can cut his sheet of size $$$w \times h$$$ at into $$$n$$$ or more pieces, using only the rules described above.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing three integers $$$w$$$, $$$h$$$, $$$n$$$ ($$$1 \le w, h \le 10^4, 1 \le n \le 10^9$$$) — the width and height of the sheet Polycarp has and the number of friends he needs to send a postcard to.

## Output Format
For each test case, output on a separate line:

- "YES", if it is possible to cut a sheet of size $$$w \times h$$$ into at least $$$n$$$ pieces;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

## Examples
```input
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4
```
```output
YES
NO
YES
YES
YES
```

## Note
In the first test case, you can first cut the $$$2 \times 2$$$ sheet into two $$$2 \times 1$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 1$$$. We can choose any three of them and send them to our friends.

In the second test case, a $$$3 \times 3$$$ sheet cannot be cut, so it is impossible to get two sheets.

In the third test case, you can cut a $$$5 \times 10$$$ sheet into two $$$5 \times 5$$$ sheets.

In the fourth test case, there is no need to cut the sheet, since we only need one sheet.

In the fifth test case, you can first cut the $$$1 \times 4$$$ sheet into two $$$1 \times 2$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
During their New Year holidays, Alice and Bob play the following game using an array $$$a$$$ of $$$n$$$ integers:

- Players take turns, Alice moves first.
- Each turn a player chooses any element and removes it from the array.
- If Alice chooses even value, then she adds it to her score. If the chosen value is odd, Alice's score does not change.
- Similarly, if Bob chooses odd value, then he adds it to his score. If the chosen value is even, then Bob's score does not change.

If there are no numbers left in the array, then the game ends. The player with the highest score wins. If the scores of the players are equal, then a draw is declared.

For example, if $$$n = 4$$$ and $$$a = [5, 2, 7, 3]$$$, then the game could go as follows (there are other options):

- On the first move, Alice chooses $$$2$$$ and get two points. Her score is now $$$2$$$. The array $$$a$$$ is now $$$[5, 7, 3]$$$.
- On the second move, Bob chooses $$$5$$$ and get five points. His score is now $$$5$$$. The array $$$a$$$ is now $$$[7, 3]$$$.
- On the third move, Alice chooses $$$7$$$ and get no points. Her score is now $$$2$$$. The array $$$a$$$ is now $$$[3]$$$.
- On the last move, Bob chooses $$$3$$$ and get three points. His score is now $$$8$$$. The array $$$a$$$ is empty now.
- Since Bob has more points at the end of the game, he is the winner.

You want to find out who will win if both players play optimally. Note that there may be duplicate numbers in the array.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$ used to play the game.

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 on a separate line:

- "Alice" if Alice wins with the optimal play;
- "Bob" if Bob wins with the optimal play;
- "Tie", if a tie is declared during the optimal play.

## Examples
```input
4
4
5 2 7 3
3
3 2 1
4
2 2 2 2
2
7 8
```
```output
Bob
Tie
Alice
Alice
```

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
Every year Santa Claus gives gifts to all children. However, each country has its own traditions, and this process takes place in different ways. For example, in Berland you need to solve the New Year's puzzle.

Polycarp got the following problem: given a grid strip of size $$$2 \times n$$$, some cells of it are blocked. You need to check if it is possible to tile all free cells using the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles (dominoes).

For example, if $$$n = 5$$$ and the strip looks like this (black cells are blocked):

Then it can be tiled, for example, using two vertical and two horizontal tiles, as in the picture below (different tiles are marked by different colors).

And if $$$n = 3$$$ and the strip looks like this:

It is impossible to tile free cells.

Polycarp easily solved this task and received his New Year's gift. Can you solve it?

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case is preceded by an empty line.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the length of the strip and the number of blocked cells on it.

Each of the next $$$m$$$ lines contains two integers $$$r_i, c_i$$$ ($$$1 \le r_i \le 2, 1 \le c_i \le n$$$) — numbers of rows and columns of blocked cells. It is guaranteed that all blocked cells are different, i.e. $$$(r_i, c_i) \ne (r_j, c_j), i \ne j$$$.

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

## Output Format
For each test case, print on a separate line:

- "YES", if it is possible to tile all unblocked squares with the $$$2 \times 1$$$ and $$$1 \times 2$$$ tiles;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

## Examples
```input
3

5 2
2 2
1 4

3 2
2 1
2 3

6 4
2 1
2 3
2 4
2 6
```
```output
YES
NO
NO
```

## Note
The first two test cases are explained in the statement.

In the third test case the strip looks like this:

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 an array $$$a_1, a_2, \ldots, a_n$$$ consisting of $$$n$$$ positive integers and a positive integer $$$m$$$.

You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.

Let's call an array $$$m$$$-divisible if for each two adjacent numbers in the array (two numbers on the positions $$$i$$$ and $$$i+1$$$ are called adjacent for each $$$i$$$) their sum is divisible by $$$m$$$. An array of one element is $$$m$$$-divisible.

Find the smallest number of $$$m$$$-divisible arrays that $$$a_1, a_2, \ldots, a_n$$$ is possible to divide into.

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

The first line of each test case contains two integers $$$n$$$, $$$m$$$ $$$(1 \le n \le 10^5, 1 \le m \le 10^5)$$$.

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

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

## Output Format
For each test case print the answer to the problem.

## Examples
```input
4
6 4
2 2 8 6 9 4
10 8
1 1 1 5 2 4 4 8 6 7
1 1
666
2 2
2 4
```
```output
3
6
1
1
```

## Note
In the first test case we can divide the elements as follows:

- $$$[4, 8]$$$. It is a $$$4$$$-divisible array because $$$4+8$$$ is divisible by $$$4$$$.
- $$$[2, 6, 2]$$$. It is a $$$4$$$-divisible array because $$$2+6$$$ and $$$6+2$$$ are divisible by $$$4$$$.
- $$$[9]$$$. It is a $$$4$$$-divisible array because it consists of one element.

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
It is the easy version of the problem. The only difference is that in this version $$$k = 3$$$.

You are given a positive integer $$$n$$$. Find $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, such that:

- $$$a_1 + a_2 + \ldots + a_k = n$$$
- $$$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$$$

Here $$$LCM$$$ is the least common multiple of numbers $$$a_1, a_2, \ldots, a_k$$$.

We can show that for given constraints the answer always exists.

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

The only line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 10^9$$$, $$$k = 3$$$).

## Output Format
For each test case print $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, for which all conditions are satisfied.

## Examples
```input
3
3 3
8 3
14 3
```
```output
1 1 1
4 2 2
2 6 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 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
It is the hard version of the problem. The only difference is that in this version $$$3 \le k \le n$$$.

You are given a positive integer $$$n$$$. Find $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, such that:

- $$$a_1 + a_2 + \ldots + a_k = n$$$
- $$$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$$$

Here $$$LCM$$$ is the least common multiple of numbers $$$a_1, a_2, \ldots, a_k$$$.

We can show that for given constraints the answer always exists.

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

The only line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 10^9$$$, $$$3 \le k \le n$$$).

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

## Output Format
For each test case print $$$k$$$ positive integers $$$a_1, a_2, \ldots, a_k$$$, for which all conditions are satisfied.

## Examples
```input
2
6 4
9 5
```
```output
1 2 2 1 
1 3 3 1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The only difference is that in this version $$$0 \leq k \leq 20$$$.

There is an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers. You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square.

Moreover, it is allowed to do at most $$$k$$$ such operations before the division: choose a number in the array and change its value to any positive integer.

What is the minimum number of continuous segments you should use if you will make changes optimally?

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

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \leq k \leq 20$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).

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

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

## Examples
```input
3
5 2
18 6 2 4 1
11 4
6 2 2 8 9 1 3 6 3 9 7
1 0
1
```
```output
1
2
1
```

## Note
In the first test case it is possible to change the array this way: $$$[\underline{3}, 6, 2, 4, \underline{5}]$$$ (changed elements are underlined). After that the array does not need to be divided, so the answer is $$$1$$$.

In the second test case it is possible to change the array this way: $$$[6, 2, \underline{3}, 8, 9, \underline{5}, 3, 6, \underline{10}, \underline{11}, 7]$$$. After that such division is optimal:

- $$$[6, 2, 3]$$$
- $$$[8, 9, 5, 3, 6, 10, 11, 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 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
Given an array $$$a$$$ of length $$$n$$$, you can do at most $$$k$$$ operations of the following type on it:

- choose $$$2$$$ different elements in the array, add $$$1$$$ to the first, and subtract $$$1$$$ from the second. However, all the elements of $$$a$$$ have to remain non-negative after this operation.

What is lexicographically the smallest array you can obtain?

An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ if there exists an index $$$i$$$ such that $$$x_i<y_i$$$, and $$$x_j=y_j$$$ for all $$$1 \le j < i$$$. Less formally, at the first index $$$i$$$ in which they differ, $$$x_i<y_i$$$.

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

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le 10000$$$) — the number of elements in the array and the maximum number of operations you can make.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i \le 100$$$) — the elements of the array $$$a$$$.

## Output Format
For each test case, print the lexicographically smallest array you can obtain after at most $$$k$$$ operations.

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

## Note
In the second test case, we start by subtracting $$$1$$$ from the first element and adding $$$1$$$ to the second. Then, we can't get any lexicographically smaller arrays, because we can't make any of the elements negative.

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
Baby Ehab is known for his love for a certain operation. He has an array $$$a$$$ of length $$$n$$$, and he decided to keep doing the following operation on it:

- he picks $$$2$$$ adjacent elements; he then removes them and places a single integer in their place: their bitwise XOR. Note that the length of the array decreases by one.

Now he asks you if he can make all elements of the array equal. Since babies like to make your life harder, he requires that you leave at least $$$2$$$ elements remaining.

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

The first line of each test case contains an integers $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of elements in the array $$$a$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i < 2^{30}$$$) — the elements of the array $$$a$$$.

## Output Format
If Baby Ehab can make all elements equal while leaving at least $$$2$$$ elements standing, print "YES". Otherwise, print "NO".

## Examples
```input
2
3
0 2 2
4
2 3 1 10
```
```output
YES
NO
```

## Note
In the first sample, he can remove the first $$$2$$$ elements, $$$0$$$ and $$$2$$$, and replace them by $$$0 \oplus 2=2$$$. The array will be $$$[2,2]$$$, so all the elements are equal.

In the second sample, there's no way to make all the elements equal.

Now solve the problem and return the code.