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

# Problem
You are given $$$n$$$ words of equal length $$$m$$$, consisting of lowercase Latin alphabet letters. The $$$i$$$-th word is denoted $$$s_i$$$.

In one move you can choose any position in any single word and change the letter at that position to the previous or next letter in alphabetical order. For example:

- you can change 'e' to 'd' or to 'f';
- 'a' can only be changed to 'b';
- 'z' can only be changed to 'y'.

The difference between two words is the minimum number of moves required to make them equal. For example, the difference between "best" and "cost" is $$$1 + 10 + 0 + 0 = 11$$$.

Find the minimum difference of $$$s_i$$$ and $$$s_j$$$ such that $$$(i < j)$$$. In other words, find the minimum difference over all possible pairs of the $$$n$$$ words.

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

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq m \leq 8$$$) — the number of strings and their length respectively.

Then follows $$$n$$$ lines, the $$$i$$$-th of which containing a single string $$$s_i$$$ of length $$$m$$$, consisting of lowercase Latin letters.

## Output Format
For each test case, print a single integer — the minimum difference over all possible pairs of the given strings.

## Examples
```input
6
2 4
best
cost
6 3
abb
zba
bef
cdu
ooo
zzz
2 7
aaabbbc
bbaezfe
3 2
ab
ab
ab
2 8
aaaaaaaa
zzzzzzzz
3 1
a
u
y
```
```output
11
8
35
0
200
4
```

## Note
For the second test case, one can show that the best pair is ("abb","bef"), which has difference equal to $$$8$$$, which can be obtained in the following way: change the first character of the first string to 'b' in one move, change the second character of the second string to 'b' in $$$3$$$ moves and change the third character of the second string to 'b' in $$$4$$$ moves, thus making in total $$$1 + 3 + 4 = 8$$$ moves.

For the third test case, there is only one possible pair and it can be shown that the minimum amount of moves necessary to make the strings equal is $$$35$$$.

For the fourth test case, there is a pair of strings which is already equal, so the answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between the two versions is that in this version $$$n \leq 1000$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.

You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the array.

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

The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.

## Output Format
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

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

## Note
The first test case is shown in the second picture in the statement.

In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.

In the third test case, the only wiring possible has one wire, so the answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The only difference between the two versions is that in this version $$$n \leq 2 \cdot 10^5$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.

You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

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

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

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

## Note
The first test case is shown in the second picture in the statement.

In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.

In the third test case, the only wiring possible has one wire, so the answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mike and Joe are playing a game with some stones. Specifically, they have $$$n$$$ piles of stones of sizes $$$a_1, a_2, \ldots, a_n$$$. These piles are arranged in a circle.

The game goes as follows. Players take turns removing some positive number of stones from a pile in clockwise order starting from pile $$$1$$$. Formally, if a player removed stones from pile $$$i$$$ on a turn, the other player removes stones from pile $$$((i\bmod n) + 1)$$$ on the next turn.

If a player cannot remove any stones on their turn (because the pile is empty), they lose. Mike goes first.

If Mike and Joe play optimally, who will win?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — the size of the piles.

## Output Format
For each test case print the winner of the game, either "Mike" or "Joe" on its own line (without quotes).

## Examples
```input
2
1
37
2
100 100
```
```output
Mike
Joe
```

## Note
In the first test case, Mike just takes all $$$37$$$ stones on his first turn.

In the second test case, Joe can just copy Mike's moves every time. Since Mike went first, he will hit $$$0$$$ on the first pile one move before Joe does so on the second pile.

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 a grid with $$$n$$$ rows and $$$m$$$ columns. We denote the square on the $$$i$$$-th ($$$1\le i\le n$$$) row and $$$j$$$-th ($$$1\le j\le m$$$) column by $$$(i, j)$$$ and the number there by $$$a_{ij}$$$. All numbers are equal to $$$1$$$ or to $$$-1$$$.

You start from the square $$$(1, 1)$$$ and can move one square down or one square to the right at a time. In the end, you want to end up at the square $$$(n, m)$$$.

Is it possible to move in such a way so that the sum of the values written in all the visited cells (including $$$a_{11}$$$ and $$$a_{nm}$$$) is $$$0$$$?

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$)  — the size of the grid.

Each of the following $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{ij}$$$ ($$$a_{ij} = 1$$$ or $$$-1$$$)  — the element in the cell $$$(i, j)$$$.

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

## Output Format
For each test case, print "YES" if there exists a path from the top left to the bottom right that adds up to $$$0$$$, and "NO" otherwise. You can output each letter in any case.

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

## Note
One possible path for the fourth test case is given in the picture in the 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 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
You are given a permutation $$$p_1,p_2,\ldots,p_n$$$ of length $$$n$$$ and a positive integer $$$k \le n$$$.

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

Find the minimum number of operations needed to make the sum $$$p_1 + p_2 + \ldots + p_k$$$ as small as possible.

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

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$).

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 the given numbers form a permutation of length $$$n$$$.

## Output Format
For each test case print one integer — the minimum number of operations needed to make the sum $$$p_1 + p_2 + \ldots + p_k$$$ as small as possible.

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

## Note
In the first test case, the value of $$$p_1 + p_2 + \ldots + p_k$$$ is initially equal to $$$2$$$, but the smallest possible value is $$$1$$$. You can achieve it by swapping $$$p_1$$$ with $$$p_3$$$, resulting in the permutation $$$[1, 3, 2]$$$.

In the second test case, the sum is already as small as possible, so the answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

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

In one operation you do the following:

1. Choose any integer $$$x$$$.
2. For all $$$i$$$ such that $$$a_i = x$$$, do $$$a_i := 0$$$ (assign $$$0$$$ to $$$a_i$$$).

Find the minimum number of operations required to sort the array in non-decreasing order.

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

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

The second line of each test case contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

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

## Output Format
For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

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

## Note
In the first test case, you can choose $$$x = 3$$$ for the operation, the resulting array is $$$[0, 0, 2]$$$.

In the second test case, you can choose $$$x = 1$$$ for the first operation and $$$x = 3$$$ for the second operation, the resulting array is $$$[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: 1.5 seconds
Memory limit: 256.0 MB

# Problem
An array of $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ fell down on you from the skies, along with a positive integer $$$k \le n$$$.

You can apply the following operation at most $$$k$$$ times:

- Choose an index $$$1 \le i \le n$$$ and an integer $$$1 \le x \le 10^9$$$. Then do $$$a_i := x$$$ (assign $$$x$$$ to $$$a_i$$$).

Then build a complete undirected weighted graph with $$$n$$$ vertices numbered with integers from $$$1$$$ to $$$n$$$, where edge $$$(l, r)$$$ ($$$1 \le l < r \le n$$$) has weight $$$\min(a_{l},a_{l+1},\ldots,a_{r})$$$.

You have to find the maximum possible diameter of the resulting graph after performing at most $$$k$$$ operations.

The diameter of a graph is equal to $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$, where $$$\operatorname{d}(u, v)$$$ is the length of the shortest path between vertex $$$u$$$ and vertex $$$v$$$.

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

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

The second line of each test case contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case print one integer — the maximum possible diameter of the graph after performing at most $$$k$$$ operations.

## Examples
```input
6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2
```
```output
4
168
10
1000000000
9
1000000000
```

## Note
In the first test case, one of the optimal arrays is $$$[2,4,5]$$$.

The graph built on this array:

$$$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$$$ and $$$\operatorname{d}(2, 3) = 4$$$, so the diameter is equal to $$$\max(2,2,4) = 4$$$.

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

# Problem
This version of the problem differs from the next one only in the constraint on $$$t$$$. You can make hacks only if both versions of the problem are solved.

You are given two positive integers $$$l$$$ and $$$r$$$.

Count the number of distinct triplets of integers $$$(i, j, k)$$$ such that $$$l \le i < j < k \le r$$$ and $$$\operatorname{lcm}(i,j,k) \ge i + j + k$$$.

Here $$$\operatorname{lcm}(i, j, k)$$$ denotes the least common multiple (LCM) of integers $$$i$$$, $$$j$$$, and $$$k$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$\bf{1 \le t \le 5}$$$). Description of the test cases follows.

The only line for each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$).

## Output Format
For each test case print one integer — the number of suitable triplets.

## Examples
```input
5
1 4
3 5
8 86
68 86
6 86868
```
```output
3
1
78975
969
109229059713337
```

## Note
In the first test case, there are $$$3$$$ suitable triplets:

- $$$(1,2,3)$$$,
- $$$(1,3,4)$$$,
- $$$(2,3,4)$$$.

In the second test case, there is $$$1$$$ suitable triplet:

- $$$(3,4,5)$$$.

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

# Problem
This version of the problem differs from the previous one only in the constraint on $$$t$$$. You can make hacks only if both versions of the problem are solved.

You are given two positive integers $$$l$$$ and $$$r$$$.

Count the number of distinct triplets of integers $$$(i, j, k)$$$ such that $$$l \le i < j < k \le r$$$ and $$$\operatorname{lcm}(i,j,k) \ge i + j + k$$$.

Here $$$\operatorname{lcm}(i, j, k)$$$ denotes the least common multiple (LCM) of integers $$$i$$$, $$$j$$$, and $$$k$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$\bf{1 \le t \le 10^5}$$$). Description of the test cases follows.

The only line for each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$).

## Output Format
For each test case print one integer — the number of suitable triplets.

## Examples
```input
5
1 4
3 5
8 86
68 86
6 86868
```
```output
3
1
78975
969
109229059713337
```

## Note
In the first test case, there are $$$3$$$ suitable triplets:

- $$$(1,2,3)$$$,
- $$$(1,3,4)$$$,
- $$$(2,3,4)$$$.

In the second test case, there is $$$1$$$ suitable triplet:

- $$$(3,4,5)$$$.

Now solve the problem and return the code.