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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

You are allowed to replace at most one character in the string with an arbitrary lowercase Latin letter.

Print the lexicographically minimal string that can be obtained from the original string and contains the maximum number of palindromes as substrings. Note that if a palindrome appears more than once as a substring, it is counted the same number of times it appears.

The string $$$a$$$ is lexicographically smaller than the 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$$$ are different, the string $$$a$$$ contains a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the number of characters in the string.

The second line contains the string $$$s$$$ itself, consisting of exactly $$$n$$$ lowercase Latin letters.

## Output Format
In the first line, print one integer — the maximum number of palindromic substrings that can be obtained using the operation described in the statement at most once.

In the second line, print the string that can be obtained from $$$s$$$ and has the maximum possible number of palindromic substrings. If there are multiple answers, print the lexicographically smallest one.

## Examples
```input
5
aabaa
```
```output
15
aaaaa
```
-----
```input
5
aaaaa
```
```output
15
aaaaa
```
-----
```input
4
awoo
```
```output
7
aooo
```

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 an array of integers $$$a_1, a_2, \dots, a_n$$$. You can perform the following operation any number of times (possibly zero):

- Choose any element $$$a_i$$$ from the array and change its value to any integer between $$$0$$$ and $$$a_i$$$ (inclusive). More formally, if $$$a_i < 0$$$, replace $$$a_i$$$ with any integer in $$$[a_i, 0]$$$, otherwise replace $$$a_i$$$ with any integer in $$$[0, a_i]$$$.

Let $$$r$$$ be the minimum possible product of all the $$$a_i$$$ after performing the operation any number of times.

Find the minimum number of operations required to make the product equal to $$$r$$$. Also, print one such shortest sequence of operations. If there are multiple answers, you can print any of them.

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

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

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

## Output Format
For each test case:

- The first line must contain the minimum number of operations $$$k$$$ ($$$0 \leq k \leq n$$$).
- The $$$j$$$-th of the next $$$k$$$ lines must contain two integers $$$i$$$ and $$$x$$$, which represent the $$$j$$$-th operation. That operation consists in replacing $$$a_i$$$ with $$$x$$$.

## Examples
```input
4
1
155
4
2 8 -1 3
4
-1 0 -2 -5
4
-15 -75 -25 -30
```
```output
1
1 0
0
0
1
3 0
```

## Note
In the first test case, we can change the value of the first integer into $$$0$$$ and the product will become $$$0$$$, which is the minimum possible.

In the second test case, initially, the product of integers is equal to $$$2 \cdot 8 \cdot (-1) \cdot 3 = -48$$$ which is the minimum possible, so we should do nothing in this case.

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 a string $$$s$$$ of length $$$n$$$. Let's define two operations you can apply on the string:

- remove the first character of the string;
- remove the second character of the string.

Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

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

The first line of each test case contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$. It is guaranteed that the string only contains lowercase letters of the English alphabet.

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 single integer: the number of distinct non-empty strings you can get.

## Examples
```input
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
```
```output
5
1
9
50
210
```

## Note
In the first test case, we can get the following strings: $$$a$$$, $$$aa$$$, $$$aaa$$$, $$$aaaa$$$, $$$aaaaa$$$.

In the third test case, for example, the word $$$ba$$$ can be reached in the following way:

- remove the first character of the current string $$$ababa$$$, getting $$$baba$$$;
- remove the second character of the current string $$$baba$$$, getting $$$bba$$$;
- remove the second character of the current string $$$bba$$$, getting $$$ba$$$.

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 permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ of odd integers from $$$1$$$ to $$$2n-1$$$ and a permutation $$$q_0, q_1, \ldots, q_{k-1}$$$ of integers from $$$0$$$ to $$$k-1$$$.

An array $$$a_0, a_1, \ldots, a_{nk-1}$$$ of length $$$nk$$$ is defined as follows:

$$$a_{i \cdot k+j}=p_i \cdot 2^{q_j}$$$ for all $$$0 \le i < n$$$ and all $$$0 \le j < k$$$

For example, if $$$p = [3, 5, 1]$$$ and $$$q = [0, 1]$$$, then $$$a = [3, 6, 5, 10, 1, 2]$$$.

Note that all arrays in the statement are zero-indexed. Note that each element of the array $$$a$$$ is uniquely determined.

Find the number of inversions in the array $$$a$$$. Since this number can be very large, you should find only its remainder modulo $$$998\,244\,353$$$.

An inversion in array $$$a$$$ is a pair $$$(i, j)$$$ ($$$0 \le i < j < nk$$$) such that $$$a_i > a_j$$$.

## 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, k \le 2 \cdot 10^5$$$) — the lengths of arrays $$$p$$$ and $$$q$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$p_0, p_1, \ldots, p_{n-1}$$$ ($$$1 \le p_i \le 2n-1$$$, $$$p_i$$$ is odd) — the array $$$p$$$.

The third line of each test case contains $$$k$$$ distinct integers $$$q_0, q_1, \ldots, q_{k-1}$$$ ($$$0 \le q_i < k$$$) — the array $$$q$$$.

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

## Output Format
For each test case, output one integer: the number of inversions in array $$$a$$$ modulo $$$998\,244\,353$$$.

## Examples
```input
4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1
```
```output
9
25
0
104
```

## Note
In the first test case, array $$$a$$$ is equal to $$$[3, 6, 5, 10, 1, 2]$$$. There are $$$9$$$ inversions in it: $$$(0, 4)$$$, $$$(0, 5)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$. Note that these are pairs $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$.

In the second test case, array $$$a$$$ is equal to $$$[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$$$. There are $$$25$$$ inversions in it.

In the third test case, array $$$a$$$ is equal to $$$[1, 2, 4, 8, 16]$$$. There are no inversions in it.

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 an even integer $$$n$$$ and an integer $$$k$$$. Your task is to construct a matrix of size $$$n \times n$$$ consisting of numbers $$$0$$$ and $$$1$$$ in such a way that the following conditions are true, or report that it is impossible:

- the sum of all the numbers in the matrix is exactly $$$k$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is the same for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is the same for each $$$j$$$.

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

Each test case is described by a single line, which contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$n$$$ is even, $$$0 \leq k \leq n^2$$$).

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

## Output Format
For each test case, output $$$\texttt{Yes}$$$ if it's possible to construct a matrix that satisfies all of the problem's conditions, and $$$\texttt{No}$$$ otherwise.

If it is possible to construct a matrix, the $$$i$$$-th of the next $$$n$$$ lines should contain $$$n$$$ integers representing the elements in the $$$i$$$-th row of the matrix.

## Examples
```input
5
4 0
6 6
6 5
4 2
6 36
```
```output
Yes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Yes
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
No
No
Yes
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
```

## Note
In the first example, all conditions are satisfied:

- the sum of all the numbers in the matrix is exactly $$$0$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is $$$0$$$ for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is $$$0$$$ for each $$$j$$$.

In the third example, it can be shown that it's impossible to find a matrix satisfying all the problem's conditions.

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 an array of integers $$$l_1, l_2, \dots, l_n$$$ and an integer $$$d$$$. Is it possible to construct a tree satisfying the following three conditions?

- The tree contains $$$n + 1$$$ nodes.
- The length of the $$$i$$$-th edge is equal to $$$l_i$$$.
- The (weighted) diameter of the tree is equal to $$$d$$$.

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

The first line of each test case contains two integers $$$n$$$, $$$d$$$ ($$$2 \leq n \leq 2000, 1 \leq d \leq 2000$$$).

The second line of each test case contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \leq l_i \leq d$$$).

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

## Output Format
For each test case, output $$$\texttt{Yes}$$$ if it is possible to construct a tree that satisfies all the conditions, and $$$\texttt{No}$$$ otherwise.

You can print the letters in any case (upper or lower).

## Examples
```input
3
4 10
1 2 3 4
4 7
1 4 3 4
6 18
2 4 3 7 6 7
```
```output
Yes
No
Yes
```

## Note
Below, you are given the illustrations of trees for the first and third test cases. One of the diameters is highlighted by coloring its edges in red.

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 an integer $$$n$$$ and three strings $$$a, b, c$$$, each consisting of $$$n$$$ lowercase Latin letters.

Let a template be a string $$$t$$$ consisting of $$$n$$$ lowercase and/or uppercase Latin letters. The string $$$s$$$ matches the template $$$t$$$ if the following conditions hold for all $$$i$$$ from $$$1$$$ to $$$n$$$:

- if the $$$i$$$-th letter of the template is lowercase, then $$$s_i$$$ must be the same as $$$t_i$$$;
- if the $$$i$$$-th letter of the template is uppercase, then $$$s_i$$$ must be different from the lowercase version of $$$t_i$$$. For example, if there is a letter 'A' in the template, you cannot use the letter 'a' in the corresponding position of the string.

Accordingly, the string doesn't match the template if the condition doesn't hold for at least one $$$i$$$.

Determine whether there exists a template $$$t$$$ such that the strings $$$a$$$ and $$$b$$$ match it, while the string $$$c$$$ does not.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 20$$$) — the length of the given strings.

The next three lines contain the strings $$$a, b$$$ and $$$c$$$. Each string consists of exactly $$$n$$$ lowercase Latin letters.

## Output Format
For each testcase, print "YES" if there exists a template $$$t$$$ such that the strings $$$a$$$ and $$$b$$$ match it, while the string $$$c$$$ does not. Otherwise, print "NO".

## Examples
```input
4
1
a
b
c
2
aa
bb
aa
10
mathforces
luckforces
adhoccoder
3
acc
abd
abc
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, you can use the template "C". The first letter of strings $$$a$$$ and $$$b$$$ differ from 'c', so they match the template. The first letter of string $$$c$$$ equals 'c', so it doesn't match.

In the third test case, you can use the template "CODEforces".

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
Let's recall that an increasing subsequence of the array $$$a$$$ is a sequence that can be obtained from it by removing some elements without changing the order of the remaining elements, and the remaining elements are strictly increasing (i. e $$$a_{b_1} < a_{b_2} < \dots < a_{b_k}$$$ and $$$b_1 < b_2 < \dots < b_k$$$). Note that an empty subsequence is also increasing.

You are given a positive integer $$$X$$$. Your task is to find an array of integers of length at most $$$200$$$, such that it has exactly $$$X$$$ increasing subsequences, or report that there is no such array. If there are several answers, you can print any of them.

If two subsequences consist of the same elements, but correspond to different positions in the array, they are considered different (for example, the array $$$[2, 2]$$$ has two different subsequences equal to $$$[2]$$$).

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

The only line of each test case contains a single integer $$$X$$$ ($$$2 \le X \le 10^{18}$$$).

## Output Format
For each query, print the answer to it. If it is impossible to find the required array, print -1 on the first line. Otherwise, print a positive integer $$$n$$$ on the first line — the length of the array. On the second line, print $$$n$$$ integers — the required array itself. If there are several answers, you can print any of them. All elements of the array should be in the range $$$[-10^9; 10^9]$$$.

## Examples
```input
4
2
5
13
37
```
```output
1
0
3
0 1 0
5
2 2 3 4 2
7
-1 -1 0 0 2 3 -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 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
Vladislav has a binary square grid of $$$n \times n$$$ cells. A triangle or a square is drawn on the grid with symbols $$$\texttt{1}$$$. As he is too busy being cool, he asks you to tell him which shape is drawn on the grid.

- A triangle is a shape consisting of $$$k$$$ ($$$k>1$$$) consecutive rows, where the $$$i$$$-th row has $$$2 \cdot i-1$$$ consecutive characters $$$\texttt{1}$$$, and the central 1s are located in one column. An upside down triangle is also considered a valid triangle (but not rotated by 90 degrees).

Two left pictures contain examples of triangles: $$$k=4$$$, $$$k=3$$$. The two right pictures don't contain triangles.

- A square is a shape consisting of $$$k$$$ ($$$k>1$$$) consecutive rows, where the $$$i$$$-th row has $$$k$$$ consecutive characters $$$\texttt{1}$$$, which are positioned at an equal distance from the left edge of the grid.

Examples of two squares: $$$k=2$$$, $$$k=4$$$.

For the given grid, determine the type of shape that is drawn on it.

## 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$$$ ($$$2 \leq n \leq 10$$$) — the size of the grid.

The next $$$n$$$ lines each contain $$$n$$$ characters $$$\texttt{0}$$$ or $$$\texttt{1}$$$.

The grid contains exactly one triangle or exactly one square that contains all the $$$\texttt{1}$$$s in the grid. It is guaranteed that the size of the triangle or square is greater than $$$1$$$ (i.e., the shape cannot consist of exactly one 1).

## Output Format
For each test case, output "SQUARE" if all the $$$\texttt{1}$$$s in the grid form a square, and "TRIANGLE" otherwise (without quotes).

## Examples
```input
6
3
000
011
011
4
0000
0000
0100
1110
2
11
11
5
00111
00010
00000
00000
00000
10
0000000000
0000000000
0000000000
0000000000
0000000000
1111111110
0111111100
0011111000
0001110000
0000100000
3
111
111
111
```
```output
SQUARE
TRIANGLE
SQUARE
TRIANGLE
TRIANGLE
SQUARE
```

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

# Problem
Please note that the time limit for this problem is only 0.5 seconds per test.

Vladislav wrote the integers from $$$1$$$ to $$$n$$$, inclusive, on the board. Then he replaced each integer with the sum of its digits.

What is the sum of the numbers on the board now?

For example, if $$$n=12$$$ then initially the numbers on the board are: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.$$$$$$ Then after the replacement, the numbers become: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3.$$$$$$ The sum of these numbers is $$$1+2+3+4+5+6+7+8+9+1+2+3=51$$$. Thus, for $$$n=12$$$ the answer is $$$51$$$.

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the largest number Vladislav writes.

## Output Format
For each test case, output a single integer — the sum of the numbers at the end of the process.

## Examples
```input
7
12
1
2
3
1434
2024
200000
```
```output
51
1
3
6
18465
28170
4600002
```

Now solve the problem and return the code.