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

# Problem
It is well known that quick sort works by randomly selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. But Jellyfish thinks that choosing a random element is just a waste of time, so she always chooses the first element to be the pivot. The time her code needs to run can be calculated by the following pseudocode:

Now you want to show her that her code is slow. When the function $$$\mathrm{fun(A)}$$$ is greater than or equal to $$$lim$$$, her code will get $$$\text{Time Limit Exceeded}$$$. You want to know how many distinct permutations $$$P$$$ of $$$[1, 2, \dots, n]$$$ satisfies $$$\mathrm{fun(P)} \geq lim$$$. Because the answer may be large, you will only need to find the answer modulo $$$10^9+7$$$.

## Input Format
The only line of the input contains two integers $$$n$$$ and $$$lim$$$ ($$$1 \leq n \leq 200$$$, $$$1 \leq lim \leq 10^9$$$).

## Output Format
Output the number of different permutations that satisfy the condition modulo $$$10^9+7$$$.

## Examples
```input
4 10
```
```output
8
```
-----
```input
8 32
```
```output
1280
```

## Note
In the first example, $$$P = [1, 4, 2, 3]$$$ satisfies the condition, because: $$$\mathrm{fun([1, 4, 2, 3]) = 4 + fun([4, 2, 3]) = 7 + fun([2, 3]) = 9 + fun([3]) = 10}$$$

Do remember to output the answer modulo $$$10^9+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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Jellyfish always uses OEIS to solve math problems, but now she finds a problem that cannot be solved by OEIS:

Count the number of permutations $$$p$$$ of $$$[1, 2, \dots, n]$$$ such that for all $$$(l, r)$$$ such that $$$l \leq r \leq m_l$$$, the subarray $$$[p_l, p_{l+1}, \dots, p_r]$$$ is not a permutation of $$$[l, l+1, \dots, r]$$$.

Since the answer may be large, you only need to find the answer modulo $$$10^9+7$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$) — the length of the permutation.

The second line of the input contains $$$n$$$ integers $$$m_1, m_2, \dots, m_n$$$ ($$$0 \leq m_i \leq n$$$).

## Output Format
Output the number of different permutations that satisfy the conditions, modulo $$$10^9+7$$$.

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

## Note
In the first example, $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ satisfies the condition.

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
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 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
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 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 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.
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
Let $$$f$$$($$$x$$$) be the floor of the binary logarithm of $$$x$$$. In other words, $$$f$$$($$$x$$$) is largest non-negative integer $$$y$$$, such that $$$2^y$$$ does not exceed $$$x$$$.

Let $$$g$$$($$$x$$$) be the floor of the logarithm of $$$x$$$ with base $$$f$$$($$$x$$$). In other words, $$$g$$$($$$x$$$) is the largest non-negative integer $$$z$$$, such that $$${f(x)}^{z}$$$ does not exceed $$$x$$$.

You are given $$$q$$$ queries. The $$$i$$$-th query consists of two integers $$$l_i$$$ and $$$r_i$$$. The answer to the query is the sum of $$$g$$$($$$k$$$) across all integers $$$k$$$, such that $$$l_i \leq k \leq r_i$$$. Since the answers might be large, print them modulo $$${10^9 + 7}$$$.

## Input Format
The first line contains a single integer $$$q$$$ — the number of queries ($$$1 \leq q \leq 10^5$$$).

The next $$$q$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ — the bounds of the $$$i$$$-th query ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$).

## Output Format
For each query, output the answer to the query modulo $$$10^9 + 7$$$.

## Examples
```input
12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625
```
```output
6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692
```

## Note
The table below contains the values of the functions $$$f$$$($$$x$$$) and $$$g$$$($$$x$$$) for all $$$x$$$ such that $$$1 \leq x \leq 8$$$.

$$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
On the official website of Berland, each account has two parameters: username and ID.

Username is a string consisting of lowercase Latin letters and/or digits, which contains at least one letter. For example, user0, 1fox1, zzzz are correct usernames, but 1337 and User22 are not.

The ID of the account for a given username is generated as follows: a positive integer without leading zeroes is appended to the end of the username. For example, the ID user0125 can be generated by the following usernames: user012, user01, user0; but neither by user nor us.

You are given a string $$$s$$$ — a valid ID. Your task is to determine any valid username that can generate the given ID. If there are several correct usernames, you can print any of them.

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

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

Additional constraint on input: there is at least one valid username that can generate the given ID.

## Output Format
For each test case on a separate line, print a string — any valid username that can generate the given ID. If there are multiple correct usernames, you can print any of them.

## Examples
```input
4
user0125
a1
kotlin990000
1code0forces101
```
```output
user0
a
kotlin9
1code0forces
```

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
Monocarp is a security guard in Berland State University. Every day, he tracks how many people and at what time enter and leave the university. He writes this information down as follows:

- when someone enters the university, Monocarp writes a plus sign '+';
- when someone leaves the university, Monocarp writes a minus sign '-'.

At the beginning of the current day, there are no people at the university, except for Monocarp. During the day, Monocarp wrote out a sequence $$$s$$$. The characters in $$$s$$$ are listed in the order Monocarp wrote them.

Suddenly, Monocarp's boss decided to check his work. Unfortunately, Monocarp is a bit careless. So, the sequence $$$s$$$ that he wrote might be impossible. For example, the sequence "+--" can't happen, since it represents a scenario when one person enters the university and two leave.

Before his boss starts checking the sequence, Monocarp has the time to swap at most one pair of characters in it. Can he do it in such a way that the resulting sequence is plausible? Note that if the given sequence is already plausible, Monocarp doesn't have to swap anything.

## 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 a single string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting only of characters '+' and/or '-'. A plus sign '+' represents a person entering the university. A minus sign '-' represents a person leaving the university.

The sum of all $$$|s|$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print an answer.

If it's impossible to swap at most one pair of characters so that the resulting sequence is plausible, print -1.

Otherwise, print two integers. If you swap one pair of characters, print two distinct integers from $$$1$$$ to $$$n$$$ — the indices of characters to swap. If you don't swap, print one integer from $$$1$$$ to $$$n$$$ twice — swap a character with itself.

If there are multiple answers, print any of them.

## Examples
```input
6
-+
+-
+++-
---++
+
-
```
```output
1 2
1 1
1 1
-1
1 1
-1
```

Now solve the problem and return the code.