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

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

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

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Consider an array $$$a$$$ of $$$n$$$ integers, where every element is from $$$1$$$ to $$$k$$$, and every integer from $$$1$$$ to $$$k$$$ appears at least once.

Let the array $$$b$$$ be constructed as follows: for the $$$i$$$-th element of $$$a$$$, $$$b_i$$$ is the distance to the closest element in $$$a$$$ which is not equal to $$$a_i$$$. In other words, $$$b_i = \min \limits_{j \in [1, n], a_j \ne a_i} |i - j|$$$.

For example, if $$$a = [1, 1, 2, 3, 3, 3, 3, 1]$$$, then $$$b = [2, 1, 1, 1, 2, 2, 1, 1]$$$.

Calculate the number of different arrays $$$b$$$ you can obtain if you consider all possible arrays $$$a$$$, and print it modulo $$$998244353$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le \min(n, 10)$$$).

## Output Format
Print one integer — the number of different arrays $$$b$$$ you can obtain, taken modulo $$$998244353$$$.

## Examples
```input
2 2
```
```output
1
```
-----
```input
4 3
```
```output
3
```
-----
```input
6 2
```
```output
20
```
-----
```input
6 5
```
```output
3
```
-----
```input
133 7
```
```output
336975971
```

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vitaly503 is given a checkered board with a side of $$$n$$$ and $$$k$$$ chips. He realized that all these $$$k$$$ chips need to be placed on the cells of the board (no more than one chip can be placed on a single cell).

Let's denote the cell in the $$$i$$$-th row and $$$j$$$-th column as $$$(i ,j)$$$. A diagonal is the set of cells for which the value $$$i + j$$$ is the same. For example, cells $$$(3, 1)$$$, $$$(2, 2)$$$, and $$$(1, 3)$$$ lie on the same diagonal, but $$$(1, 2)$$$ and $$$(2, 3)$$$ do not. A diagonal is called occupied if it contains at least one chip.

Determine what is the minimum possible number of occupied diagonals among all placements of $$$k$$$ chips.

## Input Format
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of sets of input data. Then follow the descriptions of the sets of input data.

The only line of each set of input data contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 100, 0 \le k \le n^2$$$) — the side of the checkered board and the number of available chips, respectively.

## Output Format
For each set of input data, output a single integer — the minimum number of occupied diagonals with at least one chip that he can get after placing all $$$k$$$ chips.

## Examples
```input
7
1 0
2 2
2 3
2 4
10 50
100 239
3 9
```
```output
0
1
2
3
6
3
5
```

## Note
In the first test case, there are no chips, so 0 diagonals will be occupied. In the second test case, both chips can be placed on diagonal $$$(2, 1), (1, 2)$$$, so the answer is 1. In the third test case, 3 chips can't be placed on one diagonal, but placing them on $$$(1, 2), (2, 1), (1, 1)$$$ makes 2 diagonals occupied. In the 7th test case, chips will occupy all 5 diagonals in any valid placing.

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
This is the easy version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

## Note
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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
This is the hard version of a problem. The only difference between an easy and a hard version is the constraints on $$$t$$$ and $$$n$$$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $$$2 n$$$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $$$2 i - 1$$$ is sitting at the desk with the knight $$$2 i$$$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $$$i$$$-th knight as $$$a_i$$$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ for any $$$1 \le i \le n$$$. Arthur can make any number of such swaps. What is the best result he can achieve?

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of desks.

The second line consists of $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — the intelligence values of the knights.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

## Output Format
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

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

## Note
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $$$10$$$.

In the third test case, Arthur can make $$$0$$$ operations, which will result in the total intelligence of $$$11$$$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $$$2$$$ and $$$5$$$ and achieve the difference of $$$2$$$. It can be proven that he cannot improve his result any further.

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

# Problem
There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that

- starts in the upper left cell of the matrix;
- each following cell is to the right or down from the current cell;
- the way ends in the bottom right cell.

Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

## Input Format
The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

## Output Format
In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

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

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 64.0 MB

# Problem
The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator's objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered.

Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.

## Input Format
The input data consists of three lines, each of them describes the position of one stadium. The lines have the format x,  y,  r, where (x, y) are the coordinates of the stadium's center ( -  103 ≤ x,  y ≤ 103), and r (1 ≤ r  ≤ 103) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.

## Output Format
Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn't print anything. The output data should be left blank.

## Examples
```input
0 0 10
60 0 10
30 30 10
```
```output
30.00000 0.00000
```

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
Furik loves painting stars. A star is a shape that results if we take a regular pentagon and paint all diagonals in it.

Recently he decided to teach Rubik to paint stars. After many years of training Rubik could paint stars easily. But now Furik decided to test Rubik and complicated the task. Rubik must paint n stars, observing the following rules:

- all stars must be painted in a single move (i.e. it is forbidden to take the pen away from the paper);
- it is forbidden to paint the same segment of non-zero length more than once;
- the stars can intersect only in their vertexes;
- the length of a side of the regular pentagon, in which Rubik paints each star, must equal 10.

Help Rubik to cope with this hard task.

## Input Format
A single line contains an integer (1 ≤ n ≤ 100) — the number of stars to paint.

## Output Format
On the first line print an integer m (1 ≤ m ≤ 5·n). On the next m lines print coordinates of m distinct points with accuracy of at least 9 and at most 100 digits after decimal point. All coordinates should not exceed 5000 in their absolute value. On each of the next n lines print 5 integers — the indexes of the points that form the given star in the clockwise or counterclockwise order. On the next line print 5·n + 1 integers — the numbers of points in the order, in which Rubik paints stars. That is, if number with index i is ai, and number with index i + 1 is ai + 1, then points with indexes ai and ai + 1 will have a segment painted between them.

You can consider all m printed points indexed from 1 to m in the order, in which they occur in the output. Separate the numbers on the lines with whitespaces.

Note that the answer has an imprecise validation. Try to obtain as accurate a solution as possible. The validator performs all calculations considering that the absolute error of a participant's answer is not more than 10 - 8.

## Examples
```input
1
```
```output
5
3.830127018922193 3.366025403784439
-3.601321235851749 10.057331467373021
0.466045194906253 19.192786043799030
10.411264148588986 18.147501411122495
12.490381056766580 8.366025403784439
1 2 3 4 5
1 3 5 2 4 1
```

## Note
The initial position of points in the sample is:

The order in which Rubik can paint segments is:

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
Rubik is very keen on number permutations.

A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.

Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b.

You are given permutations a and b, help Rubik solve the given problem.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.

## Output Format
On a single line print the answer to the problem.

## Examples
```input
1 1
1
1
```
```output
1
```
-----
```input
1 2
1
2 1
```
```output
2
```
-----
```input
3 3
2 3 1
1 2 3
```
```output
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
One day shooshuns found a sequence of n integers, written on a blackboard. The shooshuns can perform one operation with it, the operation consists of two steps:

1. Find the number that goes k-th in the current sequence and add the same number to the end of the sequence;
2. Delete the first number of the current sequence.

The shooshuns wonder after how many operations all numbers on the board will be the same and whether all numbers will ever be the same.

## Input Format
The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 105).

The second line contains n space-separated integers: a1, a2, ..., an (1 ≤ ai ≤ 105) — the sequence that the shooshuns found.

## Output Format
Print the minimum number of operations, required for all numbers on the blackboard to become the same. If it is impossible to achieve, print -1.

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

## Note
In the first test case after the first operation the blackboard will have sequence [1, 1, 1]. So, one operation is enough to make all numbers the same. Thus, the answer equals one.

In the second test case the sequence will never consist of the same numbers. It will always contain at least two distinct numbers 3 and 1. Thus, the answer equals -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 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
The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.

UCDHP stores some secret information about meteors as an n × m table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:

- The query to swap two table rows;
- The query to swap two table columns;
- The query to obtain a secret number in a particular table cell.

As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.

## Input Format
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 500000) — the number of table columns and rows and the number of queries, correspondingly.

Next n lines contain m space-separated numbers each — the initial state of the table. Each number p in the table is an integer and satisfies the inequality 0 ≤ p ≤ 106.

Next k lines contain queries in the format "si xi yi", where si is one of the characters "с", "r" or "g", and xi, yi are two integers.

- If si = "c", then the current query is the query to swap columns with indexes xi and yi (1 ≤ x, y ≤ m, x ≠ y);
- If si = "r", then the current query is the query to swap rows with indexes xi and yi (1 ≤ x, y ≤ n, x ≠ y);
- If si = "g", then the current query is the query to obtain the number that located in the xi-th row and in the yi-th column (1 ≤ x ≤ n, 1 ≤ y ≤ m).

The table rows are considered to be indexed from top to bottom from 1 to n, and the table columns — from left to right from 1 to m.

## Output Format
For each query to obtain a number (si = "g") print the required number. Print the answers to the queries in the order of the queries in the input.

## Examples
```input
3 3 5
1 2 3
4 5 6
7 8 9
g 3 2
r 3 2
c 2 3
g 2 2
g 3 2
```
```output
8
9
6
```
-----
```input
2 3 3
1 2 4
3 1 5
c 2 1
r 1 2
g 1 3
```
```output
5
```

## Note
Let's see how the table changes in the second test case.

After the first operation is fulfilled, the table looks like that:

2 1 4

1 3 5

After the second operation is fulfilled, the table looks like that:

1 3 5

2 1 4

So the answer to the third query (the number located in the first row and in the third column) will be 5.

Now solve the problem and return the code.