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
Gianni, SWERC's chief judge, received a huge amount of high quality problems from the judges and now he has to choose a problem set for SWERC.

He received $$$n$$$ problems and he assigned a beauty score and a difficulty to each of them. The $$$i$$$-th problem has beauty score equal to $$$b_i$$$ and difficulty equal to $$$d_i$$$. The beauty and the difficulty are integers between $$$1$$$ and $$$10$$$.

If there are no problems with a certain difficulty (the possible difficulties are $$$1,2,\dots,10$$$) then Gianni will ask for more problems to the judges.

Otherwise, for each difficulty between $$$1$$$ and $$$10$$$, he will put in the problem set one of the most beautiful problems with such difficulty (so the problem set will contain exactly $$$10$$$ problems with distinct difficulties). You shall compute the total beauty of the problem set, that is the sum of the beauty scores of the problems chosen by Gianni.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains the integer $$$n$$$ ($$$1\le n\le 100$$$) — how many problems Gianni received from the judges.

The next $$$n$$$ lines contain two integers each. The $$$i$$$-th of such lines contains $$$b_i$$$ and $$$d_i$$$ ($$$1\le b_i, d_i\le 10$$$) — the beauty score and the difficulty of the $$$i$$$-th problem.

## Output Format
For each test case, print the total beauty of the problem set chosen by Gianni. If Gianni cannot create a problem set (because there are no problems with a certain difficulty) print the string MOREPROBLEMS (all letters are uppercase, there are no spaces).

## Examples
```input
2
3
8 4
9 3
6 7
12
3 10
10 1
10 2
10 3
10 4
3 10
10 5
10 6
10 7
10 8
10 9
1 10
```
```output
MOREPROBLEMS
93
```

## Note
In the first test case, Gianni has received only $$$3$$$ problems, with difficulties $$$3, 4, 7$$$ which are not sufficient to create a problem set (for example because there is not a problem with difficulty $$$1$$$).

In the second test case, Gianni will create a problem set by taking the problems $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$11$$$ (which have beauty equal to $$$10$$$ and all difficulties from $$$1$$$ to $$$9$$$) and one of the problems $$$1$$$ and $$$6$$$ (which have both beauty $$$3$$$ and difficulty $$$10$$$). The total beauty of the resulting problem set is $$$10\cdot 9 + 3 = 93$$$.

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
Vittorio has three favorite toys: a teddy bear, an owl, and a raccoon. Each of them has a name.

Vittorio takes several sheets of paper and writes a letter on each side of every sheet so that it is possible to spell any of the three names by arranging some of the sheets in a row (sheets can be reordered and flipped as needed). The three names do not have to be spelled at the same time, it is sufficient that it is possible to spell each of them using all the available sheets (and the same sheet can be used to spell different names).

Find the minimum number of sheets required. In addition, produce a list of sheets with minimum cardinality which can be used to spell the three names (if there are multiple answers, print any).

## Input Format
The first line contains a string $$$t$$$ consisting of uppercase letters of the English alphabet ($$$1\le |t| \le 1000$$$) — the name of the teddy bear.

The second line contains a string $$$o$$$ consisting of uppercase letters of the English alphabet ($$$1\le |o| \le 1000$$$) — the name of the owl.

The third line contains a string $$$r$$$ consisting of uppercase letters of the English alphabet ($$$1\le |r| \le 1000$$$) — the name of the raccoon.

The values $$$|t|$$$, $$$|o|$$$, $$$|r|$$$ denote the length of the three names $$$t$$$, $$$o$$$, $$$r$$$.

## Output Format
The first line of the output contains a single integer $$$m$$$ — the minimum number of sheets required.

Then $$$m$$$ lines follow: the $$$j$$$-th of these lines contains a string of two uppercase letters of the English alphabet — the letters appearing on the two sides of the $$$j$$$-th sheet.

Note that you can print the sheets and the two letters of each sheet in any order.

## Examples
```input
AA
GA
MA
```
```output
2
AG
AM
```
-----
```input
TEDDY
HEDWIG
RACCOON
```
```output
8
AT
CH
CY
DG
DO
ER
IN
OW
```
-----
```input
BDC
CAA
CE
```
```output
4
AD
AE
BB
CC
```

## Note
In the first sample, the solution uses two sheets: the first sheet has A on one side and G on the other side; the second sheet has A on one side and M on the other side.

The name AA can be spelled using the A side of both sheets. The name GA can be spelled using the G side of the first sheet and the A side of the second sheet. Finally, the name MA can be spelled using the M side of the second sheet and the A side of the first sheet.

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 map of Europe can be represented by a set of $$$n$$$ cities, numbered from $$$1$$$ through $$$n$$$, which are connected by $$$m$$$ bidirectional roads, each of which connects two distinct cities. A trip of length $$$k$$$ is a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that there is a road connecting each consecutive pair $$$v_i$$$, $$$v_{i+1}$$$ of cities, for all $$$1 \le i \le k$$$. A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that it forms a trip and $$$v_i \neq v_{i + 2}$$$, for all $$$1 \le i \le k - 1$$$.

Given an integer $$$k$$$, compute the number of distinct special trips of length $$$k$$$ which begin and end in the same city. Since the answer might be large, give the answer modulo $$$998\,244\,353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$3 \le n \le 100$$$, $$$1 \le m \le n(n - 1) / 2$$$, $$$1 \le k \le 10^4$$$) — the number of cities, the number of roads and the length of trips to consider.

Each of the following $$$m$$$ lines contains a pair of distinct integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$) — each pair represents a road connecting cities $$$a$$$ and $$$b$$$. It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).

## Output Format
Print the number of special trips of length $$$k$$$ which begin and end in the same city, modulo $$$998\,244\,353$$$.

## Examples
```input
4 5 2
4 1
2 3
3 1
4 3
2 4
```
```output
0
```
-----
```input
4 5 3
1 3
4 2
4 1
2 1
3 4
```
```output
12
```
-----
```input
8 20 12
4 3
6 7
5 7
8 2
8 3
3 1
4 7
8 5
5 4
3 5
7 1
5 1
7 8
3 2
4 2
5 2
1 4
4 8
3 6
4 6
```
```output
35551130
```

## Note
In the first sample, we are looking for special trips of length $$$2$$$, but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is $$$0$$$.

In the second sample, we have the following $$$12$$$ special trips of length $$$3$$$ which begin and end in the same city: $$$(1, 2, 4, 1)$$$, $$$(1, 3, 4, 1)$$$, $$$(1, 4, 2, 1)$$$, $$$(1, 4, 3, 1)$$$, $$$(2, 1, 4, 2)$$$, $$$(2, 4, 1, 2)$$$, $$$(3, 1, 4, 3)$$$, $$$(3, 4, 1, 3)$$$, $$$(4, 1, 3, 4)$$$, $$$(4, 3, 1, 4)$$$, $$$(4, 1, 2, 4)$$$, and $$$(4, 2, 1, 4)$$$.

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel.

How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.

Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.

Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains a string $$$u$$$ ($$$1\le |u|\le 200$$$) — the DNA of the weasel.

The second line of each test case contains a string $$$v$$$ ($$$1\le |v|\le 200$$$) — the DNA of the basilisk.

The values $$$|u|$$$, $$$|v|$$$ denote the lengths of the strings $$$u$$$ and $$$v$$$. It is guaranteed that both strings $$$u$$$ and $$$v$$$ consist of the letters A, B and C.

## Output Format
For each test case, print YES if there is a sequence of mutations to get from $$$u$$$ to $$$v$$$ and NO otherwise.

## Examples
```input
8
A
B
B
C
C
A
AA
BB
BB
CC
CC
AA
ABAB
BCBC
ABC
CBA
```
```output
NO
NO
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ people, numbered from $$$1$$$ to $$$n$$$, sitting at a round table. Person $$$i+1$$$ is sitting to the right of person $$$i$$$ (with person $$$1$$$ sitting to the right of person $$$n$$$).

You have come up with a better seating arrangement, which is given as a permutation $$$p_1, p_2, \dots, p_n$$$. More specifically, you want to change the seats of the people so that at the end person $$$p_{i+1}$$$ is sitting to the right of person $$$p_i$$$ (with person $$$p_1$$$ sitting to the right of person $$$p_n$$$). Notice that for each seating arrangement there are $$$n$$$ permutations that describe it (which can be obtained by rotations).

In order to achieve that, you can swap two people sitting at adjacent places; but there is a catch: for all $$$1 \le x \le n-1$$$ you cannot swap person $$$x$$$ and person $$$x+1$$$ (notice that you can swap person $$$n$$$ and person $$$1$$$). What is the minimum number of swaps necessary? It can be proven that any arrangement can be achieved.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 10\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 200\,000$$$) — the number of people sitting at the table.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \ne p_j$$$ for $$$i \ne j$$$) — the desired final order of the people around the table.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

## Output Format
For each test case, print the minimum number of swaps necessary to achieve the desired order.

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

## Note
In the first test case, we can swap person $$$4$$$ and person $$$1$$$ (who are adjacent) in the initial configuration and get the order $$$[4, 2, 3, 1]$$$ which is equivalent to the desired one. Hence in this case a single swap is sufficient.

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
There are $$$n$$$ equidistant antennas on a line, numbered from $$$1$$$ to $$$n$$$. Each antenna has a power rating, the power of the $$$i$$$-th antenna is $$$p_i$$$.

The $$$i$$$-th and the $$$j$$$-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $$$|i-j| \leq \min(p_i, p_j)$$$. Sending a message directly between two such antennas takes $$$1$$$ second.

What is the minimum amount of time necessary to send a message from antenna $$$a$$$ to antenna $$$b$$$, possibly using other antennas as relays?

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \leq a, b \leq n \leq 200\,000$$$) — the number of antennas, and the origin and target antenna.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the powers of the antennas.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

## Output Format
For each test case, print the number of seconds needed to trasmit a message from $$$a$$$ to $$$b$$$. It can be shown that under the problem constraints, it is always possible to send such a message.

## Examples
```input
3
10 2 9
4 1 1 1 5 1 1 1 1 5
1 1 1
1
3 1 3
3 3 1
```
```output
4
0
2
```

## Note
In the first test case, we must send a message from antenna $$$2$$$ to antenna $$$9$$$. A sequence of communications requiring $$$4$$$ seconds, which is the minimum possible amount of time, is the following:

- In $$$1$$$ second we send the message from antenna $$$2$$$ to antenna $$$1$$$. This is possible since $$$|2-1|\le \min(1, 4) = \min(p_2, p_1)$$$.
- In $$$1$$$ second we send the message from antenna $$$1$$$ to antenna $$$5$$$. This is possible since $$$|1-5|\le \min(4, 5) = \min(p_1, p_5)$$$.
- In $$$1$$$ second we send the message from antenna $$$5$$$ to antenna $$$10$$$. This is possible since $$$|5-10|\le \min(5, 5) = \min(p_5, p_{10})$$$.
- In $$$1$$$ second we send the message from antenna $$$10$$$ to antenna $$$9$$$. This is possible since $$$|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$$$.

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

# Problem
SWERC organizers want to hold a gastronomic event.

The location of the event is a building with $$$n$$$ rooms connected by $$$n-1$$$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.

In each room you have to set up the tasting of a typical Italian dish. You can choose from $$$n$$$ typical Italian dishes rated from $$$1$$$ to $$$n$$$ depending on how good they are ($$$n$$$ is the best possible rating). The $$$n$$$ dishes have distinct ratings.

You want to assign the $$$n$$$ dishes to the $$$n$$$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:

- Each room in the sequence is connected to the next one in the sequence by a corridor.
- The ratings of the dishes in the rooms (in the order given by the sequence) are increasing.

## Input Format
The first line contains an integer $$$n$$$ ($$$2\le n\le 1\,000\,000$$$) — the number of rooms.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \cdots , p_n$$$ ($$$1 \leq p_i < i$$$). Each $$$p_i$$$ indicates that there is a corridor between room $$$i$$$ and room $$$p_i$$$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.

## Output Format
Print the maximum number of pleasing tours.

## Examples
```input
5
1 2 2 2
```
```output
13
```
-----
```input
10
1 2 3 4 3 2 7 8 7
```
```output
47
```

## Note
In the first sample, it is optimal to place the dish with rating $$$1$$$ in room $$$1$$$, the dish with rating $$$2$$$ in room $$$3$$$, the dish with rating $$$3$$$ in room $$$2$$$, the dish with rating $$$4$$$ in room $$$5$$$ and the dish with rating $$$5$$$ in room $$$4$$$.

All the $$$13$$$ possible pleasing tours are: $$$(1)$$$, $$$(2)$$$, $$$(3)$$$, $$$(4)$$$, $$$(5)$$$, $$$(1,2)$$$, $$$(3,2)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(1,2,4)$$$, $$$(1,2,5)$$$, $$$(3,2,4)$$$, $$$(3,2,5)$$$.

There are also other ways to assign the dishes to the rooms so that there are $$$13$$$ pleasing tours.

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
Bethany would like to tile her bathroom. The bathroom has width $$$w$$$ centimeters and length $$$l$$$ centimeters. If Bethany simply used the basic tiles of size $$$1 \times 1$$$ centimeters, she would use $$$w \cdot l$$$ of them.

However, she has something different in mind.

- On the interior of the floor she wants to use the $$$1 \times 1$$$ tiles. She needs exactly $$$(w-2) \cdot (l-2)$$$ of these.
- On the floor boundary she wants to use tiles of size $$$1 \times a$$$ for some positive integer $$$a$$$. The tiles can also be rotated by $$$90$$$ degrees.

For which values of $$$a$$$ can Bethany tile the bathroom floor as described? Note that $$$a$$$ can also be $$$1$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

Each test case consist of a single line, which contains two integers $$$w$$$, $$$l$$$ ($$$3 \leq w, l \leq 10^{9}$$$) — the dimensions of the bathroom.

## Output Format
For each test case, print an integer $$$k$$$ ($$$0\le k$$$) — the number of valid values of $$$a$$$ for the given test case — followed by $$$k$$$ integers $$$a_1, a_2,\dots, a_k$$$ ($$$1\le a_i$$$) — the valid values of $$$a$$$. The values $$$a_1, a_2, \dots, a_k$$$ have to be sorted from smallest to largest.

It is guaranteed that under the problem constraints, the output contains at most $$$200\,000$$$ integers.

## Examples
```input
3
3 5
12 12
314159265 358979323
```
```output
3 1 2 3
3 1 2 11
2 1 2
```

## Note
In the first test case, the bathroom is $$$3$$$ centimeters wide and $$$5$$$ centimeters long. There are three values of $$$a$$$ such that Bethany can tile the floor as described in the statement, namely $$$a=1$$$, $$$a=2$$$ and $$$a=3$$$. The three tilings are represented in the following pictures.

Now solve the problem and return the code.