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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has two favorite integers $$$x$$$ and $$$y$$$ (they can be equal), and he has found an array $$$a$$$ of length $$$n$$$.

Polycarp considers a pair of indices $$$\langle i, j \rangle$$$ ($$$1 \le i < j \le n$$$) beautiful if:

- $$$a_i + a_j$$$ is divisible by $$$x$$$;
- $$$a_i - a_j$$$ is divisible by $$$y$$$.

For example, if $$$x=5$$$, $$$y=2$$$, $$$n=6$$$, $$$a=$$$[$$$1, 2, 7, 4, 9, 6$$$], then the only beautiful pairs are:

- $$$\langle 1, 5 \rangle$$$: $$$a_1 + a_5 = 1 + 9 = 10$$$ ($$$10$$$ is divisible by $$$5$$$) and $$$a_1 - a_5 = 1 - 9 = -8$$$ ($$$-8$$$ is divisible by $$$2$$$);
- $$$\langle 4, 6 \rangle$$$: $$$a_4 + a_6 = 4 + 6 = 10$$$ ($$$10$$$ is divisible by $$$5$$$) and $$$a_4 - a_6 = 4 - 6 = -2$$$ ($$$-2$$$ is divisible by $$$2$$$).

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

The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x, y \le 10^9$$$) — the size of the array and Polycarp's favorite integers.

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

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, output a single integer — the number of beautiful pairs in the array $$$a$$$.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.
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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $$$m$$$ months, starting with no money, Charlie will work hard and earn $$$x$$$ pounds per month. For the $$$i$$$-th month $$$(1 \le i \le m)$$$, there'll be a single opportunity of paying cost $$$c_i$$$ pounds to obtain happiness $$$h_i$$$.

Borrowing is not allowed. Money earned in the $$$i$$$-th month can only be spent in a later $$$j$$$-th month ($$$j>i$$$).

Since physicists don't code, help Charlie find the maximum obtainable sum of happiness.

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

The first line of each test case contains two integers, $$$m$$$ and $$$x$$$ ($$$1 \le m \le 50$$$, $$$1 \le x \le 10^8$$$) — the total number of months and the monthly salary.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers, $$$c_i$$$ and $$$h_i$$$ ($$$0 \le c_i \le 10^8$$$, $$$1 \le h_i \le 10^3$$$) — the cost and happiness on offer for the $$$i$$$-th month. Note that some happiness may be free ($$$c_i=0$$$ for some $$$i$$$'s).

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

## Output Format
For each test case, print a single integer, the maximum sum of happiness Charlie could obtain.

## Examples
```input
7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2
```
```output
0
10
200
15
1
9
9
```

## Note
In the first test case, Charlie only gets paid at the end of the month, so is unable to afford anything.

In the second test case, Charlie obtains the free happiness in the first month.

In the third test case, it's optimal for Charlie to buy happiness in the second month. Even with money left at the end, Charlie could not go back in time to obtain the happiness on offer in the first month.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You can never buy enough happiness, so here we go again! In this version, you can only buy $$$h_i = 1$$$ unit of happiness each month, but the number of months is hugely increased. We are in the realm of quantum happiness and time dilation.

Being a physicist, Charlie likes to plan his life in simple and precise terms.

For the next $$$m$$$ months, starting with no money, Charlie will work hard and earn $$$x$$$ pounds per month. For the $$$i$$$-th month $$$(1 \le i \le m)$$$, there'll be a single opportunity of paying cost $$$c_i$$$ pounds to obtain one unit of happiness. You cannot buy more than one unit each month.

Borrowing is not allowed. Money earned in the $$$i$$$-th month can only be spent in a later $$$j$$$-th month ($$$j>i$$$).

Since physicists don't code, help Charlie find the maximum reachable units of happiness.

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

The first line of each test case contains two integers, $$$m$$$ and $$$x$$$ ($$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le x \le 10^3$$$) — the total number of months and the monthly salary.

The second line of each test case contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \leq c_i \leq 10^3$$$) — the cost of one unit of happiness for each month.

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

## Output Format
For each test case, output one integer — the maximal amount of happiness Charlie can get.

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

Now solve the problem and return the code.