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 $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Find the maximum value of $$$max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$ over all pairs $$$(l, r)$$$ of integers for which $$$1 \le l < r \le n$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer  — the maximum possible value of the product from the statement.

## Examples
```input
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328
```
```output
12
6
4761
381274500335
```

## Note
Let $$$f(l, r) = max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$.

In the first test case,

- $$$f(1, 2) = max(a_1, a_2) \cdot min(a_1, a_2) = max(2, 4) \cdot min(2, 4) = 4 \cdot 2 = 8$$$.
- $$$f(1, 3) = max(a_1, a_2, a_3) \cdot min(a_1, a_2, a_3) = max(2, 4, 3) \cdot min(2, 4, 3) = 4 \cdot 2 = 8$$$.
- $$$f(2, 3) = max(a_2, a_3) \cdot min(a_2, a_3) = max(4, 3) \cdot min(4, 3) = 4 \cdot 3 = 12$$$.

So the maximum is $$$f(2, 3) = 12$$$.

In the second test case, the maximum is $$$f(1, 2) = f(1, 3) = f(2, 3) = 6$$$.

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 $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$. Find the maximum value of $$$i \cdot j - k \cdot (a_i | a_j)$$$ over all pairs $$$(i, j)$$$ of integers with $$$1 \le i < j \le n$$$. Here, $$$|$$$ is the bitwise OR operator.

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

The first line of each test case contains two integers $$$n$$$ ($$$2 \le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le \min(n, 100)$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer  — the maximum possible value of $$$i \cdot j - k \cdot (a_i | a_j)$$$.

## Examples
```input
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6
```
```output
-1
-4
3
12
```

## Note
Let $$$f(i, j) = i \cdot j - k \cdot (a_i | a_j)$$$.

In the first test case,

- $$$f(1, 2) = 1 \cdot 2 - k \cdot (a_1 | a_2) = 2 - 3 \cdot (1 | 1) = -1$$$.
- $$$f(1, 3) = 1 \cdot 3 - k \cdot (a_1 | a_3) = 3 - 3 \cdot (1 | 3) = -6$$$.
- $$$f(2, 3) = 2 \cdot 3 - k \cdot (a_2 | a_3) = 6 - 3 \cdot (1 | 3) = -3$$$.

So the maximum is $$$f(1, 2) = -1$$$.

In the fourth test case, the maximum is $$$f(3, 4) = 12$$$.

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 two integers $$$n$$$ and $$$m$$$. Find the $$$\operatorname{MEX}$$$ of the sequence $$$n \oplus 0, n \oplus 1, \ldots, n \oplus m$$$. Here, $$$\oplus$$$ is the bitwise XOR operator.

$$$\operatorname{MEX}$$$ of the sequence of non-negative integers is the smallest non-negative integer that doesn't appear in this sequence. For example, $$$\operatorname{MEX}(0, 1, 2, 4) = 3$$$, and $$$\operatorname{MEX}(1, 2021) = 0$$$.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n, m \le 10^9$$$).

## Output Format
For each test case, print a single integer  — the answer to the problem.

## Examples
```input
5
3 5
4 6
3 2
69 696
123456 654321
```
```output
4
3
0
640
530866
```

## Note
In the first test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2, 3 \oplus 3, 3 \oplus 4, 3 \oplus 5$$$, or $$$3, 2, 1, 0, 7, 6$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$4$$$.

In the second test case, the sequence is $$$4 \oplus 0, 4 \oplus 1, 4 \oplus 2, 4 \oplus 3, 4 \oplus 4, 4 \oplus 5, 4 \oplus 6$$$, or $$$4, 5, 6, 7, 0, 1, 2$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$3$$$.

In the third test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2$$$, or $$$3, 2, 1$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$. Find any string $$$s$$$ of length $$$n$$$ consisting only of English lowercase letters such that each non-empty substring of $$$s$$$ occurs in $$$s$$$ an odd number of times. If there are multiple such strings, output any. It can be shown that such string always exists under the given constraints.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single line containing the string $$$s$$$. If there are multiple such strings, output any. It can be shown that such string always exists under the given constraints.

## Examples
```input
4
3
5
9
19
```
```output
abc
diane
bbcaabbba
youarethecutestuwuu
```

## Note
In the first test case, each substring of "abc" occurs exactly once.

In the third test case, each substring of "bbcaabbba" occurs an odd number of times. In particular, "b" occurs $$$5$$$ times, "a" and "bb" occur $$$3$$$ times each, and each of the remaining substrings occurs exactly 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: 512.0 MB

# Problem
You have a permutation: an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of distinct integers from $$$1$$$ to $$$n$$$. The length of the permutation $$$n$$$ is odd.

Consider the following algorithm of sorting the permutation in increasing order.

A helper procedure of the algorithm, $$$f(i)$$$, takes a single argument $$$i$$$ ($$$1 \le i \le n-1$$$) and does the following. If $$$a_i > a_{i+1}$$$, the values of $$$a_i$$$ and $$$a_{i+1}$$$ are exchanged. Otherwise, the permutation doesn't change.

The algorithm consists of iterations, numbered with consecutive integers starting with $$$1$$$. On the $$$i$$$-th iteration, the algorithm does the following:

- if $$$i$$$ is odd, call $$$f(1), f(3), \ldots, f(n - 2)$$$;
- if $$$i$$$ is even, call $$$f(2), f(4), \ldots, f(n - 1)$$$.

It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.

After how many iterations will this happen for the first time?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 999$$$; $$$n$$$ is odd) — the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$999$$$.

## Output Format
For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.

If the given permutation is already sorted, print $$$0$$$.

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

## Note
In the first test case, the permutation will be changing as follows:

- after the $$$1$$$-st iteration: $$$[2, 3, 1]$$$;
- after the $$$2$$$-nd iteration: $$$[2, 1, 3]$$$;
- after the $$$3$$$-rd iteration: $$$[1, 2, 3]$$$.

In the second test case, the permutation will be changing as follows:

- after the $$$1$$$-st iteration: $$$[4, 5, 1, 7, 2, 3, 6]$$$;
- after the $$$2$$$-nd iteration: $$$[4, 1, 5, 2, 7, 3, 6]$$$;
- after the $$$3$$$-rd iteration: $$$[1, 4, 2, 5, 3, 7, 6]$$$;
- after the $$$4$$$-th iteration: $$$[1, 2, 4, 3, 5, 6, 7]$$$;
- after the $$$5$$$-th iteration: $$$[1, 2, 3, 4, 5, 6, 7]$$$.

In the third test case, the permutation is already sorted and the answer is $$$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
Casimir has a string $$$s$$$ which consists of capital Latin letters 'A', 'B', and 'C' only. Each turn he can choose to do one of the two following actions:

- he can either erase exactly one letter 'A' and exactly one letter 'B' from arbitrary places of the string (these letters don't have to be adjacent);
- or he can erase exactly one letter 'B' and exactly one letter 'C' from arbitrary places in the string (these letters don't have to be adjacent).

Therefore, each turn the length of the string is decreased exactly by $$$2$$$. All turns are independent so for each turn, Casimir can choose any of two possible actions.

For example, with $$$s$$$ $$$=$$$ "ABCABC" he can obtain a string $$$s$$$ $$$=$$$ "ACBC" in one turn (by erasing the first occurrence of 'B' and the second occurrence of 'A'). There are also many other options for a turn aside from this particular example.

For a given string $$$s$$$ determine whether there is a sequence of actions leading to an empty string. In other words, Casimir's goal is to erase all letters from the string. Is there a way to do this?

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

Each test case is described by one string $$$s$$$, for which you need to determine if it can be fully erased by some sequence of turns. The string $$$s$$$ consists of capital letters 'A', 'B', 'C' and has a length from $$$1$$$ to $$$50$$$ letters, inclusive.

## Output Format
Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if there is a way to fully erase the corresponding string and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).

## Examples
```input
6
ABACAB
ABBA
AC
ABC
CABCBB
BCBCBCBCBCBCBCBC
```
```output
NO
YES
NO
NO
YES
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 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
An important meeting is to be held and there are exactly $$$n$$$ people invited. At any moment, any two people can step back and talk in private. The same two people can talk several (as many as they want) times per meeting.

Each person has limited sociability. The sociability of the $$$i$$$-th person is a non-negative integer $$$a_i$$$. This means that after exactly $$$a_i$$$ talks this person leaves the meeting (and does not talk to anyone else anymore). If $$$a_i = 0$$$, the $$$i$$$-th person leaves the meeting immediately after it starts.

A meeting is considered most productive if the maximum possible number of talks took place during it.

You are given an array of sociability $$$a$$$, determine which people should talk to each other so that the total number of talks is as large as possible.

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

The next $$$2t$$$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) —the number of people in the meeting. The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) — the sociability parameters of all people.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that the sum of all $$$a_i$$$ (over all test cases and all $$$i$$$) does not exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$t$$$ answers to all test cases.

On the first line of each answer print the number $$$k$$$ — the maximum number of talks possible in a meeting.

On each of the next $$$k$$$ lines print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$ and $$$i \neq j$$$) — the numbers of people who will have another talk.

If there are several possible answers, you may print any of them.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Theofanis has a riddle for you and if you manage to solve it, he will give you a Cypriot snack halloumi for free (Cypriot cheese).

You are given an integer $$$n$$$. You need to find two integers $$$l$$$ and $$$r$$$ such that $$$-10^{18} \le l < r \le 10^{18}$$$ and $$$l + (l + 1) + \ldots + (r - 1) + r = n$$$.

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

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

## Output Format
For each test case, print the two integers $$$l$$$ and $$$r$$$ such that $$$-10^{18} \le l < r \le 10^{18}$$$ and $$$l + (l + 1) + \ldots + (r - 1) + r = n$$$.

It can be proven that an answer always exists. If there are multiple answers, print any.

## Examples
```input
7
1
2
3
6
100
25
3000000000000
```
```output
0 1
-1 2 
1 2 
1 3 
18 22
-2 7
999999999999 1000000000001
```

## Note
In the first test case, $$$0 + 1 = 1$$$.

In the second test case, $$$(-1) + 0 + 1 + 2 = 2$$$.

In the fourth test case, $$$1 + 2 + 3 = 6$$$.

In the fifth test case, $$$18 + 19 + 20 + 21 + 22 = 100$$$.

In the sixth test case, $$$(-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 25$$$.

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
Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of $$$n$$$. For example, for $$$n = 4$$$ number $$$17$$$ is special, because it can be written as $$$4^0 + 4^2 = 1 + 16 = 17$$$, but $$$9$$$ is not.

Theofanis asks you to help him find the $$$k$$$-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo $$$10^9+7$$$.

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$).

## Output Format
For each test case, print one integer — the $$$k$$$-th special number in increasing order modulo $$$10^9+7$$$.

## Examples
```input
3
3 4
2 12
105 564
```
```output
9
12
3595374
```

## Note
For $$$n = 3$$$ the sequence is $$$[1,3,4,9...]$$$

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
It is the easy version of the problem. The difference is that in this version, there are no nodes with already chosen colors.

Theofanis is starving, and he wants to eat his favorite food, sheftalia. However, he should first finish his homework. Can you help him with this problem?

You have a perfect binary tree of $$$2^k - 1$$$ nodes — a binary tree where all vertices $$$i$$$ from $$$1$$$ to $$$2^{k - 1} - 1$$$ have exactly two children: vertices $$$2i$$$ and $$$2i + 1$$$. Vertices from $$$2^{k - 1}$$$ to $$$2^k - 1$$$ don't have any children. You want to color its vertices with the $$$6$$$ Rubik's cube colors (White, Green, Red, Blue, Orange and Yellow).

Let's call a coloring good when all edges connect nodes with colors that are neighboring sides in the Rubik's cube.

A picture of Rubik's cube and its 2D map.

More formally:

- a white node can not be neighboring with white and yellow nodes;
- a yellow node can not be neighboring with white and yellow nodes;
- a green node can not be neighboring with green and blue nodes;
- a blue node can not be neighboring with green and blue nodes;
- a red node can not be neighboring with red and orange nodes;
- an orange node can not be neighboring with red and orange nodes;

You want to calculate the number of the good colorings of the binary tree. Two colorings are considered different if at least one node is colored with a different color.

The answer may be too large, so output the answer modulo $$$10^9+7$$$.

## Input Format
The first and only line contains the integers $$$k$$$ ($$$1 \le k \le 60$$$) — the number of levels in the perfect binary tree you need to color.

## Output Format
Print one integer — the number of the different colorings modulo $$$10^9+7$$$.

## Examples
```input
3
```
```output
24576
```
-----
```input
14
```
```output
934234
```

## Note
In the picture below, you can see one of the correct colorings of the first example.

Now solve the problem and return the code.