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

# Problem
Serval soon said goodbye to Japari kindergarten, and began his life in Japari Primary School.

In his favorite math class, the teacher taught him the following interesting definitions.

A parenthesis sequence is a string, containing only characters "(" and ")".

A correct parenthesis sequence is a parenthesis sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, parenthesis sequences "()()", "(())" are correct (the resulting expressions are: "(1+1)+(1+1)", "((1+1)+1)"), while ")(" and ")" are not. Note that the empty string is a correct parenthesis sequence by definition.

We define that $$$|s|$$$ as the length of string $$$s$$$. A strict prefix $$$s[1\dots l]$$$ $$$(1\leq l< |s|)$$$ of a string $$$s = s_1s_2\dots s_{|s|}$$$ is string $$$s_1s_2\dots s_l$$$. Note that the empty string and the whole string are not strict prefixes of any string by the definition.

Having learned these definitions, he comes up with a new problem. He writes down a string $$$s$$$ containing only characters "(", ")" and "?". And what he is going to do, is to replace each of the "?" in $$$s$$$ independently by one of "(" and ")" to make all strict prefixes of the new sequence not a correct parenthesis sequence, while the new sequence should be a correct parenthesis sequence.

After all, he is just a primary school student so this problem is too hard for him to solve. As his best friend, can you help him to replace the question marks? If there are many solutions, any of them is acceptable.

## Input Format
The first line contains a single integer $$$|s|$$$ ($$$1\leq |s|\leq 3 \cdot 10^5$$$), the length of the string.

The second line contains a string $$$s$$$, containing only "(", ")" and "?".

## Output Format
A single line contains a string representing the answer.

If there are many solutions, any of them is acceptable.

If there is no answer, print a single line containing ":(" (without the quotes).

## Examples
```input
6
(?????
```
```output
(()())
```
-----
```input
10
(???(???(?
```
```output
:(
```

## Note
It can be proved that there is no solution for the second sample, so print ":(".

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
Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length of a random subsegment of a given segment. Then he left a bonus problem as homework, with the award of a garage kit from IOI. The bonus is to extend this problem to the general case as follows.

You are given a segment with length $$$l$$$. We randomly choose $$$n$$$ segments by choosing two points (maybe with non-integer coordinates) from the given segment equiprobably and the interval between the two points forms a segment. You are given the number of random segments $$$n$$$, and another integer $$$k$$$. The $$$2n$$$ endpoints of the chosen segments split the segment into $$$(2n+1)$$$ intervals. Your task is to calculate the expected total length of those intervals that are covered by at least $$$k$$$ segments of the $$$n$$$ random segments.

You should find the answer modulo $$$998244353$$$.

## Input Format
First line contains three space-separated positive integers $$$n$$$, $$$k$$$ and $$$l$$$ ($$$1\leq k \leq n \leq 2000$$$, $$$1\leq l\leq 10^9$$$).

## Output Format
Output one integer — the expected total length of all the intervals covered by at least $$$k$$$ segments of the $$$n$$$ random segments modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

## Examples
```input
1 1 1
```
```output
332748118
```
-----
```input
6 2 1
```
```output
760234711
```
-----
```input
7 5 3
```
```output
223383352
```
-----
```input
97 31 9984524
```
```output
267137618
```

## Note
In the first example, the expected total length is $$$\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}$$$, and $$$3^{-1}$$$ modulo $$$998244353$$$ is $$$332748118$$$.

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 long decimal number $$$a$$$ consisting of $$$n$$$ digits from $$$1$$$ to $$$9$$$. You also have a function $$$f$$$ that maps every digit from $$$1$$$ to $$$9$$$ to some (possibly the same) digit from $$$1$$$ to $$$9$$$.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in $$$a$$$, and replace each digit $$$x$$$ from this segment with $$$f(x)$$$. For example, if $$$a = 1337$$$, $$$f(1) = 1$$$, $$$f(3) = 5$$$, $$$f(7) = 3$$$, and you choose the segment consisting of three rightmost digits, you get $$$1553$$$ as the result.

What is the maximum possible number you can obtain applying this operation no more than once?

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of digits in $$$a$$$.

The second line contains a string of $$$n$$$ characters, denoting the number $$$a$$$. Each character is a decimal digit from $$$1$$$ to $$$9$$$.

The third line contains exactly $$$9$$$ integers $$$f(1)$$$, $$$f(2)$$$, ..., $$$f(9)$$$ ($$$1 \le f(i) \le 9$$$).

## Output Format
Print the maximum number you can get after applying the operation described in the statement no more than once.

## Examples
```input
4
1337
1 2 5 4 6 6 3 1 9
```
```output
1557
```
-----
```input
5
11111
9 8 7 6 5 4 3 2 1
```
```output
99999
```
-----
```input
2
33
1 1 1 1 1 1 1 1 1
```
```output
33
```

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
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence $$$a$$$ consisting of $$$n$$$ integers. All these integers are distinct, each value from $$$1$$$ to $$$n$$$ appears in the sequence exactly once.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence $$$[2, 1, 5, 4, 3]$$$ the answer is $$$4$$$ (you take $$$2$$$ and the sequence becomes $$$[1, 5, 4, 3]$$$, then you take the rightmost element $$$3$$$ and the sequence becomes $$$[1, 5, 4]$$$, then you take $$$4$$$ and the sequence becomes $$$[1, 5]$$$ and then you take $$$5$$$ and the sequence becomes $$$[1]$$$, the obtained increasing sequence is $$$[2, 3, 4, 5]$$$).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$. All these integers are pairwise distinct.

## Output Format
In the first line of the output print $$$k$$$ — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string $$$s$$$ of length $$$k$$$, where the $$$j$$$-th character of this string $$$s_j$$$ should be 'L' if you take the leftmost element during the $$$j$$$-th move and 'R' otherwise. If there are multiple answers, you can print any.

## Examples
```input
5
2 1 5 4 3
```
```output
4
LRRR
```
-----
```input
7
1 3 5 6 7 4 2
```
```output
7
LRLRLLL
```
-----
```input
3
1 2 3
```
```output
3
LLL
```
-----
```input
4
1 2 4 3
```
```output
4
LLRL
```

## Note
The first example is described in the problem statement.

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
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence $$$a$$$ consisting of $$$n$$$ integers.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence $$$[1, 2, 4, 3, 2]$$$ the answer is $$$4$$$ (you take $$$1$$$ and the sequence becomes $$$[2, 4, 3, 2]$$$, then you take the rightmost element $$$2$$$ and the sequence becomes $$$[2, 4, 3]$$$, then you take $$$3$$$ and the sequence becomes $$$[2, 4]$$$ and then you take $$$4$$$ and the sequence becomes $$$[2]$$$, the obtained increasing sequence is $$$[1, 2, 3, 4]$$$).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
In the first line of the output print $$$k$$$ — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string $$$s$$$ of length $$$k$$$, where the $$$j$$$-th character of this string $$$s_j$$$ should be 'L' if you take the leftmost element during the $$$j$$$-th move and 'R' otherwise. If there are multiple answers, you can print any.

## Examples
```input
5
1 2 4 3 2
```
```output
4
LRRR
```
-----
```input
7
1 3 5 6 5 4 2
```
```output
6
LRLRRR
```
-----
```input
3
2 2 2
```
```output
1
R
```
-----
```input
4
1 2 4 3
```
```output
4
LLRR
```

## Note
The first example is described in the problem statement.

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 two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. All elements of both arrays are from $$$0$$$ to $$$n-1$$$.

You can reorder elements of the array $$$b$$$ (if you want, you may leave the order of elements as it is). After that, let array $$$c$$$ be the array of length $$$n$$$, the $$$i$$$-th element of this array is $$$c_i = (a_i + b_i) \% n$$$, where $$$x \% y$$$ is $$$x$$$ modulo $$$y$$$.

Your task is to reorder elements of the array $$$b$$$ to obtain the lexicographically minimum possible array $$$c$$$.

Array $$$x$$$ of length $$$n$$$ is lexicographically less than array $$$y$$$ of length $$$n$$$, if there exists such $$$i$$$ ($$$1 \le i \le n$$$), that $$$x_i < y_i$$$, and for any $$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$, $$$b$$$ and $$$c$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < n$$$), where $$$b_i$$$ is the $$$i$$$-th element of $$$b$$$.

## Output Format
Print the lexicographically minimum possible array $$$c$$$. Recall that your task is to reorder elements of the array $$$b$$$ and obtain the lexicographically minimum possible array $$$c$$$, where the $$$i$$$-th element of $$$c$$$ is $$$c_i = (a_i + b_i) \% n$$$.

## Examples
```input
4
0 1 2 1
3 2 1 1
```
```output
1 0 0 2
```
-----
```input
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1
```
```output
0 0 0 1 0 2 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
There are $$$n$$$ people in a row. The height of the $$$i$$$-th person is $$$a_i$$$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $$$1$$$. For example, let heights of chosen people be $$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$$$, where $$$k$$$ is the number of people you choose. Then the condition $$$|a_{i_j} - a_{i_{j + 1}}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|a_{i_1} - a_{i_k}| \le 1$$$ should be also satisfied. $$$|x|$$$ means the absolute value of $$$x$$$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of people.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the height of the $$$i$$$-th person.

## Output Format
In the first line of the output print $$$k$$$ — the number of people in the maximum balanced circle.

In the second line print $$$k$$$ integers $$$res_1, res_2, \dots, res_k$$$, where $$$res_j$$$ is the height of the $$$j$$$-th person in the maximum balanced circle. The condition $$$|res_{j} - res_{j + 1}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|res_{1} - res_{k}| \le 1$$$ should be also satisfied.

## Examples
```input
7
4 3 5 1 2 2 1
```
```output
5
2 1 1 2 3
```
-----
```input
5
3 7 5 1 5
```
```output
2
5 5
```
-----
```input
3
5 1 4
```
```output
2
4 5
```
-----
```input
7
2 2 3 2 1 2 2
```
```output
7
1 2 2 2 2 3 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
Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length $$$k$$$ is vowelly if there are positive integers $$$n$$$ and $$$m$$$ such that $$$n\cdot m = k$$$ and when the word is written by using $$$n$$$ rows and $$$m$$$ columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer $$$k$$$ and you must either print a vowelly word of length $$$k$$$ or print $$$-1$$$ if no such word exists.

In this problem the vowels of the English alphabet are 'a', 'e', 'i', 'o' ,'u'.

## Input Format
Input consists of a single line containing the integer $$$k$$$ ($$$1\leq k \leq 10^4$$$) — the required length.

## Output Format
The output must consist of a single line, consisting of a vowelly word of length $$$k$$$ consisting of lowercase English letters if it exists or $$$-1$$$ if it does not.

If there are multiple possible words, you may output any of them.

## Examples
```input
7
```
```output
-1
```
-----
```input
36
```
```output
agoeuioaeiruuimaeoieauoweouoiaouimae
```

## Note
In the second example, the word "agoeuioaeiruuimaeoieauoweouoiaouimae" can be arranged into the following $$$6 \times 6$$$ grid:

It is easy to verify that every row and every column contain all the vowels.

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
Given a positive integer $$$m$$$, we say that a sequence $$$x_1, x_2, \dots, x_n$$$ of positive integers is $$$m$$$-cute if for every index $$$i$$$ such that $$$2 \le i \le n$$$ it holds that $$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$$$ for some positive integer $$$r_i$$$ satisfying $$$1 \le r_i \le m$$$.

You will be given $$$q$$$ queries consisting of three positive integers $$$a$$$, $$$b$$$ and $$$m$$$. For each query you must determine whether or not there exists an $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$. If such a sequence exists, you must additionally find an example of it.

## Input Format
The first line contains an integer number $$$q$$$ ($$$1 \le q \le 10^3$$$) — the number of queries.

Each of the following $$$q$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$), describing a single query.

## Output Format
For each query, if no $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$ exists, print $$$-1$$$.

Otherwise print an integer $$$k$$$ ($$$1 \le k \leq 50$$$), followed by $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le 10^{14}$$$). These integers must satisfy $$$x_1 = a$$$, $$$x_k = b$$$, and that the sequence $$$x_1, x_2, \dots, x_k$$$ is $$$m$$$-cute.

It can be shown that under the problem constraints, for each query either no $$$m$$$-cute sequence exists, or there exists one with at most $$$50$$$ terms.

If there are multiple possible sequences, you may print any of them.

## Examples
```input
2
5 26 2
3 9 1
```
```output
4 5 6 13 26
-1
```

## Note
Consider the sample. In the first query, the sequence $$$5, 6, 13, 26$$$ is valid since $$$6 = 5 + \bf{\color{blue} 1}$$$, $$$13 = 6 + 5 + {\bf\color{blue} 2}$$$ and $$$26 = 13 + 6 + 5 + {\bf\color{blue} 2}$$$ have the bold values all between $$$1$$$ and $$$2$$$, so the sequence is $$$2$$$-cute. Other valid sequences, such as $$$5, 7, 13, 26$$$ are also accepted.

In the second query, the only possible $$$1$$$-cute sequence starting at $$$3$$$ is $$$3, 4, 8, 16, \dots$$$, which does not contain $$$9$$$.

Now solve the problem and return the code.