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

# Problem
Three guys play a game: first, each person writes down $$$n$$$ distinct words of length $$$3$$$. Then, they total up the number of points as follows:

- if a word was written by one person — that person gets 3 points,
- if a word was written by two people — each of the two gets 1 point,
- if a word was written by all — nobody gets any points.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of words written by each person.

The following three lines each contain $$$n$$$ distinct strings — the words written by each person. Each string consists of $$$3$$$ lowercase English characters.

## Output Format
For each test case, output three space-separated integers — the number of points each of the three guys earned. You should output the answers in the same order as the input; the $$$i$$$-th integer should be the number of points earned by the $$$i$$$-th guy.

## Examples
```input
3
1
abc
def
abc
3
orz for qaq
qaq orz for
cod for ces
5
iat roc hem ica lly
bac ter iol ogi sts
bac roc lly iol iat
```
```output
1 3 1 
2 2 6 
9 11 5
```

## Note
In the first test case:

- The word $$$\texttt{abc}$$$ was written by the first and third guys — they each get $$$1$$$ point.
- The word $$$\texttt{def}$$$ was written by the second guy only — he gets $$$3$$$ points.

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

# Problem
You have $$$n$$$ rectangles, the $$$i$$$-th rectangle has height $$$h_i$$$ and width $$$w_i$$$.

You are asked $$$q$$$ queries of the form $$$h_s \ w_s \ h_b \ w_b$$$.

For each query output, the total area of rectangles you own that can fit a rectangle of height $$$h_s$$$ and width $$$w_s$$$ while also fitting in a rectangle of height $$$h_b$$$ and width $$$w_b$$$. In other words, print $$$\sum h_i \cdot w_i$$$ for $$$i$$$ such that $$$h_s < h_i < h_b$$$ and $$$w_s < w_i < w_b$$$.

Please note, that if two rectangles have the same height or the same width, then they cannot fit inside each other. Also note that you cannot rotate rectangles.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

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

The first line of each test case two integers $$$n, q$$$ ($$$1 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^5$$$) — the number of rectangles you own and the number of queries.

Then $$$n$$$ lines follow, each containing two integers $$$h_i, w_i$$$ ($$$1 \leq h_i, w_i \leq 1000$$$) — the height and width of the $$$i$$$-th rectangle.

Then $$$q$$$ lines follow, each containing four integers $$$h_s, w_s, h_b, w_b$$$ ($$$1 \leq h_s < h_b,\ w_s < w_b \leq 1000$$$) — the description of each query.

The sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output $$$q$$$ lines, the $$$i$$$-th line containing the answer to the $$$i$$$-th query.

## Examples
```input
3
2 1
2 3
3 2
1 1 3 4
5 5
1 1
2 2
3 3
4 4
5 5
3 3 6 6
2 1 4 5
1 1 2 10
1 1 100 100
1 1 3 3
3 1
999 999
999 999
999 998
1 1 1000 1000
```
```output
6
41
9
0
54
4
2993004
```

## Note
In the first test case, there is only one query. We need to find the sum of areas of all rectangles that can fit a $$$1 \times 1$$$ rectangle inside of it and fit into a $$$3 \times 4$$$ rectangle.

Only the $$$2 \times 3$$$ rectangle works, because $$$1 < 2$$$ (comparing heights) and $$$1 < 3$$$ (comparing widths), so the $$$1 \times 1$$$ rectangle fits inside, and $$$2 < 3$$$ (comparing heights) and $$$3 < 4$$$ (comparing widths), so it fits inside the $$$3 \times 4$$$ rectangle. The $$$3 \times 2$$$ rectangle is too tall to fit in a $$$3 \times 4$$$ rectangle. The total area is $$$2 \cdot 3 = 6$$$.

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
An L-shape is a figure on gridded paper that looks like the first four pictures below. An L-shape contains exactly three shaded cells (denoted by *), which can be rotated in any way.

You are given a rectangular grid. Determine if it contains L-shapes only, where L-shapes can't touch an edge or corner. More formally:

- Each shaded cell in the grid is part of exactly one L-shape, and
- no two L-shapes are adjacent by edge or corner.

For example, the last two grids in the picture above do not satisfy the condition because the two L-shapes touch by corner and edge, respectively.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 50$$$) — the number of rows and columns in the grid, respectively.

Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either '.' or '*' — an empty cell or a shaded cell, respectively.

## Output Format
For each test case, output "YES" if the grid is made up of L-shape that don't share edges or corners, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
10
6 10
........**
.**......*
..*..*....
.....**...
...*.....*
..**....**
6 10
....*...**
.**......*
..*..*....
.....**...
...*.....*
..**....**
3 3
...
***
...
4 4
.*..
**..
..**
..*.
5 4
.*..
**..
....
..**
..*.
3 2
.*
**
*.
2 3
*..
.**
3 2
..
**
*.
3 3
.**
*.*
**.
3 3
..*
.**
..*
```
```output
YES
NO
NO
NO
YES
NO
NO
YES
NO
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Pak Chanek has a prime number$$$^\dagger$$$ $$$n$$$. Find a prime number $$$m$$$ such that $$$n + m$$$ is not prime.

$$$^\dagger$$$ A prime number is a number with exactly $$$2$$$ factors. The first few prime numbers are $$$2,3,5,7,11,13,\ldots$$$. In particular, $$$1$$$ is not a prime number.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The only line of each test case contains a prime number $$$n$$$ ($$$2 \leq n \leq 10^5$$$).

## Output Format
For each test case, output a line containing a prime number $$$m$$$ ($$$2 \leq m \leq 10^5$$$) such that $$$n + m$$$ is not prime. It can be proven that under the constraints of the problem, such $$$m$$$ always exists.

If there are multiple solutions, you can output any of them.

## Examples
```input
3
7
2
75619
```
```output
2
7
47837
```

## Note
In the first test case, $$$m = 2$$$, which is prime, and $$$n + m = 7 + 2 = 9$$$, which is not prime.

In the second test case, $$$m = 7$$$, which is prime, and $$$n + m = 2 + 7 = 9$$$, which is not prime.

In the third test case, $$$m = 47837$$$, which is prime, and $$$n + m = 75619 + 47837 = 123456$$$, which is not prime.

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
Pak Chanek has $$$n$$$ two-dimensional slices of cheese. The $$$i$$$-th slice of cheese can be represented as a rectangle of dimensions $$$a_i \times b_i$$$. We want to arrange them on the two-dimensional plane such that:

- Each edge of each cheese is parallel to either the x-axis or the y-axis.
- The bottom edge of each cheese is a segment of the x-axis.
- No two slices of cheese overlap, but their sides can touch.
- They form one connected shape.

Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.

Find the minimum possible perimeter of the constructed shape.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of slices of cheese Pak Chanek has.

The $$$i$$$-th of the next $$$n$$$ lines of each test case contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i,b_i \leq 10^9$$$) — the dimensions of the $$$i$$$-th slice of cheese.

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 line containing an integer representing the minimum possible perimeter of the constructed shape.

## Examples
```input
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65
```
```output
26
24
134
```

## Note
In the first test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $$$2+5+1+1+1+1+3+1+5+1+2+3=26$$$. It can be shown that we cannot get a smaller perimeter.

Consider the following invalid arrangement.

Even though the perimeter of the shape above is $$$24$$$, it does not satisfy all conditions of the problem. The bottom edge of the $$$1 \times 1$$$ slice of cheese is not a segment of the x-axis.

In the second test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $$$2+2+2+3+2+3+2+2+2+4=24$$$. It can be shown that we cannot get a smaller perimeter.

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
There are $$$n$$$ bricks numbered from $$$1$$$ to $$$n$$$. Brick $$$i$$$ has a weight of $$$a_i$$$.

Pak Chanek has $$$3$$$ bags numbered from $$$1$$$ to $$$3$$$ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.

After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $$$w_j$$$ be the weight of the brick Bu Dengklek takes from bag $$$j$$$. The score is calculated as $$$|w_1 - w_2| + |w_2 - w_3|$$$, where $$$|x|$$$ denotes the absolute value of $$$x$$$.

It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of bricks.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the weights of the bricks.

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 line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.

## Examples
```input
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
```
```output
6
63
0
```

## Note
In the first test case, one way of achieving a final score of $$$6$$$ is to do the following:

- Put bricks $$$1$$$, $$$4$$$, and $$$5$$$ into bag $$$1$$$.
- Put brick $$$3$$$ into bag $$$2$$$.
- Put brick $$$2$$$ into bag $$$3$$$.

If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is:

- Take brick $$$5$$$ from bag $$$1$$$.
- Take brick $$$3$$$ from bag $$$2$$$.
- Take brick $$$2$$$ from bag $$$3$$$.

The score is $$$|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$$$. It can be shown that Bu Dengklek cannot get a smaller score from this distribution.

It can be shown that there is no other distribution that results in a final score bigger than $$$6$$$.

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

# Problem
Pak Chanek is given an array $$$a$$$ of $$$n$$$ integers. For each $$$i$$$ ($$$1 \leq i \leq n$$$), Pak Chanek will write the one-element set $$$\{a_i\}$$$ on a whiteboard.

After that, in one operation, Pak Chanek may do the following:

1. Choose two different sets $$$S$$$ and $$$T$$$ on the whiteboard such that $$$S \cap T = \varnothing$$$ ($$$S$$$ and $$$T$$$ do not have any common elements).
2. Erase $$$S$$$ and $$$T$$$ from the whiteboard and write $$$S \cup T$$$ (the union of $$$S$$$ and $$$T$$$) onto the whiteboard.

After performing zero or more operations, Pak Chanek will construct a multiset $$$M$$$ containing the sizes of all sets written on the whiteboard. In other words, each element in $$$M$$$ corresponds to the size of a set after the operations.

How many distinct$$$^\dagger$$$ multisets $$$M$$$ can be created by this process? Since the answer may be large, output it modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ Multisets $$$B$$$ and $$$C$$$ are different if and only if there exists a value $$$k$$$ such that the number of elements with value $$$k$$$ in $$$B$$$ is different than the number of elements with value $$$k$$$ in $$$C$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

## Output Format
Output the number of distinct multisets $$$M$$$ modulo $$$998\,244\,353$$$.

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

## Note
In the first example, the possible multisets $$$M$$$ are $$$\{1,1,1,1,1,1\}$$$, $$$\{1,1,1,1,2\}$$$, $$$\{1,1,1,3\}$$$, $$$\{1,1,2,2\}$$$, $$$\{1,1,4\}$$$, $$$\{1,2,3\}$$$, and $$$\{2,2,2\}$$$.

As an example, let's consider a possible sequence of operations.

1. In the beginning, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{1\}$$$, $$$\{4\}$$$, and $$$\{3\}$$$.
2. Do an operation on sets $$$\{1\}$$$ and $$$\{3\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{4\}$$$, and $$$\{1,3\}$$$.
3. Do an operation on sets $$$\{2\}$$$ and $$$\{4\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{1,3\}$$$, and $$$\{2,4\}$$$.
4. Do an operation on sets $$$\{1,3\}$$$ and $$$\{2,4\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, and $$$\{1,2,3,4\}$$$.
5. The multiset $$$M$$$ that is constructed is $$$\{1,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 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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
Given a rooted tree, define the value of vertex $$$u$$$ in the tree recursively as the MEX$$$^\dagger$$$ of the values of its children. Note that it is only the children, not all of its descendants. In particular, the value of a leaf is $$$0$$$.

Pak Chanek has a rooted tree that initially only contains a single vertex with index $$$1$$$, which is the root. Pak Chanek is going to do $$$q$$$ queries. In the $$$i$$$-th query, Pak Chanek is given an integer $$$x_i$$$. Pak Chanek needs to add a new vertex with index $$$i+1$$$ as the child of vertex $$$x_i$$$. After adding the new vertex, Pak Chanek needs to recalculate the values of all vertices and report the sum of the values of all vertices in the current tree.

$$$^\dagger$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For example, the MEX of $$$[0,1,1,2,6,7]$$$ is $$$3$$$ and the MEX of $$$[6,9]$$$ is $$$0$$$.

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

Each of the next $$$q$$$ lines contains a single integer $$$x_i$$$ ($$$1 \leq x_i \leq i$$$) — the description of the $$$i$$$-th query.

## Output Format
For each query, print a line containing an integer representing the sum of the new values of all vertices in the tree after adding the vertex.

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

## Note
In the first example, the tree after the $$$6$$$-th query will look like this.

- Vertex $$$7$$$ is a leaf, so its value is $$$0$$$.
- Vertex $$$6$$$ is a leaf, so its value is $$$0$$$.
- Vertex $$$5$$$ only has a child with value $$$0$$$, so its value is $$$1$$$.
- Vertex $$$4$$$ is a leaf, so its value is $$$0$$$.
- Vertex $$$3$$$ only has a child with value $$$0$$$, so its value is $$$1$$$.
- Vertex $$$2$$$ has children with values $$$0$$$ and $$$1$$$, so its value is $$$2$$$.
- Vertex $$$1$$$ has children with values $$$1$$$ and $$$2$$$, so its value is $$$0$$$.

The sum of the values of all vertices is $$$0+0+1+0+1+2+0=4$$$.

Now solve the problem and return the code.