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
There are $$$n$$$ people in the programming contest chat. Chat participants are ordered by activity, but each person sees himself at the top of the list.

For example, there are $$$4$$$ participants in the chat, and their order is $$$[2, 3, 1, 4]$$$. Then

- $$$1$$$-st user sees the order $$$[1, 2, 3, 4]$$$.
- $$$2$$$-nd user sees the order $$$[2, 3, 1, 4]$$$.
- $$$3$$$-rd user sees the order $$$[3, 2, 1, 4]$$$.
- $$$4$$$-th user sees the order $$$[4, 2, 3, 1]$$$.

$$$k$$$ people posted screenshots in the chat, which show the order of participants shown to this user. The screenshots were taken within a short period of time, and the order of participants has not changed.

Your task is to determine whether there is a certain order that all screenshots correspond to.

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

The first line of the description of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5, n \cdot k \le 2 \cdot 10^5$$$) — the number of chat participants and the number of participants who posted screenshots.

The following $$$k$$$ lines contain descriptions of screenshots posted by the participants.

The $$$i$$$-th row contains $$$n$$$ integers $$$a_{ij}$$$ each ($$$1 \le a_{ij} \le n$$$, all $$$a_{ij}$$$ are different) — the order of participants shown to the participant $$$a_{i0}$$$, where $$$a_{i0}$$$ — the author of the screenshot. You can show that in the screenshot description it will always be at the top of the list.

It is guaranteed that the sum of $$$n \cdot k$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that all the authors of the screenshots are different.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if there exists at least one order of participants, under which all $$$k$$$ screenshots could have been obtained. Otherwise, output "NO".

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
10
5 1
1 2 3 4 5
4 4
1 2 3 4
2 3 1 4
3 2 1 4
4 2 3 1
6 2
1 3 5 2 4 6
6 3 5 2 1 4
3 3
1 2 3
2 3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1
1
5 2
1 2 3 5 4
2 1 3 5 4
3 3
3 1 2
2 3 1
1 3 2
5 4
3 5 1 4 2
2 5 1 4 3
1 5 4 3 2
5 1 4 3 2
3 3
1 3 2
2 1 3
3 2 1
```
```output
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
```

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

# Problem
You have a one-dimensional puzzle, all the elements of which need to be put in one row, connecting with each other. All the puzzle elements are completely white and distinguishable from each other only if they have different shapes.

Each element has straight borders at the top and bottom, and on the left and right it has connections, each of which can be a protrusion or a recess. You cannot rotate the elements.

You can see that there are exactly $$$4$$$ types of elements. Two elements can be connected if the right connection of the left element is opposite to the left connection of the right element.

All possible types of elements.

The puzzle contains $$$c_1, c_2, c_3, c_4$$$ elements of each type. The puzzle is considered complete if you have managed to combine all elements into one long chain. You want to know how many ways this can be done.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of input test cases. The descriptions of the test cases follow.

The description of each test case contains $$$4$$$ integers $$$c_i$$$ ($$$0 \le c_i \le 10^6$$$) — the number of elements of each type, respectively.

It is guaranteed that the sum of $$$c_i$$$ for all test cases does not exceed $$$4 \cdot 10^6$$$.

## Output Format
For each test case, print one integer — the number of possible ways to solve the puzzle.

Two methods are considered different if there is $$$i$$$, such that the types of elements at the $$$i$$$ position in these methods differ.

Since the answer can be very large, output it modulo $$$998244353$$$.

If it is impossible to solve the puzzle, print $$$0$$$.

## Examples
```input
11
1 1 1 1
1 2 5 10
4 6 100 200
900000 900000 900000 900000
0 0 0 0
0 0 566 239
1 0 0 0
100 0 100 0
0 0 0 4
5 5 0 2
5 4 0 5
```
```output
4
66
0
794100779
1
0
1
0
1
36
126
```

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
Rudolf is going to visit Bernard, and he decided to take the metro to get to him. The ticket can be purchased at a machine that accepts exactly two coins, the sum of which does not exceed $$$k$$$.

Rudolf has two pockets with coins. In the left pocket, there are $$$n$$$ coins with denominations $$$b_1, b_2, \dots, b_n$$$. In the right pocket, there are $$$m$$$ coins with denominations $$$c_1, c_2, \dots, c_m$$$. He wants to choose exactly one coin from the left pocket and exactly one coin from the right pocket (two coins in total).

Help Rudolf determine how many ways there are to select indices $$$f$$$ and $$$s$$$ such that $$$b_f + c_s \le k$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then follows the description of each test case.

The first line of each test case contains three natural numbers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 100, 1 \le k \le 2000$$$) — the number of coins in the left and right pockets, and the maximum sum of two coins for the ticket payment at the counter, respectively.

The second line of each test case contains $$$n$$$ integers $$$b_i$$$ ($$$1 \le b_i \le 1000$$$) — the denominations of coins in the left pocket.

The third line of each test case contains $$$m$$$ integers $$$c_i$$$ ($$$1 \le c_i \le 1000$$$) — the denominations of coins in the right pocket.

## Output Format
For each testcase, output a single integer — the number of ways Rudolf can select two coins, taking one from each pocket, so that the sum of the coins does not exceed $$$k$$$.

## Examples
```input
4
4 4 8
1 5 10 14
2 1 8 1
2 3 4
4 8
1 2 3
4 2 7
1 1 1 1
2 7
3 4 2000
1 1 1
1 1 1 1
```
```output
6
0
4
12
```

## Note
Note that the pairs indicate the indices of the coins in the array, not their denominations.

In the first test case, Rudolf can choose the following pairs of coins: $$$[1, 1], [1, 2], [1, 4], [2, 1], [2, 2], [2, 4]$$$.

In the second test case, Rudolf cannot choose one coin from each pocket in any way, as the sum of any two elements from the first and second arrays will exceed the value of $$$k=4$$$.

In the third test case, Rudolf can choose: $$$[1, 1], [2, 1], [3, 1], [4, 1]$$$.

In the fourth test case, Rudolf can choose any coin from the left pocket and any coin from the right pocket.

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
Rudolf has a string $$$s$$$ of length $$$n$$$. Rudolf considers the string $$$s$$$ to be ugly if it contains the substring$$$^\dagger$$$ "pie" or the substring "map", otherwise the string $$$s$$$ will be considered beautiful.

For example, "ppiee", "mmap", "dfpiefghmap" are ugly strings, while "mathp", "ppiiee" are beautiful strings.

Rudolf wants to shorten the string $$$s$$$ by removing some characters to make it beautiful.

The main character doesn't like to strain, so he asks you to make the string beautiful by removing the minimum number of characters. He can remove characters from any positions in the string (not just from the beginning or end of the string).

$$$^\dagger$$$ String $$$a$$$ is a substring of $$$b$$$ if there exists a consecutive segment of characters in string $$$b$$$ equal to $$$a$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the string $$$s$$$.

The next line of each test case contains the string $$$s$$$ of length $$$n$$$. The string $$$s$$$ consists of lowercase Latin letters.

The sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output a single integer — the minimum number of characters that need to be deleted to make the string $$$s$$$ beautiful. If the string is initially beautiful, then output $$$0$$$.

## Examples
```input
6
9
mmapnapie
9
azabazapi
8
mappppie
18
mapmapmapmapmapmap
1
p
11
pppiepieeee
```
```output
2
0
2
6
0
2
```

## Note
In the first test case, for example, you can delete the $$$4$$$th and $$$9$$$th characters to make the string beautiful.

In the second test case, the string is already beautiful.

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
The organizing committee plans to take the participants of the Olympiad on a hike after the tour. Currently, the number of tents needed to be taken is being calculated. It is known that each tent can accommodate up to $$$3$$$ people.

Among the participants, there are $$$a$$$ introverts, $$$b$$$ extroverts, and $$$c$$$ universals:

- Each introvert wants to live in a tent alone. Thus, a tent with an introvert must contain exactly one person — only the introvert himself.
- Each extrovert wants to live in a tent with two others. Thus, the tent with an extrovert must contain exactly three people.
- Each universal is fine with any option (living alone, with one other person, or with two others).

The organizing committee respects the wishes of each participant very much, so they want to fulfill all of them.

Tell us the minimum number of tents needed to be taken so that all participants can be accommodated according to their preferences. If it is impossible to accommodate the participants in a way that fulfills all the wishes, output $$$-1$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by the descriptions of the test cases.

Each test case is described by a single line containing three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$) — the number of introverts, extroverts, and universals, respectively.

## Output Format
For each test case, output a single integer — the minimum number of tents, or $$$-1$$$ if it is impossible to accommodate the participants.

## Examples
```input
10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000
```
```output
3
-1
3
-1
3
28
0
7
8
1666666667
```

## Note
In the first test case, $$$1$$$ tent will be given to the introverts, $$$1$$$ tent will be shared by two extroverts and one universal, and the last tent will be shared by two universals. In total, $$$3$$$ tents are needed.

In the second test case, three extroverts will take $$$1$$$ tent, and $$$1$$$ tent will be taken by an introvert. Then, one extrovert and one universal will be left. This extrovert will not be able to live with two others.

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
Little Rosie has a phone with a desktop (or launcher, as it is also called). The desktop can consist of several screens. Each screen is represented as a grid of size $$$5 \times 3$$$, i.e., five rows and three columns.

There are $$$x$$$ applications with an icon size of $$$1 \times 1$$$ cells; such an icon occupies only one cell of the screen. There are also $$$y$$$ applications with an icon size of $$$2 \times 2$$$ cells; such an icon occupies a square of $$$4$$$ cells on the screen. Each cell of each screen can be occupied by no more than one icon.

Rosie wants to place the application icons on the minimum number of screens. Help her find the minimum number of screens needed.

## Input Format
The first line of the input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first and only line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \leq x, y \leq 99$$$) — the number of applications with a $$$1 \times 1$$$ icon and the number of applications with a $$$2 \times 2$$$ icon, respectively.

## Output Format
For each test case, output the minimal number of required screens on a separate line.

## Examples
```input
11
1 1
7 2
12 4
0 3
1 0
8 1
0 0
2 0
15 0
8 2
0 9
```
```output
1
1
2
2
1
1
0
1
1
2
5
```

## Note
The solution for the first test case can look as follows:

Blue squares represent empty spaces for icons, green squares represent $$$1 \times 1$$$ icons, red squares represent $$$2 \times 2$$$ icons

The solution for the third test case can look as follows:

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
Polycarp has a string $$$s$$$, which consists of lowercase Latin letters. He encodes this string using the following algorithm:

- first, he constructs a new auxiliary string $$$r$$$, which consists of all distinct letters of the string $$$s$$$, written in alphabetical order;
- then the encoding happens as follows: each character in the string $$$s$$$ is replaced by its symmetric character from the string $$$r$$$ (the first character of the string $$$r$$$ will be replaced by the last, the second by the second from the end, and so on).

For example, encoding the string $$$s$$$="codeforces" happens as follows:

- the string $$$r$$$ is obtained as "cdefors";
- the first character $$$s_1$$$='c' is replaced by 's';
- the second character $$$s_2$$$='o' is replaced by 'e';
- the third character $$$s_3$$$='d' is replaced by 'r';
- ...
- the last character $$$s_{10}$$$='s' is replaced by 'c'.

The string $$$r$$$ and replacements for $$$s$$$="codeforces".

Thus, the result of encoding the string $$$s$$$="codeforces" is the string "serofedsoc".

Write a program that performs decoding — that is, restores the original string $$$s$$$ from the encoding result.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$b$$$.

The second line of each test case contains a string $$$b$$$ of length $$$n$$$, consisting of lowercase Latin letters — the result of encoding the original string $$$s$$$.

It is guaranteed that the sum of the values of $$$n$$$ over all test cases in the test does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output the string $$$s$$$ from which the encoding result $$$b$$$ was obtained.

## Examples
```input
5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin
```
```output
codeforces
fft
algorithm
w
meetinthemiddle
```

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

# Problem
Polycarp was given an array $$$a$$$ of $$$n$$$ integers. He really likes triples of numbers, so for each $$$j$$$ ($$$1 \le j \le n - 2$$$) he wrote down a triple of elements $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Polycarp considers a pair of triples $$$b$$$ and $$$c$$$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:

- $$$b_1 \ne c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 \ne c_2$$$ and $$$b_3 = c_3$$$;
- $$$b_1 = c_1$$$ and $$$b_2 = c_2$$$ and $$$b_3 \ne c_3$$$.

Find the number of beautiful pairs of triples among the written triples $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array.

It is guaranteed that the sum of the values of $$$n$$$ for all test cases in the test does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Note that the answer may not fit into 32-bit data types.

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

## Note
In the first example, $$$a = [3, 2, 2, 2, 3]$$$, Polycarp will write the following triples:

1. $$$[3, 2, 2]$$$;
2. $$$[2, 2, 2]$$$;
3. $$$[2, 2, 3]$$$.

In the third example, $$$a = [1, 2, 3, 2, 2, 3, 4, 2]$$$, Polycarp will write the following triples:

1. $$$[1, 2, 3]$$$;
2. $$$[2, 3, 2]$$$;
3. $$$[3, 2, 2]$$$;
4. $$$[2, 2, 3]$$$;
5. $$$[2, 3, 4]$$$;
6. $$$[3, 4, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's imagine the surface of Mars as an infinite coordinate plane. Initially, the rover Perseverance-2 and the helicopter Ingenuity-2 are located at the point with coordinates $$$(0, 0)$$$. A set of instructions $$$s$$$ consisting of $$$n$$$ instructions of the following types was specially developed for them:

- N: move one meter north (from point $$$(x, y)$$$ to $$$(x, y + 1)$$$);
- S: move one meter south (from point $$$(x, y)$$$ to $$$(x, y - 1)$$$);
- E: move one meter east (from point $$$(x, y)$$$ to $$$(x + 1, y)$$$);
- W: move one meter west (from point $$$(x, y)$$$ to $$$(x - 1, y)$$$).

Each instruction must be executed either by the rover or by the helicopter. Moreover, each device must execute at least one instruction. Your task is to distribute the instructions in such a way that after executing all $$$n$$$ instructions, the helicopter and the rover end up at the same point, or determine that this is impossible.

## Input Format
The first line of input contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of instructions.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of the characters 'N', 'S', 'E', 'W' — the sequence of instructions.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

## Output Format
For each test case, if the required distribution of instructions exists, output a string $$$p$$$ of length $$$n$$$ consisting of the characters 'R', 'H'. If the $$$i$$$-th operation should be executed by the rover, then $$$p_i=\text{R}$$$, if the $$$i$$$-th operation should be executed by the helicopter, then $$$p_i=\text{H}$$$. If there are multiple solutions, output any of them.

Otherwise, output NO.

## Examples
```input
10
6
NENSNE
3
WWW
6
NESSWS
2
SN
2
WE
4
SSNN
4
WESN
2
SS
4
EWNN
4
WEWE
```
```output
RRHRRH
NO
HRRHRH
NO
NO
RHRH
RRHH
RH
RRRH
RRHH
```

## Note
Let's consider the first example: the string $$$S = \texttt{NENSNE}$$$. One of the possible solutions, shown in the figure below, is $$$p = \texttt{RRHRRH}$$$, using which both the rover and the helicopter will end up one meter north and one meter east.

For WWW, the solution is impossible.

Now solve the problem and return the code.