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: 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 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: 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 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
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
You are given $$$n$$$ sticks with positive integral length $$$a_1, a_2, \ldots, a_n$$$.

You can perform the following operation any number of times (possibly zero):

- choose one stick, then either increase or decrease its length by $$$1$$$. After each operation, all sticks should have positive lengths.

What is the minimum number of operations that you have to perform such that it is possible to select three of the $$$n$$$ sticks and use them without breaking to form an equilateral triangle?

An equilateral triangle is a triangle where all of its three sides have the same length.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 300$$$) — the number of sticks.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300$$$.

## Output Format
For each test case, print one integer on a single line — the minimum number of operations to be made.

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

## Note
In the first test case, you can increase the length of the first stick by $$$1$$$, then decrease the length of the third stick by $$$1$$$. In total, you perform $$$2$$$ operations, such that the three sticks form an equilateral triangle of side length $$$2$$$.

In the fourth test case, you can decrease the length of the seventh stick by $$$1$$$. An equilateral triangle of side length $$$1$$$ can be selected and formed by the second, fourth, and seventh sticks.

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 are given a set $$$S$$$, which contains the first $$$n$$$ positive integers: $$$1, 2, \ldots, n$$$.

You can perform the following operation on $$$S$$$ any number of times (possibly zero):

- Choose a positive integer $$$k$$$ where $$$1 \le k \le n$$$, such that there exists a multiple of $$$k$$$ in $$$S$$$. Then, delete the smallest multiple of $$$k$$$ from $$$S$$$. This operation requires a cost of $$$k$$$.

You are given a set $$$T$$$, which is a subset of $$$S$$$. Find the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$. We can show that such a transformation is always possible.

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

The first line contains a single positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line of each test case contains a binary string of length $$$n$$$, describing the set $$$T$$$. The $$$i$$$-th character of the string is '1' if and only if $$$i$$$ is an element of $$$T$$$, and '0' otherwise.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

## Output Format
For each test case, output one non-negative integer — the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$.

## Examples
```input
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100
```
```output
0
11
4
4
17
60
```

## Note
In the first test case, we shall not perform any operations as $$$S$$$ is already equal to $$$T$$$, which is the set $$$\{1, 2, 3, 4, 5, 6\}$$$.

In the second test case, initially, $$$S = \{1, 2, 3, 4, 5, 6, 7\}$$$, and $$$T = \{1, 2, 4, 7\}$$$. We shall perform the following operations:

1. Choose $$$k=3$$$, then delete $$$3$$$ from $$$S$$$.
2. Choose $$$k=3$$$, then delete $$$6$$$ from $$$S$$$.
3. Choose $$$k=5$$$, then delete $$$5$$$ from $$$S$$$.

The total cost is $$$3+3+5 = 11$$$. It can be shown that this is the smallest cost possible.

In the third test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{\}$$$ (empty set). We shall perform $$$4$$$ operations of $$$k=1$$$ to delete $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$.

In the fourth test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{3\}$$$. We shall perform two operations with $$$k=1$$$ to delete $$$1$$$ and $$$2$$$, then perform one operation with $$$k=2$$$ to delete $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$S$$$ be the Thue-Morse sequence. In other words, $$$S$$$ is the $$$0$$$-indexed binary string with infinite length that can be constructed as follows:

- Initially, let $$$S$$$ be "0".
- Then, we perform the following operation infinitely many times: concatenate $$$S$$$ with a copy of itself with flipped bits.For example, here are the first four iterations:  Iteration$$$S$$$ before iteration$$$S$$$ before iteration with flipped bitsConcatenated $$$S$$$1010120110011030110100101101001401101001100101100110100110010110$$$\ldots$$$$$$\ldots$$$$$$\ldots$$$$$$\ldots$$$

You are given two positive integers $$$n$$$ and $$$m$$$. Find the number of positions where the strings $$$S_0 S_1 \ldots S_{m-1}$$$ and $$$S_n S_{n + 1} \ldots S_{n + m - 1}$$$ are different.

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

The first and only line of each test case contains two positive integers, $$$n$$$ and $$$m$$$ respectively ($$$1 \leq n,m \leq 10^{18}$$$).

## Output Format
For each testcase, output a non-negative integer — the Hamming distance between the two required strings.

## Examples
```input
6
1 1
5 10
34 211
73 34
19124639 56348772
12073412269 96221437021
```
```output
1
6
95
20
28208137
48102976088
```

## Note
The string $$$S$$$ is equal to 0110100110010110....

In the first test case, $$$S_0$$$ is "0", and $$$S_1$$$ is "1". The Hamming distance between the two strings is $$$1$$$.

In the second test case, $$$S_0 S_1 \ldots S_9$$$ is "0110100110", and $$$S_5 S_6 \ldots S_{14}$$$ is "0011001011". The Hamming distance between the two strings is $$$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 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
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 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
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 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
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.