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
Monocarp wants to throw a party. He has $$$n$$$ friends, and he wants to have at least $$$2$$$ of them at his party.

The $$$i$$$-th friend's best friend is $$$p_i$$$. All $$$p_i$$$ are distinct, and for every $$$i \in [1, n]$$$, $$$p_i \ne i$$$.

Monocarp can send invitations to friends. The $$$i$$$-th friend comes to the party if both the $$$i$$$-th friend and the $$$p_i$$$-th friend receive an invitation (note that the $$$p_i$$$-th friend doesn't have to actually come to the party). Each invitation is sent to exactly one of the friends.

For example, if $$$p = [3, 1, 2, 5, 4]$$$, and Monocarp sends invitations to the friends $$$[1, 2, 4, 5]$$$, then the friends $$$[2, 4, 5]$$$ will come to the party. The friend $$$1$$$ won't come since his best friend didn't receive an invitation; the friend $$$3$$$ won't come since he didn't receive an invitation.

Calculate the minimum number of invitations Monocarp has to send so that at least $$$2$$$ friends come to the party.

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

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of friends;
- the second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \ne i$$$; all $$$p_i$$$ are distinct).

## Output Format
Print one integer — the minimum number of invitations Monocarp has to send.

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

## Note
In the first testcase, Monocarp can send invitations to friends $$$4$$$ and $$$5$$$. Both of them will come to the party since they are each other's best friends, and both of them have invitations.

In the second testcase, Monocarp can send invitations to friends $$$1, 2$$$ and $$$3$$$, for example. Then friends $$$1$$$ and $$$2$$$ will attend: friend $$$1$$$ and his best friend $$$2$$$ have invitations, friend $$$2$$$ and his best friend $$$3$$$ have invitations. Friend $$$3$$$ won't attend since his friend $$$4$$$ doesn't have an invitation. It's impossible to send invitations to fewer than $$$3$$$ friends in such a way that at least $$$2$$$ come.

In the third testcase, Monocarp can send invitations to both friends $$$1$$$ and $$$2$$$, and both of them will attend.

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
You are given an integer array $$$a$$$ of length $$$n$$$.

You can perform the following operation: choose an element of the array and replace it with any of its neighbor's value.

For example, if $$$a=[3, 1, 2]$$$, you can get one of the arrays $$$[3, 3, 2]$$$, $$$[3, 2, 2]$$$ and $$$[1, 1, 2]$$$ using one operation, but not $$$[2, 1, 2$$$] or $$$[3, 4, 2]$$$.

Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most $$$k$$$ times.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$0 \le k \le 10$$$).

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

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most $$$k$$$ times.

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

## Note
In the first example, one of the possible sequences of operations is the following: $$$[3, 1, 2] \rightarrow [1, 1, 2$$$].

In the second example, you do not need to apply the operation.

In the third example, one of the possible sequences of operations is the following: $$$[2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1]$$$.

In the fourth example, one of the possible sequences of operations is the following: $$$[4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 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 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 and Bob are playing a game in the shop. There are $$$n$$$ items in the shop; each item has two parameters: $$$a_i$$$ (item price for Alice) and $$$b_i$$$ (item price for Bob).

Alice wants to choose a subset (possibly empty) of items and buy them. After that, Bob does the following:

- if Alice bought less than $$$k$$$ items, Bob can take all of them for free;
- otherwise, he will take $$$k$$$ items for free that Alice bought (Bob chooses which $$$k$$$ items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay $$$b_i$$$ for the $$$i$$$-th item.

Alice's profit is equal to $$$\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j$$$, where $$$S$$$ is the set of items Bob buys from Alice, and $$$T$$$ is the set of items Alice buys from the shop. In other words, Alice's profit is the difference between the amount Bob pays her and the amount she spends buying the items.

Alice wants to maximize her profit, Bob wants to minimize Alice's profit. Your task is to calculate Alice's profit if both Alice and Bob act optimally.

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

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

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

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — Alice's profit if both Alice and Bob act optimally.

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

## Note
In the first test case, Alice should buy the $$$2$$$-nd item and sell it to Bob, so her profit is $$$2 - 1 = 1$$$.

In the second test case, Alice should buy the $$$1$$$-st, the $$$2$$$-nd and the $$$3$$$-rd item; then Bob takes the $$$1$$$-st item for free and pays for the $$$2$$$-nd and the $$$3$$$-rd item. Alice's profit is $$$(3+2) - (1+2+1) = 1$$$. Bob could take $$$2$$$-nd item for free instead; this does not change Alice's profit. Bob won't take the $$$3$$$-rd item for free, since this would lead to a profit of $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer array $$$a$$$ of length $$$n$$$. A subarray of $$$a$$$ is one of its contiguous subsequences (i. e. an array $$$[a_l, a_{l+1}, \dots, a_r]$$$ for some integers $$$l$$$ and $$$r$$$ such that $$$1 \le l < r \le n$$$). Let's call a subarray unique if there is an integer that occurs exactly once in the subarray.

You can perform the following operation any number of times (possibly zero): choose an element of the array and replace it with any integer.

Your task is to calculate the minimum number of aforementioned operation in order for all the subarrays of the array $$$a$$$ to be unique.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum number of aforementioned operation in order for all the subarrays of the array $$$a$$$ to be unique.

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

## Note
In the second test case, you can replace the $$$1$$$-st and the $$$3$$$-rd element, for example, like this: $$$[3, 4, 1, 4]$$$.

In the third test case, you can replace the $$$4$$$-th element, for example, like this: $$$[3, 1, 2, 3, 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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
There is a deck of $$$n$$$ cards, each card has one of $$$k$$$ types. You are given the sequence $$$a_1, a_2, \dots, a_n$$$ denoting the types of cards in the deck from top to bottom. Both $$$n$$$ and $$$k$$$ are even numbers.

You play a game with these cards. First, you draw $$$k$$$ topmost cards from the deck. Then, the following happens each turn of the game:

- you choose exactly two cards from your hand and play them. If these cards have the same type, you earn a coin;
- then, if the deck is not empty, you draw exactly two top cards from it;
- then, if both your hand and your deck are empty, the game ends. Otherwise, the new turn begins.

You have to calculate the maximum number of coins you can earn during the game.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 1000$$$, both $$$n$$$ and $$$k$$$ are even).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$).

## Output Format
Print one integer — the maximum number of coins you can earn.

## Examples
```input
4 2
1 2 1 2
```
```output
0
```
-----
```input
8 2
2 1 2 2 1 2 1 2
```
```output
1
```
-----
```input
4 4
1 2 1 2
```
```output
2
```
-----
```input
6 4
3 2 3 1 2 1
```
```output
3
```
-----
```input
6 4
3 2 3 3 2 1
```
```output
2
```
-----
```input
18 6
5 6 1 1 6 5 4 1 5 1 1 6 2 6 2 2 6 3
```
```output
6
```
-----
```input
8 4
1 2 3 4 4 3 1 2
```
```output
2
```
-----
```input
8 4
1 2 3 4 4 3 3 2
```
```output
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 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 a string $$$s$$$ consisting of lowercase English letters.

Rearrange the characters of $$$s$$$ to form a new string $$$r$$$ that is not equal to $$$s$$$, or report that it's impossible.

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

The only line of each test case contains a string $$$s$$$ of length at most $$$10$$$ consisting of lowercase English letters.

## Output Format
For each test case, if no such string $$$r$$$ exists as described in the statement, output "NO" (without quotes).

Otherwise, output "YES" (without quotes). Then, output one line — the string $$$r$$$, consisting of letters of string $$$s$$$.

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

If multiple answers are possible, you can output any of them.

## Examples
```input
8
codeforces
aaaaa
xxxxy
co
d
nutdealer
mwistht
hhhhhhhhhh
```
```output
YES
forcodesec
NO
YES
xxyxx
YES
oc
NO
YES
undertale
YES
thtsiwm
NO
```

## Note
In the first test case, another possible answer is $$$\texttt{forcescode}$$$.

In the second test case, all rearrangements of $$$\texttt{aaaaa}$$$ are equal to $$$\texttt{aaaaa}$$$.

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
There is a clock labeled with the numbers $$$1$$$ through $$$12$$$ in clockwise order, as shown below.

In this example, $$$(a,b,c,d)=(2,9,10,6)$$$, and the strings intersect.

Alice and Bob have four distinct integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ not more than $$$12$$$. Alice ties a red string connecting $$$a$$$ and $$$b$$$, and Bob ties a blue string connecting $$$c$$$ and $$$d$$$. Do the strings intersect? (The strings are straight line segments.)

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

The only line of each test case contains four distinct integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$1 \leq a, b, c, d \leq 12$$$).

## Output Format
For each test case, output "YES" (without quotes) if the strings intersect, and "NO" (without quotes) otherwise.

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

## Examples
```input
15
2 9 10 6
3 8 9 1
1 2 3 4
5 3 4 12
1 8 2 10
3 12 11 8
9 10 12 1
12 1 10 2
3 12 6 9
1 9 8 4
6 7 9 12
7 12 9 6
10 12 11 1
3 9 6 12
1 4 3 5
```
```output
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
```

## Note
The first test case is pictured in the statement.

In the second test case, the strings do not intersect, as shown below.

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
You are given a binary string$$$^{\dagger}$$$. Please find the minimum number of pieces you need to cut it into, so that the resulting pieces can be rearranged into a sorted binary string.

Note that:

- each character must lie in exactly one of the pieces;
- the pieces must be contiguous substrings of the original string;
- you must use all the pieces in the rearrangement.

$$$^{\dagger}$$$ A binary string is a string consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$. A sorted binary string is a binary string such that all characters $$$\texttt{0}$$$ come before all characters $$$\texttt{1}$$$.

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

The only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 500$$$) consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$, where $$$|s|$$$ denotes the length of the string $$$s$$$.

## Output Format
For each test case, output a single integer — the minimum number of pieces needed to be able to rearrange the string into a sorted binary string.

## Examples
```input
6
11010
00000000
1
10
0001111
0110
```
```output
3
1
1
2
1
2
```

## Note
The first test case is pictured in the statement. It can be proven that you can't use fewer than $$$3$$$ pieces.

In the second and third test cases, the binary string is already sorted, so only $$$1$$$ piece is needed.

In the fourth test case, you need to make a single cut between the two characters and rearrange them to make the string $$$\texttt{01}$$$.

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 integer $$$r$$$, find the number of lattice points that have a Euclidean distance from $$$(0, 0)$$$ greater than or equal to $$$r$$$ but strictly less than $$$r+1$$$.

A lattice point is a point with integer coordinates. The Euclidean distance from $$$(0, 0)$$$ to the point $$$(x,y)$$$ is $$$\sqrt{x^2 + y^2}$$$.

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

The only line of each test case contains a single integer $$$r$$$ ($$$1 \leq r \leq 10^5$$$).

The sum of $$$r$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output a single integer — the number of lattice points that have an Euclidean distance $$$d$$$ from $$$(0, 0)$$$ such that $$$r \leq d < r+1$$$.

## Examples
```input
6
1
2
3
4
5
1984
```
```output
8
16
20
24
40
12504
```

## Note
The points for the first three test cases are shown below.

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
You are given an array $$$a$$$ consisting of $$$n$$$ nonnegative integers.

You can swap the elements at positions $$$i$$$ and $$$j$$$ if $$$a_i~\mathsf{XOR}~a_j < 4$$$, where $$$\mathsf{XOR}$$$ is the bitwise XOR operation.

Find the lexicographically smallest array that can be made with any number of swaps.

An array $$$x$$$ is lexicographically smaller than an array $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, $$$x_i < y_i$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$0 \leq a_i \leq 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 $$$n$$$ integers — the lexicographically smallest array that can be made with any number of swaps.

## Examples
```input
4
4
1 0 3 2
5
2 7 1 5 6
8
1 2 1 2 1 2 1 2
4
16 4 1 64
```
```output
0 1 2 3 
1 5 2 6 7 
1 1 1 1 2 2 2 2 
16 4 1 64
```

## Note
For the first test case, you can swap any two elements, so we can produce the sorted array.

For the second test case, you can swap $$$2$$$ and $$$1$$$ (their $$$\mathsf{XOR}$$$ is $$$3$$$), $$$7$$$ and $$$5$$$ (their $$$\mathsf{XOR}$$$ is $$$2$$$), and $$$7$$$ and $$$6$$$ (their $$$\mathsf{XOR}$$$ is $$$1$$$) to get the lexicographically smallest array.

Now solve the problem and return the code.