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: 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 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
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 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 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 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$$$. 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 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: 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 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 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 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 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.
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
Alice and Bob are playing a game. They have a tree consisting of $$$n$$$ vertices. Initially, Bob has $$$k$$$ chips, the $$$i$$$-th chip is located in the vertex $$$a_i$$$ (all these vertices are unique). Before the game starts, Alice will place a chip into one of the vertices of the tree.

The game consists of turns. Each turn, the following events happen (sequentially, exactly in the following order):

1. Alice either moves her chip to an adjacent vertex or doesn't move it;
2. for each Bob's chip, he either moves it to an adjacent vertex or doesn't move it. Note that this choice is done independently for each chip.

The game ends when Alice's chip shares the same vertex with one (or multiple) of Bob's chips. Note that Bob's chips may share the same vertex, even though they are in different vertices at the beginning of the game.

Alice wants to maximize the number of turns, Bob wants to minimize it. If the game ends in the middle of some turn (Alice moves her chip to a vertex that contains one or multiple Bob's chips), this turn is counted.

For each vertex, calculate the number of turns the game will last if Alice places her chip in that vertex.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Then $$$n - 1$$$ lines follow, each line contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) that denote the endpoints of an edge. These edges form a tree.

The next line contains one integer $$$k$$$ ($$$1 \le k \le n - 1$$$) — the number of Bob's chips.

The last line contains $$$k$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne a_j$$$ if $$$i \ne j$$$) — the vertices where the Bob's chips are initially placed.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of turns the game will last if Alice initially places her chip in the vertex $$$i$$$. If one of Bob's chips is already placed in vertex $$$i$$$, then the answer for vertex $$$i$$$ is $$$0$$$.

## Examples
```input
5
2 4
3 1
3 4
3 5
2
4 5
```
```output
2 1 2 0 0
```
-----
```input
8
4 1
8 4
4 5
6 4
2 5
4 3
1 7
3
2 8 3
```
```output
3 0 0 3 1 2 3 0
```
-----
```input
10
2 5
4 3
7 3
7 2
5 8
3 6
8 10
7 9
7 1
4
10 6 9 1
```
```output
0 2 2 2 2 0 2 2 0 0
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Given integers $$$c_{0}, c_{1}, \ldots, c_{k-1}$$$ we can define the cost of a number $$$0 \le x < 2^{k}$$$ as $$$p(x) = \sum_{i=0}^{k-1} \left( \left\lfloor \frac{x}{2^{i}} \right\rfloor \bmod 2 \right) \cdot c_{i}$$$. In other words, the cost of number $$$x$$$ is the sum of $$$c_{i}$$$ over the bits of $$$x$$$ which are equal to one.

Let's define the cost of array $$$a$$$ of length $$$n \ge 2$$$ with elements from $$$[0, 2^{k})$$$ as follows: $$$cost(a) = \sum_{i=1}^{n - 1} p(a_{i} \oplus a_{i+1})$$$, where $$$\oplus$$$ denotes bitwise exclusive OR operation.

You have to construct an array of length $$$n$$$ with minimal cost, given that each element should belong to the given segment: $$$l_{i} \le a_{i} \le r_{i}$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 50$$$, $$$1 \le k \le 50$$$) — the size of an array and bit length of the numbers in question.

Next $$$n$$$ lines contain the restrictions for elements of the array: the $$$i$$$-th line contains two integers $$$l_{i}$$$ and $$$r_{i}$$$ ($$$0 \le l_{i} \le r_{i} < 2^{k}$$$).

The last line contains integers $$$c_{0}, c_{1}, \ldots, c_{k-1}$$$ ($$$0 \le c_{i} \le 10^{12}$$$).

## Output Format
Output one integer — the minimal cost of an array satisfying all the restrictions.

## Examples
```input
4 3
3 3
5 5
6 6
1 1
5 2 7
```
```output
30
```
-----
```input
3 3
2 2
3 4
4 6
1 10 100
```
```output
102
```

## Note
In the first example there is only one array satisfying all the restrictions — $$$[3, 5, 6, 1]$$$ — and its cost is equal to $$$cost([3, 5, 6, 1]) = p(3 \oplus 5) + p(5 \oplus 6) + p(6 \oplus 1) = p(6) + p(3) + p(7) = (c_{1} + c_{2}) + (c_{0} + c_{1}) + (c_{0} + c_{1} + c_{2}) = (2 + 7) + (5 + 2) + (5 + 2 + 7) = 30$$$.

In the second example the only optimal array is $$$[2, 3, 6]$$$.

Now solve the problem and return the code.