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

# Problem
XYMXYM and CQXYM will prepare $$$n$$$ problems for Codeforces. The difficulty of the problem $$$i$$$ will be an integer $$$a_i$$$, where $$$a_i \geq 0$$$. The difficulty of the problems must satisfy $$$a_i+a_{i+1}<m$$$ ($$$1 \leq i < n$$$), and $$$a_1+a_n<m$$$, where $$$m$$$ is a fixed integer. XYMXYM wants to know how many plans of the difficulty of the problems there are modulo $$$998\,244\,353$$$.

Two plans of difficulty $$$a$$$ and $$$b$$$ are different only if there is an integer $$$i$$$ ($$$1 \leq i \leq n$$$) satisfying $$$a_i \neq b_i$$$.

## Input Format
A single line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 50\,000$$$, $$$1 \leq m \leq 10^9$$$).

## Output Format
Print a single integer — the number of different plans.

## Examples
```input
3 2
```
```output
4
```
-----
```input
5 9
```
```output
8105
```
-----
```input
21038 3942834
```
```output
338529212
```

## Note
In the first test case, the valid $$$a$$$ are: $$$[0,0,0]$$$, $$$[0,0,1]$$$, $$$[0,1,0]$$$, $$$[1,0,0]$$$.

$$$[1,0,1]$$$ is invalid since $$$a_1+a_n \geq m$$$.

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

# Problem
Polycarpus has n markers and m marker caps. Each marker is described by two numbers: xi is the color and yi is the diameter. Correspondingly, each cap is described by two numbers: aj is the color and bj is the diameter. Cap (aj, bj) can close marker (xi, yi) only if their diameters match, that is, bj = yi. Besides, a marker is considered to be beautifully closed, if the cap color and the marker color match, that is, aj = xi.

Find the way to close the maximum number of markers. If there are several such ways, then choose the one that has the maximum number of beautifully closed markers.

## Input Format
The first input line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the number of markers and the number of caps, correspondingly.

Next n lines describe the markers. The i-th line contains two space-separated integers xi, yi (1 ≤ xi, yi ≤ 1000) — the i-th marker's color and diameter, correspondingly.

Next m lines describe the caps. The j-th line contains two space-separated integers aj, bj (1 ≤ aj, bj ≤ 1000) — the color and diameter of the j-th cap, correspondingly.

## Output Format
Print two space-separated integers u, v, where u is the number of closed markers and v is the number of beautifully closed markers in the sought optimal way. Remember that you have to find the way to close the maximum number of markers, and if there are several such ways, you should choose the one where the number of beautifully closed markers is maximum.

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

## Note
In the first test sample the first marker should be closed by the fourth cap, the second marker should be closed by the first cap and the third marker should be closed by the second cap. Thus, three markers will be closed, and two of them will be beautifully closed — the first and the third markers.

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

# Problem
One popular website developed an unusual username editing procedure. One can change the username only by deleting some characters from it: to change the current name s, a user can pick number p and character c and delete the p-th occurrence of character c from the name. After the user changed his name, he can't undo the change.

For example, one can change name "arca" by removing the second occurrence of character "a" to get "arc".

Polycarpus learned that some user initially registered under nickname t, where t is a concatenation of k copies of string s. Also, Polycarpus knows the sequence of this user's name changes. Help Polycarpus figure out the user's final name.

## Input Format
The first line contains an integer k (1 ≤ k ≤ 2000). The second line contains a non-empty string s, consisting of lowercase Latin letters, at most 100 characters long. The third line contains an integer n (0 ≤ n ≤ 20000) — the number of username changes. Each of the next n lines contains the actual changes, one per line. The changes are written as "pi ci" (without the quotes), where pi (1 ≤ pi ≤ 200000) is the number of occurrences of letter ci, ci is a lowercase Latin letter. It is guaranteed that the operations are correct, that is, the letter to be deleted always exists, and after all operations not all letters are deleted from the name. The letters' occurrences are numbered starting from 1.

## Output Format
Print a single string — the user's final name after all changes are applied to it.

## Examples
```input
2
bac
3
2 a
1 b
2 c
```
```output
acb
```
-----
```input
1
abacaba
4
1 a
1 a
1 c
2 b
```
```output
baa
```

## Note
Let's consider the first sample. Initially we have name "bacbac"; the first operation transforms it into "bacbc", the second one — to "acbc", and finally, the third one transforms it into "acb".

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

# Problem
You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x... y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = s1s2... s|s| is a string sisi + 1... sj. For example, substring s[2...4] of string s = "abacaba" equals "bac".

## Input Format
The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

## Output Format
Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.

## Examples
```input
aa
```
```output
1
```
-----
```input
aaa
```
```output
5
```
-----
```input
abacaba
```
```output
36
```

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

# Problem
Integers from $$$1$$$ to $$$n$$$ (inclusive) were sorted lexicographically (considering integers as strings). As a result, array $$$a_1, a_2, \dots, a_n$$$ was obtained.

Calculate value of $$$(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$$$.

$$$x \mod y$$$ here means the remainder after division $$$x$$$ by $$$y$$$. This remainder is always non-negative and doesn't exceed $$$y - 1$$$. For example, $$$5 \mod 3 = 2$$$, $$$(-1) \mod 6 = 5$$$.

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$).

## Output Format
Print one integer — the required sum.

## Examples
```input
3
```
```output
0
```
-----
```input
12
```
```output
994733045
```
-----
```input
21
```
```output
978932159
```
-----
```input
1000000000000
```
```output
289817887
```

## Note
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$$$.

For example, $$$42$$$ is lexicographically smaller than $$$6$$$, because they differ in the first digit, and $$$4 < 6$$$; $$$42 < 420$$$, because $$$42$$$ is a prefix of $$$420$$$.

Let's denote $$$998244353$$$ as $$$M$$$.

In the first example, array $$$a$$$ is equal to $$$[1, 2, 3]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 2) \mod M = 0 \mod M = 0$$$
- $$$(3 - 3) \mod M = 0 \mod M = 0$$$

As a result, $$$(0 + 0 + 0) \mod 10^9 + 7 = 0$$$

In the second example, array $$$a$$$ is equal to $$$[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 10) \mod M = (-8) \mod M = 998244345$$$
- $$$(3 - 11) \mod M = (-8) \mod M = 998244345$$$
- $$$(4 - 12) \mod M = (-8) \mod M = 998244345$$$
- $$$(5 - 2) \mod M = 3 \mod M = 3$$$
- $$$(6 - 3) \mod M = 3 \mod M = 3$$$
- $$$(7 - 4) \mod M = 3 \mod M = 3$$$
- $$$(8 - 5) \mod M = 3 \mod M = 3$$$
- $$$(9 - 6) \mod M = 3 \mod M = 3$$$
- $$$(10 - 7) \mod M = 3 \mod M = 3$$$
- $$$(11 - 8) \mod M = 3 \mod M = 3$$$
- $$$(12 - 9) \mod M = 3 \mod M = 3$$$

As a result, $$$(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$$$ $$$=$$$ $$$2994733059 \mod 10^9 + 7$$$ $$$=$$$ $$$994733045$$$

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
A string is called square if it is some string written twice in a row. For example, the strings "aa", "abcabc", "abab" and "baabaa" are square. But the strings "aaa", "abaaab" and "abcdabc" are not square.

For a given string $$$s$$$ determine if it is square.

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

This is followed by $$$t$$$ lines, each containing a description of one test case. The given strings consist only of lowercase Latin letters and have lengths between $$$1$$$ and $$$100$$$ inclusive.

## Output Format
For each test case, output on a separate line:

- YES if the string in the corresponding test case is square,
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

## Examples
```input
10
a
aa
aaa
aaaa
abab
abcabc
abacaba
xxyy
xyyx
xyxy
```
```output
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES
```

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
Tanya is learning how to add numbers, but so far she is not doing it correctly. She is adding two numbers $$$a$$$ and $$$b$$$ using the following algorithm:

1. If one of the numbers is shorter than the other, Tanya adds leading zeros so that the numbers are the same length.
2. The numbers are processed from right to left (that is, from the least significant digits to the most significant).
3. In the first step, she adds the last digit of $$$a$$$ to the last digit of $$$b$$$ and writes their sum in the answer.
4. At each next step, she performs the same operation on each pair of digits in the same place and writes the result to the left side of the answer.

For example, the numbers $$$a = 17236$$$ and $$$b = 3465$$$ Tanya adds up as follows:

$$$$$$ \large{ \begin{array}{r} + \begin{array}{r} 17236\\ 03465\\ \end{array} \\ \hline \begin{array}{r} 1106911 \end{array} \end{array}} $$$$$$

- calculates the sum of $$$6 + 5 = 11$$$ and writes $$$11$$$ in the answer.
- calculates the sum of $$$3 + 6 = 9$$$ and writes the result to the left side of the answer to get $$$911$$$.
- calculates the sum of $$$2 + 4 = 6$$$ and writes the result to the left side of the answer to get $$$6911$$$.
- calculates the sum of $$$7 + 3 = 10$$$, and writes the result to the left side of the answer to get $$$106911$$$.
- calculates the sum of $$$1 + 0 = 1$$$ and writes the result to the left side of the answer and get $$$1106911$$$.

As a result, she gets $$$1106911$$$.

You are given two positive integers $$$a$$$ and $$$s$$$. Find the number $$$b$$$ such that by adding $$$a$$$ and $$$b$$$ as described above, Tanya will get $$$s$$$. Or determine that no suitable $$$b$$$ exists.

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

Each test case consists of a single line containing two positive integers $$$a$$$ and $$$s$$$ ($$$1 \le a \lt s \le 10^{18}$$$) separated by a space.

## Output Format
For each test case print the answer on a separate line.

If the solution exists, print a single positive integer $$$b$$$. The answer must be written without leading zeros. If multiple answers exist, print any of them.

If no suitable number $$$b$$$ exists, output -1.

## Examples
```input
6
17236 1106911
1 5
108 112
12345 1023412
1 11
1 20
```
```output
3465
4
-1
90007
10
-1
```

## Note
The first test case is explained in the main part of the statement.

In the third test case, we cannot choose $$$b$$$ that satisfies the problem statement.

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
Dmitry has an array of $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$.

In one operation, Dmitry can choose any index $$$j$$$ ($$$1 \le j \le n$$$) and increase the value of the element $$$a_j$$$ by $$$1$$$. He can choose the same index $$$j$$$ multiple times.

For each $$$i$$$ from $$$0$$$ to $$$n$$$, determine whether Dmitry can make the $$$\mathrm{MEX}$$$ of the array equal to exactly $$$i$$$. If it is possible, then determine the minimum number of operations to do it.

The $$$\mathrm{MEX}$$$ of the array is equal to the minimum non-negative integer that is not in the array. For example, the $$$\mathrm{MEX}$$$ of the array $$$[3, 1, 0]$$$ is equal to $$$2$$$, and the array $$$[3, 3, 1, 4]$$$ is equal to $$$0$$$.

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

The descriptions of the test cases follow.

The first line of the description of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — elements of the array $$$a$$$.

It is guaranteed that the sum of the values $$$n$$$ over all test cases in the test does not exceed $$$2\cdot10^5$$$.

## Output Format
For each test case, output $$$n + 1$$$ integer — $$$i$$$-th number is equal to the minimum number of operations for which you can make the array $$$\mathrm{MEX}$$$ equal to $$$i$$$ ($$$0 \le i \le n$$$), or -1 if this cannot be done.

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

## Note
In the first set of example inputs, $$$n=3$$$:

- to get $$$\mathrm{MEX}=0$$$, it is enough to perform one increment: $$$a_1$$$++;
- to get $$$\mathrm{MEX}=1$$$, it is enough to perform one increment: $$$a_2$$$++;
- $$$\mathrm{MEX}=2$$$ for a given array, so there is no need to perform increments;
- it is impossible to get $$$\mathrm{MEX}=3$$$ by performing increments.

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

# Problem
You are given an undirected graph of $$$n$$$ vertices indexed from $$$1$$$ to $$$n$$$, where vertex $$$i$$$ has a value $$$a_i$$$ assigned to it and all values $$$a_i$$$ are different. There is an edge between two vertices $$$u$$$ and $$$v$$$ if either $$$a_u$$$ divides $$$a_v$$$ or $$$a_v$$$ divides $$$a_u$$$.

Find the minimum number of vertices to remove such that the remaining graph is bipartite, when you remove a vertex you remove all the edges incident to it.

## Input Format
The input consists of 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 a single integer $$$n$$$ ($$$1 \le n \le 5\cdot10^4$$$) — the number of vertices in the graph.

The second line of each test case contains $$$n$$$ integers, the $$$i$$$-th of them is the value $$$a_i$$$ ($$$1 \le a_i \le 5\cdot10^4$$$) assigned to the $$$i$$$-th vertex, all values $$$a_i$$$ are different.

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

## Output Format
For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.

## Examples
```input
4
4
8 4 2 1
4
30 2 3 5
5
12 4 6 2 3
10
85 195 5 39 3 13 266 154 14 2
```
```output
2
0
1
2
```

## Note
In the first test case if we remove the vertices with values $$$1$$$ and $$$2$$$ we will obtain a bipartite graph, so the answer is $$$2$$$, it is impossible to remove less than $$$2$$$ vertices and still obtain a bipartite graph.

BeforeAfter test case #1

In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $$$0$$$.

BeforeAfter test case #2

In the third test case we only have to remove the vertex with value $$$12$$$, so the answer is $$$1$$$.

BeforeAfter test case #3

In the fourth test case we remove the vertices with values $$$2$$$ and $$$195$$$, so the answer is $$$2$$$.

BeforeAfter test case #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 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 $$$a_1, a_2, \ldots, a_n$$$ of positive integers. A good pair is a pair of indices $$$(i, j)$$$ with $$$1 \leq i, j \leq n$$$ such that, for all $$$1 \leq k \leq n$$$, the following equality holds:

$$$$$$ |a_i - a_k| + |a_k - a_j| = |a_i - a_j|, $$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.

Find a good pair. Note that $$$i$$$ can be equal to $$$j$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.

The sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single line with two space-separated indices $$$i$$$ and $$$j$$$ which form a good pair of the array. The case $$$i=j$$$ is allowed. It can be shown that such a pair always exists. If there are multiple good pairs, print any of them.

## Examples
```input
3
3
5 2 7
5
1 4 2 2 3
1
2
```
```output
2 3
1 2
1 1
```

## Note
In the first case, for $$$i = 2$$$ and $$$j = 3$$$ the equality holds true for all $$$k$$$:

- $$$k = 1$$$: $$$|a_2 - a_1| + |a_1 - a_3| = |2 - 5| + |5 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$,
- $$$k = 2$$$: $$$|a_2 - a_2| + |a_2 - a_3| = |2 - 2| + |2 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$,
- $$$k = 3$$$: $$$|a_2 - a_3| + |a_3 - a_3| = |2 - 7| + |7 - 7| = 5 = |2 - 7| = |a_2-a_3|$$$.

Now solve the problem and return the code.