apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Monocarp is wandering through a matrix consisting of $$$2$$$ rows and $$$n$$$ columns. Let's denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i, j)$$$. Monocarp starts at cell $$$(1, 1)$$$ and wants to reach cell $$$(2, n)$$$.

In one move, Monocarp can move in one of two directions:

- right — from cell $$$(i, j)$$$ to cell $$$(i, j + 1)$$$;
- down — from cell $$$(i, j)$$$ to cell $$$(i + 1, j)$$$.

Monocarp can't go outside the matrix.

Polycarp wants to prevent Monocarp from freely wandering through the matrix. To do this, he wants to choose exactly $$$k$$$ different cells in the matrix and block them. He cannot choose cells $$$(1, 1)$$$ and $$$(2, n)$$$.

For each $$$i$$$ from $$$0$$$ to $$$n$$$, Polycarp wants to know how many ways he can block exactly $$$k$$$ cells, so that Monocarp has exactly $$$i$$$ different paths from $$$(1, 1)$$$ to $$$(2, n)$$$. Two paths are considered different if there exists a cell that Monocarp visits in one path but not in the other.

As the number of ways can be quite large, output it modulo $$$10^9 + 7$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 2 \cdot n - 2$$$) — the number of columns in the matrix and the number of cells Polycarp wants to block.

## Output Format
Output $$$n + 1$$$ integers: for each $$$i$$$ from $$$0$$$ to $$$n$$$, the number of ways to block exactly $$$k$$$ cells, so that Monocarp has exactly $$$i$$$ different paths from $$$(1, 1)$$$ to $$$(2, n)$$$. Output all answers modulo $$$10^9 + 7$$$.

## Examples
```input
2 2
```
```output
1 0 0
```
-----
```input
10 2
```
```output
45 24 21 18 15 12 9 6 3 0 0
```
-----
```input
10 5
```
```output
7812 420 210 90 30 6 0 0 0 0 0
```
-----
```input
22 10
```
```output
467563090 1847560 1016158 534820 267410 125840 55055 22022 7865 2420 605 110 11 0 0 0 0 0 0 0 0 0 0
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a segment of an OX axis from $$$1$$$ to $$$n$$$. There are $$$k$$$ observation towers on this segment.

Each tower has two parameters — the coordinate $$$x_i$$$ and the height $$$h_i$$$. The coordinates of all towers are distinct. From tower $$$i$$$, you can see point $$$j$$$ if $$$|x_i - j| \le h_i$$$ (where $$$|a|$$$ is an absolute value of $$$a$$$).

You can increase the height of any tower by $$$1$$$ for one coin. The height of each tower can be increased any number of times (including zero).

You need to process $$$q$$$ independent queries. In the $$$i$$$-th query, two different points $$$l$$$ and $$$r$$$ are given. You need to calculate the minimum number of coins required to be able to see both of these points (from one tower or from different towers).

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the length of the segment of an OX axis and the number of observation towers.

The second line contains $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le n$$$) — the coordinates of the observation towers. The coordinates of all towers are distinct.

The third line contains $$$k$$$ integers $$$h_1, h_2, \dots, h_k$$$ ($$$0 \le h_i \le n$$$) — the heights of the observation towers.

The fourth line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) — the description of the next query.

## Output Format
For each query, output a single integer — the minimum number of coins required to be able to see both points (from one tower or from different towers).

## Examples
```input
20 3
2 15 10
6 2 0
3
1 20
10 11
3 4
```
```output
3 1 0
```
-----
```input
10 2
2 9
1 2
3
4 5
5 6
1 10
```
```output
2 2 0
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two rooted trees, consisting of $$$n$$$ vertices each. The vertices in the trees are numbered from $$$1$$$ to $$$n$$$, and the root is the vertex $$$1$$$.

You can perform the following operation: choose the tree and the vertex $$$v$$$ (except the root of the tree) in it; connect the child nodes of $$$v$$$ to the parent of $$$v$$$ and remove $$$v$$$ from the tree.

Let's say that two trees are equal if both of the following conditions hold:

- the sets of remaining vertices in both trees are the same;
- for every vertex $$$v$$$ which is not deleted, its parent in the first tree is the same as its parent in the second tree.

Your task is to calculate the minimum number of aforementioned operation in order to make the trees equal.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 40$$$) — the number of vertices in the trees.

The second line contains $$$n-1$$$ integers $$$a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ the parent of the $$$i$$$-th vertex in the first tree. Vertex $$$1$$$ is the root.

The third line contains $$$n-1$$$ integers $$$b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le n$$$), where $$$b_i$$$ the parent of the $$$i$$$-th vertex in the second tree. Vertex $$$1$$$ is the root.

## Output Format
Print a single integer — the minimum number of aforementioned operation in order to make the trees equal.

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

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
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 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
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 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
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 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
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 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: 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 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 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 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
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.