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
Sherlock Holmes and Dr. Watson played some game on a checkered board n × n in size. During the game they put numbers on the board's squares by some tricky rules we don't know. However, the game is now over and each square of the board contains exactly one number. To understand who has won, they need to count the number of winning squares. To determine if the particular square is winning you should do the following. Calculate the sum of all numbers on the squares that share this column (including the given square) and separately calculate the sum of all numbers on the squares that share this row (including the given square). A square is considered winning if the sum of the column numbers is strictly greater than the sum of the row numbers.

For instance, lets game was ended like is shown in the picture. Then the purple cell is winning, because the sum of its column numbers equals 8 + 3 + 6 + 7 = 24, sum of its row numbers equals 9 + 5 + 3 + 2 = 19, and 24 > 19.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 30). Each of the following n lines contain n space-separated integers. The j-th number on the i-th line represents the number on the square that belongs to the j-th column and the i-th row on the board. All number on the board are integers from 1 to 100.

## Output Format
Print the single number — the number of the winning squares.

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

## Note
In the first example two upper squares are winning.

In the third example three left squares in the both middle rows are winning:

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
One day, as Sherlock Holmes was tracking down one very important criminal, he found a wonderful painting on the wall. This wall could be represented as a plane. The painting had several concentric circles that divided the wall into several parts. Some parts were painted red and all the other were painted blue. Besides, any two neighboring parts were painted different colors, that is, the red and the blue color were alternating, i. e. followed one after the other. The outer area of the wall (the area that lied outside all circles) was painted blue. Help Sherlock Holmes determine the total area of red parts of the wall.

Let us remind you that two circles are called concentric if their centers coincide. Several circles are called concentric if any two of them are concentric.

## Input Format
The first line contains the single integer n (1 ≤ n ≤ 100). The second line contains n space-separated integers ri (1 ≤ ri ≤ 1000) — the circles' radii. It is guaranteed that all circles are different.

## Output Format
Print the single real number — total area of the part of the wall that is painted red. The answer is accepted if absolute or relative error doesn't exceed 10 - 4.

## Examples
```input
1
1
```
```output
3.1415926536
```
-----
```input
3
1 4 2
```
```output
40.8407044967
```

## Note
In the first sample the picture is just one circle of radius 1. Inner part of the circle is painted red. The area of the red part equals π × 12 = π.

In the second sample there are three circles of radii 1, 4 and 2. Outside part of the second circle is painted blue. Part between the second and the third circles is painted red. Part between the first and the third is painted blue. And, finally, the inner part of the first circle is painted red. Overall there are two red parts: the ring between the second and the third circles and the inner part of the first circle. Total area of the red parts is equal (π × 42 - π × 22) + π × 12 = π × 12 + π = 13π

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
Hemose was shopping with his friends Samez, AhmedZ, AshrafEzz, TheSawan and O_E in Germany. As you know, Hemose and his friends are problem solvers, so they are very clever. Therefore, they will go to all discount markets in Germany.

Hemose has an array of $$$n$$$ integers. He wants Samez to sort the array in the non-decreasing order. Since it would be a too easy problem for Samez, Hemose allows Samez to use only the following operation:

- Choose indices $$$i$$$ and $$$j$$$ such that $$$1 \le i, j \le n$$$, and $$$\lvert i - j \rvert \geq x$$$. Then, swap elements $$$a_i$$$ and $$$a_j$$$.

Can you tell Samez if there's a way to sort the array in the non-decreasing order by using the operation written above some finite number of times (possibly $$$0$$$)?

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ $$$(1 \leq x \leq n \leq 10^5)$$$.

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, you should output a single string.

If Samez can sort the array in non-decreasing order using the operation written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

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

## Note
In the first test case, you can't do any operations.

In the second test case, the array is already sorted.

In the third test case, you can do the operations as follows:

- $$$[5,1,2,3,4]$$$, $$$swap(a_1,a_3)$$$
- $$$[2,1,5,3,4]$$$, $$$swap(a_2,a_5)$$$
- $$$[2,4,5,3,1]$$$, $$$swap(a_2,a_4)$$$
- $$$[2,3,5,4,1]$$$, $$$swap(a_1,a_5)$$$
- $$$[1,3,5,4,2]$$$, $$$swap(a_2,a_5)$$$
- $$$[1,2,5,4,3]$$$, $$$swap(a_3,a_5)$$$
- $$$[1,2,3,4,5]$$$

(Here $$$swap(a_i, a_j)$$$ refers to swapping elements at positions $$$i$$$, $$$j$$$).

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
Bakry faced a problem, but since he's lazy to solve it, he asks for your help.

You are given a tree of $$$n$$$ nodes, the $$$i$$$-th node has value $$$a_i$$$ assigned to it for each $$$i$$$ from $$$1$$$ to $$$n$$$. As a reminder, a tree on $$$n$$$ nodes is a connected graph with $$$n-1$$$ edges.

You want to delete at least $$$1$$$, but at most $$$k-1$$$ edges from the tree, so that the following condition would hold:

- For every connected component calculate the bitwise XOR of the values of the nodes in it. Then, these values have to be the same for all connected components.

Is it possible to achieve this condition?

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(2 \leq k \leq n \leq 10^5)$$$.

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

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i\neq v_i$$$), which means that there's an edge between nodes $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, you should output a single string. If you can delete the edges according to the conditions written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

## Examples
```input
5
2 2
1 3
1 2
5 5
3 3 3 3 3
1 2
2 3
1 4
4 5
5 2
1 7 2 3 5
1 2
2 3
1 4
4 5
5 3
1 6 4 1 2
1 2
2 3
1 4
4 5
3 3
1 7 4
1 2
2 3
```
```output
NO
YES
NO
YES
NO
```

## Note
It can be shown that the objection is not achievable for first, third, and fifth test cases.

In the second test case, you can just remove all the edges. There will be $$$5$$$ connected components, each containing only one node with value $$$3$$$, so the bitwise XORs will be $$$3$$$ for all of them.

In the fourth test case, this is the tree: .

You can remove an edge $$$(4,5)$$$

The bitwise XOR of the first component will be, $$$a_1 \oplus a_2 \oplus a_3 \oplus a_4 = 1 \oplus 6 \oplus 4 \oplus 1 = 2$$$ (where $$$\oplus$$$ denotes the bitwise XOR).

The bitwise XOR of the second component will be, $$$a_5 = 2$$$.

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

# Problem
Bakry got bored of solving problems related to xor, so he asked you to solve this problem for him.

You are given an array $$$a$$$ of $$$n$$$ integers $$$[a_1, a_2, \ldots, a_n]$$$.

Let's call a subarray $$$a_{l}, a_{l+1}, a_{l+2}, \ldots, a_r$$$ good if $$$a_l \, \& \, a_{l+1} \, \& \, a_{l+2} \, \ldots \, \& \, a_r > a_l \oplus a_{l+1} \oplus a_{l+2} \ldots \oplus a_r$$$, where $$$\oplus$$$ denotes the bitwise XOR operation and $$$\&$$$ denotes the bitwise AND operation.

Find the length of the longest good subarray of $$$a$$$, or determine that no such subarray exists.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array.

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

## Output Format
Print a single integer — the length of the longest good subarray. If there are no good subarrays, print $$$0$$$.

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

## Note
In the first case, the answer is $$$2$$$, as the whole array is good: $$$5 \& 6 = 4 > 5 \oplus 6 = 3$$$.

In the third case, the answer is $$$4$$$, and one of the longest good subarrays is $$$[a_2, a_3, a_4, a_5]$$$: $$$1\& 3 \& 3 \&1 = 1 > 1\oplus 3 \oplus 3\oplus 1 = 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 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
The difference between the versions is in the costs of operations. Solution for one version won't work for another!

Alice has a grid of size $$$n \times m$$$, initially all its cells are colored white. The cell on the intersection of $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. Alice can do the following operations with this grid:

- Choose any subrectangle containing cell $$$(1, 1)$$$, and flip the colors of all its cells. (Flipping means changing its color from white to black or from black to white). This operation costs $$$1$$$ coin.
- Choose any subrectangle containing cell $$$(n, 1)$$$, and flip the colors of all its cells. This operation costs $$$2$$$ coins.
- Choose any subrectangle containing cell $$$(1, m)$$$, and flip the colors of all its cells. This operation costs $$$4$$$ coins.
- Choose any subrectangle containing cell $$$(n, m)$$$, and flip the colors of all its cells. This operation costs $$$3$$$ coins.

As a reminder, subrectangle is a set of all cells $$$(x, y)$$$ with $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ for some $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$.

Alice wants to obtain her favorite coloring with these operations. What's the smallest number of coins that she would have to spend? It can be shown that it's always possible to transform the initial grid into any other.

## Input Format
The first line of the input contains $$$2$$$ integers $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — the dimensions of the grid.

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ of length $$$m$$$, consisting of letters W and B. The $$$j$$$-th character of string $$$s_i$$$ is W if the cell $$$(i, j)$$$ is colored white in the favorite coloring of Alice, and B if it's colored black.

## Output Format
Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.

## Examples
```input
3 3
WWW
WBB
WBB
```
```output
3
```
-----
```input
10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW
```
```output
74
```

## Note
In the first sample, it's optimal to just apply the fourth operation once to the rectangle containing cells $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$. This would cost $$$3$$$ coins.

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
The difference between the versions is in the costs of operations. Solution for one version won't work for another!

Alice has a grid of size $$$n \times m$$$, initially all its cells are colored white. The cell on the intersection of $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. Alice can do the following operations with this grid:

- Choose any subrectangle containing cell $$$(1, 1)$$$, and flip the colors of all its cells. (Flipping means changing its color from white to black or from black to white). This operation costs $$$1$$$ coin.
- Choose any subrectangle containing cell $$$(n, 1)$$$, and flip the colors of all its cells. This operation costs $$$3$$$ coins.
- Choose any subrectangle containing cell $$$(1, m)$$$, and flip the colors of all its cells. This operation costs $$$4$$$ coins.
- Choose any subrectangle containing cell $$$(n, m)$$$, and flip the colors of all its cells. This operation costs $$$2$$$ coins.

As a reminder, subrectangle is a set of all cells $$$(x, y)$$$ with $$$x_1 \le x \le x_2$$$, $$$y_1 \le y \le y_2$$$ for some $$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$.

Alice wants to obtain her favorite coloring with these operations. What's the smallest number of coins that she would have to spend? It can be shown that it's always possible to transform the initial grid into any other.

## Input Format
The first line of the input contains $$$2$$$ integers $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — the dimensions of the grid.

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ of length $$$m$$$, consisting of letters W and B. The $$$j$$$-th character of string $$$s_i$$$ is W if the cell $$$(i, j)$$$ is colored white in the favorite coloring of Alice, and B if it's colored black.

## Output Format
Output the smallest number of coins Alice would have to spend to achieve her favorite coloring.

## Examples
```input
3 3
WWW
WBB
WBB
```
```output
2
```
-----
```input
10 15
WWWBBBWBBBBBWWW
BBBBWWWBBWWWBBB
BBBWWBWBBBWWWBB
BBWBWBBWWWBBWBW
BBBBWWWBBBWWWBB
BWBBWWBBBBBBWWW
WBWWBBBBWWBBBWW
WWBWWWWBBWWBWWW
BWBWWBWWWWWWBWB
BBBWBWBWBBBWWBW
```
```output
68
```

## Note
In the first sample, it's optimal to just apply the fourth operation once to the rectangle containing cells $$$(2, 2), (2, 3), (3, 2), (3, 3)$$$. This would cost $$$2$$$ coins.

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 strings $$$S$$$ and $$$T$$$, consisting of lowercase English letters. It is guaranteed that $$$T$$$ is a permutation of the string abc.

Find string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

String $$$a$$$ is a permutation of string $$$b$$$ if the number of occurrences of each distinct character is the same in both strings.

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

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

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

The first line of each test case contains a string $$$S$$$ ($$$1 \le |S| \le 100$$$), consisting of lowercase English letters.

The second line of each test case contains a string $$$T$$$ that is a permutation of the string abc. (Hence, $$$|T| = 3$$$).

Note that there is no limit on the sum of $$$|S|$$$ across all test cases.

## Output Format
For each test case, output a single string $$$S'$$$, the lexicographically smallest permutation of $$$S$$$ such that $$$T$$$ is not a subsequence of $$$S'$$$.

## Examples
```input
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc
```
```output
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac
```

## Note
In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.

In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.

In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.

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
Given a positive integer $$$n$$$. Find three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ such that $$$a + b + c = n$$$ and $$$\operatorname{gcd}(a, b) = c$$$, where $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

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

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

## Output Format
For each test case, output three distinct positive integers $$$a$$$, $$$b$$$, $$$c$$$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

## Examples
```input
6
18
63
73
91
438
122690412
```
```output
6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2
```

## Note
In the first test case, $$$6 + 9 + 3 = 18$$$ and $$$\operatorname{gcd}(6, 9) = 3$$$.

In the second test case, $$$21 + 39 + 3 = 63$$$ and $$$\operatorname{gcd}(21, 39) = 3$$$.

In the third test case, $$$29 + 43 + 1 = 73$$$ and $$$\operatorname{gcd}(29, 43) = 1$$$.

Now solve the problem and return the code.