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

# Problem
Given an undirected weighted graph with $$$n$$$ vertices and $$$m$$$ edges. There is at most one edge between each pair of vertices in the graph, and the graph does not contain loops (edges from a vertex to itself). The graph is not necessarily connected.

A cycle in the graph is called simple if it doesn't pass through the same vertex twice and doesn't contain the same edge twice.

Find any simple cycle in this graph in which the weight of the lightest edge is minimal.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — the size of the graph and the number of edges.

The next $$$m$$$ lines of the test case contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$1 \le w \le 10^6$$$) — vertices $$$u$$$ and $$$v$$$ are connected by an edge of weight $$$w$$$.

It is guaranteed that there is at most one edge between each pair of vertices. Note that under the given constraints, there is always at least one simple cycle in the graph.

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

## Output Format
For each test case, output a pair of numbers $$$b$$$ and $$$k$$$, where:

- $$$b$$$ — the minimum weight of the edge in the found cycle,
- $$$k$$$ — the number of vertices in the found cycle.

On the next line, output $$$k$$$ numbers from $$$1$$$ to $$$n$$$  — the vertices of the cycle in traversal order.

Note that the answer always exists, as under the given constraints, there is always at least one simple cycle in the graph.

## Examples
```input
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3
```
```output
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
A horizontal grid strip of $$$n$$$ cells is given. In the $$$i$$$-th cell, there is a paint charge of size $$$a_i$$$. This charge can be:

- either used to the left — then all cells to the left at a distance less than $$$a_i$$$ (from $$$\max(i - a_i + 1, 1)$$$ to $$$i$$$ inclusive) will be painted,
- or used to the right — then all cells to the right at a distance less than $$$a_i$$$ (from $$$i$$$ to $$$\min(i + a_i - 1, n)$$$ inclusive) will be painted,
- or not used at all.

Note that a charge can be used no more than once (that is, it cannot be used simultaneously to the left and to the right). It is allowed for a cell to be painted more than once.

What is the minimum number of times a charge needs to be used to paint all the cells of the strip?

## Input Format
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases in the test. This is followed by descriptions of $$$t$$$ test cases.

Each test case is specified by two lines. The first one contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells in the strip. The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the size of the paint charge in the $$$i$$$-th cell from the left of the strip.

It is guaranteed that the sum of the values of $$$n$$$ in the test does not exceed $$$1000$$$.

## Output Format
For each test case, output the minimum number of times the charges need to be used to paint all the cells of the strip.

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

## Note
In the third test case of the example, it is sufficient to use the charge from the $$$1$$$-st cell to the right, then it will cover both cells $$$1$$$ and $$$2$$$.

In the ninth test case of the example, you need to:

- use the charge from the $$$3$$$-rd cell to the left, covering cells from the $$$1$$$-st to the $$$3$$$-rd;
- use the charge from the $$$5$$$-th cell to the left, covering cells from the $$$4$$$-th to the $$$5$$$-th;
- use the charge from the $$$7$$$-th cell to the left, covering cells from the $$$6$$$-th to the $$$7$$$-th.

In the eleventh test case of the example, you need to:

- use the charge from the $$$5$$$-th cell to the right, covering cells from the $$$5$$$-th to the $$$10$$$-th;
- use the charge from the $$$7$$$-th cell to the left, covering cells from the $$$1$$$-st to the $$$7$$$-th.

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
Rudolf is going to visit Bernard, and he decided to take the metro to get to him. The ticket can be purchased at a machine that accepts exactly two coins, the sum of which does not exceed $$$k$$$.

Rudolf has two pockets with coins. In the left pocket, there are $$$n$$$ coins with denominations $$$b_1, b_2, \dots, b_n$$$. In the right pocket, there are $$$m$$$ coins with denominations $$$c_1, c_2, \dots, c_m$$$. He wants to choose exactly one coin from the left pocket and exactly one coin from the right pocket (two coins in total).

Help Rudolf determine how many ways there are to select indices $$$f$$$ and $$$s$$$ such that $$$b_f + c_s \le k$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then follows the description of each test case.

The first line of each test case contains three natural numbers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 100, 1 \le k \le 2000$$$) — the number of coins in the left and right pockets, and the maximum sum of two coins for the ticket payment at the counter, respectively.

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ ($$$1 \le b_i \le 1000$$$) — the denominations of coins in the left pocket.

The third line of each test case contains $$$m$$$ integers $$$c_i$$$ ($$$1 \le c_i \le 1000$$$) — the denominations of coins in the right pocket.

## Output Format
For each testcase, output a single integer — the number of ways Rudolf can select two coins, taking one from each pocket, so that the sum of the coins does not exceed $$$k$$$.

## Examples
```input
4
4 4 8
1 5 10 14
2 1 8 1
2 3 4
4 8
1 2 3
4 2 7
1 1 1 1
2 7
3 4 2000
1 1 1
1 1 1 1
```
```output
6
0
4
12
```

## Note
Note that the pairs indicate the indices of the coins in the array, not their denominations.

In the first test case, Rudolf can choose the following pairs of coins: $$$[1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]$$$.

In the second test case, Rudolf cannot choose one coin from each pocket in any way, as the sum of any two elements from the first and second arrays will exceed the value of $$$k=4$$$.

In the third test case, Rudolf can choose: $$$[1, 1], [2, 1], [3, 1], [4, 1]$$$.

In the fourth test case, Rudolf can choose any coin from the left pocket and any coin from the right pocket.

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
Rudolf has a string $$$s$$$ of length $$$n$$$. Rudolf considers the string $$$s$$$ to be ugly if it contains the substring$$$^\dagger$$$ "pie" or the substring "map", otherwise the string $$$s$$$ will be considered beautiful.

For example, "ppiee", "mmap", "dfpiefghmap" are ugly strings, while "mathp", "ppiiee" are beautiful strings.

Rudolf wants to shorten the string $$$s$$$ by removing some characters to make it beautiful.

The main character doesn't like to strain, so he asks you to make the string beautiful by removing the minimum number of characters. He can remove characters from any positions in the string (not just from the beginning or end of the string).

$$$^\dagger$$$ String $$$a$$$ is a substring of $$$b$$$ if there exists a consecutive segment of characters in string $$$b$$$ equal to $$$a$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the string $$$s$$$.

The next line of each test case contains the string $$$s$$$ of length $$$n$$$. The string $$$s$$$ consists of lowercase Latin letters.

The sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output a single integer — the minimum number of characters that need to be deleted to make the string $$$s$$$ beautiful. If the string is initially beautiful, then output $$$0$$$.

## Examples
```input
6
9
mmapnapie
9
azabazapi
8
mappppie
18
mapmapmapmapmapmap
1
p
11
pppiepieeee
```
```output
2
0
2
6
0
2
```

## Note
In the first test case, for example, you can delete the $$$4$$$th and $$$9$$$th characters to make the string beautiful.

In the second test case, the string is already beautiful.

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 organizing committee plans to take the participants of the Olympiad on a hike after the tour. Currently, the number of tents needed to be taken is being calculated. It is known that each tent can accommodate up to $$$3$$$ people.

Among the participants, there are $$$a$$$ introverts, $$$b$$$ extroverts, and $$$c$$$ universals:

- Each introvert wants to live in a tent alone. Thus, a tent with an introvert must contain exactly one person — only the introvert himself.
- Each extrovert wants to live in a tent with two others. Thus, the tent with an extrovert must contain exactly three people.
- Each universal is fine with any option (living alone, with one other person, or with two others).

The organizing committee respects the wishes of each participant very much, so they want to fulfill all of them.

Tell us the minimum number of tents needed to be taken so that all participants can be accommodated according to their preferences. If it is impossible to accommodate the participants in a way that fulfills all the wishes, output $$$-1$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the descriptions of the test cases.

Each test case is described by a single line containing three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) — the number of introverts, extroverts, and universals, respectively.

## Output Format
For each test case, output a single integer — the minimum number of tents, or $$$-1$$$ if it is impossible to accommodate the participants.

## Examples
```input
10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000
```
```output
3
-1
3
-1
3
28
0
7
8
1666666667
```

## Note
In the first test case, $$$1$$$ tent will be given to the introverts, $$$1$$$ tent will be shared by two extroverts and one universal, and the last tent will be shared by two universals. In total, $$$3$$$ tents are needed.

In the second test case, three extroverts will take $$$1$$$ tent, and $$$1$$$ tent will be taken by an introvert. Then, one extrovert and one universal will be left. This extrovert will not be able to live with two others.

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 $$$x$$$. Your task is to find any integer $$$y$$$ $$$(1\le y<x)$$$ such that $$$\gcd(x,y)+y$$$ is maximum possible.

Note that if there is more than one $$$y$$$ which satisfies the statement, you are allowed to find any.

$$$\gcd(a,b)$$$ is the Greatest Common Divisor of $$$a$$$ and $$$b$$$. For example, $$$\gcd(6,4)=2$$$.

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

Each of the following $$$t$$$ lines contains a single integer $$$x$$$ ($$$2 \le x \le 1000$$$).

## Output Format
For each test case, output any $$$y$$$ ($$$1 \le y < x$$$), which satisfies the statement.

## Examples
```input
7
10
7
21
100
2
1000
6
```
```output
5
6
18
98
1
750
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two binary strings $$$a$$$ and $$$b$$$. A binary string is a string consisting of the characters '0' and '1'.

Your task is to determine the maximum possible number $$$k$$$ such that a prefix of string $$$a$$$ of length $$$k$$$ is a subsequence of string $$$b$$$.

A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m \le 2 \cdot 10^5$$$) — the length of string $$$a$$$ and the length of string $$$b$$$, respectively.

The second line of each test case contains a binary string $$$a$$$ of length $$$n$$$.

The third line of each test case contains a binary string $$$b$$$ of length $$$m$$$.

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

## Output Format
For each test case, output a single number — the maximum $$$k$$$, such that the first $$$k$$$ characters of $$$a$$$ form a subsequence of $$$b$$$.

## Examples
```input
6
5 4
10011
1110
3 3
100
110
1 3
1
111
4 4
1011
1111
3 5
100
11010
3 1
100
0
```
```output
2
2
1
1
3
0
```

## Note
In the first example, the string '$$$10$$$' is a subsequence of '$$$1\color{red}11\color{red}0$$$' but the string '$$$100$$$' is not. So the answer is $$$2$$$.

In the fifth example, $$$a$$$='$$$100$$$', $$$b$$$='$$$1\color{red}{10}1\color{red}0$$$', whole string $$$a$$$ is a subsequence of string $$$b$$$. So the answer is $$$3$$$.

In the sixth example, string $$$b$$$ does not contain '$$$1$$$' 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$x_2,x_3,\dots,x_n$$$. Your task is to find any array $$$a_1,\dots,a_n$$$, where:

- $$$1\le a_i\le 10^9$$$ for all $$$1\le i\le n$$$.
- $$$x_i=a_i \bmod a_{i-1}$$$ for all $$$2\le i\le n$$$.

Here $$$c\bmod d$$$ denotes the remainder of the division of the integer $$$c$$$ by the integer $$$d$$$. For example $$$5 \bmod 2 = 1$$$, $$$72 \bmod 3 = 0$$$, $$$143 \bmod 14 = 3$$$.

Note that if there is more than one $$$a$$$ which satisfies the statement, you are allowed to find any.

## 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 $$$n$$$ $$$(2\le n\le 500)$$$ — the number of elements in $$$a$$$.

The second line of each test case contains $$$n-1$$$ integers $$$x_2,\dots,x_n$$$ $$$(1\le x_i\le 500)$$$ — the elements of $$$x$$$.

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

## Output Format
For each test case output any $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) which satisfies the statement.

## Examples
```input
5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5
```
```output
3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5
```

## Note
In the first test case $$$a=[3,5,4,9]$$$ satisfies the conditions, because:

- $$$a_2\bmod a_1=5\bmod 3=2=x_2$$$;
- $$$a_3\bmod a_2=4\bmod 5=4=x_3$$$;
- $$$a_4\bmod a_3=9\bmod 4=1=x_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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$. You choose $$$n$$$ cells $$$(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$$$ in the grid $$$n\times n$$$ where $$$1\le x_i\le n$$$ and $$$1\le y_i\le n$$$.

Let $$$\mathcal{H}$$$ be the set of distinct Manhattan distances between any pair of cells. Your task is to maximize the size of $$$\mathcal{H}$$$. Examples of sets and their construction are given in the notes.

If there exists more than one solution, you are allowed to output any.

Manhattan distance between cells $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ equals $$$|x_1-x_2|+|y_1-y_2|$$$.

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

Each of the following $$$t$$$ lines contains a single integer $$$n$$$ ($$$2\le n\le 10^3$$$).

## Output Format
For each test case, output $$$n$$$ points which maximize the size of $$$\mathcal{H}$$$. It is not necessary to output an empty line at the end of the answer for each test case.

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

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

1 4
1 5
1 6
5 2
5 5
6 1
```

## Note
In the first testcase we have $$$n=2$$$. One of the possible arrangements is:

The arrangement with cells located in $$$(1,1)$$$ and $$$(1,2)$$$.

In the second testcase we have $$$n=3$$$. The optimal arrangement is:

The arrangement with cells located in $$$(2,1)$$$, $$$(2,3)$$$ and $$$(3,1)$$$.

$$$\mathcal{H}$$$=$$$\{|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3|,|2-3|+|1-1|,|2-3|+|3-1|\}$$$=$$$\{0,0,0,2,1,3\}$$$=$$$\{0,1,2,3\}$$$.

For $$$n=4$$$ a possible arrangement is:

For $$$n=5$$$ a possible arrangement is:

For $$$n=6$$$ a possible arrangement is:

Now solve the problem and return the code.