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
The first location in the brand new critically acclaimed fantasy action RPG "Ancient Staff" is a poisonous swamp. The swamp has some lily pads growing in it. It can be represented as a $$$2 \times n$$$ grid ($$$2$$$ rows and $$$n$$$ columns), where each cell is either empty or has a lily pad in it.

There are exactly $$$n$$$ lily pads in a swamp — one in each column. A frog is sitting on top of every lily pad. In one move, every frog must jump to an adjacent by a side cell.

After the move, no frog can be outside the grid and no two frogs can share the same lily pad. Two frogs from adjacent cells can't jump towards each other (i.e. swap cells).

If a frog jumps to a lily pad, it survives. Otherwise, it falls into a poisonous swamp and gets devoured by an eldritch creature living on its bottom.

You can choose the direction each frogs jumps at. Determine the maximum number of frogs that can survive after one move.

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

The first line of the testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of columns in a swamp grid.

Each of the following two lines contains a description of a row of a swamp — a string, consisting of exactly $$$n$$$ characters. Each character is either a dot ('.'), denoting a swamp cell, or an asterisk ('*'), denoting a lily pad with a frog.

In each column, there is exactly one dot and exactly one asterisk. The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the maximum number of frogs that can survive after one move, if you choose the direction each frogs jumps at.

## Examples
```input
3
5
*..**
.**..
1
*
.
3
...
***
```
```output
2
0
2
```

## Note
The $$$i$$$-th frog is the frog on the lily pad in the $$$i$$$-th column.

In the first testcase:

- the first frog can't survive because there's no adjacent lily pad;
- the second and the third frogs can jump right and up, respectively, — there's no way to save them both at the same time;
- the fourth and the fifth frogs can jump left and left, respectively, — there's no way to save them both at the same time; note, however, that the third and the fourth frogs will end up in the same cell in the swamp, which is not prohibited.

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

# Problem
You are given an array $$$[a_1, a_2, \dots, a_n]$$$, consisting of positive integers.

For every $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$, where $$$F(x)$$$ is the sum of digits of $$$x$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$.

## Examples
```input
4
1 3 3 7
```
```output
18 17 17 15
```
-----
```input
3
42 1337 999
```
```output
38 53 47
```

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
Consider the following problem.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters, and an integer $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$). Each letter is one of the first $$$c$$$ letters of the alphabet.

You apply the following operation until the length of the string is less than $$$k$$$: choose a contiguous substring of the string of length exactly $$$k$$$, remove it from the string and glue the resulting parts together without changing the order.

Let the resulting string of length smaller than $$$k$$$ be $$$t$$$. What is lexicographically smallest string $$$t$$$ that can obtained?

You are asked the inverse of this problem. Given two integers $$$n$$$ and $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$) and a string $$$t$$$, consisting of ($$$n \bmod k$$$) lowercase Latin letters, count the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

Print that number modulo $$$998\,244\,353$$$.

## Input Format
The first line contains three integers $$$n, k$$$ and $$$c$$$ ($$$1 \le n \le 10^6$$$; $$$2 \le k \le 10^6$$$; $$$1 \le c \le 26$$$; $$$n$$$ is not divisible by $$$k$$$) — the length of string $$$s$$$, the length of the substring that is being removed and the number of first letters from the alphabet.

The second line contains string $$$t$$$, consisting of exactly ($$$n \bmod k$$$) lowercase Latin letters. Each letter is one of the first $$$c$$$ letters of the alphabet.

## Output Format
Print a single integer — the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

## Examples
```input
3 2 2
a
```
```output
6
```
-----
```input
5 3 3
bc
```
```output
15
```
-----
```input
34 12 26
codeforces
```
```output
988024123
```
-----
```input
5 3 1
aa
```
```output
1
```

## Note
The strings $$$s$$$ in the first example: "aaa", "aab", "aba", "abb", "baa", "bba".

The strings $$$s$$$ in the second example: "bcabc", "bcacc", "bcbbc", "bcbcc", "bccbc", "bcccc", "caabc", "cabbc", "cacbc", "cbabc", "cbbbc", "cbcbc", "ccabc", "ccbbc", "cccbc".

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

# Problem
You are given a tree consisting of $$$n$$$ vertices. Some vertices of the tree are red, all other vertices are blue.

Each edge of the tree has a positive weight. Let's define $$$d(x, y)$$$ as the distance between the vertices $$$x$$$ and $$$y$$$, i. e. the sum of weights of edges belonging to the simple path between $$$x$$$ and $$$y$$$.

For each vertex, you have to choose an integer $$$v_i$$$. These integers should meet the following constraint: for every blue vertex $$$b$$$ and every red vertex $$$r$$$, $$$d(b, r) \ge v_b + v_r$$$.

You have to maximize the value of $$$\sum \limits_{i=1}^{n} v_i$$$.

Note that the values of $$$v_i$$$ are not necessarily positive.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$). If the $$$i$$$-th vertex is red, $$$c_i = 1$$$, otherwise $$$c_i = 0$$$.

Then $$$n-1$$$ lines follow. Each line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le w_i \le 10^6$$$; $$$x_i \ne y_i$$$) denoting an edge between the vertices $$$x_i$$$ and $$$y_i$$$ which has weight $$$w_i$$$. These edges form a tree.

## Output Format
If the value of $$$\sum \limits_{i=1}^{n} v_i$$$ can be as big as possible, print Infinity. Otherwise, print one integer — the maximum possible value of $$$\sum \limits_{i=1}^{n} v_i$$$ you can get.

## Examples
```input
4
1 1 0 0
3 4 50
3 2 100
2 1 100
```
```output
350
```
-----
```input
6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100
```
```output
203
```
-----
```input
3
1 1 1
1 2 100
2 3 100
```
```output
Infinity
```

## Note
In the first example, you can assign $$$v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130$$$.

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
A square of positive (strictly greater than $$$0$$$) area is located on the coordinate plane, with sides parallel to the coordinate axes. You are given the coordinates of its corners, in random order. Your task is to find the area of the square.

## Input Format
Each test consists of several testcases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases. The following is a description of the testcases.

Each testcase contains four lines, each line contains two integers $$$x_i, y_i$$$ ($$$-1000\le x_i, y_i\le 1000$$$), coordinates of the corners of the square.

It is guaranteed that there is a square with sides parallel to the coordinate axes, with positive (strictly greater than $$$0$$$) area, with corners in given points.

## Output Format
For each test case, print a single integer, the area of the square.

## Examples
```input
3
1 2
4 5
1 5
4 2
-1 1
1 -1
1 1
-1 -1
45 11
45 39
17 11
17 39
```
```output
9
4
784
```

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
Petya has an array $$$a_i$$$ of $$$n$$$ integers. His brother Vasya became envious and decided to make his own array of $$$n$$$ integers.

To do this, he found $$$m$$$ integers $$$b_i$$$ ($$$m\ge n$$$), and now he wants to choose some $$$n$$$ integers of them and arrange them in a certain order to obtain an array $$$c_i$$$ of length $$$n$$$.

To avoid being similar to his brother, Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $$$D = \sum_{i=1}^{n} |a_i - c_i|$$$ to be as large as possible.

Help Vasya find the maximum difference $$$D$$$ he can obtain.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le m\le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^9$$$). The third line of each test case contains $$$m$$$ integers $$$b_i$$$ ($$$1\le b_i\le 10^9$$$).

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

## Output Format
For each test case, output a single integer — the maximum total difference $$$D$$$ that can be obtained.

## Examples
```input
9
4 6
6 1 2 4
3 5 1 7 2 3
3 4
1 1 1
1 1 1 1
5 5
1 2 3 4 5
1 2 3 4 5
2 6
5 8
8 7 5 8 2 10
2 2
4 1
9 6
4 6
8 10 6 4
3 10 6 1 8 9
3 5
6 5 2
1 7 9 7 2
5 5
9 10 6 3 7
5 9 2 3 9
1 6
3
2 7 10 1 1 5
```
```output
16
0
12
11
10
23
15
25
7
```

## Note
In the first example, Vasya can, for example, create the array $$$(1, 5, 7, 2)$$$. Then the total difference will be $$$D = |6-1|+|1-5|+|2-7|+|4-2| = 5+4+5+2 = 16$$$.

In the second example, all the integers available to Vasya are equal to 1, so he can only create the array $$$(1, 1, 1)$$$, for which the difference $$$D = 0$$$.

In the third example, Vasya can, for example, create the array $$$(5, 4, 3, 2, 1)$$$. Then the total difference will be $$$D = |1-5|+|2-4|+|3-3|+|4-2|+|5-1| = 4+2+0+2+4 = 12$$$.

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
The Master's Assistance Center has announced an entrance exam, which consists of the following.

The candidate is given a set $$$s$$$ of size $$$n$$$ and some strange integer $$$c$$$. For this set, it is needed to calculate the number of pairs of integers $$$(x, y)$$$ such that $$$0 \leq x \leq y \leq c$$$, $$$x + y$$$ is not contained in the set $$$s$$$, and also $$$y - x$$$ is not contained in the set $$$s$$$.

Your friend wants to enter the Center. Help him pass the exam!

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — the size of the set and the strange integer.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — the elements of the set $$$s$$$.

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

## Output Format
For each test case, output a single integer — the number of suitable pairs of integers.

## Examples
```input
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353
```
```output
3
16139
10
2
33
36
35
499999998999122959
```

## Note
In the first test case, the following pairs are suitable: $$$(0, 0)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$.

In the third test case, the following pairs are suitable: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$, $$$(5, 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: 256.0 MB

# Problem
One day the Codeforces round author sat exams. He had n exams and he needed to get an integer from 2 to 5 for each exam. He will have to re-sit each failed exam, i.e. the exam that gets mark 2.

The author would need to spend too much time and effort to make the sum of his marks strictly more than k. That could have spoilt the Codeforces round. On the other hand, if the sum of his marks is strictly less than k, the author's mum won't be pleased at all.

The Codeforces authors are very smart and they always get the mark they choose themselves. Also, the Codeforces authors just hate re-sitting exams.

Help the author and find the minimum number of exams he will have to re-sit if he passes the exams in the way that makes the sum of marks for all n exams equal exactly k.

## Input Format
The single input line contains space-separated integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 250) — the number of exams and the required sum of marks.

It is guaranteed that there exists a way to pass n exams in the way that makes the sum of marks equal exactly k.

## Output Format
Print the single number — the minimum number of exams that the author will get a 2 for, considering that the sum of marks for all exams must equal k.

## Examples
```input
4 8
```
```output
4
```
-----
```input
4 10
```
```output
2
```
-----
```input
1 3
```
```output
0
```

## Note
In the first sample the author has to get a 2 for all his exams.

In the second sample he should get a 3 for two exams and a 2 for two more.

In the third sample he should get a 3 for one exam.

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 of lengths $$$a_1, a_2, \ldots, a_n$$$. Find the maximum number of regular (equal-sided) polygons you can construct simultaneously, such that:

- Each side of a polygon is formed by exactly one stick.
- No stick is used in more than $$$1$$$ polygon.

Note: Sticks cannot be broken.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the number of sticks available.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — the stick lengths.

## Output Format
For each test case, output a single integer on a new line — the maximum number of regular (equal-sided) polygons you can make simultaneously from the sticks available.

## Examples
```input
4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4
```
```output
0
0
1
2
```

## Note
In the first test case, we only have one stick, hence we can't form any polygon.

In the second test case, the two sticks aren't enough to form a polygon either.

In the third test case, we can use the $$$4$$$ sticks of length $$$3$$$ to create a square.

In the fourth test case, we can make a pentagon with side length $$$2$$$, and a square of side length $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Given integers $$$n$$$ and $$$k$$$, construct a sequence of $$$n$$$ non-negative (i.e. $$$\geq 0$$$) integers $$$a_1, a_2, \ldots, a_n$$$ such that

1. $$$\sum\limits_{i = 1}^n a_i = k$$$
2. The number of $$$1$$$s in the binary representation of $$$a_1 | a_2 | \ldots | a_n$$$ is maximized, where $$$|$$$ denotes the bitwise OR operation.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the number of non-negative integers to be printed and the sum respectively.

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 sequence $$$a_1, a_2, \ldots, a_n$$$ on a new line that satisfies the conditions given above.

If there are multiple solutions, print any of them.

## Examples
```input
4
1 5
2 3
2 5
6 51
```
```output
5
1 2
5 0
3 1 1 32 2 12
```

## Note
In the first test case, we have to print exactly one integer, hence we can only output $$$5$$$ as the answer.

In the second test case, we output $$$1, 2$$$ which sum up to $$$3$$$, and $$$1 | 2 = (11)_2$$$ has two $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

In the fourth test case, we output $$$3, 1, 1, 32, 2, 12$$$ which sum up to $$$51$$$, and $$$3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2$$$ has five $$$1$$$s in its binary representation, which is the maximum we can achieve in these constraints.

Now solve the problem and return the code.