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
After a team finished their training session on Euro football championship, Valeric was commissioned to gather the balls and sort them into baskets. Overall the stadium has n balls and m baskets. The baskets are positioned in a row from left to right and they are numbered with numbers from 1 to m, correspondingly. The balls are numbered with numbers from 1 to n.

Valeric decided to sort the balls in the order of increasing of their numbers by the following scheme. He will put each new ball in the basket with the least number of balls. And if he's got several variants, he chooses the basket which stands closer to the middle. That means that he chooses the basket for which $$\left|\frac{m+1}{2}-i\right|$$ is minimum, where i is the number of the basket. If in this case Valeric still has multiple variants, he chooses the basket with the minimum number.

For every ball print the number of the basket where it will go according to Valeric's scheme.

Note that the balls are sorted into baskets in the order of increasing numbers, that is, the first ball goes first, then goes the second ball and so on.

## Input Format
The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105) — the number of balls and baskets, correspondingly.

## Output Format
Print n numbers, one per line. The i-th line must contain the number of the basket for the i-th ball.

## Examples
```input
4 3
```
```output
2
1
3
2
```
-----
```input
3 1
```
```output
1
1
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
As Valeric and Valerko were watching one of the last Euro Championship games in a sports bar, they broke a mug. Of course, the guys paid for it but the barman said that he will let them watch football in his bar only if they help his son complete a programming task. The task goes like that.

Let's consider a set of functions of the following form:

$$y_i(x) = \begin{cases} 
k_i \cdot x + b_i, & \text{if } k_i \cdot x + b_i \geq 0; \\
0, & \text{if } k_i \cdot x + b_i < 0.
\end{cases}$$

Valeric and Valerko really want to watch the next Euro Championship game, so they asked you to help them.

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of functions. Each of the following n lines contains two space-separated integer numbers ki, bi ( - 109 ≤ ki, bi ≤ 109) that determine the i-th function.

## Output Format
Print a single number — the number of angles that do not equal 180 degrees in the graph of the polyline that equals the sum of the given functions.

## Examples
```input
1
1 0
```
```output
1
```
-----
```input
3
1 0
0 2
-1 1
```
```output
2
```
-----
```input
3
-2 -4
1 7
-5 1
```
```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: 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 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
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 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 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 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
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.
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 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 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: 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 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 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: 15.0 seconds
Memory limit: 1024.0 MB

# Problem
Let $$$p_1, \ldots, p_n$$$ be a permutation of $$$[1, \ldots, n]$$$.

Let the $$$q$$$-subsequence of $$$p$$$ be a permutation of $$$[1, q]$$$, whose elements are in the same relative order as in $$$p_1, \ldots, p_n$$$. That is, we extract all elements not exceeding $$$q$$$ together from $$$p$$$ in the original order, and they make the $$$q$$$-subsequence of $$$p$$$.

For a given array $$$a$$$, let $$$pre(i)$$$ be the largest value satisfying $$$pre(i) < i$$$ and $$$a_{pre(i)} > a_i$$$. If it does not exist, let $$$pre(i) = -10^{100}$$$. Let $$$nxt(i)$$$ be the smallest value satisfying $$$nxt(i) > i$$$ and $$$a_{nxt(i)} > a_i$$$. If it does not exist, let $$$nxt(i) = 10^{100}$$$.

For each $$$q$$$ such that $$$1 \leq q \leq n$$$, let $$$a_1, \ldots, a_q$$$ be the $$$q$$$-subsequence of $$$p$$$. For each $$$i$$$ such that $$$1 \leq i \leq q$$$, $$$pre(i)$$$ and $$$nxt(i)$$$ will be calculated as defined. Then, you will be given some integer values of $$$x$$$, and for each of them you have to calculate $$$\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the initial permutation.

Then, for each $$$q$$$ such that $$$1 \leq q \leq n$$$ in ascending order, you will be given an integer $$$k$$$ ($$$0 \leq k \leq 10^5$$$), representing the number of queries for the $$$q$$$-subsequence. Then $$$k$$$ numbers in a line follow: each of them is the value of $$$x$$$ for a single query ($$$1 \leq x \leq q$$$).

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

## Output Format
For each test case, for each query, print a single line with an integer: the answer to the query.

## Examples
```input
1
7
6 1 4 3 2 5 7
1 1
0
1 3
1 2
3 1 2 3
1 3
2 2 6
```
```output
1
9
8
5
10
14
16
14
30
```

## Note
The $$$1$$$-subsequence is $$$[1]$$$, and $$$pre=[-10^{100}]$$$, $$$nxt=[10^{100}]$$$. $$$ans(1)=\min(10^{100}-(-10^{100}),1)=1$$$.

The $$$5$$$-subsequence is $$$[1,4,3,2,5]$$$, and $$$pre=[-10^{100},-10^{100},2,3,-10^{100}]$$$, $$$nxt=[2,5,5,5,10^{100}]$$$. $$$ans(1)=5,ans(2)=10,ans(3)=14$$$.

Now solve the problem and return the code.