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

# Problem
Naman has two binary strings $$$s$$$ and $$$t$$$ of length $$$n$$$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $$$s$$$ into $$$t$$$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $$$s$$$ and rotate it clockwise once.

For example, if $$$s = 1\textbf{1}101\textbf{00}$$$, he can choose a subsequence corresponding to indices ($$$1$$$-based) $$$\{2, 6, 7 \}$$$ and rotate them clockwise. The resulting string would then be $$$s = 1\textbf{0}101\textbf{10}$$$.

A string $$$a$$$ is said to be a subsequence of string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $$$c$$$ of size $$$k$$$ is to perform an operation which sets $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $$$s$$$ into $$$t$$$ or say that it is impossible.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the length of the strings.

The second line contains the binary string $$$s$$$ of length $$$n$$$.

The third line contains the binary string $$$t$$$ of length $$$n$$$.

## Output Format
If it is impossible to convert $$$s$$$ to $$$t$$$ after any number of operations, print $$$-1$$$.

Otherwise, print the minimum number of operations required.

## Examples
```input
6
010000
000001
```
```output
1
```
-----
```input
10
1111100000
0000011111
```
```output
5
```
-----
```input
8
10101010
01010101
```
```output
1
```
-----
```input
10
1111100000
1111100001
```
```output
-1
```

## Note
In the first test, Naman can choose the subsequence corresponding to indices $$$\{2, 6\}$$$ and rotate it once to convert $$$s$$$ into $$$t$$$.

In the second test, he can rotate the subsequence corresponding to all indices $$$5$$$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $$$s$$$ into $$$t$$$.

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 integers $$$x, y$$$ and $$$n$$$. Your task is to find the maximum integer $$$k$$$ such that $$$0 \le k \le n$$$ that $$$k \bmod x = y$$$, where $$$\bmod$$$ is modulo operation. Many programming languages use percent operator % to implement it.

In other words, with given $$$x, y$$$ and $$$n$$$ you need to find the maximum possible integer from $$$0$$$ to $$$n$$$ that has the remainder $$$y$$$ modulo $$$x$$$.

You have to answer $$$t$$$ independent test cases. It is guaranteed that such $$$k$$$ exists for each test case.

## Input Format
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases. The next $$$t$$$ lines contain test cases.

The only line of the test case contains three integers $$$x, y$$$ and $$$n$$$ ($$$2 \le x \le 10^9;~ 0 \le y < x;~ y \le n \le 10^9$$$).

It can be shown that such $$$k$$$ always exists under the given constraints.

## Output Format
For each test case, print the answer — maximum non-negative integer $$$k$$$ such that $$$0 \le k \le n$$$ and $$$k \bmod x = y$$$. It is guaranteed that the answer always exists.

## Examples
```input
7
7 5 12345
5 0 4
10 5 15
17 8 54321
499999993 9 1000000000
10 5 187
2 0 999999999
```
```output
12339
0
15
54306
999999995
185
999999998
```

## Note
In the first test case of the example, the answer is $$$12339 = 7 \cdot 1762 + 5$$$ (thus, $$$12339 \bmod 7 = 5$$$). It is obvious that there is no greater integer not exceeding $$$12345$$$ which has the remainder $$$5$$$ modulo $$$7$$$.

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 an integer $$$n$$$. In one move, you can either multiply $$$n$$$ by two or divide $$$n$$$ by $$$6$$$ (if it is divisible by $$$6$$$ without the remainder).

Your task is to find the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ or determine if it's impossible to do that.

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

## Output Format
For each test case, print the answer — the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ if it's possible to do that or -1 if it's impossible to obtain $$$1$$$ from $$$n$$$.

## Examples
```input
7
1
2
3
12
12345
15116544
387420489
```
```output
0
-1
2
-1
-1
12
36
```

## Note
Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $$$15116544$$$:

1. Divide by $$$6$$$ and get $$$2519424$$$;
2. divide by $$$6$$$ and get $$$419904$$$;
3. divide by $$$6$$$ and get $$$69984$$$;
4. divide by $$$6$$$ and get $$$11664$$$;
5. multiply by $$$2$$$ and get $$$23328$$$;
6. divide by $$$6$$$ and get $$$3888$$$;
7. divide by $$$6$$$ and get $$$648$$$;
8. divide by $$$6$$$ and get $$$108$$$;
9. multiply by $$$2$$$ and get $$$216$$$;
10. divide by $$$6$$$ and get $$$36$$$;
11. divide by $$$6$$$ and get $$$6$$$;
12. divide by $$$6$$$ and get $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a bracket sequence $$$s$$$ of length $$$n$$$, where $$$n$$$ is even (divisible by two). The string $$$s$$$ consists of $$$\frac{n}{2}$$$ opening brackets '(' and $$$\frac{n}{2}$$$ closing brackets ')'.

In one move, you can choose exactly one bracket and move it to the beginning of the string or to the end of the string (i.e. you choose some index $$$i$$$, remove the $$$i$$$-th character of $$$s$$$ and insert it before or after all remaining characters of $$$s$$$).

Your task is to find the minimum number of moves required to obtain regular bracket sequence from $$$s$$$. It can be proved that the answer always exists under the given constraints.

Recall what the regular bracket sequence is:

- "()" is regular bracket sequence;
- if $$$s$$$ is regular bracket sequence then "(" + $$$s$$$ + ")" is regular bracket sequence;
- if $$$s$$$ and $$$t$$$ are regular bracket sequences then $$$s$$$ + $$$t$$$ is regular bracket sequence.

For example, "()()", "(())()", "(())" and "()" are regular bracket sequences, but ")(", "()(" and ")))" are not.

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of $$$s$$$. It is guaranteed that $$$n$$$ is even. The second line of the test case containg the string $$$s$$$ consisting of $$$\frac{n}{2}$$$ opening and $$$\frac{n}{2}$$$ closing brackets.

## Output Format
For each test case, print the answer — the minimum number of moves required to obtain regular bracket sequence from $$$s$$$. It can be proved that the answer always exists under the given constraints.

## Examples
```input
4
2
)(
4
()()
8
())()()(
10
)))((((())
```
```output
1
0
1
3
```

## Note
In the first test case of the example, it is sufficient to move the first bracket to the end of the string.

In the third test case of the example, it is sufficient to move the last bracket to the beginning of the string.

In the fourth test case of the example, we can choose last three openning brackets, move them to the beginning of the string and obtain "((()))(())".

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 array $$$a$$$ consisting of $$$n$$$ positive integers.

Initially, you have an integer $$$x = 0$$$. During one move, you can do one of the following two operations:

1. Choose exactly one $$$i$$$ from $$$1$$$ to $$$n$$$ and increase $$$a_i$$$ by $$$x$$$ ($$$a_i := a_i + x$$$), then increase $$$x$$$ by $$$1$$$ ($$$x := x + 1$$$).
2. Just increase $$$x$$$ by $$$1$$$ ($$$x := x + 1$$$).

The first operation can be applied no more than once to each $$$i$$$ from $$$1$$$ to $$$n$$$.

Your task is to find the minimum number of moves required to obtain such an array that each its element is divisible by $$$k$$$ (the value $$$k$$$ is given).

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5; 1 \le k \le 10^9$$$) — the length of $$$a$$$ and the required divisior. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer — the minimum number of moves required to obtain such an array that each its element is divisible by $$$k$$$.

## Examples
```input
5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8
```
```output
6
18
0
227
8
```

## Note
Consider the first test case of the example:

1. $$$x=0$$$, $$$a = [1, 2, 1, 3]$$$. Just increase $$$x$$$;
2. $$$x=1$$$, $$$a = [1, 2, 1, 3]$$$. Add $$$x$$$ to the second element and increase $$$x$$$;
3. $$$x=2$$$, $$$a = [1, 3, 1, 3]$$$. Add $$$x$$$ to the third element and increase $$$x$$$;
4. $$$x=3$$$, $$$a = [1, 3, 3, 3]$$$. Add $$$x$$$ to the fourth element and increase $$$x$$$;
5. $$$x=4$$$, $$$a = [1, 3, 3, 6]$$$. Just increase $$$x$$$;
6. $$$x=5$$$, $$$a = [1, 3, 3, 6]$$$. Add $$$x$$$ to the first element and increase $$$x$$$;
7. $$$x=6$$$, $$$a = [6, 3, 3, 6]$$$. We obtained the required array.

Note that you can't add $$$x$$$ to the same element more than once.

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
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read some amount of books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are $$$n$$$ books in the family library. The $$$i$$$-th book is described by three integers: $$$t_i$$$ — the amount of time Alice and Bob need to spend to read it, $$$a_i$$$ (equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ if not), and $$$b_i$$$ (equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ if not).

So they need to choose some books from the given $$$n$$$ books in such a way that:

- Alice likes at least $$$k$$$ books from the chosen set and Bob likes at least $$$k$$$ books from the chosen set;
- the total reading time of these books is minimized (they are children and want to play and joy as soon a possible).

The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of $$$t_i$$$ over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The next $$$n$$$ lines contain descriptions of books, one description per line: the $$$i$$$-th line contains three integers $$$t_i$$$, $$$a_i$$$ and $$$b_i$$$ ($$$1 \le t_i \le 10^4$$$, $$$0 \le a_i, b_i \le 1$$$), where:

- $$$t_i$$$ — the amount of time required for reading the $$$i$$$-th book;
- $$$a_i$$$ equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ otherwise;
- $$$b_i$$$ equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ otherwise.

## Output Format
If there is no solution, print only one integer -1. Otherwise print one integer $$$T$$$ — the minimum total reading time of the suitable set of books.

## Examples
```input
8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0
```
```output
18
```
-----
```input
5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0
```
```output
8
```
-----
```input
5 3
3 0 0
2 1 0
3 1 0
5 0 1
3 0 1
```
```output
-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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read exactly $$$m$$$ books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are $$$n$$$ books in the family library. The $$$i$$$-th book is described by three integers: $$$t_i$$$ — the amount of time Alice and Bob need to spend to read it, $$$a_i$$$ (equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ if not), and $$$b_i$$$ (equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ if not).

So they need to choose exactly $$$m$$$ books from the given $$$n$$$ books in such a way that:

- Alice likes at least $$$k$$$ books from the chosen set and Bob likes at least $$$k$$$ books from the chosen set;
- the total reading time of these $$$m$$$ books is minimized (they are children and want to play and joy as soon a possible).

The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of $$$t_i$$$ over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.

## Input Format
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le k \le m \le n \le 2 \cdot 10^5$$$).

The next $$$n$$$ lines contain descriptions of books, one description per line: the $$$i$$$-th line contains three integers $$$t_i$$$, $$$a_i$$$ and $$$b_i$$$ ($$$1 \le t_i \le 10^4$$$, $$$0 \le a_i, b_i \le 1$$$), where:

- $$$t_i$$$ — the amount of time required for reading the $$$i$$$-th book;
- $$$a_i$$$ equals $$$1$$$ if Alice likes the $$$i$$$-th book and $$$0$$$ otherwise;
- $$$b_i$$$ equals $$$1$$$ if Bob likes the $$$i$$$-th book and $$$0$$$ otherwise.

## Output Format
If there is no solution, print only one integer -1.

If the solution exists, print $$$T$$$ in the first line — the minimum total reading time of the suitable set of books. In the second line print $$$m$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order — indices of books which are in the set you found.

If there are several answers, print any of them.

## Examples
```input
6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1
```
```output
24
6 5 1
```
-----
```input
6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1
```
```output
39
4 6 5
```

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 array $$$a$$$ consisting of $$$n$$$ integers.

In one move, you can choose some index $$$i$$$ ($$$1 \le i \le n - 2$$$) and shift the segment $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ cyclically to the right (i.e. replace the segment $$$[a_i, a_{i + 1}, a_{i + 2}]$$$ with $$$[a_{i + 2}, a_i, a_{i + 1}]$$$).

Your task is to sort the initial array by no more than $$$n^2$$$ such operations or say that it is impossible to do that.

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$3 \le n \le 500$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 500$$$), where $$$a_i$$$ is the $$$i$$$-th element $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$500$$$.

## Output Format
For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $$$ans$$$ on the first line and $$$ans$$$ integers $$$idx_1, idx_2, \dots, idx_{ans}$$$ ($$$1 \le idx_i \le n - 2$$$), where $$$idx_i$$$ is the index of left border of the segment for the $$$i$$$-th operation. You should print indices in order of performing operations.

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

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 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 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 positive (i.e. strictly greater than zero) integers $$$x$$$, $$$y$$$ and $$$z$$$.

Your task is to find positive integers $$$a$$$, $$$b$$$ and $$$c$$$ such that $$$x = \max(a, b)$$$, $$$y = \max(a, c)$$$ and $$$z = \max(b, c)$$$, or determine that it is impossible to find such $$$a$$$, $$$b$$$ and $$$c$$$.

You have to answer $$$t$$$ independent test cases. Print required $$$a$$$, $$$b$$$ and $$$c$$$ in any (arbitrary) order.

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

The only line of the test case contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le x, y, z \le 10^9$$$).

## Output Format
For each test case, print the answer:

- "NO" in the only line of the output if a solution doesn't exist;
- or "YES" in the first line and any valid triple of positive integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 10^9$$$) in the second line. You can print $$$a$$$, $$$b$$$ and $$$c$$$ in any order.

## Examples
```input
5
3 2 3
100 100 100
50 49 49
10 30 20
1 1000000000 1000000000
```
```output
YES
3 2 1
YES
100 100 100
NO
NO
YES
1 1 1000000000
```

Now solve the problem and return the code.