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
Professor Ibrahim has prepared the final homework for his algorithm’s class. He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $$$i$$$-th integer represents the color of the $$$i$$$-th pixel in the image. The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key. In order to preserve image details, the size of a group must not be greater than $$$k$$$, and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $$$k$$$ to the right.

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 256$$$), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \leq p_i \leq 255$$$), where $$$p_i$$$ is the color of the $$$i$$$-th pixel.

## Output Format
Print $$$n$$$ space-separated integers; the lexicographically smallest possible array that represents the image after applying the Posterization filter.

## Examples
```input
4 3
2 14 3 4
```
```output
0 12 3 3
```
-----
```input
5 2
0 2 1 255 254
```
```output
0 1 1 254 254
```

## Note
One possible way to group colors and assign keys for the first sample:

Color $$$2$$$ belongs to the group $$$[0,2]$$$, with group key $$$0$$$.

Color $$$14$$$ belongs to the group $$$[12,14]$$$, with group key $$$12$$$.

Colors $$$3$$$ and $$$4$$$ belong to group $$$[3, 5]$$$, with group key $$$3$$$.

Other groups won't affect the result so they are not listed here.

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
The nation of Panel holds an annual show called The Number Games, where each district in the nation will be represented by one contestant.

The nation has $$$n$$$ districts numbered from $$$1$$$ to $$$n$$$, each district has exactly one path connecting it to every other district. The number of fans of a contestant from district $$$i$$$ is equal to $$$2^i$$$.

This year, the president decided to reduce the costs. He wants to remove $$$k$$$ contestants from the games. However, the districts of the removed contestants will be furious and will not allow anyone to cross through their districts.

The president wants to ensure that all remaining contestants are from districts that can be reached from one another. He also wishes to maximize the total number of fans of the participating contestants.

Which contestants should the president remove?

## Input Format
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k < n \leq 10^6$$$) — the number of districts in Panel, and the number of contestants the president wishes to remove, respectively.

The next $$$n-1$$$ lines each contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \ne b$$$), that describe a road that connects two different districts $$$a$$$ and $$$b$$$ in the nation. It is guaranteed that there is exactly one path between every two districts.

## Output Format
Print $$$k$$$ space-separated integers: the numbers of the districts of which the contestants should be removed, in increasing order of district number.

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

## Note
In the first sample, the maximum possible total number of fans is $$$2^2 + 2^5 + 2^6 = 100$$$. We can achieve it by removing the contestants of the districts 1, 3, and 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
Two players play a game.

Initially there are $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ written on the board. Each turn a player selects one number and erases it from the board. This continues until there is only one number left on the board, i. e. $$$n - 1$$$ turns are made. The first player makes the first move, then players alternate turns.

The first player wants to minimize the last number that would be left on the board, while the second player wants to maximize it.

You want to know what number will be left on the board after $$$n - 1$$$ turns if both players make optimal moves.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of numbers on the board.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

## Output Format
Print one number that will be left on the board.

## Examples
```input
3
2 1 3
```
```output
2
```
-----
```input
3
2 2 2
```
```output
2
```

## Note
In the first sample, the first player erases $$$3$$$ and the second erases $$$1$$$. $$$2$$$ is left on the board.

In the second sample, $$$2$$$ is left on the board regardless of the actions of the players.

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
One day Alex decided to remember childhood when computers were not too powerful and lots of people played only default games. Alex enjoyed playing Minesweeper that time. He imagined that he saved world from bombs planted by terrorists, but he rarely won.

Alex has grown up since then, so he easily wins the most difficult levels. This quickly bored him, and he thought: what if the computer gave him invalid fields in the childhood and Alex could not win because of it?

He needs your help to check it.

A Minesweeper field is a rectangle $$$n \times m$$$, where each cell is either empty, or contains a digit from $$$1$$$ to $$$8$$$, or a bomb. The field is valid if for each cell:

- if there is a digit $$$k$$$ in the cell, then exactly $$$k$$$ neighboring cells have bombs.
- if the cell is empty, then all neighboring cells have no bombs.

Two cells are neighbors if they have a common side or a corner (i. e. a cell has at most $$$8$$$ neighboring cells).

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 100$$$) — the sizes of the field.

The next $$$n$$$ lines contain the description of the field. Each line contains $$$m$$$ characters, each of them is "." (if this cell is empty), "*" (if there is bomb in this cell), or a digit from $$$1$$$ to $$$8$$$, inclusive.

## Output Format
Print "YES", if the field is valid and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrarily.

## Examples
```input
3 3
111
1*1
111
```
```output
YES
```
-----
```input
2 4
*.*.
1211
```
```output
NO
```

## Note
In the second example the answer is "NO" because, if the positions of the bombs are preserved, the first line of the field should be *2*1.

You can read more about Minesweeper in Wikipedia's article.

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
There are $$$n$$$ distinct points on a coordinate line, the coordinate of $$$i$$$-th point equals to $$$x_i$$$. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points $$$x_{i_1}, x_{i_2}, \dots, x_{i_m}$$$ such that for each pair $$$x_{i_j}$$$, $$$x_{i_k}$$$ it is true that $$$|x_{i_j} - x_{i_k}| = 2^d$$$ where $$$d$$$ is some non-negative integer number (not necessarily the same for each pair of points).

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

The second line contains $$$n$$$ pairwise distinct integers $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$) — the coordinates of points.

## Output Format
In the first line print $$$m$$$ — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print $$$m$$$ integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

## Examples
```input
6
3 5 4 7 10 12
```
```output
3
7 3 5
```
-----
```input
5
-1 2 5 8 11
```
```output
1
8
```

## Note
In the first example the answer is $$$[7, 3, 5]$$$. Note, that $$$|7-3|=4=2^2$$$, $$$|7-5|=2=2^1$$$ and $$$|3-5|=2=2^1$$$. You can't find a subset having more points satisfying the required property.

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 an integer $$$n$$$ from $$$1$$$ to $$$10^{18}$$$ without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by $$$25$$$? Print -1 if it is impossible to obtain a number that is divisible by $$$25$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$). It is guaranteed that the first (left) digit of the number $$$n$$$ is not a zero.

## Output Format
If it is impossible to obtain a number that is divisible by $$$25$$$, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.

## Examples
```input
5071
```
```output
4
```
-----
```input
705
```
```output
1
```
-----
```input
1241367
```
```output
-1
```

## Note
In the first example one of the possible sequences of moves is 5071 $$$\rightarrow$$$ 5701 $$$\rightarrow$$$ 7501 $$$\rightarrow$$$ 7510 $$$\rightarrow$$$ 7150.

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
Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

## Input Format
The input contains three positive integer numbers in the first line: n,  m and a (1 ≤  n, m, a ≤ 109).

## Output Format
Write the needed number of flagstones.

## Examples
```input
6 6 4
```
```output
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: 64.0 MB

# Problem
Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

## Input Format
The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

## Output Format
Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

## Examples
```input
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000
```
```output
1.00000000
```

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
Alice has a lovely piece of cloth. It has the shape of a square with a side of length $$$a$$$ centimeters. Bob also wants such piece of cloth. He would prefer a square with a side of length $$$b$$$ centimeters (where $$$b < a$$$). Alice wanted to make Bob happy, so she cut the needed square out of the corner of her piece and gave it to Bob. Now she is left with an ugly L shaped cloth (see pictures below).

Alice would like to know whether the area of her cloth expressed in square centimeters is prime. Could you help her to determine it?

## Input Format
The first line contains a number $$$t$$$ ($$$1 \leq t \leq 5$$$) — the number of test cases.

Each of the next $$$t$$$ lines describes the $$$i$$$-th test case. It contains two integers $$$a$$$ and $$$b~(1 \leq b < a \leq 10^{11})$$$ — the side length of Alice's square and the side length of the square that Bob wants.

## Output Format
Print $$$t$$$ lines, where the $$$i$$$-th line is the answer to the $$$i$$$-th test case. Print "YES" (without quotes) if the area of the remaining piece of cloth is prime, otherwise print "NO".

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

## Examples
```input
4
6 5
16 13
61690850361 24777622630
34 33
```
```output
YES
NO
NO
YES
```

## Note
The figure below depicts the first test case. The blue part corresponds to the piece which belongs to Bob, and the red part is the piece that Alice keeps for herself. The area of the red part is $$$6^2 - 5^2 = 36 - 25 = 11$$$, which is prime, so the answer is "YES".

In the second case, the area is $$$16^2 - 13^2 = 87$$$, which is divisible by $$$3$$$.

In the third case, the area of the remaining piece is $$$61690850361^2 - 24777622630^2 = 3191830435068605713421$$$. This number is not prime because $$$3191830435068605713421 = 36913227731 \cdot 86468472991 $$$.

In the last case, the area is $$$34^2 - 33^2 = 67$$$.

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
After a long day, Alice and Bob decided to play a little game. The game board consists of $$$n$$$ cells in a straight line, numbered from $$$1$$$ to $$$n$$$, where each cell contains a number $$$a_i$$$ between $$$1$$$ and $$$n$$$. Furthermore, no two cells contain the same number.

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $$$i$$$ to cell $$$j$$$ only if the following two conditions are satisfied:

- the number in the new cell $$$j$$$ must be strictly larger than the number in the old cell $$$i$$$ (i.e. $$$a_j > a_i$$$), and
- the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $$$|i-j|\bmod a_i = 0$$$).

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Furthermore, there are no pair of indices $$$i \neq j$$$ such that $$$a_i = a_j$$$.

## Output Format
Print $$$s$$$ — a string of $$$n$$$ characters, where the $$$i$$$-th character represents the outcome of the game if the token is initially placed in the cell $$$i$$$. If Alice wins, then $$$s_i$$$ has to be equal to "A"; otherwise, $$$s_i$$$ has to be equal to "B".

## Examples
```input
8
3 6 5 4 2 7 1 8
```
```output
BAAAABAB
```
-----
```input
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
```
```output
ABAAAABBBAABAAB
```

## Note
In the first sample, if Bob puts the token on the number (not position):

- $$$1$$$: Alice can move to any number. She can win by picking $$$7$$$, from which Bob has no move.
- $$$2$$$: Alice can move to $$$3$$$ and $$$5$$$. Upon moving to $$$5$$$, Bob can win by moving to $$$8$$$. If she chooses $$$3$$$ instead, she wins, as Bob has only a move to $$$4$$$, from which Alice can move to $$$8$$$.
- $$$3$$$: Alice can only move to $$$4$$$, after which Bob wins by moving to $$$8$$$.
- $$$4$$$, $$$5$$$, or $$$6$$$: Alice wins by moving to $$$8$$$.
- $$$7$$$, $$$8$$$: Alice has no move, and hence she loses immediately.

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
Little C loves number «3» very much. He loves all things about it.

Now he has a positive integer $$$n$$$. He wants to split $$$n$$$ into $$$3$$$ positive integers $$$a,b,c$$$, such that $$$a+b+c=n$$$ and none of the $$$3$$$ integers is a multiple of $$$3$$$. Help him to find a solution.

## Input Format
A single line containing one integer $$$n$$$ ($$$3 \leq n \leq 10^9$$$) — the integer Little C has.

## Output Format
Print $$$3$$$ positive integers $$$a,b,c$$$ in a single line, such that $$$a+b+c=n$$$ and none of them is a multiple of $$$3$$$.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

## Examples
```input
3
```
```output
1 1 1
```
-----
```input
233
```
```output
77 77 79
```

Now solve the problem and return the code.