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
Let $$$f(i)$$$ denote the minimum positive integer $$$x$$$ such that $$$x$$$ is not a divisor of $$$i$$$.

Compute $$$\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$. In other words, compute $$$f(1)+f(2)+\dots+f(n)$$$ modulo $$$10^9+7$$$.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 10^{16}$$$).

## Output Format
For each test case, output a single integer $$$ans$$$, where $$$ans=\sum_{i=1}^n f(i)$$$ modulo $$$10^9+7$$$.

## Examples
```input
6
1
2
3
4
10
10000000000000000
```
```output
2
5
7
10
26
366580019
```

## Note
In the fourth test case $$$n=4$$$, so $$$ans=f(1)+f(2)+f(3)+f(4)$$$.

- $$$1$$$ is a divisor of $$$1$$$ but $$$2$$$ isn't, so $$$2$$$ is the minimum positive integer that isn't a divisor of $$$1$$$. Thus, $$$f(1)=2$$$.
- $$$1$$$ and $$$2$$$ are divisors of $$$2$$$ but $$$3$$$ isn't, so $$$3$$$ is the minimum positive integer that isn't a divisor of $$$2$$$. Thus, $$$f(2)=3$$$.
- $$$1$$$ is a divisor of $$$3$$$ but $$$2$$$ isn't, so $$$2$$$ is the minimum positive integer that isn't a divisor of $$$3$$$. Thus, $$$f(3)=2$$$.
- $$$1$$$ and $$$2$$$ are divisors of $$$4$$$ but $$$3$$$ isn't, so $$$3$$$ is the minimum positive integer that isn't a divisor of $$$4$$$. Thus, $$$f(4)=3$$$.

Therefore, $$$ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$$$.

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: 512.0 MB

# Problem
You are given a sequence $$$A$$$, where its elements are either in the form + x or -, where $$$x$$$ is an integer.

For such a sequence $$$S$$$ where its elements are either in the form + x or -, define $$$f(S)$$$ as follows:

- iterate through $$$S$$$'s elements from the first one to the last one, and maintain a multiset $$$T$$$ as you iterate through it.
- for each element, if it's in the form + x, add $$$x$$$ to $$$T$$$; otherwise, erase the smallest element from $$$T$$$ (if $$$T$$$ is empty, do nothing).
- after iterating through all $$$S$$$'s elements, compute the sum of all elements in $$$T$$$. $$$f(S)$$$ is defined as the sum.

The sequence $$$b$$$ is a subsequence of the sequence $$$a$$$ if $$$b$$$ can be derived from $$$a$$$ by removing zero or more elements without changing the order of the remaining elements. For all $$$A$$$'s subsequences $$$B$$$, compute the sum of $$$f(B)$$$, modulo $$$998\,244\,353$$$.

## Input Format
The first line contains an integer $$$n$$$ ($$$1\leq n\leq 500$$$) — the length of $$$A$$$.

Each of the next $$$n$$$ lines begins with an operator + or -. If the operator is +, then it's followed by an integer $$$x$$$ ($$$1\le x<998\,244\,353$$$). The $$$i$$$-th line of those $$$n$$$ lines describes the $$$i$$$-th element in $$$A$$$.

## Output Format
Print one integer, which is the answer to the problem, modulo $$$998\,244\,353$$$.

## Examples
```input
4
-
+ 1
+ 2
-
```
```output
16
```
-----
```input
15
+ 2432543
-
+ 4567886
+ 65638788
-
+ 578943
-
-
+ 62356680
-
+ 711111
-
+ 998244352
-
-
```
```output
750759115
```

## Note
In the first example, the following are all possible pairs of $$$B$$$ and $$$f(B)$$$:

- $$$B=$$$ {}, $$$f(B)=0$$$.
- $$$B=$$$ {-}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 1, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-, + 1, -}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 2, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-, + 2, -}, $$$f(B)=0$$$.
- $$$B=$$$ {-}, $$$f(B)=0$$$.
- $$$B=$$$ {-, -}, $$$f(B)=0$$$.
- $$$B=$$$ {+ 1, + 2}, $$$f(B)=3$$$.
- $$$B=$$$ {+ 1, + 2, -}, $$$f(B)=2$$$.
- $$$B=$$$ {-, + 1, + 2}, $$$f(B)=3$$$.
- $$$B=$$$ {-, + 1, + 2, -}, $$$f(B)=2$$$.
- $$$B=$$$ {-, + 1}, $$$f(B)=1$$$.
- $$$B=$$$ {+ 1}, $$$f(B)=1$$$.
- $$$B=$$$ {-, + 2}, $$$f(B)=2$$$.
- $$$B=$$$ {+ 2}, $$$f(B)=2$$$.

The sum of these values is $$$16$$$.

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: 512.0 MB

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

A permutation of $$$1, 2, \ldots, n$$$ is a sequence of $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[2,3,1,4]$$$ is a permutation of $$$1, 2, 3, 4$$$, but $$$[1,4,2,2]$$$ isn't because $$$2$$$ appears twice in it.

Recall that the number of inversions in a permutation $$$a_1, a_2, \ldots, a_n$$$ is the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

Let $$$p$$$ and $$$q$$$ be two permutations of $$$1, 2, \ldots, n$$$. Find the number of permutation pairs $$$(p,q)$$$ that satisfy the following conditions:

- $$$p$$$ is lexicographically smaller than $$$q$$$.
- the number of inversions in $$$p$$$ is greater than the number of inversions in $$$q$$$.

Print the number of such pairs modulo $$$mod$$$. Note that $$$mod$$$ may not be a prime.

## Input Format
The only line contains two integers $$$n$$$ and $$$mod$$$ ($$$1\le n\le 50$$$, $$$1\le mod\le 10^9$$$).

## Output Format
Print one integer, which is the answer modulo $$$mod$$$.

## Examples
```input
4 403458273
```
```output
17
```

## Note
The following are all valid pairs $$$(p,q)$$$ when $$$n=4$$$.

- $$$p=[1,3,4,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,2,3]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,4,3]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,3,1,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,3,4,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,1,3]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,4,2]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,2,1,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,2,4,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,1,2]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,3,2]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,2,1,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: 4.0 seconds
Memory limit: 512.0 MB

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

A permutation of $$$1, 2, \ldots, n$$$ is a sequence of $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[2,3,1,4]$$$ is a permutation of $$$1, 2, 3, 4$$$, but $$$[1,4,2,2]$$$ isn't because $$$2$$$ appears twice in it.

Recall that the number of inversions in a permutation $$$a_1, a_2, \ldots, a_n$$$ is the number of pairs of indices $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

Let $$$p$$$ and $$$q$$$ be two permutations of $$$1, 2, \ldots, n$$$. Find the number of permutation pairs $$$(p,q)$$$ that satisfy the following conditions:

- $$$p$$$ is lexicographically smaller than $$$q$$$.
- the number of inversions in $$$p$$$ is greater than the number of inversions in $$$q$$$.

Print the number of such pairs modulo $$$mod$$$. Note that $$$mod$$$ may not be a prime.

## Input Format
The only line contains two integers $$$n$$$ and $$$mod$$$ ($$$1\le n\le 500$$$, $$$1\le mod\le 10^9$$$).

## Output Format
Print one integer, which is the answer modulo $$$mod$$$.

## Examples
```input
4 403458273
```
```output
17
```

## Note
The following are all valid pairs $$$(p,q)$$$ when $$$n=4$$$.

- $$$p=[1,3,4,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,2,3]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,3,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,1,4,3]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[2,3,1,4]$$$,
- $$$p=[1,4,3,2]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,3,4,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,1,3]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,2,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,1,4,2]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[3,2,1,4]$$$,
- $$$p=[2,4,3,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,2,4,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,1,2]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,2,3]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,1,3,2]$$$,
- $$$p=[3,4,2,1]$$$, $$$q=[4,2,1,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
William has two numbers $$$a$$$ and $$$b$$$ initially both equal to zero. William mastered performing three different operations with them quickly. Before performing each operation some positive integer $$$k$$$ is picked, which is then used to perform one of the following operations: (note, that for each operation you can choose a new positive integer $$$k$$$)

1. add number $$$k$$$ to both $$$a$$$ and $$$b$$$, or
2. add number $$$k$$$ to $$$a$$$ and subtract $$$k$$$ from $$$b$$$, or
3. add number $$$k$$$ to $$$b$$$ and subtract $$$k$$$ from $$$a$$$.

Note that after performing operations, numbers $$$a$$$ and $$$b$$$ may become negative as well.

William wants to find out the minimal number of operations he would have to perform to make $$$a$$$ equal to his favorite number $$$c$$$ and $$$b$$$ equal to his second favorite number $$$d$$$.

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

The only line of each test case contains two integers $$$c$$$ and $$$d$$$ $$$(0 \le c, d \le 10^9)$$$, which are William's favorite numbers and which he wants $$$a$$$ and $$$b$$$ to be transformed into.

## Output Format
For each test case output a single number, which is the minimal number of operations which William would have to perform to make $$$a$$$ equal to $$$c$$$ and $$$b$$$ equal to $$$d$$$, or $$$-1$$$ if it is impossible to achieve this using the described operations.

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

## Note
Let us demonstrate one of the suboptimal ways of getting a pair $$$(3, 5)$$$:

- Using an operation of the first type with $$$k=1$$$, the current pair would be equal to $$$(1, 1)$$$.
- Using an operation of the third type with $$$k=8$$$, the current pair would be equal to $$$(-7, 9)$$$.
- Using an operation of the second type with $$$k=7$$$, the current pair would be equal to $$$(0, 2)$$$.
- Using an operation of the first type with $$$k=3$$$, the current pair would be equal to $$$(3, 5)$$$.

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
William has a favorite bracket sequence. Since his favorite sequence is quite big he provided it to you as a sequence of positive integers $$$c_1, c_2, \dots, c_n$$$ where $$$c_i$$$ is the number of consecutive brackets "(" if $$$i$$$ is an odd number or the number of consecutive brackets ")" if $$$i$$$ is an even number.

For example for a bracket sequence "((())()))" a corresponding sequence of numbers is $$$[3, 2, 1, 3]$$$.

You need to find the total number of continuous subsequences (subsegments) $$$[l, r]$$$ ($$$l \le r$$$) of the original bracket sequence, which are regular bracket sequences.

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 1000)$$$, the size of the compressed sequence.

The second line contains a sequence of integers $$$c_1, c_2, \dots, c_n$$$ $$$(1 \le c_i \le 10^9)$$$, the compressed sequence.

## Output Format
Output a single integer — the total number of subsegments of the original bracket sequence, which are regular bracket sequences.

It can be proved that the answer fits in the signed 64-bit integer data type.

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

## Note
In the first example a sequence (((()(()))( is described. This bracket sequence contains $$$5$$$ subsegments which form regular bracket sequences:

1. Subsequence from the $$$3$$$rd to $$$10$$$th character: (()(()))
2. Subsequence from the $$$4$$$th to $$$5$$$th character: ()
3. Subsequence from the $$$4$$$th to $$$9$$$th character: ()(())
4. Subsequence from the $$$6$$$th to $$$9$$$th character: (())
5. Subsequence from the $$$7$$$th to $$$8$$$th character: ()

In the second example a sequence ()))(()(()))) is described.

In the third example a sequence ()()(()) is described.

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: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from $$$0$$$ to $$$2^n - 1$$$. On each planet, there are gates that allow the player to move from planet $$$i$$$ to planet $$$j$$$ if the binary representations of $$$i$$$ and $$$j$$$ differ in exactly one bit.

William wants to test you and see how you can handle processing the following queries in this game universe:

- Destroy planets with numbers from $$$l$$$ to $$$r$$$ inclusively. These planets cannot be moved to anymore.
- Figure out if it is possible to reach planet $$$b$$$ from planet $$$a$$$ using some number of planetary gates. It is guaranteed that the planets $$$a$$$ and $$$b$$$ are not destroyed.

## Input Format
The first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$1 \leq m \leq 5 \cdot 10^4$$$), which are the number of bits in binary representation of each planets' designation and the number of queries, respectively.

Each of the next $$$m$$$ lines contains a query of two types:

block l r — query for destruction of planets with numbers from $$$l$$$ to $$$r$$$ inclusively ($$$0 \le l \le r < 2^n$$$). It's guaranteed that no planet will be destroyed twice.

ask a b — query for reachability between planets $$$a$$$ and $$$b$$$ ($$$0 \le a, b < 2^n$$$). It's guaranteed that planets $$$a$$$ and $$$b$$$ hasn't been destroyed yet.

## Output Format
For each query of type ask you must output "1" in a new line, if it is possible to reach planet $$$b$$$ from planet $$$a$$$ and "0" otherwise (without quotation marks).

## Examples
```input
3 3
ask 0 7
block 3 6
ask 0 7
```
```output
1
0
```
-----
```input
6 10
block 12 26
ask 44 63
block 32 46
ask 1 54
block 27 30
ask 10 31
ask 11 31
ask 49 31
block 31 31
ask 2 51
```
```output
1
1
0
0
1
0
```

## Note
The first example test can be visualized in the following way:

Response to a query ask 0 7 is positive.

Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):

Response to a query ask 0 7 is negative, since any path from vertex $$$0$$$ to vertex $$$7$$$ must go through one of the destroyed vertices.

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

# Problem
William really likes puzzle kits. For one of his birthdays, his friends gifted him a complete undirected edge-weighted graph consisting of $$$n$$$ vertices.

He wants to build a spanning tree of this graph, such that for the first $$$k$$$ vertices the following condition is satisfied: the degree of a vertex with index $$$i$$$ does not exceed $$$d_i$$$. Vertices from $$$k + 1$$$ to $$$n$$$ may have any degree.

William wants you to find the minimum weight of a spanning tree that satisfies all the conditions.

A spanning tree is a subset of edges of a graph that forms a tree on all $$$n$$$ vertices of the graph. The weight of a spanning tree is defined as the sum of weights of all the edges included in a spanning tree.

## Input Format
The first line of input contains two integers $$$n$$$, $$$k$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq k \leq min(n - 1, 5)$$$).

The second line contains $$$k$$$ integers $$$d_1, d_2, \ldots, d_k$$$ ($$$1 \leq d_i \leq n$$$).

The $$$i$$$-th of the next $$$n - 1$$$ lines contains $$$n - i$$$ integers $$$w_{i,i+1}, w_{i,i+2}, \ldots, w_{i,n}$$$ ($$$1 \leq w_{i,j} \leq 100$$$): weights of edges $$$(i,i+1),(i,i+2),\ldots,(i,n)$$$.

## Output Format
Print one integer: the minimum weight of a spanning tree under given degree constraints for the first $$$k$$$ vertices.

## Examples
```input
10 5
5 3 4 2 1
29 49 33 12 55 15 32 62 37
61 26 15 58 15 22 8 58
37 16 9 39 20 14 58
10 15 40 3 19 55
53 13 37 44 52
23 59 58 4
69 80 29
89 28
48
```
```output
95
```

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
Alice has a grid with $$$2$$$ rows and $$$n$$$ columns. She fully covers the grid using $$$n$$$ dominoes of size $$$1 \times 2$$$ — Alice may place them vertically or horizontally, and each cell should be covered by exactly one domino.

Now, she decided to show one row of the grid to Bob. Help Bob and figure out what the other row of the grid looks like!

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the width of the grid.

The second line of each test case contains a string $$$s$$$ consisting of $$$n$$$ characters, each of which is either L, R, U, or D, representing the left, right, top, or bottom half of a domino, respectively (see notes for better understanding). This string represents one of the rows of the grid.

Additional constraint on the input: each input corresponds to at least one valid tiling.

## Output Format
For each test case, output one string — the other row of the grid, using the same format as the input string. If there are multiple answers, print any.

## Examples
```input
4
1
U
2
LR
5
LRDLR
6
UUUUUU
```
```output
D
LR
LRULR
DDDDDD
```

## Note
In the first test case, Alice shows Bob the top row, the whole grid may look like:

In the second test case, Alice shows Bob the bottom row, the whole grid may look like:

In the third test case, Alice shows Bob the bottom row, the whole grid may look like:

In the fourth test case, Alice shows Bob the top row, the whole grid may look like:

Now solve the problem and return the code.