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
Paprika loves permutations. She has an array $$$a_1, a_2, \dots, a_n$$$. She wants to make the array a permutation of integers $$$1$$$ to $$$n$$$.

In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$x > 0$$$), then perform $$$a_i := a_i \bmod x$$$ (that is, replace $$$a_i$$$ by the remainder of $$$a_i$$$ divided by $$$x$$$). In different operations, the chosen $$$i$$$ and $$$x$$$ can be different.

Determine the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$. If it is impossible, output $$$-1$$$.

A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

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

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 the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$, or $$$-1$$$ if it is impossible.

## Examples
```input
4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7
```
```output
1
-1
4
2
```

## Note
For the first test, the only possible sequence of operations which minimizes the number of operations is:

- Choose $$$i=2$$$, $$$x=5$$$. Perform $$$a_2 := a_2 \bmod 5 = 2$$$.

For the second test, it is impossible to obtain a permutation of integers from $$$1$$$ to $$$n$$$.

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 three sticks with integer lengths $$$l_1, l_2$$$ and $$$l_3$$$.

You are asked to break exactly one of them into two pieces in such a way that:

- both pieces have positive (strictly greater than $$$0$$$) integer length;
- the total length of the pieces is equal to the original length of the stick;
- it's possible to construct a rectangle from the resulting four sticks such that each stick is used as exactly one of its sides.

A square is also considered a rectangle.

Determine if it's possible to do that.

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

The only line of each testcase contains three integers $$$l_1, l_2, l_3$$$ ($$$1 \le l_i \le 10^8$$$) — the lengths of the sticks.

## Output Format
For each testcase, print "YES" if it's possible to break one of the sticks into two pieces with positive integer length in such a way that it's possible to construct a rectangle from the resulting four sticks. Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as a positive answer).

## Examples
```input
4
6 1 5
2 5 2
2 4 2
5 5 4
```
```output
YES
NO
YES
YES
```

## Note
In the first testcase, the first stick can be broken into parts of length $$$1$$$ and $$$5$$$. We can construct a rectangle with opposite sides of length $$$1$$$ and $$$5$$$.

In the second testcase, breaking the stick of length $$$2$$$ can only result in sticks of lengths $$$1, 1, 2, 5$$$, which can't be made into a rectangle. Breaking the stick of length $$$5$$$ can produce results $$$2, 3$$$ or $$$1, 4$$$ but neither of them can't be put into a rectangle.

In the third testcase, the second stick can be broken into parts of length $$$2$$$ and $$$2$$$. The resulting rectangle has opposite sides $$$2$$$ and $$$2$$$ (which is a square).

In the fourth testcase, the third stick can be broken into parts of length $$$2$$$ and $$$2$$$. The resulting rectangle has opposite sides $$$2$$$ and $$$5$$$.

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 an integer array $$$a_1, a_2, \dots, a_n$$$ and integer $$$k$$$.

In one step you can

- either choose some index $$$i$$$ and decrease $$$a_i$$$ by one (make $$$a_i = a_i - 1$$$);
- or choose two indices $$$i$$$ and $$$j$$$ and set $$$a_i$$$ equal to $$$a_j$$$ (make $$$a_i = a_j$$$).

What is the minimum number of steps you need to make the sum of array $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$? (You are allowed to make values of array negative).

## 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 two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{15}$$$) — the size of array $$$a$$$ and upper bound on its sum.

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 array itself.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the minimum number of steps to make $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$.

## Examples
```input
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
```
```output
10
0
2
7
```

## Note
In the first test case, you should decrease $$$a_1$$$ $$$10$$$ times to get the sum lower or equal to $$$k = 10$$$.

In the second test case, the sum of array $$$a$$$ is already less or equal to $$$69$$$, so you don't need to change it.

In the third test case, you can, for example:

1. set $$$a_4 = a_3 = 1$$$;
2. decrease $$$a_4$$$ by one, and get $$$a_4 = 0$$$.

In the fourth test case, you can, for example:

1. choose $$$a_7$$$ and decrease in by one $$$3$$$ times; you'll get $$$a_7 = -2$$$;
2. choose $$$4$$$ elements $$$a_6$$$, $$$a_8$$$, $$$a_9$$$ and $$$a_{10}$$$ and them equal to $$$a_7 = -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: 512.0 MB

# Problem
You are given a binary string (i. e. a string consisting of characters 0 and/or 1) $$$s$$$ of length $$$n$$$. You can perform the following operation with the string $$$s$$$ at most once: choose a substring (a contiguous subsequence) of $$$s$$$ having exactly $$$k$$$ characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).

Calculate the number of different strings which can be obtained from $$$s$$$ by performing this operation at most once.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$).

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of characters 0 and/or 1.

## Output Format
Print one integer — the number of different strings which can be obtained from $$$s$$$ by performing the described operation at most once. Since the answer can be large, output it modulo $$$998244353$$$.

## Examples
```input
7 2
1100110
```
```output
16
```
-----
```input
5 0
10010
```
```output
1
```
-----
```input
8 1
10001000
```
```output
10
```
-----
```input
10 8
0010011000
```
```output
1
```

## Note
Some strings you can obtain in the first example:

- to obtain 0110110, you can take the substring from the $$$1$$$-st character to the $$$4$$$-th character, which is 1100, and reorder its characters to get 0110;
- to obtain 1111000, you can take the substring from the $$$3$$$-rd character to the $$$7$$$-th character, which is 00110, and reorder its characters to get 11000;
- to obtain 1100101, you can take the substring from the $$$5$$$-th character to the $$$7$$$-th character, which is 110, and reorder its characters to get 101.

In the second example, $$$k = 0$$$ so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.

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
Let's call a set of positive integers $$$a_1, a_2, \dots, a_k$$$ quadratic if the product of the factorials of its elements is a square of an integer, i. e. $$$\prod\limits_{i=1}^{k} a_i! = m^2$$$, for some integer $$$m$$$.

You are given a positive integer $$$n$$$.

Your task is to find a quadratic subset of a set $$$1, 2, \dots, n$$$ of maximum size. If there are multiple answers, print any of them.

## Input Format
A single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

## Output Format
In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.

## Examples
```input
1
```
```output
1
1
```
-----
```input
4
```
```output
3
1 3 4
```
-----
```input
7
```
```output
4
1 4 5 6
```
-----
```input
9
```
```output
7
1 2 4 5 6 7 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 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 string $$$s$$$, consisting of lowercase Latin letters. Every letter appears in it no more than twice.

Your task is to rearrange the letters in the string in such a way that for each pair of letters that appear exactly twice, the distance between the letters in the pair is the same. You are not allowed to add or remove letters.

It can be shown that the answer always exists. If there are multiple answers, print any of them.

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

Each testcase consists of a non-empty string $$$s$$$, consisting of lowercase Latin letters. Every letter appears in the string no more than twice. The length of the string doesn't exceed $$$52$$$.

## Output Format
For each testcase, print a single string. Every letter should appear in it the same number of times as it appears in string $$$s$$$. For each pair of letters that appear exactly twice, the distance between the letters in the pair should be the same.

If there are multiple answers, print any of them.

## Examples
```input
3
oelhl
abcdcba
ac
```
```output
hello
ababcdc
ac
```

## Note
In the first testcase of the example, the only letter that appears exactly twice is letter 'l'. You can rearrange the letters arbitrarily, since there are no distances to compare.

In the second testcase of the example, the letters that appear exactly twice are 'a', 'b' and 'c'. Initially, letters 'a' are distance $$$6$$$ apart, letters 'b' are distance $$$4$$$ apart and letters 'c' are distance $$$2$$$ apart. They are not the same, so we have to rearrange the letters. After rearrangement, letters 'a' are distance $$$2$$$ apart, letters 'b' are distance $$$2$$$ apart and letters 'c' are distance $$$2$$$ apart. They are all the same, so the answer is valid.

In the third testcase of the example, there are no letters that appear exactly twice. Thus, any rearrangement is valid. Including not changing the string at all.

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 decimal representation of an integer $$$x$$$ without leading zeros.

You have to perform the following reduction on it exactly once: take two neighboring digits in $$$x$$$ and replace them with their sum without leading zeros (if the sum is $$$0$$$, it's represented as a single $$$0$$$).

For example, if $$$x = 10057$$$, the possible reductions are:

- choose the first and the second digits $$$1$$$ and $$$0$$$, replace them with $$$1+0=1$$$; the result is $$$1057$$$;
- choose the second and the third digits $$$0$$$ and $$$0$$$, replace them with $$$0+0=0$$$; the result is also $$$1057$$$;
- choose the third and the fourth digits $$$0$$$ and $$$5$$$, replace them with $$$0+5=5$$$; the result is still $$$1057$$$;
- choose the fourth and the fifth digits $$$5$$$ and $$$7$$$, replace them with $$$5+7=12$$$; the result is $$$10012$$$.

What's the largest number that can be obtained?

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

Each testcase consists of a single integer $$$x$$$ ($$$10 \le x < 10^{200000}$$$). $$$x$$$ doesn't contain leading zeros.

The total length of the decimal representations of $$$x$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the largest number that can be obtained after the reduction is applied exactly once. The number should not contain leading zeros.

## Examples
```input
2
10057
90
```
```output
10012
9
```

## Note
The first testcase of the example is already explained in the statement.

In the second testcase, there is only one possible reduction: the first and the second digits.

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 of the vertices (at least two) are black, all the other vertices are white.

You place a chip on one of the vertices of the tree, and then perform the following operations:

- let the current vertex where the chip is located is $$$x$$$. You choose a black vertex $$$y$$$, and then move the chip along the first edge on the simple path from $$$x$$$ to $$$y$$$.

You are not allowed to choose the same black vertex $$$y$$$ in two operations in a row (i. e., for every two consecutive operations, the chosen black vertex should be different).

You end your operations when the chip moves to the black vertex (if it is initially placed in a black vertex, you don't perform the operations at all), or when the number of performed operations exceeds $$$100^{500}$$$.

For every vertex $$$i$$$, you have to determine if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex, if the chip is initially placed on the vertex $$$i$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$), where $$$c_i = 0$$$ means that the $$$i$$$-th vertex is white, and $$$c_i = 1$$$ means that the $$$i$$$-th vertex is black. At least two values of $$$c_i$$$ are equal to $$$1$$$.

Then $$$n-1$$$ lines follow, each of them contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — the endpoints of some edge. These edges form a tree.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th integer should be equal to $$$1$$$ if there exists a (possibly empty) sequence of operations that moves the chip to some black vertex if it is placed on the vertex $$$i$$$, and $$$0$$$ if no such sequence of operations exists.

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

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

# Problem
You are given an integer array $$$a_0, a_1, \dots, a_{n - 1}$$$, and an integer $$$k$$$. You perform the following code with it:

Your task is to calculate the expected value of the variable ans after performing this code.

Note that the input is generated according to special rules (see the input format section).

## Input Format
The only line contains six integers $$$n$$$, $$$a_0$$$, $$$x$$$, $$$y$$$, $$$k$$$ and $$$M$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a_0, x, y < M \le 998244353$$$; $$$1 \le k \le 17$$$).

The array $$$a$$$ in the input is constructed as follows:

- $$$a_0$$$ is given in the input;
- for every $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the value of $$$a_i$$$ can be calculated as $$$a_i = (a_{i - 1} \cdot x + y) \bmod M$$$.

## Output Format
Let the expected value of the variable ans after performing the code be $$$E$$$. It can be shown that $$$E \cdot n^k$$$ is an integer. You have to output this integer modulo $$$998244353$$$.

## Examples
```input
3 10 3 5 13 88
```
```output
382842030
```
-----
```input
2 15363 270880 34698 17 2357023
```
```output
319392398
```

## Note
The array in the first example test is $$$[10, 35, 22]$$$. In the second example, it is $$$[15363, 1418543]$$$.

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
You are given an array $$$a$$$ of length $$$n$$$. Also you are given $$$m$$$ distinct positions $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \leq n$$$).

A non-empty subset of these positions $$$T$$$ is randomly selected with equal probability and the following value is calculated: $$$$$$\sum_{i=1}^{n} (a_i \cdot \min_{j \in T} \left|i - j\right|).$$$$$$ In other word, for each index of the array, $$$a_i$$$ and the distance to the closest chosen position are multiplied, and then these values are summed up.

Find the expected value of this sum.

This value must be found modulo $$$998\,244\,353$$$. More formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be represented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \neq 0$$$ (mod $$$M$$$). Output the integer equal to $$$p \cdot q^{-1}$$$ (mod $$$M$$$). In other words, output such integer $$$x$$$ that $$$0 \leq x < M$$$ and $$$x \cdot q = p$$$ (mod $$$M$$$).

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 998\,244\,353$$$).

The third line contains $$$m$$$ distinct integers $$$p_1, p_2, \ldots, p_m$$$ ($$$1 \leq p_i \le n$$$).

For every $$$1 \leq i < m$$$ it is guaranteed that $$$p_i < p_{i+1}$$$.

## Output Format
Print a single integer — the answer to the problem.

## Examples
```input
4 2
1 2 3 4
1 4
```
```output
665496247
```
-----
```input
6 6
4 2 4 2 4 2
1 2 3 4 5 6
```
```output
855638030
```

## Note
In the first test:

- If only $$$1$$$ is choosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 20$$$.
- If only $$$4$$$ is choosen, than the value equals to $$$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 + 4 \cdot 0 = 10$$$.
- If both positions are chosen, than the value equals to $$$1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 = 5$$$.

The answer to the problem is $$$\frac{20 + 10 + 5}{3} = \frac{35}{3} = 665\,496\,247$$$ (modulo $$$998\,244\,353$$$).

Now solve the problem and return the code.