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
Vladislav has $$$n$$$ cards numbered $$$1, 2, \dots, n$$$. He wants to lay them down in a row as follows:

- First, he lays down all the odd-numbered cards from smallest to largest.
- Next, he lays down all cards that are twice an odd number from smallest to largest (i.e. $$$2$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$3$$$ times an odd number from smallest to largest (i.e. $$$3$$$ multiplied by an odd number).
- Next, he lays down all cards that are $$$4$$$ times an odd number from smallest to largest (i.e. $$$4$$$ multiplied by an odd number).
- And so on, until all cards are laid down.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^9$$$) — the number of cards Vlad has, and the position of the card you need to output.

## Output Format
For each test case, output a single integer — the $$$k$$$-th card Vladislav lays down.

## Examples
```input
11
7 1
7 2
7 3
7 4
7 5
7 6
7 7
1 1
34 14
84 19
1000000000 1000000000
```
```output
1
3
5
7
2
6
4
1
27
37
536870912
```

## Note
In the first seven test cases, $$$n=7$$$. Vladislav lays down the cards as follows:

- First — all the odd-numbered cards in the order $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.
- Next — all cards that are twice an odd number in the order $$$2$$$, $$$6$$$.
- Next, there are no remaining cards that are $$$3$$$ times an odd number. (Vladislav has only one of each card.)
- Next — all cards that are $$$4$$$ times an odd number, and there is only one such card: $$$4$$$.
- There are no more cards left, so Vladislav stops.

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
Vladislav has a grid of size $$$7 \times 7$$$, where each cell is colored black or white. In one operation, he can choose any cell and change its color (black $$$\leftrightarrow$$$ white).

Find the minimum number of operations required to ensure that there are no black cells with four diagonal neighbors also being black.

The left image shows that initially there are two black cells violating the condition. By flipping one cell, the grid will work.

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

Each test case consists of $$$7$$$ lines, each containing $$$7$$$ characters. Each of these characters is either $$$\texttt{W}$$$ or $$$\texttt{B}$$$, denoting a white or black cell, respectively.

## Output Format
For each test case, output a single integer — the minimum number of operations required to ensure that there are no black cells with all four diagonal neighbors also being black.

## Examples
```input
4
WWWWWWW
WWWWBBB
WWWWWBW
WWBBBBB
WWWBWWW
WWBBBWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
WBBBBBW
WBBBBBW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
BBBBBBB
BBBBBBB
WWWWWWW
BBBBBBB
BBBBBBB
BBBBBBB
```
```output
1
2
0
5
```

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

The second test case is illustrated below:

In the third test case, the grid already satisfies the condition.

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
Vladislav has a son who really wanted to go to MIT. The college dormitory at MIT (Moldova Institute of Technology) can be represented as a tree with $$$n$$$ vertices, each vertex being a room with exactly one student. A tree is a connected undirected graph with $$$n$$$ vertices and $$$n-1$$$ edges.

Tonight, there are three types of students:

- students who want to party and play music (marked with $$$\texttt{P}$$$),
- students who wish to sleep and enjoy silence (marked with $$$\texttt{S}$$$), and
- students who don't care (marked with $$$\texttt{C}$$$).

Initially, all the edges are thin walls which allow music to pass through, so when a partying student puts music on, it will be heard in every room. However, we can place some thick walls on any edges — thick walls don't allow music to pass through them.

The university wants to install some thick walls so that every partying student can play music, and no sleepy student can hear it.

Because the university lost a lot of money in a naming rights lawsuit, they ask you to find the minimum number of thick walls they will need to use.

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The second line of each test case contains $$$n-1$$$ integers $$$a_2, \dots , a_n$$$ ($$$1 \leq a_i < i$$$) — it means there is an edge between $$$i$$$ and $$$a_i$$$ in the tree.

The third line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{P}$$$, $$$\texttt{S}$$$, and $$$\texttt{C}$$$, denoting that student $$$i$$$ is of type $$$s_i$$$.

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

## Output Format
For each test case, output a single integer — the minimum number of thick walls needed.

## Examples
```input
3
3
1 1
CSP
4
1 2 2
PCSS
4
1 2 2
PPSS
```
```output
1
1
2
```

## Note
In the first case, we can install one thick wall between rooms $$$1$$$ and $$$2$$$, as shown below. We cannot install $$$0$$$ walls, since then the music from room 3 will reach room 2 where a student wants to sleep, so the answer is $$$1$$$. There are other valid solutions.

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 are $$$n$$$ islands, numbered $$$1, 2, \ldots, n$$$. Initially, every pair of islands is connected by a bridge. Hence, there are a total of $$$\frac{n (n - 1)}{2}$$$ bridges.

Everule lives on island $$$1$$$ and enjoys visiting the other islands using bridges. Dominater has the power to destroy at most $$$k$$$ bridges to minimize the number of islands that Everule can reach using (possibly multiple) bridges.

Find the minimum number of islands (including island $$$1$$$) that Everule can visit if Dominater destroys bridges optimally.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le \frac{n \cdot (n - 1)}{2}$$$).

## Output Format
For each test case, output the minimum number of islands that Everule can visit if Dominater destroys bridges optimally.

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

## Note
In the first test case, since no bridges can be destroyed, all the islands will be reachable.

In the second test case, you can destroy the bridge between islands $$$1$$$ and $$$2$$$. Everule will not be able to visit island $$$2$$$ but can still visit island $$$1$$$. Therefore, the total number of islands that Everule can visit is $$$1$$$.

In the third test case, Everule always has a way of reaching all islands despite what Dominater does. For example, if Dominater destroyed the bridge between islands $$$1$$$ and $$$2$$$, Everule can still visit island $$$2$$$ by traveling by $$$1 \to 3 \to 2$$$ as the bridges between $$$1$$$ and $$$3$$$, and between $$$3$$$ and $$$2$$$ are not destroyed.

In the fourth test case, you can destroy all bridges since $$$k = \frac{n \cdot (n - 1)}{2}$$$. Everule will be only able to visit $$$1$$$ island (island $$$1$$$).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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 array $$$a$$$ of length $$$2n$$$, consisting of each integer from $$$1$$$ to $$$n$$$ exactly twice.

You are also given an integer $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).

You need to find two arrays $$$l$$$ and $$$r$$$ each of length $$$\mathbf{2k}$$$ such that:

- $$$l$$$ is a subset$$$^\dagger$$$ of $$$[a_1, a_2, \ldots a_n]$$$
- $$$r$$$ is a subset of $$$[a_{n+1}, a_{n+2}, \ldots a_{2n}]$$$
- bitwise XOR of elements of $$$l$$$ is equal to the bitwise XOR of elements of $$$r$$$; in other words, $$$l_1 \oplus l_2 \oplus \ldots \oplus l_{2k} = r_1 \oplus r_2 \oplus \ldots \oplus r_{2k}$$$

It can be proved that at least one pair of $$$l$$$ and $$$r$$$ always exists. If there are multiple solutions, you may output any one of them.

$$$^\dagger$$$ A sequence $$$x$$$ is a subset of a sequence $$$y$$$ if $$$x$$$ can be obtained by deleting several (possibly none or all) elements of $$$y$$$ and rearranging the elements in any order. For example, $$$[3,1,2,1]$$$, $$$[1, 2, 3]$$$, $$$[1, 1]$$$ and $$$[3, 2]$$$ are subsets of $$$[1, 1, 2, 3]$$$ but $$$[4]$$$ and $$$[2, 2]$$$ are not subsets of $$$[1, 1, 2, 3]$$$.

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

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5 \cdot 10^4$$$, $$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).

The second line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that every integer from $$$1$$$ to $$$n$$$ occurs exactly twice in $$$a$$$.

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

## Output Format
For each test case, output two lines.

On the first line of output, output $$$2k$$$ integers $$$l_1, l_2, \ldots, l_{2k}$$$.

On the second line of output, output $$$2k$$$ integers $$$r_1, r_2, \ldots r_{2k}$$$.

If there are multiple solutions, you may output any one of them.

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

## Note
In the first test case, we choose $$$l=[2,1]$$$ and $$$r=[2,1]$$$. $$$[2, 1]$$$ is a subset of $$$[a_1, a_2]$$$ and $$$[2, 1]$$$ is a subset of $$$[a_3, a_4]$$$, and $$$2 \oplus 1 = 2 \oplus 1 = 3$$$.

In the second test case, $$$6 \oplus 4 = 1 \oplus 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: 256.0 MB

# Problem
You are swimming in the pool, and you need to control the time of swimming.

The pool has a clock that cycles between three different modes: showing water temperature, showing air temperature, and showing time. At the start of the $$$0$$$-th second it starts showing water temperature, at the start of the $$$k$$$-th second it switches to air temperature. At the start of the $$$2k$$$-th second, it switches to showing time.

At the start of the $$$3k$$$-th second the clock starts showing water temperature again, at the start of the $$$4k$$$-th second — air temperature, and so on.

You looked at the clock during the $$$m$$$-th second to check the time, but it may be that the clock is not showing time right now. How much time do you have to wait to see the time on the clock?

Answer $$$t$$$ independent test cases.

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

The first and only line of each test case contains two integers $$$k$$$ and $$$m$$$ ($$$1 \le k \le 10^8; 1 \le m \le 10^9$$$) — the length of the period of the clock and the moment of time you check the clock.

## Output Format
For each test case, print a single integer — the time you have to wait from the moment $$$m$$$ until the moment the clock starts showing the time.

You can assume that you are able to read the time instantly the moment it displays on the clock.

## Examples
```input
5
1 1
5 14
5 15
10 110
99999999 1000000000
```
```output
1
0
10
0
99999989
```

## Note
In the first test case, the clock will start showing time during the $$$2$$$-nd second, so you have to wait $$$2 - 1 = 1$$$ second.

In the second test case, the clock shows time from the $$$10$$$-th until the $$$15$$$-th second, so during the $$$14$$$-th second it shows time, and you don't have to wait.

In the third test case, during the $$$15$$$-th second, the clock is already showing water temperature. So you have to wait till the $$$25$$$-th second, when the clock starts showing time again. You'll wait $$$25 - 15 = 10$$$ seconds.

In the fourth test case, the clock will start showing time at the start of the $$$110$$$-th second, so you'll wait $$$110 - 110 = 0$$$ seconds.

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
It's pretty cold in Berland (yes, even in May). So Monocarp has to light his fireplace.

Monocarp has a big log of wood, which weighs $$$2^n$$$ grams. Monocarp has watched the weather forecast and decided that he has to burn $$$k$$$ grams of wood in the fireplace today, and the remaining $$$2^n-k$$$ grams of wood will be used tomorrow.

In one minute, Monocarp can use his saw to split one of his logs in half. Initially he has only one log, but of course, after splitting a log, he gets two new logs. If the weight of the log is $$$x$$$, then each of the resulting logs has weight equal to $$$\frac{x}{2}$$$. Monocarp can't split logs of weight $$$1$$$ gram.

Monocarp has to cut his log in such a way that some of the resulting logs weigh exactly $$$k$$$ grams in total (and since the total weight of wood doesn't change, the remaining logs will have a total weight equal to exactly $$$2^n-k$$$). Help him to calculate the minimum number of minutes he has to spend cutting the logs.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 60$$$; $$$1 \le k \le 2^n-1$$$).

## Output Format
For each test case, print one integer — the minimum number of minutes Monocarp has to spend splitting the wood.

## Examples
```input
4
2 2
2 1
10 3
50 36679020707840
```
```output
1
2
10
16
```

## Note
In the first test case, Monocarp has to cut his log exactly once. Then he will have two logs weighing $$$2$$$ grams each.

In the second test case, Monocarp has to cut his log of $$$4$$$ grams once, then cut one of the resulting logs. He will have one log of weight $$$2$$$ and two logs of weight $$$1$$$, so he can use two logs to get exactly $$$3$$$ grams.

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 staircase consisting of $$$n$$$ steps. Each step is either intact, or broken. For each broken step, an integer $$$a_i$$$ is given denoting the difficulty of repairing it.

Every day, you can either:

- repair an arbitrary broken step. The effort it takes to repair the $$$i$$$-th step is equal to $$$a_i$$$;
- or repair two adjacent broken steps. The effort it takes to repair both the $$$i$$$-th step and the $$$(i+1)$$$-th step is equal to $$$2 \cdot (a_i+a_{i+1})$$$.

You want to repair all broken steps of the staircase, and you want to do it in the minimum possible number of days. What is the minimum total effort it will take to repair all broken steps in the minimum number of days?

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

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of steps;
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$). If $$$a_i = 0$$$, then the $$$i$$$-th step does not need to be repaired; otherwise, the $$$i$$$-th step is broken and $$$a_i$$$ is the difficulty of repairing it.

Additional constraint on the input: the sum of values of $$$n$$$ does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the minimum possible total effort it will take to repair all broken steps in the minimum number of days.

## Examples
```input
6
5
0 0 0 0 0
4
0 13 15 8
4
13 15 0 8
8
1 2 3 4 5 6 7 8
5
99999999 100000000 99999999 99999999 99999999
5
2 3 4 3 2
```
```output
0
59
64
72
899999993
24
```

## Note
In the first test case, you don't have to do anything.

In the second test case, you can repair the $$$3$$$-rd and the $$$4$$$-th step during the first day, and the $$$2$$$-nd step during the second day. The total effort will be $$$2 \cdot (15 + 8) + 13 = 59$$$.

In the third test case, you can repair the $$$4$$$-th step during the first day, and two first steps during the second day. The total effort will be $$$8 + 2 \cdot (13 + 15) = 64$$$.

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
Suppose you have a permutation $$$p$$$ of $$$n$$$ integers — an array where each element is an integer from $$$1$$$ to $$$n$$$, and every integer from $$$1$$$ to $$$n$$$ appears exactly once.

In one operation, you remove every element of this permutation which is less than at least one of its neighbors. For example, when you apply the operation to $$$[3, 1, 2, 5, 4]$$$, you get $$$[3, 5]$$$. If you apply an operation again, you get $$$[5]$$$.

It's easy to see that after applying a finite number of operations, you get an array consisting of a single integer $$$n$$$.

You are given two integers $$$n$$$ and $$$k$$$. Find a permutation of $$$n$$$ integers such that it becomes an array consisting of a single element $$$n$$$ after exactly $$$k$$$ operations (and not earlier).

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$1 \le k \le n - 1$$$).

## Output Format
For each test case, print the answer as follows:

- if a permutation of size $$$n$$$ which becomes an array consisting of a single element $$$n$$$ after exactly $$$k$$$ operations does not exist, print $$$-1$$$;
- otherwise, print $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ — the requested permutation. If there are multiple such permutations, print any of them.

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

Now solve the problem and return the code.