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

# Problem
Vlad came home and found out that someone had reconfigured the old thermostat to the temperature of $$$a$$$.

The thermostat can only be set to a temperature from $$$l$$$ to $$$r$$$ inclusive, the temperature cannot change by less than $$$x$$$. Formally, in one operation you can reconfigure the thermostat from temperature $$$a$$$ to temperature $$$b$$$ if $$$|a - b| \ge x$$$ and $$$l \le b \le r$$$.

You are given $$$l$$$, $$$r$$$, $$$x$$$, $$$a$$$ and $$$b$$$. Find the minimum number of operations required to get temperature $$$b$$$ from temperature $$$a$$$, or say that it is impossible.

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

The descriptions of the test cases follow.

The first line of each case contains three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$-10^9 \le l \le r \le 10^9$$$, $$$1 \le x \le 10^9$$$) — range of temperature and minimum temperature change.

The second line of each case contains two integers $$$a$$$ and $$$b$$$ ($$$l \le a, b \le r$$$) — the initial and final temperatures.

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case. If it is impossible to achieve the temperature $$$b$$$, output -1, otherwise output the minimum number of operations.

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

## Note
In the first example, the thermostat is already set up correctly.

In the second example, you can achieve the desired temperature as follows: $$$4 \rightarrow 10 \rightarrow 5$$$.

In the third example, you can achieve the desired temperature as follows: $$$3 \rightarrow 8 \rightarrow 2 \rightarrow 7$$$.

In the fourth test, it is impossible to make any operation.

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
Inflation has occurred in Berlandia, so the store needs to change the price of goods.

The current price of good $$$n$$$ is given. It is allowed to increase the price of the good by $$$k$$$ times, with $$$1 \le k \le m$$$, k is an integer. Output the roundest possible new price of the good. That is, the one that has the maximum number of zeros at the end.

For example, the number 481000 is more round than the number 1000010 (three zeros at the end of 481000 and only one at the end of 1000010).

If there are several possible variants, output the one in which the new price is maximal.

If it is impossible to get a rounder price, output $$$n \cdot m$$$ (that is, the maximum possible price).

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

Each test case consists of one line.

This line contains two integers: $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$). Where $$$n$$$ is the old price of the good, and the number $$$m$$$ means that you can increase the price $$$n$$$ no more than $$$m$$$ times.

## Output Format
For each test case, output on a separate line the roundest integer of the form $$$n \cdot k$$$ ($$$1 \le k \le m$$$, $$$k$$$ — an integer).

If there are several possible variants, output the one in which the new price (value $$$n \cdot k$$$) is maximal.

If it is impossible to get a more rounded price, output $$$n \cdot m$$$ (that is, the maximum possible price).

## Examples
```input
10
6 11
5 43
13 5
4 16
10050 12345
2 6
4 30
25 10
2 81
1 7
```
```output
60
200
65
60
120600000
10
100
200
100
7
```

## Note
In the first case $$$n = 6$$$, $$$m = 11$$$. We cannot get a number with two zeros or more at the end, because we need to increase the price $$$50$$$ times, but $$$50 > m = 11$$$. The maximum price multiple of $$$10$$$ would be $$$6 \cdot 10 = 60$$$.

In the second case $$$n = 5$$$, $$$m = 43$$$. The maximum price multiple of $$$100$$$ would be $$$5 \cdot 40 = 200$$$.

In the third case, $$$n = 13$$$, $$$m = 5$$$. All possible new prices will not end in $$$0$$$, then you should output $$$n \cdot m = 65$$$.

In the fourth case, you should increase the price $$$15$$$ times.

In the fifth case, increase the price $$$12000$$$ times.

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
A positive number $$$x$$$ of length $$$n$$$ in base $$$p$$$ ($$$2 \le p \le 10^9$$$) is written on the blackboard. The number $$$x$$$ is given as a sequence $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — the digits of $$$x$$$ in order from left to right (most significant to least significant).

Dmitry is very fond of all the digits of this number system, so he wants to see each of them at least once.

In one operation, he can:

- take any number $$$x$$$ written on the board, increase it by $$$1$$$, and write the new value $$$x + 1$$$ on the board.

For example, $$$p=5$$$ and $$$x=234_5$$$.

- Initially, the board contains the digits $$$2$$$, $$$3$$$ and $$$4$$$;
- Dmitry increases the number $$$234_5$$$ by $$$1$$$ and writes down the number $$$240_5$$$. On the board there are digits $$$0, 2, 3, 4$$$;
- Dmitry increases the number $$$240_5$$$ by $$$1$$$ and writes down the number $$$241_5$$$. Now the board contains all the digits from $$$0$$$ to $$$4$$$.

Your task is to determine the minimum number of operations required to make all the digits from $$$0$$$ to $$$p-1$$$ appear on the board at least once.

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^3$$$) — the number of test cases. The descriptions of the input test cases follow.

The first line of description of each test case contains two integers $$$n$$$ ($$$1 \le n \le 100$$$) and $$$p$$$ ($$$2 \le p \le 10^9$$$) — the length of the number and the base of the number system.

The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) — digits of $$$x$$$ in number system with base $$$p$$$

It is guaranteed that the number $$$x$$$ does not contain leading zeros (that is, $$$a_1>0$$$).

## Output Format
For each test case print a single integer — the minimum number of operations required for Dmitry to get all the digits on the board from $$$0$$$ to $$$p-1$$$.

It can be shown that this always requires a finite number of operations.

## Examples
```input
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
```
```output
1
1
0
0
7
995
2
1
1
1
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A sequence of $$$n$$$ numbers is called permutation if it contains all numbers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences [$$$3, 1, 4, 2$$$], [$$$1$$$] and [$$$2,1$$$] are permutations, but [$$$1,2,1$$$], [$$$0,1$$$] and [$$$1,3,4$$$] — are not.

For a permutation $$$p$$$ of even length $$$n$$$ you can make an array $$$b$$$ of length $$$\frac{n}{2}$$$ such that:

- $$$b_i = \max(p_{2i - 1}, p_{2i})$$$ for $$$1 \le i \le \frac{n}{2}$$$

For example, if $$$p$$$ = [$$$2, 4, 3, 1, 5, 6$$$], then:

- $$$b_1 = \max(p_1, p_2) = \max(2, 4) = 4$$$
- $$$b_2 = \max(p_3, p_4) = \max(3,1)=3$$$
- $$$b_3 = \max(p_5, p_6) = \max(5,6) = 6$$$

For a given array $$$b$$$, find the lexicographically minimal permutation $$$p$$$ such that you can make the given array $$$b$$$ from it.

If $$$b$$$ = [$$$4,3,6$$$], then the lexicographically minimal permutation from which it can be made is $$$p$$$ = [$$$1,4,2,3,5,6$$$], since:

- $$$b_1 = \max(p_1, p_2) = \max(1, 4) = 4$$$
- $$$b_2 = \max(p_3, p_4) = \max(2, 3) = 3$$$
- $$$b_3 = \max(p_5, p_6) = \max(5, 6) = 6$$$

A permutation $$$x_1, x_2, \dots, x_n$$$ is lexicographically smaller than a permutation $$$y_1, y_2 \dots, y_n$$$ if and only if there exists such $$$i$$$ ($$$1 \le i \le n$$$) that $$$x_1=y_1, x_2=y_2, \dots, x_{i-1}=y_{i-1}$$$ and $$$x_i<y_i$$$.

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

The description of the test cases follows.

The first line of each test case contains one even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains exactly $$$\frac{n}{2}$$$ integers $$$b_i$$$ ($$$1 \le b_i \le n$$$) — elements of array $$$b$$$.

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

## Output Format
For each test case, print on a separate line:

- lexicographically minimal permutation $$$p$$$ such that you can make an array $$$b$$$ from it;
- or a number -1 if the permutation you are looking for does not exist.

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

## Note
The first test case is parsed in the problem statement.

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 array $$$a$$$ of $$$n$$$ integers.

Find two permutations$$$^\dagger$$$ $$$p$$$ and $$$q$$$ of length $$$n$$$ such that $$$\max(p_i,q_i)=a_i$$$ for all $$$1 \leq i \leq n$$$ or report that such $$$p$$$ and $$$q$$$ do not exist.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — the array $$$a$$$.

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

## Output Format
For each test case, if there do not exist $$$p$$$ and $$$q$$$ that satisfy the conditions, output "NO" (without quotes).

Otherwise, output "YES" (without quotes) and then output $$$2$$$ lines. The first line should contain $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ and the second line should contain $$$n$$$ integers $$$q_1,q_2,\ldots,q_n$$$.

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

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
3
1
1
5
5 3 4 2 5
2
1 1
```
```output
YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO
```

## Note
In the first test case, $$$p=q=[1]$$$. It is correct since $$$a_1 = max(p_1,q_1) = 1$$$.

In the second test case, $$$p=[1,3,4,2,5]$$$ and $$$q=[5,2,3,1,4]$$$. It is correct since:

- $$$a_1 = \max(p_1, q_1) = \max(1, 5) = 5$$$,
- $$$a_2 = \max(p_2, q_2) = \max(3, 2) = 3$$$,
- $$$a_3 = \max(p_3, q_3) = \max(4, 3) = 4$$$,
- $$$a_4 = \max(p_4, q_4) = \max(2, 1) = 2$$$,
- $$$a_5 = \max(p_5, q_5) = \max(5, 4) = 5$$$.

In the third test case, one can show that no such $$$p$$$ and $$$q$$$ exist.

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 permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$.

In one operation, you can choose two indices $$$1 \le i < j \le n$$$ and swap $$$p_i$$$ with $$$p_j$$$.

Find the minimum number of operations needed to have exactly one inversion$$$^\ddagger$$$ in the permutation.

$$$^\dagger$$$ A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

$$$^\ddagger$$$ The number of inversions of a permutation $$$p$$$ is the number of pairs of indices $$$(i, j)$$$ such that $$$1 \le i < j \le n$$$ and $$$p_i > p_j$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$). It is guaranteed that $$$p$$$ is a permutation.

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 a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

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

## Note
In the first test case, the permutation already satisfies the condition.

In the second test case, you can perform the operation with $$$(i,j)=(1,2)$$$, after that the permutation will be $$$[2,1]$$$ which has exactly one inversion.

In the third test case, it is not possible to satisfy the condition with less than $$$3$$$ operations. However, if we perform $$$3$$$ operations with $$$(i,j)$$$ being $$$(1,3)$$$,$$$(2,4)$$$, and $$$(3,4)$$$ in that order, the final permutation will be $$$[1, 2, 4, 3]$$$ which has exactly one inversion.

In the fourth test case, you can perform the operation with $$$(i,j)=(2,4)$$$, after that the permutation will be $$$[2,1,3,4]$$$ which has exactly one inversion.

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.5 seconds
Memory limit: 1024.0 MB

# Problem
Consider a permutation$$$^\dagger$$$ $$$p$$$ of length $$$3n$$$. Each time you can do one of the following operations:

- Sort the first $$$2n$$$ elements in increasing order.
- Sort the last $$$2n$$$ elements in increasing order.

We can show that every permutation can be made sorted in increasing order using only these operations. Let's call $$$f(p)$$$ the minimum number of these operations needed to make the permutation $$$p$$$ sorted in increasing order.

Given $$$n$$$, find the sum of $$$f(p)$$$ over all $$$(3n)!$$$ permutations $$$p$$$ of size $$$3n$$$.

Since the answer could be very large, output it modulo a prime $$$M$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

## Input Format
The only line of input contains two numbers $$$n$$$ and $$$M$$$ ($$$1 \leq n \leq 10^6$$$, $$$10^8 \leq M \leq 10^9$$$). It is guaranteed that $$$M$$$ is a prime number.

## Output Format
Output the answer modulo $$$M$$$.

## Examples
```input
1 100009067
```
```output
9
```
-----
```input
2 100000357
```
```output
1689
```
-----
```input
69 999900997
```
```output
193862705
```

## Note
In the first test case, all the permutations are:

- $$$[1, 2, 3]$$$, which requires $$$0$$$ operations;
- $$$[1, 3, 2]$$$, which requires $$$1$$$ operation;
- $$$[2, 1, 3]$$$, which requires $$$1$$$ operation;
- $$$[2, 3, 1]$$$, which requires $$$2$$$ operations;
- $$$[3, 1, 2]$$$, which requires $$$2$$$ operations;
- $$$[3, 2, 1]$$$, which requires $$$3$$$ operations.

Therefore, the answer is $$$0+1+1+2+2+3=9$$$.

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: 128.0 MB

# Problem
You are given an array of positive integers $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$.

In one operation you can jump from index $$$i$$$ to index $$$j$$$ ($$$1 \le i \le j \le n$$$) by paying $$$\min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2$$$ eris.

For all $$$k$$$ from $$$1$$$ to $$$n$$$, find the minimum number of eris needed to get from index $$$1$$$ to index $$$k$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$).

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

## Output Format
Output $$$n$$$ integers — the $$$k$$$-th integer is the minimum number of eris needed to reach index $$$k$$$ if you start from index $$$1$$$.

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

## Note
In the first example:

- From $$$1$$$ to $$$1$$$: the cost is $$$0$$$,
- From $$$1$$$ to $$$2$$$: $$$1 \rightarrow 2$$$ — the cost is $$$\min(2, 1) \cdot (2 - 1) ^ 2=1$$$,
- From $$$1$$$ to $$$3$$$: $$$1 \rightarrow 2 \rightarrow 3$$$ — the cost is $$$\min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2$$$.

In the fourth example from $$$1$$$ to $$$4$$$: $$$1 \rightarrow 3 \rightarrow 4$$$ — the cost is $$$\min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8$$$.

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
Reve has two integers $$$n$$$ and $$$k$$$.

Let $$$p$$$ be a permutation$$$^\dagger$$$ of length $$$n$$$. Let $$$c$$$ be an array of length $$$n - k + 1$$$ such that $$$$$$c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots, p_{i+k-1}).$$$$$$ Let the cost of the permutation $$$p$$$ be the maximum element of $$$c$$$.

Koxia wants you to construct a permutation with the minimum possible cost.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

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

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 $$$p_1,p_2,\dots,p_n$$$, which is a permutation with minimal cost. If there is more than one permutation with minimal cost, you may output any of them.

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

## Note
In the first test case,

- $$$c_1 = \max(p_1,p_2,p_3) + \min(p_1,p_2,p_3) = 5 + 1 = 6$$$.
- $$$c_2 = \max(p_2,p_3,p_4) + \min(p_2,p_3,p_4) = 3 + 1 = 4$$$.
- $$$c_3 = \max(p_3,p_4,p_5) + \min(p_3,p_4,p_5) = 4 + 2 = 6$$$.

Therefore, the cost is $$$\max(6,4,6)=6$$$. It can be proven that this is the minimal cost.

Now solve the problem and return the code.