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
In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $$$p$$$ of length $$$n$$$ to the zoo.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ occurs twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).

The gorillas had their own permutation $$$q$$$ of length $$$n$$$. They suggested that you count the number of pairs of integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) such that $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$.

The $$$\operatorname{MEX}$$$ of the sequence is the minimum integer positive number missing from this sequence. For example, $$$\operatorname{MEX}([1, 3]) = 2$$$, $$$\operatorname{MEX}([5]) = 1$$$, $$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$.

You do not want to risk your health, so you will not dare to refuse the gorillas.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the permutations length.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.

The third line contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — the elements of the permutation $$$q$$$.

## Output Format
Print a single integer — the number of suitable pairs $$$l$$$ and $$$r$$$.

## Examples
```input
3
1 3 2
2 1 3
```
```output
2
```
-----
```input
7
7 3 6 2 1 5 4
6 7 2 5 3 1 4
```
```output
16
```
-----
```input
6
1 2 3 4 5 6
6 5 4 3 2 1
```
```output
11
```

## Note
In the first example, two segments are correct – $$$[1, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$4$$$ in both arrays and $$$[3, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$1$$$ in both of arrays.

In the second example, for example, the segment $$$[1, 4]$$$ is correct, and the segment $$$[6, 7]$$$ isn't correct, because $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 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
In this problem, unlike problem A, you need to look for unluckiest number, not the luckiest one.

Note that the constraints of this problem differ from such in problem A.

Olympus City recently launched the production of personal starships. Now everyone on Mars can buy one and fly to other planets inexpensively.

Each starship has a number —some positive integer $$$x$$$. Let's define the luckiness of a number $$$x$$$ as the difference between the largest and smallest digits of that number. For example, $$$142857$$$ has $$$8$$$ as its largest digit and $$$1$$$ as its smallest digit, so its luckiness is $$$8-1=7$$$. And the number $$$111$$$ has all digits equal to $$$1$$$, so its luckiness is zero.

Hateehc is a famous Martian blogger who often flies to different corners of the solar system. To release interesting videos even faster, he decided to buy himself a starship. When he came to the store, he saw starships with numbers from $$$l$$$ to $$$r$$$ inclusively. While in the store, Hateehc wanted to find a starship with the unluckiest number.

Since there are a lot of starships in the store, and Hateehc can't program, you have to help the blogger and write a program that answers his question.

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

Each of the following $$$t$$$ lines contains a description of the test case. The description consists of two integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — the largest and smallest numbers of the starships in the store.

## Output Format
Print $$$t$$$ lines, one line for each test case, containing the unluckiest starship number in the store.

If there are several ways to choose the unluckiest number, output any of them.

## Examples
```input
5
59 63
42 49
48 53
90 90
1 100
```
```output
63
44
53
90
1
```

## Note
Let's look at two test examples:

- the luckiness of the number $$$59$$$ is $$$9 - 5 = 4$$$;
- the luckiness of $$$60$$$ equals $$$6 - 0 = 6$$$;
- the luckiness of $$$61$$$ equals $$$6 - 1 = 5$$$;
- the luckiness of $$$62$$$ equals $$$6 - 2 = 4$$$;
- the luckiness of $$$63$$$ is $$$6 - 3 = 3$$$.

In the fifth test case, the unluckiest numbers are $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$11$$$, $$$22$$$, $$$33$$$, $$$44$$$, $$$55$$$, $$$66$$$, $$$77$$$, $$$88$$$, $$$99$$$, so you are allowed to choose any of them.

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

# Problem
Petya and his friend, the robot Petya++, have a common friend — the cyborg Petr#. Sometimes Petr# comes to the friends for a cup of tea and tells them interesting problems.

Today, Petr# told them the following problem.

A palindrome is a sequence that reads the same from left to right as from right to left. For example, $$$[38, 12, 8, 12, 38]$$$, $$$[1]$$$, and $$$[3, 8, 8, 3]$$$ are palindromes.

Let's call the palindromicity of a sequence $$$a_1, a_2, \dots, a_n$$$ the minimum count of elements that need to be replaced to make this sequence a palindrome. For example, the palindromicity of the sequence $$$[38, 12, 8, 38, 38]$$$ is $$$1$$$ since it is sufficient to replace the number $$$38$$$ at the fourth position with the number $$$12$$$. And the palindromicity of the sequence $$$[3, 3, 5, 5, 5]$$$ is two since you can replace the first two threes with fives, and the resulting sequence $$$[5, 5, 5, 5, 5]$$$ is a palindrome.

Given a sequence $$$a$$$ of length $$$n$$$, and an odd integer $$$k$$$, you need to find the sum of palindromicity of all subarrays of length $$$k$$$, i. e., the sum of the palindromicity values for the sequences $$$a_i, a_{i+1}, \dots, a_{i+k-1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n-k+1$$$.

The students quickly solved the problem. Can you do it too?

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le n$$$, $$$k$$$ is odd) — the length of the sequence and the length of subarrays for which it is necessary to determine whether they are palindromes.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the sequence itself.

## Output Format
Output a single integer — the total palindromicity of all subarrays of length $$$k$$$.

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

## Note
In the first example, the palindromicity of the subarray $$$[1, 2, 8, 2, 5]$$$ is $$$1$$$, the palindromicity of the string $$$[2, 8, 2, 5, 2]$$$ is also $$$1$$$, the palindromicity of the string $$$[8, 2, 5, 2, 8]$$$ is $$$0$$$, and the palindromicity of the string $$$[2, 5, 2, 8, 6]$$$ is $$$2$$$. The total palindromicity is $$$1+1+0+2 = 4$$$.

In the second example, the only substring of length $$$9$$$ coincides with the entire string, and its palindromicity is $$$0$$$, so the answer is also $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the three versions is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

Maxim is a minibus driver on Venus.

To ride on Maxim's minibus, you need a ticket. Each ticket has a number consisting of $$$n$$$ digits. However, as we know, the residents of Venus use a numeral system with base $$$k$$$, rather than the decimal system. Therefore, the ticket number can be considered as a sequence of $$$n$$$ integers from $$$0$$$ to $$$k-1$$$, inclusive.

The residents of Venus consider a ticket to be lucky if there is a digit on it that is equal to the sum of the remaining digits, modulo $$$k$$$. For example, if $$$k=10$$$, then the ticket $$$7135$$$ is lucky because $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$. On the other hand, the ticket $$$7136$$$ is not lucky because no digit is equal to the sum of the others modulo $$$10$$$.

Once, while on a trip, Maxim wondered: how many lucky tickets exist? At the same time, Maxim understands that this number can be very large, so he is interested only in the answer modulo some prime number $$$m$$$.

## Input Format
The only line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 30$$$, $$$10^8 \le m \le 10^9 + 7$$$, $$$m$$$ is a prime number) — the number of digits on the ticket, the base of the numeral system on Venus, and the module for answer calculation.

## Output Format
Print one integer — the number of lucky tickets modulo $$$m$$$, i. e. the remainder after dividing the answer by $$$m$$$.

## Examples
```input
3 2 1000000007
```
```output
4
```
-----
```input
3 4 1000000007
```
```output
28
```

## Note
In the first example, there are only four lucky tickets: $$$000$$$, $$$011$$$, $$$101$$$, and $$$110$$$.

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
This is the medium version of the problem. The only difference between the three versions is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

Maxim is a minibus driver on Venus.

To ride on Maxim's minibus, you need a ticket. Each ticket has a number consisting of $$$n$$$ digits. However, as we know, the residents of Venus use a numeral system with base $$$k$$$, rather than the decimal system. Therefore, the ticket number can be considered as a sequence of $$$n$$$ integers from $$$0$$$ to $$$k-1$$$, inclusive.

The residents of Venus consider a ticket to be lucky if there is a digit on it that is equal to the sum of the remaining digits, modulo $$$k$$$. For example, if $$$k=10$$$, then the ticket $$$7135$$$ is lucky because $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$. On the other hand, the ticket $$$7136$$$ is not lucky because no digit is equal to the sum of the others modulo $$$10$$$.

Once, while on a trip, Maxim wondered: how many lucky tickets exist? At the same time, Maxim understands that this number can be very large, so he is interested only in the answer modulo some prime number $$$m$$$.

## Input Format
The only line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 100$$$, $$$10^8 \le m \le 10^9 + 7$$$, $$$m$$$ is a prime number) — the number of digits on the ticket, the base of the numeral system on Venus, and the module for answer calculation.

## Output Format
Print one integer — the number of lucky tickets modulo $$$m$$$, i. e. the remainder after dividing the answer by $$$m$$$.

## Examples
```input
3 2 1000000007
```
```output
4
```
-----
```input
3 4 1000000007
```
```output
28
```

## Note
In the first example, there are only four lucky tickets: $$$000$$$, $$$011$$$, $$$101$$$, and $$$110$$$.

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
This is the hard version of the problem. The only difference between the three versions is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

Maxim is a minibus driver on Venus.

To ride on Maxim's minibus, you need a ticket. Each ticket has a number consisting of $$$n$$$ digits. However, as we know, the residents of Venus use a numeral system with base $$$k$$$, rather than the decimal system. Therefore, the ticket number can be considered as a sequence of $$$n$$$ integers from $$$0$$$ to $$$k-1$$$, inclusive.

The residents of Venus consider a ticket to be lucky if there is a digit on it that is equal to the sum of the remaining digits, modulo $$$k$$$. For example, if $$$k=10$$$, then the ticket $$$7135$$$ is lucky because $$$7 + 1 + 5 \equiv 3 \pmod{10}$$$. On the other hand, the ticket $$$7136$$$ is not lucky because no digit is equal to the sum of the others modulo $$$10$$$.

Once, while on a trip, Maxim wondered: how many lucky tickets exist? At the same time, Maxim understands that this number can be very large, so he is interested only in the answer modulo some prime number $$$m$$$.

## Input Format
The only line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 2000$$$, $$$10^8 \le m \le 10^9 + 7$$$, $$$m$$$ is a prime number) — the number of digits on the ticket, the base of the numeral system on Venus, and the module for answer calculation.

## Output Format
Print one integer — the number of lucky tickets modulo $$$m$$$, i. e. the remainder after dividing the answer by $$$m$$$.

## Examples
```input
3 2 1000000007
```
```output
4
```
-----
```input
3 4 1000000007
```
```output
28
```

## Note
In the first example, there are only four lucky tickets: $$$000$$$, $$$011$$$, $$$101$$$, and $$$110$$$.

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
A sequence of $$$m$$$ integers $$$a_{1}, a_{2}, \ldots, a_{m}$$$ is good, if and only if there exists at least one $$$i$$$ ($$$1 \le i \le m$$$) such that $$$a_{i} = i$$$. For example, $$$[3,2,3]$$$ is a good sequence, since $$$a_{2} = 2$$$, $$$a_{3} = 3$$$, while $$$[3,1,1]$$$ is not a good sequence, since there is no $$$i$$$ such that $$$a_{i} = i$$$.

A sequence $$$a$$$ is beautiful, if and only if there exists at least one subsequence of $$$a$$$ satisfying that this subsequence is good. For example, $$$[4,3,2]$$$ is a beautiful sequence, since its subsequence $$$[4,2]$$$ is good, while $$$[5,3,4]$$$ is not a beautiful sequence.

A sequence $$$b$$$ is a subsequence of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements.

Now you are given a sequence, check whether it is beautiful or not.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the given sequence.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le 10^9$$$), representing the sequence.

## Output Format
For each test case, output "YES" or "NO"(without quotes) in one line, representing whether the given sequence is beautiful.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

## Note
In the first test case, the good subsequence is $$$b=[3,2]$$$, where $$$b_{2} = 2$$$.

In the second test case, the good subsequence is $$$b=[2,4,3]$$$, where $$$b_{3} = 3$$$.

In the fourth test case, the good subsequence is $$$b=[1]$$$, where $$$b_{1} = 1$$$.

In the fifth test case, the good subsequence is $$$b=[2,2]$$$, where $$$b_{2} = 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 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
This problem is about candy. Initially, you only have $$$1$$$ candy, and you want to have exactly $$$n$$$ candies.

You can use the two following spells in any order at most $$$40$$$ times in total.

- Assume you have $$$x$$$ candies now. If you use the first spell, then $$$x$$$ candies become $$$2x-1$$$ candies.
- Assume you have $$$x$$$ candies now. If you use the second spell, then $$$x$$$ candies become $$$2x+1$$$ candies.

Construct a sequence of spells, such that after using them in order, you will have exactly $$$n$$$ candies, or determine it's impossible.

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

Each test case contains one line with a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the required final number of candies.

## Output Format
For each test case, output the following.

If it's possible to eventually have $$$n$$$ candies within $$$40$$$ spells, in the first line print an integer $$$m$$$ ($$$1 \le m \le 40$$$), representing the total number of spells you use.

In the second print $$$m$$$ integers $$$a_{1}, a_{2}, \ldots, a_{m}$$$ ($$$a_{i}$$$ is $$$1$$$ or $$$2$$$) separated by spaces, where $$$a_{i} = 1$$$ means that you use the first spell in the $$$i$$$-th step, while $$$a_{i} = 2$$$ means that you use the second spell in the $$$i$$$-th step.

Note that you do not have to minimize $$$m$$$, and if there are multiple solutions, you may output any one of them.

If it's impossible, output $$$-1$$$ in one line.

## Examples
```input
4
2
3
7
17
```
```output
-1
1
2 
2
2 2 
4
2 1 1 1
```

## Note
For $$$n=3$$$, you can just use the second spell once, and then have $$$2 \cdot 1 + 1 = 3$$$ candies.

For $$$n=7$$$, you can use the second spell twice. After the first step, you will have $$$3$$$ candies. And after the second step, you will have $$$2 \cdot 3 + 1 = 7$$$ candies.

Now solve the problem and return the code.