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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call integer martian if it is a non-negative integer and strictly less than $$$2^k$$$, for example, when $$$k = 12$$$, the numbers $$$51$$$, $$$1960$$$, $$$0$$$ are martian, and the numbers $$$\pi$$$, $$$-1$$$, $$$\frac{21}{8}$$$, $$$4096$$$ are not.

The aliens will give Lisa $$$n$$$ martian numbers $$$a_1, a_2, \ldots, a_n$$$. Then they will ask her to name any martian number $$$x$$$. After that, Lisa will select a pair of numbers $$$a_i, a_j$$$ ($$$i \neq j$$$) in the given sequence and count $$$(a_i \oplus x) \& (a_j \oplus x)$$$. The operation $$$\oplus$$$ means Bitwise exclusive OR, the operation $$$\&$$$ means Bitwise And. For example, $$$(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$$$.

Lisa is sure that the higher the calculated value, the higher her chances of returning home. Help the girl choose such $$$i, j, x$$$ that maximize the calculated value.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.

Each testcase is described by two lines.

The first line contains integers $$$n, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 30$$$) — the length of the sequence of martian numbers and the value of $$$k$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^k$$$) — a sequence of martian numbers.

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

## Output Format
For each testcase, print three integers $$$i, j, x$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$0 \le x < 2^k$$$). The value of $$$(a_i \oplus x) \& (a_j \oplus x)$$$ should be the maximum possible.

If there are several solutions, you can print any one.

## Examples
```input
10
5 4
3 9 1 4 13
3 1
1 0 1
6 12
144 1580 1024 100 9 13
4 3
7 3 0 4
3 2
0 0 1
2 4
12 2
9 4
6 14 9 4 4 4 5 10 2
2 1
1 0
2 4
11 4
9 4
2 11 10 1 6 9 11 0 5
```
```output
1 3 14
1 3 0
5 6 4082
2 3 7
1 2 3
1 2 15
4 5 11
1 2 0
1 2 0
2 7 4
```

## Note
First testcase: $$$(3 \oplus 14) \& (1 \oplus 14) = (0011_2 \oplus 1110_2) \& (0001_2 \oplus 1110_2) = 1101_2 = 1101_2 \& 1111_2 = 1101_2 = 13$$$.

Second testcase: $$$(1 \oplus 0) \& (1 \oplus 0) = 1$$$.

Third testcase: $$$(9 \oplus 4082) \& (13 \oplus 4082) = 4091$$$.

Fourth testcase: $$$(3 \oplus 7) \& (0 \oplus 7) = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A bracket sequence is a string consisting of characters '(' and/or ')'. A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (they can be transformed into "(1)+(1)" and "((1+1)+1)", respectively);
- bracket sequences ")(", "(" and ")" are not regular.

You are given a bracket sequence $$$s$$$; let's define its length as $$$n$$$. Your task is to find a regular bracket sequence $$$t$$$ of length $$$2n$$$ such that $$$s$$$ does not occur in $$$t$$$ as a contiguous substring, or report that there is no such sequence.

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

The only line of each test case contains a string $$$s$$$ ($$$2 \le |s| \le 50$$$), consisting of characters "(" and/or ")".

## Output Format
For each test case, print the answer to it. If there is no required regular bracket sequence, print NO in a separate line. Otherwise, print YES in the first line, and the required regular bracket sequence $$$t$$$ itself in the second line. If there are multiple answers — you may print any of them.

## Examples
```input
4
)(
(()
()
))()
```
```output
YES
(())
YES
()()()
NO
YES
()(()())
```

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
Monocarp is going to make a purchase with cost of exactly $$$m$$$ burles.

He has two types of coins, in the following quantities:

- coins worth $$$1$$$ burle: $$$a_1$$$ regular coins and infinitely many fancy coins;
- coins worth $$$k$$$ burles: $$$a_k$$$ regular coins and infinitely many fancy coins.

Monocarp wants to make his purchase in such a way that there's no change — the total worth of provided coins is exactly $$$m$$$. He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible.

What's the smallest total number of fancy coins he can use to make a purchase?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of testcases.

The only line of each testcase contains four integers $$$m, k, a_1$$$ and $$$a_k$$$ ($$$1 \le m \le 10^8$$$; $$$2 \le k \le 10^8$$$; $$$0 \le a_1, a_k \le 10^8$$$) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.

## Output Format
For each testcase, print a single integer — the smallest total number of fancy coins Monocarp can use to make a purchase.

## Examples
```input
4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0
```
```output
5
0
1
50000000
```

## Note
In the first testcase, there are no regular coins of either type. Monocarp can use $$$2$$$ fancy coins worth $$$1$$$ burle and $$$3$$$ fancy coins worth $$$3$$$ (since $$$k=3$$$) burles to get $$$11$$$ total burles with $$$5$$$ total fancy coins.

In the second testcase, Monocarp has a lot of regular coins of both types. He can use $$$11$$$ regular coins worth $$$1$$$ burle, for example. Notice that Monocarp doesn't have to minimize the total number of used coins. That way he uses $$$0$$$ fancy coins.

In the third testcase, Monocarp can use $$$5$$$ regular coins worth $$$1$$$ burle and $$$1$$$ regular coin worth $$$3$$$ burles. That will get him to $$$8$$$ total burles when he needs $$$11$$$. So, $$$1$$$ fancy coin worth $$$3$$$ burles is enough.

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 binary string $$$s$$$ (a binary string is a string consisting of characters 0 and/or 1).

Let's call a binary string balanced if the number of subsequences 01 (the number of indices $$$i$$$ and $$$j$$$ such that $$$1 \le i < j \le n$$$, $$$s_i=0$$$ and $$$s_j=1$$$) equals to the number of subsequences 10 (the number of indices $$$k$$$ and $$$l$$$ such that $$$1 \le k < l \le n$$$, $$$s_k=1$$$ and $$$s_l=0$$$) in it.

For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $$$6$$$. On the other hand, 11010 is not balanced, because the number of subsequences 01 is $$$1$$$, but the number of subsequences 10 is $$$5$$$.

You can perform the following operation any number of times: choose two characters in $$$s$$$ and swap them. Your task is to calculate the minimum number of operations to make the string $$$s$$$ balanced.

## Input Format
The only line contains the string $$$s$$$ ($$$3 \le |s| \le 100$$$) consisting of characters 0 and/or 1.

Additional constraint on the input: the string $$$s$$$ can be made balanced.

## Output Format
Print a single integer — the minimum number of swap operations to make the string $$$s$$$ balanced.

## Examples
```input
101
```
```output
0
```
-----
```input
1000110
```
```output
0
```
-----
```input
11010
```
```output
1
```
-----
```input
11001100
```
```output
2
```

## Note
In the first example, the string is already balanced, the number of both 01 and 10 is equal to $$$1$$$.

In the second example, the string is already balanced, the number of both 01 and 10 is equal to $$$6$$$.

In the third example, one of the possible answers is the following one: 11010 $$$\rightarrow$$$ 01110. After that, the number of both 01 and 10 is equal to $$$3$$$.

In the fourth example, one of the possible answers is the following one: 11001100 $$$\rightarrow$$$ 11001010 $$$\rightarrow$$$ 11000011. After that, the number of both 01 and 10 is equal to $$$8$$$.

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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a string $$$s$$$, consisting of lowercase Latin letters.

There's a cursor, initially placed between two adjacent letters of the string. The cursor can't be placed before the first or after the last letter.

In one move, you can perform one of three actions:

- move a cursor one position to the left (if that doesn't place it before the first letter);
- move a cursor one position to the right (if that doesn't place it after the last letter);
- let $$$x$$$ be the letter immediately to the left of the cursor, and $$$y$$$ be the letter immediately to the right of the cursor. Choose any pair of adjacent letters in the string such that the left of them is $$$x$$$ and the right of them is $$$y$$$, and move the cursor to the position between these two letters.

You are asked $$$m$$$ queries. In each query, you are given two integers $$$f$$$ and $$$t$$$, which correspond to two valid positions of the cursor in the string. In response to the query, you have to calculate the minimum number of operations required to move the cursor from position $$$f$$$ to position $$$t$$$.

## Input Format
The first line contains a string $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^4$$$), consisting of lowercase Latin letters.

The second line contains a single integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — the number of queries.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$f$$$ and $$$t$$$ ($$$1 \le f, t \le |s| - 1$$$) — the initial and the target positions of the cursor in the $$$i$$$-th query. Position $$$x$$$ means that the cursor is between the $$$x$$$-th and the $$$(x+1)$$$-st letters of the string ($$$1$$$-indexed).

## Output Format
For each query, print the minimum number of actions required to move the cursor from position $$$f$$$ to position $$$t$$$.

## Examples
```input
codecode
3
1 7
3 5
3 6
```
```output
3
2
2
```
-----
```input
abcdefghij
3
1 9
9 1
5 5
```
```output
8
8
0
```
-----
```input
aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11
```
```output
1
1
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 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: 10.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$2n$$$ tuples of values $$$(a, b, c)$$$, where $$$a$$$ and $$$b$$$ are positive integers and $$$c$$$ is a bracket '(' or ')'. Exactly $$$n$$$ tuples have $$$c = $$$'(' and the other $$$n$$$ tuples have $$$c =$$$ ')'.

You are asked to choose two positive values $$$x$$$ and $$$y$$$ ($$$x > 0$$$ and $$$y > 0$$$; not necessarily integers) and sort the tuples in the increasing value of $$$a \cdot x + b \cdot y$$$. If several tuples have the same value, you can place them in any order among themselves.

Is it possible to choose such $$$x$$$ and $$$y$$$ that taking brackets $$$c$$$ from the tuples in the resulting order produces a regular bracket sequence?

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence.

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 1500$$$).

The $$$i$$$-th of the next $$$2n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) and a character $$$c_i$$$ ($$$c_i = $$$'(' or $$$c_i = $$$')'). Exactly $$$n$$$ tuples have $$$c_i = $$$'(' and the other $$$n$$$ tuples have $$$c_i =$$$ ')'.

The sum of $$$n$$$ over all testcases doesn't exceed $$$1500$$$.

## Output Format
For each testcase, print "YES" if it's possible to choose such $$$x$$$ and $$$y$$$ that taking brackets $$$c$$$ from the tuples in the resulting order produces a regular bracket sequence. Otherwise, print "NO".

## Examples
```input
4
1
1 4 (
2 3 )
1
1 2 )
3 4 (
4
16 5 (
12 3 (
19 6 )
4 10 )
3 10 )
19 11 (
19 7 )
7 14 (
4
16 8 (
11 9 )
20 10 )
20 19 )
2 13 (
18 7 (
15 19 )
5 6 (
```
```output
YES
NO
NO
YES
```

## Note
In the first testcase, you can choose $$$x = 10, y = 0.1$$$. The values for tuples will be $$$10 \cdot 1 + 0.1 \cdot 4 = 10.4$$$ and $$$10 \cdot 2 + 0.1 \cdot 3 = 20.3$$$. Thus, the first tuple will go first, then the second one, making the bracket sequence "()", which is regular.

In the second testcase, you can't choose positive $$$x$$$ and $$$y$$$ such that the opening brackets gets assigned a value less or equal to the value of the closing bracket.

In the fourth testcase, you can choose $$$x = 0.6, y = 0.55$$$. The bracket sequence is "(()(()))".

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
We define an integer to be the most common on a subsegment, if its number of occurrences on that subsegment is larger than the number of occurrences of any other integer in that subsegment. A subsegment of an array is a consecutive segment of elements in the array $$$a$$$.

Given an array $$$a$$$ of size $$$n$$$, and an integer $$$k$$$, determine if there exists a non-empty subsegment of $$$a$$$ where $$$k$$$ is the most common element.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 100$$$) — the number of elements in array and the element which must be the most common.

The second line of each test case contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$\dots$$$, $$$a_n$$$ ($$$1 \le a_i \le 100$$$) — elements of the array.

## Output Format
For each test case output "YES" if there exists a subsegment in which $$$k$$$ is the most common element, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

## Examples
```input
7
5 4
1 4 3 4 1
4 1
2 3 4 4
5 6
43 5 60 4 2
2 5
1 5
4 1
5 3 3 1
1 3
3
5 3
3 4 1 5 5
```
```output
YES
NO
NO
YES
YES
YES
YES
```

## Note
In the first test case we need to check if there is a subsegment where the most common element is $$$4$$$.

On the subsegment $$$[2,5]$$$ the elements are $$$4, \ 3, \ 4, \ 1$$$.

- $$$4$$$ appears $$$2$$$ times;
- $$$1$$$ appears $$$1$$$ time;
- $$$3$$$ appears $$$1$$$ time.

This means that $$$4$$$ is the most common element on the subsegment $$$[2, 5]$$$, so there exists a subsegment where $$$4$$$ is the most common element.

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
Aca and Milovan, two fellow competitive programmers, decided to give Vasilije a problem to test his skills.

Vasilije is given three positive integers: $$$n$$$, $$$k$$$, and $$$x$$$, and he has to determine if he can choose $$$k$$$ distinct integers between $$$1$$$ and $$$n$$$, such that their sum is equal to $$$x$$$.

Since Vasilije is now in the weirdest city in Serbia where Aca and Milovan live, Cacak, the problem seems weird to him. So he needs your help with this problem.

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

The only line of each test case contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$1 \le x \le 4 \cdot 10^{10}$$$) — the maximum element he can choose, the number of elements he can choose and the sum he has to reach.

Note that the sum of $$$n$$$ over all test cases may exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case output one line: "YES", if it is possible to choose $$$k$$$ distinct integers between $$$1$$$ and $$$n$$$, such that their sum is equal to $$$x$$$, and "NO", if it isn't.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

## Examples
```input
12
5 3 10
5 3 3
10 10 55
6 5 20
2 1 26
187856 87856 2609202300
200000 190000 19000000000
28 5 2004
2 2 2006
9 6 40
47202 32455 613407217
185977 145541 15770805980
```
```output
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
```

## Note
In the first test case $$$n = 5,\ k=3,\ x=10$$$, so we can choose the numbers: $$$2$$$, $$$3$$$, $$$5$$$, whose sum is $$$10$$$, so the answer is "YES".

In the second test case $$$n = 5, \ k=3, \ x=3$$$, there is no three numbers which satisfies the condition, so the answer is "NO". It can be shown that there are no three numbers whose sum is $$$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 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 of integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you do the following:

- Choose a non-negative integer $$$m$$$, such that $$$2^m \leq n$$$.
- Subtract $$$1$$$ from $$$a_i$$$ for all integers $$$i$$$, such that $$$1 \leq i \leq 2^m$$$.

Can you sort the array in non-decreasing order by performing some number (possibly zero) of operations?

An array is considered non-decreasing if $$$a_i \leq a_{i + 1}$$$ for all integers $$$i$$$ such that $$$1 \leq i \leq n - 1$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 20$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the integers in array $$$a$$$ ($$$0 \leq a_i \leq 1000$$$).

## Output Format
For each test case, output "YES" if the array can be sorted, and "NO" otherwise.

## Examples
```input
8
5
1 2 3 4 5
5
6 5 3 4 4
9
6 5 5 7 5 6 6 8 7
4
4 3 2 1
6
2 2 4 5 3 2
8
1 3 17 19 27 57 179 13
5
3 17 57 179 92
10
1 2 3 4 0 6 7 8 9 10
```
```output
YES
YES
YES
NO
NO
NO
YES
YES
```

## Note
In the first test case, the array is already sorted in non-decreasing order, so we don't have to perform any operations.

In the second test case, we can choose $$$m = 1$$$ twice to get the array $$$[4, 3, 3, 4, 4]$$$. Then, we can choose $$$m = 0$$$ once and get the sorted in non-decreasing order array $$$[3, 3, 3, 4, 4]$$$.

In the third test case, we can choose $$$m = 0$$$ once and get the array $$$[5, 5, 5, 7, 5, 6, 6, 8, 7]$$$. Then, we can choose $$$m = 2$$$ twice and get the array $$$[3, 3, 3, 5, 5, 6, 6, 8, 7]$$$. After that, we can choose $$$m = 3$$$ once and get the sorted in non-decreasing order array $$$[2, 2, 2, 4, 4, 5, 5, 7, 7]$$$.

For the fourth and fifth test case, it can be shown that the array could not be sorted using these operations.

Now solve the problem and return the code.