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
You are given a string $$$s$$$, consisting of lowercase Latin letters. Every letter appears in it no more than twice.

Your task is to rearrange the letters in the string in such a way that for each pair of letters that appear exactly twice, the distance between the letters in the pair is the same. You are not allowed to add or remove letters.

It can be shown that the answer always exists. If there are multiple answers, print any of them.

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

Each testcase consists of a non-empty string $$$s$$$, consisting of lowercase Latin letters. Every letter appears in the string no more than twice. The length of the string doesn't exceed $$$52$$$.

## Output Format
For each testcase, print a single string. Every letter should appear in it the same number of times as it appears in string $$$s$$$. For each pair of letters that appear exactly twice, the distance between the letters in the pair should be the same.

If there are multiple answers, print any of them.

## Examples
```input
3
oelhl
abcdcba
ac
```
```output
hello
ababcdc
ac
```

## Note
In the first testcase of the example, the only letter that appears exactly twice is letter 'l'. You can rearrange the letters arbitrarily, since there are no distances to compare.

In the second testcase of the example, the letters that appear exactly twice are 'a', 'b' and 'c'. Initially, letters 'a' are distance $$$6$$$ apart, letters 'b' are distance $$$4$$$ apart and letters 'c' are distance $$$2$$$ apart. They are not the same, so we have to rearrange the letters. After rearrangement, letters 'a' are distance $$$2$$$ apart, letters 'b' are distance $$$2$$$ apart and letters 'c' are distance $$$2$$$ apart. They are all the same, so the answer is valid.

In the third testcase of the example, there are no letters that appear exactly twice. Thus, any rearrangement is valid. Including not changing the string at all.

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 decimal representation of an integer $$$x$$$ without leading zeros.

You have to perform the following reduction on it exactly once: take two neighboring digits in $$$x$$$ and replace them with their sum without leading zeros (if the sum is $$$0$$$, it's represented as a single $$$0$$$).

For example, if $$$x = 10057$$$, the possible reductions are:

- choose the first and the second digits $$$1$$$ and $$$0$$$, replace them with $$$1+0=1$$$; the result is $$$1057$$$;
- choose the second and the third digits $$$0$$$ and $$$0$$$, replace them with $$$0+0=0$$$; the result is also $$$1057$$$;
- choose the third and the fourth digits $$$0$$$ and $$$5$$$, replace them with $$$0+5=5$$$; the result is still $$$1057$$$;
- choose the fourth and the fifth digits $$$5$$$ and $$$7$$$, replace them with $$$5+7=12$$$; the result is $$$10012$$$.

What's the largest number that can be obtained?

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

Each testcase consists of a single integer $$$x$$$ ($$$10 \le x < 10^{200000}$$$). $$$x$$$ doesn't contain leading zeros.

The total length of the decimal representations of $$$x$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the largest number that can be obtained after the reduction is applied exactly once. The number should not contain leading zeros.

## Examples
```input
2
10057
90
```
```output
10012
9
```

## Note
The first testcase of the example is already explained in the statement.

In the second testcase, there is only one possible reduction: the first and the second digits.

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
You are given a tree consisting of $$$n$$$ vertices. Some of the vertices (at least two) are black, all the other vertices are white.

You place a chip on one of the vertices of the tree, and then perform the following operations:

- let the current vertex where the chip is located is $$$x$$$. You choose a black vertex $$$y$$$, and then move the chip along the first edge on the simple path from $$$x$$$ to $$$y$$$.

You are not allowed to choose the same black vertex $$$y$$$ in two operations in a row (i. e., for every two consecutive operations, the chosen black vertex should be different).

You end your operations when the chip moves to the black vertex (if it is initially placed in a black vertex, you don't perform the operations at all), or when the number of performed operations exceeds $$$100^{500}$$$.

For every vertex $$$i$$$, you have to determine if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex, if the chip is initially placed on the vertex $$$i$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$), where $$$c_i = 0$$$ means that the $$$i$$$-th vertex is white, and $$$c_i = 1$$$ means that the $$$i$$$-th vertex is black. At least two values of $$$c_i$$$ are equal to $$$1$$$.

Then $$$n-1$$$ lines follow, each of them contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the endpoints of some edge. These edges form a tree.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th integer should be equal to $$$1$$$ if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex if it is placed on the vertex $$$i$$$, and $$$0$$$ if no such sequence of operations exists.

## Examples
```input
8
0 1 0 0 0 0 1 0
8 6
2 5
7 8
6 5
4 5
6 1
7 3
```
```output
0 1 1 1 1 0 1 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 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 an integer array $$$a_0, a_1, \dots, a_{n - 1}$$$, and an integer $$$k$$$. You perform the following code with it:

Your task is to calculate the expected value of the variable ans after performing this code.

Note that the input is generated according to special rules (see the input format section).

## Input Format
The only line contains six integers $$$n$$$, $$$a_0$$$, $$$x$$$, $$$y$$$, $$$k$$$ and $$$M$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a_0, x, y < M \le 998244353$$$; $$$1 \le k \le 17$$$).

The array $$$a$$$ in the input is constructed as follows:

- $$$a_0$$$ is given in the input;
- for every $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the value of $$$a_i$$$ can be calculated as $$$a_i = (a_{i - 1} \cdot x + y) \bmod M$$$.

## Output Format
Let the expected value of the variable ans after performing the code be $$$E$$$. It can be shown that $$$E \cdot n^k$$$ is an integer. You have to output this integer modulo $$$998244353$$$.

## Examples
```input
3 10 3 5 13 88
```
```output
382842030
```
-----
```input
2 15363 270880 34698 17 2357023
```
```output
319392398
```

## Note
The array in the first example test is $$$[10, 35, 22]$$$. In the second example, it is $$$[15363, 1418543]$$$.

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

# Problem
You are given an array $$$a$$$ of length $$$n$$$. Also you are given $$$m$$$ distinct positions $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \leq n$$$).

A non-empty subset of these positions $$$T$$$ is randomly selected with equal probability and the following value is calculated: $$$$$$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|).$$$$$$ In other word, for each index of the array, $$$a_i$$$ and the distance to the closest chosen position are multiplied, and then these values are summed up.

Find the expected value of this sum.

This value must be found modulo $$$998\,244\,353$$$. More formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \neq 0$$$ (mod $$$M$$$). Output the integer equal to $$$p \cdot q^{-1}$$$ (mod $$$M$$$). In other words, output such integer $$$x$$$ that $$$0 \leq x < M$$$ and $$$x \cdot q = p$$$ (mod $$$M$$$).

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 998\,244\,353$$$).

The third line contains $$$m$$$ distinct integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \le n$$$).

For every $$$1 \leq i < m$$$ it is guaranteed that $$$p_i < p_{i+1}$$$.

## Output Format
Print a single integer — the answer to the problem.

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

## Note
In the first test:

- If only $$$1$$$ is choosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$$$.
- If only $$$4$$$ is choosen, than the value equals to $$$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$$$.
- If both positions are chosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$$$.

The answer to the problem is $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (modulo $$$998\,244\,353$$$).

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 knight is standing in front of a long and narrow hallway. A princess is waiting at the end of it.

In a hallway there are three doors: a red door, a green door and a blue door. The doors are placed one after another, however, possibly in a different order. To proceed to the next door, the knight must first open the door before.

Each door can be only opened with a key of the corresponding color. So three keys: a red key, a green key and a blue key — are also placed somewhere in the hallway. To open the door, the knight should first pick up the key of its color.

The knight has a map of the hallway. It can be transcribed as a string, consisting of six characters:

- R, G, B — denoting red, green and blue doors, respectively;
- r, g, b — denoting red, green and blue keys, respectively.

Each of these six characters appears in the string exactly once.

The knight is standing at the beginning of the hallway — on the left on the map.

Given a map of the hallway, determine if the knight can open all doors and meet the princess at the end of the hallway.

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

Each testcase consists of a single string. Each character is one of R, G, B (for the doors), r, g, b (for the keys), and each of them appears exactly once.

## Output Format
For each testcase, print YES if the knight can open all doors. Otherwise, print NO.

## Examples
```input
4
rgbBRG
RgbrBG
bBrRgG
rgRGBb
```
```output
YES
NO
YES
NO
```

## Note
In the first testcase, the knight first collects all keys, then opens all doors with them.

In the second testcase, there is a red door right in front of the knight, but he doesn't have a key for it.

In the third testcase, the key to each door is in front of each respective door, so the knight collects the key and uses it immediately three times.

In the fourth testcase, the knight can't open the blue door.

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 is a sheet of paper that can be represented with a grid of size $$$n \times m$$$: $$$n$$$ rows and $$$m$$$ columns of cells. All cells are colored in white initially.

$$$q$$$ operations have been applied to the sheet. The $$$i$$$-th of them can be described as follows:

- $$$x_i$$$ $$$y_i$$$ — choose one of $$$k$$$ non-white colors and color the entire row $$$x_i$$$ and the entire column $$$y_i$$$ in it. The new color is applied to each cell, regardless of whether the cell was colored before the operation.

The sheet after applying all $$$q$$$ operations is called a coloring. Two colorings are different if there exists at least one cell that is colored in different colors.

How many different colorings are there? Print the number modulo $$$998\,244\,353$$$.

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

The first line of the testcase contains four integers $$$n, m, k$$$ and $$$q$$$ ($$$1 \le n, m, k, q \le 2 \cdot 10^5$$$) — the size of the sheet, the number of non-white colors and the number of operations.

The $$$i$$$-th of the following $$$q$$$ lines contains a description of the $$$i$$$-th operation — two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$) — the row and the column the operation is applied to.

The sum of $$$q$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the number of different colorings modulo $$$998\,244\,353$$$.

## Examples
```input
2
1 1 3 2
1 1
1 1
2 2 2 3
2 1
1 1
2 2
```
```output
3
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Team Red and Team Blue competed in a competitive FPS. Their match was streamed around the world. They played a series of $$$n$$$ matches.

In the end, it turned out Team Red won $$$r$$$ times and Team Blue won $$$b$$$ times. Team Blue was less skilled than Team Red, so $$$b$$$ was strictly less than $$$r$$$.

You missed the stream since you overslept, but you think that the match must have been neck and neck since so many people watched it. So you imagine a string of length $$$n$$$ where the $$$i$$$-th character denotes who won the $$$i$$$-th match  — it is R if Team Red won or B if Team Blue won. You imagine the string was such that the maximum number of times a team won in a row was as small as possible. For example, in the series of matches RBBRRRB, Team Red won $$$3$$$ times in a row, which is the maximum.

You must find a string satisfying the above conditions. If there are multiple answers, print any.

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

Each test case has a single line containing three integers $$$n$$$, $$$r$$$, and $$$b$$$ ($$$3 \leq n \leq 100$$$; $$$1 \leq b < r \leq n$$$, $$$r+b=n$$$).

## Output Format
For each test case, output a single line containing a string satisfying the given conditions. If there are multiple answers, print any.

## Examples
```input
3
7 4 3
6 5 1
19 13 6
```
```output
RBRBRBR
RRRBRR
RRBRRBRRBRRBRRBRRBR
```
-----
```input
6
3 2 1
10 6 4
11 6 5
10 9 1
10 8 2
11 9 2
```
```output
RBR
RRBRBRBRBR
RBRBRBRBRBR
RRRRRBRRRR
RRRBRRRBRR
RRRBRRRBRRR
```

## Note
The first test case of the first example gives the optimal answer for the example in the statement. The maximum number of times a team wins in a row in RBRBRBR is $$$1$$$. We cannot minimize it any further.

The answer for the second test case of the second example is RRBRBRBRBR. The maximum number of times a team wins in a row is $$$2$$$, given by RR at the beginning. We cannot minimize the answer any further.

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've got another geometrical task. You are given two non-degenerate polygons A and B as vertex coordinates. Polygon A is strictly convex. Polygon B is an arbitrary polygon without any self-intersections and self-touches. The vertices of both polygons are given in the clockwise order. For each polygon no three consecutively following vertices are located on the same straight line.

Your task is to check whether polygon B is positioned strictly inside polygon A. It means that any point of polygon B should be strictly inside polygon A. "Strictly" means that the vertex of polygon B cannot lie on the side of the polygon A.

## Input Format
The first line contains the only integer n (3 ≤ n ≤ 105) — the number of vertices of polygon A. Then n lines contain pairs of integers xi, yi (|xi|, |yi| ≤ 109) — coordinates of the i-th vertex of polygon A. The vertices are given in the clockwise order.

The next line contains a single integer m (3 ≤ m ≤ 2·104) — the number of vertices of polygon B. Then following m lines contain pairs of integers xj, yj (|xj|, |yj| ≤ 109) — the coordinates of the j-th vertex of polygon B. The vertices are given in the clockwise order.

The coordinates of the polygon's vertices are separated by a single space. It is guaranteed that polygons A and B are non-degenerate, that polygon A is strictly convex, that polygon B has no self-intersections and self-touches and also for each polygon no three consecutively following vertices are located on the same straight line.

## Output Format
Print on the only line the answer to the problem — if polygon B is strictly inside polygon A, print "YES", otherwise print "NO" (without the quotes).

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

Now solve the problem and return the code.