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

# Problem
You have an array $$$a$$$ consisting of $$$n$$$ distinct positive integers, numbered from $$$1$$$ to $$$n$$$. Define $$$p_k$$$ as $$$$$$p_k = \sum_{1 \le i, j \le k} a_i \bmod a_j,$$$$$$ where $$$x \bmod y$$$ denotes the remainder when $$$x$$$ is divided by $$$y$$$. You have to find and print $$$p_1, p_2, \ldots, p_n$$$.

## Input Format
The first line contains $$$n$$$ — the length of the array ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ space-separated distinct integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 3 \cdot 10^5$$$, $$$a_i \neq a_j$$$ if $$$i \neq j$$$).

## Output Format
Print $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$.

## Examples
```input
4
6 2 7 3
```
```output
0 2 12 22
```
-----
```input
3
3 2 1
```
```output
0 3 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 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ distinct elements and an integer $$$k$$$. Each element in the array is a non-negative integer not exceeding $$$2^k-1$$$.

Let's define the XOR distance for a number $$$x$$$ as the value of

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

For every integer $$$x$$$ from $$$0$$$ to $$$2^k-1$$$, you have to calculate $$$f(x)$$$.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$). All these integers are distinct.

## Output Format
Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.

## Examples
```input
3 3
6 0 3
```
```output
3 1 1 2 2 1 1 3
```
-----
```input
3 4
13 4 2
```
```output
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2
```

## Note
Consider the first example:

- for $$$x = 0$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[6, 0, 3]$$$, and the minimum absolute difference of two elements is $$$3$$$;
- for $$$x = 1$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[7, 1, 2]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 2$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[4, 2, 1]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 3$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[5, 3, 0]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 4$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[2, 4, 7]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 5$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[3, 5, 6]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 6$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[0, 6, 5]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 7$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[1, 7, 4]$$$, and the minimum absolute difference of two elements is $$$3$$$.

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: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
For a permutation $$$p$$$ of numbers $$$1$$$ through $$$n$$$, we define a stair array $$$a$$$ as follows: $$$a_i$$$ is length of the longest segment of permutation which contains position $$$i$$$ and is made of consecutive values in sorted order: $$$[x, x+1, \ldots, y-1, y]$$$ or $$$[y, y-1, \ldots, x+1, x]$$$ for some $$$x \leq y$$$. For example, for permutation $$$p = [4, 1, 2, 3, 7, 6, 5]$$$ we have $$$a = [1, 3, 3, 3, 3, 3, 3]$$$.

You are given the stair array $$$a$$$. Your task is to calculate the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$. Note that this number can be equal to zero.

## Input Format
The first line of input contains integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the length of a stair array $$$a$$$.

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

## Output Format
Print the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$.

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

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
During the hypnosis session, Nicholas suddenly remembered a positive integer $$$n$$$, which doesn't contain zeros in decimal notation.

Soon, when he returned home, he got curious: what is the maximum number of digits that can be removed from the number so that the number becomes not prime, that is, either composite or equal to one?

For some numbers doing so is impossible: for example, for number $$$53$$$ it's impossible to delete some of its digits to obtain a not prime integer. However, for all $$$n$$$ in the test cases of this problem, it's guaranteed that it's possible to delete some of their digits to obtain a not prime number.

Note that you cannot remove all the digits from the number.

A prime number is a number that has no divisors except one and itself. A composite is a number that has more than two divisors. $$$1$$$ is neither a prime nor a composite number.

## Input Format
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^3$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$k$$$ ($$$1 \le k \le 50$$$) — the number of digits in the number.

The second line of each test case contains a positive integer $$$n$$$, which doesn't contain zeros in decimal notation ($$$10^{k-1} \le n < 10^{k}$$$). It is guaranteed that it is always possible to remove less than $$$k$$$ digits to make the number not prime.

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

## Output Format
For every test case, print two numbers in two lines. In the first line print the number of digits, that you have left in the number. In the second line print the digits left after all delitions.

If there are multiple solutions, print any.

## Examples
```input
7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221
```
```output
2
27
1
4
1
1
2
35
2
77
1
4
1
6
```

## Note
In the first test case, you can't delete $$$2$$$ digits from the number $$$237$$$, as all the numbers $$$2$$$, $$$3$$$, and $$$7$$$ are prime. However, you can delete $$$1$$$ digit, obtaining a number $$$27 = 3^3$$$.

In the second test case, you can delete all digits except one, as $$$4 = 2^2$$$ is a composite number.

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
After crossing the Windswept Wastes, Ori has finally reached the Windtorn Ruins to find the Heart of the Forest! However, the ancient repository containing this priceless Willow light did not want to open!

Ori was taken aback, but the Voice of the Forest explained to him that the cunning Gorleks had decided to add protection to the repository.

The Gorleks were very fond of the "string expansion" operation. They were also very fond of increasing subsequences.

Suppose a string $$$s_1s_2s_3 \ldots s_n$$$ is given. Then its "expansion" is defined as the sequence of strings $$$s_1$$$, $$$s_1 s_2$$$, ..., $$$s_1 s_2 \ldots s_n$$$, $$$s_2$$$, $$$s_2 s_3$$$, ..., $$$s_2 s_3 \ldots s_n$$$, $$$s_3$$$, $$$s_3 s_4$$$, ..., $$$s_{n-1} s_n$$$, $$$s_n$$$. For example, the "expansion" the string 'abcd' will be the following sequence of strings: 'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'.

To open the ancient repository, Ori must find the size of the largest increasing subsequence of the "expansion" of the string $$$s$$$. Here, strings are compared lexicographically.

Help Ori with this task!

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
Each test contains multiple test cases.

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^3$$$), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer $$$n$$$ ($$$1 \le n \le 5000$$$) — length of the string.

The second line of each test case contains a non-empty string of length $$$n$$$, which consists of lowercase latin letters.

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

## Output Format
For every test case print one non-negative integer — the answer to the problem.

## Examples
```input
7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky
```
```output
9
17
12
29
14
3
9
```

## Note
In first test case the "expansion" of the string is: 'a', 'ac', 'acb', 'acba', 'acbac', 'c', 'cb', 'cba', 'cbac', 'b', 'ba', 'bac', 'a', 'ac', 'c'. The answer can be, for example, 'a', 'ac', 'acb', 'acba', 'acbac', 'b', 'ba', 'bac', 'c'.

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
You are given a string $$$s$$$. You need to find two non-empty strings $$$a$$$ and $$$b$$$ such that the following conditions are satisfied:

1. Strings $$$a$$$ and $$$b$$$ are both subsequences of $$$s$$$.
2. For each index $$$i$$$, character $$$s_i$$$ of string $$$s$$$ must belong to exactly one of strings $$$a$$$ or $$$b$$$.
3. String $$$a$$$ is lexicographically minimum possible; string $$$b$$$ may be any possible string.

Given string $$$s$$$, print any valid $$$a$$$ and $$$b$$$.

Reminder:

A string $$$a$$$ ($$$b$$$) is a subsequence of a string $$$s$$$ if $$$a$$$ ($$$b$$$) can be obtained from $$$s$$$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

A string $$$x$$$ is lexicographically smaller than a string $$$y$$$ if and only if one of the following holds:

- $$$x$$$ is a prefix of $$$y$$$, but $$$x \ne y$$$;
- in the first position where $$$x$$$ and $$$y$$$ differ, the string $$$x$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$y$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first and only line of each test case contains one string $$$s$$$ ($$$2 \le |s| \le 100$$$ where $$$|s|$$$ means the length of $$$s$$$). String $$$s$$$ consists of lowercase Latin letters.

## Output Format
For each test case, print the strings $$$a$$$ and $$$b$$$ that satisfy the given conditions. If there are multiple answers, print any.

## Examples
```input
3
fc
aaaa
thebrightboiler
```
```output
c f
a aaa
b therightboiler
```

## Note
In the first test case, there are only two choices: either $$$a =$$$ f and $$$b = $$$ c or $$$a = $$$ c and $$$b = $$$ f. And $$$a = $$$c is lexicographically smaller than $$$a = $$$ f.

In the second test case, a is the only character in the string.

In the third test case, it can be proven that b is the lexicographically smallest subsequence of $$$s$$$. The second string can be of two variants; one of them is given here.

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
You are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. You choose any subset of the given numbers (possibly, none or all numbers) and negate these numbers (i. e. change $$$x \to (-x)$$$). What is the maximum number of different values in the array you can achieve?

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

The next lines contain the description of the $$$t$$$ test cases, two lines per a test case.

In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 100$$$): the number of integers in the array.

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

## Output Format
For each test case, print one integer: the maximum number of different elements in the array that you can achieve negating numbers in the array.

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

## Note
In the first example we can, for example, negate the first and the last numbers, achieving the array $$$[-1, 1, 2, -2]$$$ with four different values.

In the second example all three numbers are already different.

In the third example negation does not change anything.

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
You have a string $$$s_1 s_2 \ldots s_n$$$ and you stand on the left of the string looking right. You want to choose an index $$$k$$$ ($$$1 \le k \le n$$$) and place a mirror after the $$$k$$$-th letter, so that what you see is $$$s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$$$. What is the lexicographically smallest string you can see?

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$): the number of test cases.

The next $$$t$$$ lines contain the description of the test cases, two lines per a test case.

In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$): the length of the string.

The second line contains the string $$$s$$$ consisting of $$$n$$$ lowercase English characters.

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

## Output Format
For each test case print the lexicographically smallest string you can see.

## Examples
```input
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa
```
```output
cc
cbaabc
aa
bb
```

## Note
In the first test case choose $$$k = 1$$$ to obtain "cc".

In the second test case choose $$$k = 3$$$ to obtain "cbaabc".

In the third test case choose $$$k = 1$$$ to obtain "aa".

In the fourth test case choose $$$k = 1$$$ to obtain "bb".

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 array $$$a_1, a_2, \ldots, a_n$$$ is good if and only if for every subsegment $$$1 \leq l \leq r \leq n$$$, the following holds: $$$a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$$$.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you can replace any one element of this array with any real number. Find the minimum number of operations you need to make this array good.

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

Each of the next $$$t$$$ lines contains the description of a test case.

In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 70$$$): the number of integers in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$): the initial array.

## Output Format
For each test case, print one integer: the minimum number of elements that you need to replace to make the given array good.

## Examples
```input
5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100
```
```output
0
2
0
3
0
```

## Note
In the first test case, the array is good already.

In the second test case, one of the possible good arrays is $$$[1, 1, \underline{1}, \underline{1}]$$$ (replaced elements are underlined).

In the third test case, the array is good already.

In the fourth test case, one of the possible good arrays is $$$[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$$$.

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

# Problem
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$x$$$.

You need to select the maximum number of elements in the array, such that for every subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ containing strictly more than one element $$$(l < r)$$$, either:

- At least one element on this subsegment is not selected, or
- $$$a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$$$.

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 10$$$): the number of test cases.

The descriptions of $$$t$$$ test cases follow, three lines per test case.

In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 50\,000$$$): the number of integers in the array.

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

The third line contains one integer $$$x$$$ ($$$-100\,000 \leq x \leq 100\,000$$$).

## Output Format
For each test case, print one integer: the maximum number of elements that you can select.

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

## Note
In the first example, one valid way to select the elements is $$$[\underline{1}, 2, \underline{3}, \underline{4}, \underline{5}]$$$. All subsegments satisfy at least one of the criteria. For example, for the subsegment $$$l = 1$$$, $$$r = 2$$$ we have that the element $$$2$$$ is not selected, satisfying the first criterion. For the subsegment $$$l = 3$$$, $$$r = 5$$$ we have $$$3 + 4 + 5 = 12 \ge 2 \cdot 3$$$, satisfying the second criterion.

We can't select all elements, because in this case for $$$l = 1$$$, $$$r = 2$$$ all elements are selected and we have $$$a_1 + a_2 = 3 < 2 \cdot 2$$$. Thus, the maximum number of selected elements is $$$4$$$.

In the second example, one valid solution is $$$[\underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}, 2, \underline{4}, \underline{2}, \underline{4}]$$$.

In the third example, one valid solution is $$$[\underline{-10}, -5, \underline{-10}]$$$.

In the fourth example, one valid solution is $$$[\underline{9}, \underline{9}, -3]$$$.

Now solve the problem and return the code.