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
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 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 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 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 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 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 $$$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 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
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 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: 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 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 $$$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 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 are $$$n$$$ programmers that you want to split into several non-empty teams. The skill of the $$$i$$$-th programmer is $$$a_i$$$. You want to assemble the maximum number of teams from them. There is a restriction for each team: the number of programmers in the team multiplied by the minimum skill among all programmers in the team must be at least $$$x$$$.

Each programmer should belong to at most one team. Some programmers may be left without a team.

Calculate the maximum number of teams that you can assemble.

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

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5; 1 \le x \le 10^9$$$) — the number of programmers and the restriction of team skill respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the skill of the $$$i$$$-th programmer.

The sum of $$$n$$$ over all inputs does not exceed $$$10^5$$$.

## Output Format
For each test case print one integer — the maximum number of teams that you can assemble.

## Examples
```input
3
5 10
7 11 2 9 5
4 8
2 4 2 3
4 11
1 3 3 7
```
```output
2
1
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
There are $$$n$$$ warriors in a row. The power of the $$$i$$$-th warrior is $$$a_i$$$. All powers are pairwise distinct.

You have two types of spells which you may cast:

1. Fireball: you spend $$$x$$$ mana and destroy exactly $$$k$$$ consecutive warriors;
2. Berserk: you spend $$$y$$$ mana, choose two consecutive warriors, and the warrior with greater power destroys the warrior with smaller power.

For example, let the powers of warriors be $$$[2, 3, 7, 8, 11, 5, 4]$$$, and $$$k = 3$$$. If you cast Berserk on warriors with powers $$$8$$$ and $$$11$$$, the resulting sequence of powers becomes $$$[2, 3, 7, 11, 5, 4]$$$. Then, for example, if you cast Fireball on consecutive warriors with powers $$$[7, 11, 5]$$$, the resulting sequence of powers becomes $$$[2, 3, 4]$$$.

You want to turn the current sequence of warriors powers $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$. Calculate the minimum amount of mana you need to spend on it.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the length of sequence $$$a$$$ and the length of sequence $$$b$$$ respectively.

The second line contains three integers $$$x, k, y$$$ ($$$1 \le x, y, \le 10^9; 1 \le k \le n$$$) — the cost of fireball, the range of fireball and the cost of berserk respectively.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that all integers $$$a_i$$$ are pairwise distinct.

The fourth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le n$$$). It is guaranteed that all integers $$$b_i$$$ are pairwise distinct.

## Output Format
Print the minimum amount of mana for turning the sequnce $$$a_1, a_2, \dots, a_n$$$ into $$$b_1, b_2, \dots, b_m$$$, or $$$-1$$$ if it is impossible.

## Examples
```input
5 2
5 2 3
3 1 4 5 2
3 5
```
```output
8
```
-----
```input
4 4
5 1 4
4 3 1 2
2 4 3 1
```
```output
-1
```
-----
```input
4 4
2 1 11
1 3 2 4
1 3 2 4
```
```output
0
```

Now solve the problem and return the code.