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

# Problem
You are given $$$n$$$ circles on the plane. The $$$i$$$-th of these circles is given by a tuple of integers $$$(x_i, y_i, r_i)$$$, where $$$(x_i, y_i)$$$ are the coordinates of its center, and $$$r_i$$$ is the radius of the circle.

Please find a circle $$$C$$$ which meets the following conditions:

- $$$C$$$ is contained inside all $$$n$$$ circles given in the input.
- Among all circles $$$C$$$ that meet the first condition, the radius of the circle is maximum.

Let the largest suitable circle have the radius of $$$a$$$.

Your output $$$C$$$, described as $$$(x,y,r)$$$, will be accepted if it meets the following conditions:

- For each $$$i$$$, $$$\sqrt{(x_i-x)^2+(y_i-y)^2}+ r \le r_i+\max(a,1)\cdot 10^{-7}$$$.
- The absolute or relative error of $$$r$$$ does not exceed $$$10^{-7}$$$. Formally, your answer is accepted if and only if $$$\frac{\left|r - a\right|}{\max(1, a)} \le 10^{-7}$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of circles.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$r_i$$$ ($$$-10^6 \le x_i,y_i \le 10^6$$$, $$$1 \le r_i \le 2 \cdot 10^6$$$).

It is guaranteed that there is a circle with a radius of at least $$$10^{-6}$$$ which is contained inside all $$$n$$$ circles.

## Output Format
Output three real values, $$$x$$$, $$$y$$$, and $$$r$$$ — the coordinates of the center and the radius of the circle.

## Examples
```input
4
1 1 3
-1 1 3
1 -1 2
-1 -1 2
```
```output
0.0000000000000000 -0.7637626158259733 0.9724747683480533
```
-----
```input
4
41580 -23621 95642
-41580 -23621 95642
0 47821 95642
0 0 109750
```
```output
0.0000000000000000 0.0000000000000000 47821.0000000000000000
```

## Note
A two-dimensional plot depicting the first test case is given below. The output circle $$$C$$$ is dashed with blue lines.

A two-dimensional plot depicting the second test case is given below. The output circle $$$C$$$ is dashed with blue lines.

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 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 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
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 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 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 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: 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 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: 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 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 three digits $$$a$$$, $$$b$$$, and $$$c$$$. Determine whether they form a stair, a peak, or neither.

- A stair satisfies the condition $$$a<b<c$$$.
- A peak satisfies the condition $$$a<b>c$$$.

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

The only line of each test case contains three digits $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \leq a$$$, $$$b$$$, $$$c \leq 9$$$).

## Output Format
For each test case, output "STAIR" if the digits form a stair, "PEAK" if the digits form a peak, and "NONE" otherwise (output the strings without quotes).

## Examples
```input
7
1 2 3
3 2 1
1 5 3
3 4 1
0 0 0
4 1 7
4 5 7
```
```output
STAIR
NONE
PEAK
PEAK
NONE
NONE
STAIR
```

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
Given the time in 24-hour format, output the equivalent time in 12-hour format.

- 24-hour format divides the day into 24 hours from $$$00$$$ to $$$23$$$, each of which has 60 minutes from $$$00$$$ to $$$59$$$.
- 12-hour format divides the day into two halves: the first half is $$$\mathrm{AM}$$$, and the second half is $$$\mathrm{PM}$$$. In each half, the hours are numbered in the order $$$12, 01, 02, 03, \dots, 11$$$. Each hour has 60 minutes numbered from $$$00$$$ to $$$59$$$.

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

The only line of each test case contains a string $$$s$$$ of length $$$5$$$ with format hh:mm representing a valid time in the 24-hour format. hh represents the hour from $$$00$$$ to $$$23$$$, and mm represents the minute from $$$00$$$ to $$$59$$$.

The input will always be a valid time in 24-hour format.

## Output Format
For each test case, output two strings separated by a space ("hh:mm AM" or "hh:mm PM"), which are the 12-hour equivalent to the time provided in the test case (without quotes).

You should output the time exactly as indicated; in particular, you should not remove leading zeroes.

## Examples
```input
11
09:41
18:06
12:14
00:59
00:00
14:34
01:01
19:07
11:59
12:00
21:37
```
```output
09:41 AM
06:06 PM
12:14 PM
12:59 AM
12:00 AM
02:34 PM
01:01 AM
07:07 PM
11:59 AM
12:00 PM
09:37 PM
```

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
Let's call a number a binary decimal if it is a positive integer and all digits in its decimal notation are either $$$0$$$ or $$$1$$$. For example, $$$1\,010\,111$$$ is a binary decimal, while $$$10\,201$$$ and $$$787\,788$$$ are not.

Given a number $$$n$$$, you are asked whether or not it is possible to represent $$$n$$$ as a product of some (not necessarily distinct) binary decimals.

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

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

## Output Format
For each test case, output "YES" (without quotes) if $$$n$$$ can be represented as a product of binary decimals, and "NO" (without quotes) otherwise.

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
11
121
1
14641
12221
10110
100000
99
112
2024
12421
1001
```
```output
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
YES
```

## Note
The first five test cases can be represented as a product of binary decimals as follows:

- $$$121 = 11 \times 11$$$.
- $$$1 = 1$$$ is already a binary decimal.
- $$$14\,641 = 11 \times 11 \times 11 \times 11$$$.
- $$$12\,221 = 11 \times 11 \times 101$$$.
- $$$10\,110 = 10\,110$$$ is already a binary decimal.

Now solve the problem and return the code.