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

# Problem
There is a game where you need to move through a labyrinth. The labyrinth consists of $$$n$$$ platforms, connected by $$$m$$$ passages.

Each platform is at some level $$$l_i$$$, an integer number from $$$0$$$ to $$$H - 1$$$. In a single step, if you are currently on platform $$$i$$$, you can stay on it, or move to another platform $$$j$$$. To move to platform $$$j$$$ they have to be connected by the passage, and their levels have to be the same, namely $$$l_i = l_j$$$.

After each step, the levels of all platforms change. The new level of platform $$$i$$$ is calculated as $$$l'_i = (l_i + s_i) \bmod H$$$, for all $$$i$$$.

You start on platform $$$1$$$. Find the minimum number of steps you need to get to platform $$$n$$$.

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

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$H$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 10^5$$$, $$$1 \le H \le 10^9$$$).

The second line contains $$$n$$$ integers $$$l_i$$$, the initial level of each platform ($$$0 \le l_i \le H-1$$$).

The third line contains $$$n$$$ integers $$$s_i$$$, the change of level for each platform ($$$0 \le s_i \le H-1$$$).

Next $$$m$$$ lines contain a description of the passages. Each passage is described as a pair of integers — the platforms, connected by the passage. There is at most one passage connecting each pair of platforms, and there is no passage connecting a platform to itself.

The sum of $$$n$$$ for all tests does not exceed $$$10^5$$$, the sum of $$$m$$$ for all tests does not exceed $$$10^5$$$.

## Output Format
For each test case, print a single integer, the minimum number of steps needed to get from platform $$$1$$$ to platform $$$n$$$.

If it is impossible to get to platform $$$n$$$, print $$$-1$$$.

## Examples
```input
3
3 3 10
1 9 4
2 3 0
1 2
3 2
1 3
2 1 10
1 2
4 6
1 2
8 7 25
22 14 5 3 10 14 11 1
9 5 4 10 7 16 18 18
2 8
6 3
3 5
7 5
2 6
1 4
4 7
```
```output
6
-1
52
```

## Note
This is how levels of the platforms change, and what actions we need to perform in the first example.

Platform 1Platform 2Platform 3ActionStep 1194Stay on the platform 1Step 2324Stay on the platform 1Step 3554Move to the platform 2Step 4784Stay on the platform 2Step 5914Stay on the platform 2Step 6144Move to the platform 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ islands, numbered $$$1, 2, \ldots, n$$$. Initially, every pair of islands is connected by a bridge. Hence, there are a total of $$$\frac{n (n - 1)}{2}$$$ bridges.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

In the second test case, $$$6 \oplus 4 = 1 \oplus 3 = 2$$$.

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

You can perform the following operation any number of times (possibly zero): take any element of the array $$$a$$$, which is at least $$$10$$$, delete it, and instead insert the digits that element consisted of in the same position, in order they appear in that element.

For example:

- if we apply this operation to the $$$3$$$-rd element of the array $$$[12, 3, 45, 67]$$$, then the array becomes $$$[12, 3, 4, 5, 67]$$$.
- if we apply this operation to the $$$2$$$-nd element of the array $$$[2, 10]$$$, then the array becomes $$$[2, 1, 0]$$$.

Your task is to determine whether it is possible to make $$$a$$$ sorted in non-descending order using the aforementioned operation any number of times (possibly zero). In other words, you have to determine if it is possible to transform the array $$$a$$$ in such a way that $$$a_1 \le a_2 \le \dots \le a_k$$$, where $$$k$$$ is the current length of the array $$$a$$$.

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

Each test case consists of two lines:

- the first line contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$).
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 99$$$).

## Output Format
For each test case, print YES if it is possible to make $$$a$$$ sorted in non-decreasing order using the aforementioned operation; otherwise, print NO.

You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as a positive answer.

## Examples
```input
3
4
12 3 45 67
3
12 28 5
2
0 0
```
```output
YES
NO
YES
```

## Note
In the first example, you can split the first element, then the array becomes $$$[1, 2, 3, 45, 67]$$$.

In the second example, there is no way to get a sorted array.

In the third example, the array is already sorted.

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
There is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell of the grid contains an arrow pointing either to the left or to the right. No arrow points outside the grid.

There is a robot that starts in a cell $$$(1, 1)$$$. Every second, the following two actions happen one after another:

1. Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move);
2. then it moves along the arrow that is placed in the current cell (the cell it ends up after its move).

Your task is to determine whether the robot can reach the cell $$$(2, n)$$$.

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

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

The second line contains a string consisting of exactly $$$n$$$ characters < and/or > — the first row of the grid.

The third line contains a string consisting of exactly $$$n$$$ characters < and/or > — the second row of the grid.

Additional constraints on the input:

- $$$n$$$ is even;
- there are no arrows pointing outside the grid;
- the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print YES if the robot can reach the cell $$$(2, n)$$$; otherwise, print NO.

You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as positive answer.

## Examples
```input
4
4
>><<
>>><
2
><
><
4
>>><
>><<
6
>><<><
><>>><
```
```output
YES
YES
NO
YES
```

## Note
In the first example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$$$.

In the second example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.

In the third example, there is no way to reach the cell $$$(2, 4)$$$.

In the fourth example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (2, 5) \rightarrow (2, 6)$$$.

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 string $$$s$$$, consisting of lowercase Latin letters and/or question marks.

A tandem repeat is a string of an even length such that its first half is equal to its second half.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Your goal is to replace each question mark with some lowercase Latin letter in such a way that the length of the longest substring that is a tandem repeat is maximum possible.

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

The only line of each testcase contains a string $$$s$$$ ($$$1 \le |s| \le 5000$$$), consisting only of lowercase Latin letters and/or question marks.

The total length of the strings over all testcases doesn't exceed $$$5000$$$.

## Output Format
For each testcase, print a single integer — the maximum length of the longest substring that is a tandem repeat after you replace each question mark in the string with some lowercase Latin letter.

If it's impossible to make any tandem repeat substrings in the string, print $$$0$$$.

## Examples
```input
4
zaabaabz
?????
code?????s
codeforces
```
```output
6
4
10
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: 512.0 MB

# Problem
You are given two integers, $$$n$$$ and $$$k$$$. There is a graph on $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$, which initially has no edges.

You have to assign each vertex an integer; let $$$a_i$$$ be the integer on the vertex $$$i$$$. All $$$a_i$$$ should be distinct integers from $$$1$$$ to $$$n$$$.

After assigning integers, for every pair of vertices $$$(i, j)$$$, you add an edge between them if $$$|i - j| + |a_i - a_j| \le k$$$.

Your goal is to create a graph which can be partitioned into the minimum possible (for the given values of $$$n$$$ and $$$k$$$) number of cliques. Each vertex of the graph should belong to exactly one clique. Recall that a clique is a set of vertices such that every pair of vertices in it are connected with an edge.

Since BledDest hasn't really brushed his programming skills up, he can't solve the problem "given a graph, partition it into the minimum number of cliques". So we also ask you to print the partition itself.

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

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

## Output Format
For each test case, print three lines:

- the first line should contain $$$n$$$ distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the values you assign to the vertices;
- the second line should contain one integer $$$q$$$ ($$$1 \le q \le n$$$) — the number of cliques you partition the graph into;
- the third line should contain $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le q$$$) — the partition of the graph into cliques. Where two vertices $$$u$$$ and $$$v$$$ are in the same clique if $$$c_u = c_v$$$.

If there are multiple answers, print any of them.

## Examples
```input
3
2 3
5 4
8 16
```
```output
2 1
1
1 1
3 1 5 2 4
2
1 1 2 1 2
1 2 3 4 5 6 7 8
1
1 1 1 1 1 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 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: 6.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an undirected connected graph on $$$n$$$ vertices. Each edge of this graph has a weight; the weight of the edge connecting vertices $$$i$$$ and $$$j$$$ is $$$w_{i,j}$$$ (or $$$w_{i,j} = 0$$$ if there is no edge between $$$i$$$ and $$$j$$$). All weights are positive integers.

You are also given a positive integer $$$c$$$.

You have to build a spanning tree of this graph; i. e. choose exactly $$$(n-1)$$$ edges of this graph in such a way that every vertex can be reached from every other vertex by traversing some of the chosen edges. The cost of the spanning tree is the sum of two values:

- the sum of weights of all chosen edges;
- the maximum matching in the spanning tree (i. e. the maximum size of a set of edges such that they all belong to the chosen spanning tree, and no vertex has more than one incident edge in this set), multiplied by the given integer $$$c$$$.

Find any spanning tree with the minimum cost. Since the graph is connected, there exists at least one spanning tree.

## Input Format
The first line contains two integers $$$n$$$ and $$$c$$$ ($$$2 \le n \le 20$$$; $$$1 \le c \le 10^6$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains $$$n$$$ integers $$$w_{i,1}, w_{i,2}, \dots, w_{i,n}$$$ ($$$0 \le w_{i,j} \le 10^6$$$), where $$$w_{i,j}$$$ denotes the weight of the edge between $$$i$$$ and $$$j$$$ (or $$$w_{i,j} = 0$$$ if there is no such edge).

Additional constraints on the input:

- for every $$$i \in [1, n]$$$, $$$w_{i,i} = 0$$$;
- for every pair of integers $$$(i, j)$$$ such that $$$i \in [1, n]$$$ and $$$j \in [1, n]$$$, $$$w_{i,j} = w_{j,i}$$$;
- the given graph is connected.

## Output Format
Print one integer — the minimum cost of a spanning tree of the given graph.

## Examples
```input
4 10
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
```
```output
21
```
-----
```input
4 5
0 1 8 0
1 0 1 0
8 1 0 2
0 0 2 0
```
```output
14
```

## Note
In the first example, the minimum cost spanning tree consists of edges $$$(1, 3)$$$, $$$(2, 3)$$$ and $$$(3, 4)$$$. The maximum matching for it is $$$1$$$.

In the second example, the minimum cost spanning tree consists of edges $$$(1, 2)$$$, $$$(2, 3)$$$ and $$$(3, 4)$$$. The maximum matching for it is $$$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 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
Mocha likes arrays, so before her departure, 378QAQ gave her an array $$$a$$$ consisting of $$$n$$$ positive integers as a gift.

Mocha thinks that $$$a$$$ is beautiful if there exist two numbers $$$i$$$ and $$$j$$$ ($$$1\leq i,j\leq n$$$, $$$i\neq j$$$) such that for all $$$k$$$ ($$$1 \leq k \leq n$$$), $$$a_k$$$ is divisible$$$^\dagger$$$ by either $$$a_i$$$ or $$$a_j$$$.

Determine whether $$$a$$$ is beautiful.

$$$^\dagger$$$ $$$x$$$ is divisible by $$$y$$$ if there exists an integer $$$z$$$ such that $$$x = y \cdot z$$$.

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

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

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

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

## Output Format
For each test case, output "Yes" if array $$$a$$$ is beautiful, and output "No" otherwise.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

## Examples
```input
4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 49 9 3 1000000000
```
```output
No
Yes
Yes
No
```

## Note
In the first test case, any two numbers in the array are coprime, so the answer is "No".

In the second test case, we can pick $$$i=2$$$ and $$$j=1$$$. Since every number in the array is divisible by $$$a_i = 1$$$, the answer is "Yes".

In the third test case, we can pick $$$i=3$$$ and $$$j=5$$$. $$$2$$$ and $$$4$$$ is divisible by $$$a_i = 2$$$ while $$$3$$$, $$$6$$$ and $$$12$$$ is divisible by $$$a_j = 3$$$, so the answer is "Yes".

Now solve the problem and return the code.