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

# Problem
An agent called Cypher is decrypting a message, that contains a composite number $$$n$$$. All divisors of $$$n$$$, which are greater than $$$1$$$, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.

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

In a single line of each test case description, there is a single composite number $$$n$$$ $$$(4 \le n \le 10^9)$$$ — the number from the message.

It's guaranteed that the total number of divisors of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case in the first line output the initial order of divisors, which are greater than $$$1$$$, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.

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

## Note
In the first test case $$$6$$$ has three divisors, which are greater than $$$1$$$: $$$2, 3, 6$$$. Regardless of the initial order, numbers $$$2$$$ and $$$3$$$ are adjacent, so it's needed to place their least common multiple between them. After that the circle becomes $$$2, 6, 3, 6$$$, and every two adjacent numbers are not coprime.

In the second test case $$$4$$$ has two divisors greater than $$$1$$$: $$$2, 4$$$, and they are not coprime, so any initial order is correct, and it's not needed to place any least common multiples.

In the third test case all divisors of $$$30$$$ greater than $$$1$$$ can be placed in some order so that there are no two adjacent numbers that are coprime.

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
Recently a new building with a new layout was constructed in Monocarp's hometown. According to this new layout, the building consists of three types of apartments: three-room, five-room, and seven-room apartments. It's also known that each room of each apartment has exactly one window. In other words, a three-room apartment has three windows, a five-room — five windows, and a seven-room — seven windows.

Monocarp went around the building and counted $$$n$$$ windows. Now he is wondering, how many apartments of each type the building may have.

Unfortunately, Monocarp only recently has learned to count, so he is asking you to help him to calculate the possible quantities of three-room, five-room, and seven-room apartments in the building that has $$$n$$$ windows. If there are multiple answers, you can print any of them.

Here are some examples:

- if Monocarp has counted $$$30$$$ windows, there could have been $$$2$$$ three-room apartments, $$$2$$$ five-room apartments and $$$2$$$ seven-room apartments, since $$$2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$$$;
- if Monocarp has counted $$$67$$$ windows, there could have been $$$7$$$ three-room apartments, $$$5$$$ five-room apartments and $$$3$$$ seven-room apartments, since $$$7 \cdot 3 + 5 \cdot 5 + 3 \cdot 7 = 67$$$;
- if Monocarp has counted $$$4$$$ windows, he should have mistaken since no building with the aforementioned layout can have $$$4$$$ windows.

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

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of windows in the building.

## Output Format
For each test case, if a building with the new layout and the given number of windows just can't exist, print $$$-1$$$.

Otherwise, print three non-negative integers — the possible number of three-room, five-room, and seven-room apartments. If there are multiple answers, print any of them.

## Examples
```input
4
30
67
4
14
```
```output
2 2 2
7 5 3
-1
0 0 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
Numbers $$$1, 2, 3, \dots n$$$ (each integer from $$$1$$$ to $$$n$$$ once) are written on a board. In one operation you can erase any two numbers $$$a$$$ and $$$b$$$ from the board and write one integer $$$\frac{a + b}{2}$$$ rounded up instead.

You should perform the given operation $$$n - 1$$$ times and make the resulting number that will be left on the board as small as possible.

For example, if $$$n = 4$$$, the following course of action is optimal:

1. choose $$$a = 4$$$ and $$$b = 2$$$, so the new number is $$$3$$$, and the whiteboard contains $$$[1, 3, 3]$$$;
2. choose $$$a = 3$$$ and $$$b = 3$$$, so the new number is $$$3$$$, and the whiteboard contains $$$[1, 3]$$$;
3. choose $$$a = 1$$$ and $$$b = 3$$$, so the new number is $$$2$$$, and the whiteboard contains $$$[2]$$$.

It's easy to see that after $$$n - 1$$$ operations, there will be left only one number. Your goal is to minimize it.

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

The only line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of integers written on the board initially.

It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, in the first line, print the minimum possible number left on the board after $$$n - 1$$$ operations. Each of the next $$$n - 1$$$ lines should contain two integers — numbers $$$a$$$ and $$$b$$$ chosen and erased in each operation.

## Examples
```input
1
4
```
```output
2
2 4
3 3
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a string $$$s$$$ consisting of $$$n$$$ characters. Each character is either 0 or 1.

You can perform operations on the string. Each operation consists of two steps:

1. select an integer $$$i$$$ from $$$1$$$ to the length of the string $$$s$$$, then delete the character $$$s_i$$$ (the string length gets reduced by $$$1$$$, the indices of characters to the right of the deleted one also get reduced by $$$1$$$);
2. if the string $$$s$$$ is not empty, delete the maximum length prefix consisting of the same characters (the indices of the remaining characters and the string length get reduced by the length of the deleted prefix).

Note that both steps are mandatory in each operation, and their order cannot be changed.

For example, if you have a string $$$s =$$$ 111010, the first operation can be one of the following:

1. select $$$i = 1$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
2. select $$$i = 2$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
3. select $$$i = 3$$$: we'll get 111010 $$$\rightarrow$$$ 11010 $$$\rightarrow$$$ 010;
4. select $$$i = 4$$$: we'll get 111010 $$$\rightarrow$$$ 11110 $$$\rightarrow$$$ 0;
5. select $$$i = 5$$$: we'll get 111010 $$$\rightarrow$$$ 11100 $$$\rightarrow$$$ 00;
6. select $$$i = 6$$$: we'll get 111010 $$$\rightarrow$$$ 11101 $$$\rightarrow$$$ 01.

You finish performing operations when the string $$$s$$$ becomes empty. What is the maximum number of operations you can perform?

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

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

The second line contains string $$$s$$$ of $$$n$$$ characters. Each character is either 0 or 1.

It's guaranteed that the total sum of $$$n$$$ over test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum number of operations you can perform.

## Examples
```input
5
6
111010
1
0
1
1
2
11
6
101010
```
```output
3
1
1
1
3
```

## Note
In the first test case, you can, for example, select $$$i = 2$$$ and get string 010 after the first operation. After that, you can select $$$i = 3$$$ and get string 1. Finally, you can only select $$$i = 1$$$ and get empty string.

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$$$. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string.

Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the length of $$$s$$$.

The second line contains $$$s$$$ — a string consisting of $$$n$$$ lowercase Latin letters.

## Output Format
Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.

## Examples
```input
5
aaaza
```
```output
2
```
-----
```input
6
cbaabc
```
```output
0
```
-----
```input
9
icpcsguru
```
```output
30
```

## Note
In the first example, you have to swap the third and the fourth elements, so the string becomes "aazaa". Then you have to swap the second and the third elements, so the string becomes "azaaa". So, it is possible to reverse the string in two swaps.

Since the string in the second example is a palindrome, you don't have to do anything to reverse it.

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

# Problem
You are given a directed acyclic graph (a directed graph that does not contain cycles) of $$$n$$$ vertices and $$$m$$$ arcs. The $$$i$$$-th arc leads from the vertex $$$x_i$$$ to the vertex $$$y_i$$$ and has the weight $$$w_i$$$.

Your task is to select an integer $$$a_v$$$ for each vertex $$$v$$$, and then write a number $$$b_i$$$ on each arcs $$$i$$$ such that $$$b_i = a_{x_i} - a_{y_i}$$$. You must select the numbers so that:

- all $$$b_i$$$ are positive;
- the value of the expression $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ is the lowest possible.

It can be shown that for any directed acyclic graph with non-negative $$$w_i$$$, such a way to choose numbers exists.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$).

Then $$$m$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — the description of the $$$i$$$-th arc.

It is guaranteed that the lines describe $$$m$$$ arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.

## Output Format
Print $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$), which must be written on the vertices so that all $$$b_i$$$ are positive, and the value of the expression $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints $$$0 \le a_v \le 10^9$$$.

## Examples
```input
3 2
2 1 4
1 3 2
```
```output
1 2 0
```
-----
```input
5 4
1 2 1
2 3 1
1 3 6
4 5 8
```
```output
43 42 41 1337 1336
```
-----
```input
5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10
```
```output
4 3 2 1 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Shikamaru and Asuma like to play different games, and sometimes they play the following: given an increasing list of numbers, they take turns to move. Each move consists of picking a number from the list.

Assume the picked numbers are $$$v_{i_1}$$$, $$$v_{i_2}$$$, $$$\ldots$$$, $$$v_{i_k}$$$. The following conditions must hold:

- $$$i_{j} < i_{j+1}$$$ for all $$$1 \leq j \leq k-1$$$;
- $$$v_{i_{j+1}} - v_{i_j} < v_{i_{j+2}} - v_{i_{j+1}}$$$ for all $$$1 \leq j \leq k-2$$$.

However, it's easy to play only one instance of game, so today Shikamaru and Asuma decided to play $$$n$$$ simultaneous games. They agreed on taking turns as for just one game, Shikamaru goes first. At each turn, the player performs a valid move in any single game. The player who cannot move loses. Find out who wins, provided that both play optimally.

## Input Format
The first line contains the only integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) standing for the number of games Shikamaru and Asuma play at once. Next lines describe the games.

Each description starts from a line with the only number $$$m$$$ ($$$m\geq 1$$$) denoting the length of the number list. The second line contains the increasing space-separated sequence $$$v_1$$$, $$$v_2$$$, ..., $$$v_m$$$ from the game ($$$1 \leq v_{1} < v_{2} < ... < v_{m} \leq 10^{5}$$$).

The total length of all sequences doesn't exceed $$$10^5$$$.

## Output Format
Print "YES" if Shikamaru can secure the victory, and "NO" otherwise.

## Examples
```input
1
10
1 2 3 4 5 6 7 8 9 10
```
```output
YES
```
-----
```input
2
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
```
```output
NO
```
-----
```input
4
7
14404 32906 41661 47694 51605 75933 80826
5
25374 42550 60164 62649 86273
2
7002 36731
8
23305 45601 46404 47346 47675 58125 74092 87225
```
```output
NO
```

## Note
In the first example Shikamaru can pick the last number, and Asuma cannot do anything because of the first constraint.

In the second sample test Asuma can follow the symmetric strategy, repeating Shikamaru's moves in the other instance each time, and therefore win.

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 an infinite 2-dimensional grid. The robot stands in cell $$$(0, 0)$$$ and wants to reach cell $$$(x, y)$$$. Here is a list of possible commands the robot can execute:

- move north from cell $$$(i, j)$$$ to $$$(i, j + 1)$$$;
- move east from cell $$$(i, j)$$$ to $$$(i + 1, j)$$$;
- move south from cell $$$(i, j)$$$ to $$$(i, j - 1)$$$;
- move west from cell $$$(i, j)$$$ to $$$(i - 1, j)$$$;
- stay in cell $$$(i, j)$$$.

The robot wants to reach cell $$$(x, y)$$$ in as few commands as possible. However, he can't execute the same command two or more times in a row.

What is the minimum number of commands required to reach $$$(x, y)$$$ from $$$(0, 0)$$$?

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

Each of the next $$$t$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^4$$$) — the destination coordinates of the robot.

## Output Format
For each testcase print a single integer — the minimum number of commands required for the robot to reach $$$(x, y)$$$ from $$$(0, 0)$$$ if no command is allowed to be executed two or more times in a row.

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

## Note
The explanations for the example test:

We use characters N, E, S, W and 0 to denote going north, going east, going south, going west and staying in the current cell, respectively.

In the first test case, the robot can use the following sequence: NENENENENE.

In the second test case, the robot can use the following sequence: NENENEN.

In the third test case, the robot can use the following sequence: ESENENE0ENESE.

In the fourth test case, the robot doesn't need to go anywhere at all.

In the fifth test case, the robot can use the following sequence: E0E.

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 string $$$s$$$, consisting of brackets of two types: '(', ')', '[' and ']'.

A string is called a regular bracket sequence (RBS) if it's of one of the following types:

- empty string;
- '(' + RBS + ')';
- '[' + RBS + ']';
- RBS + RBS.

where plus is a concatenation of two strings.

In one move you can choose a non-empty subsequence of the string $$$s$$$ (not necessarily consecutive) that is an RBS, remove it from the string and concatenate the remaining parts without changing the order.

What is the maximum number of moves you can perform?

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

Each of the next $$$t$$$ lines contains a non-empty string, consisting only of characters '(', ')', '[' and ']'. The total length of the strings over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase print a single integer — the maximum number of moves you can perform on a given string $$$s$$$.

## Examples
```input
5
()
[]()
([)]
)]([
)[(]
```
```output
1
2
2
0
1
```

## Note
In the first example you can just erase the whole string.

In the second example you can first erase the brackets on positions $$$1$$$ and $$$2$$$: "[]()", then "()" is left. After that you can erase it whole. You could erase the whole string from the beginning but you would get one move instead of two.

In the third example you can first erase the brackets on positions $$$1$$$ and $$$3$$$: "([)]". They form an RBS "()". Then "[]" is left, so you can erase it whole.

In the fourth example there is no subsequence that is an RBS, so you can't perform a move at all.

In the fifth example you can erase the brackets on positions $$$2$$$ and $$$4$$$: ")[(]" and get ")(" as a result. You can erase nothing from it.

Now solve the problem and return the code.