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

# Problem
The only difference between the easy and the hard version is the constraint on $$$n$$$.

You are given an undirected complete graph on $$$n$$$ vertices. A complete graph is a graph where each pair of vertices is connected by an edge. You have to paint the edges of the graph into two colors, red and blue (each edge will have one color).

A set of vertices $$$S$$$ is red-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through red edges and vertices from $$$S$$$. Similarly, a set of vertices $$$S$$$ is blue-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through blue edges and vertices from $$$S$$$.

You have to paint the graph in such a way that:

- there is at least one red edge;
- there is at least one blue edge;
- for each set of vertices $$$S$$$ such that $$$|S| \ge 2$$$, $$$S$$$ is either red-connected or blue-connected, but not both.

Calculate the number of ways to paint the graph, and print it modulo $$$998244353$$$.

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

## Output Format
Print one integer — the number of ways to paint the graph, taken modulo $$$998244353$$$.

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
50
```
-----
```input
100
```
```output
878752271
```
-----
```input
1337
```
```output
520628749
```
-----
```input
42013
```
```output
906821221
```

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 two strings $$$a$$$ and $$$b$$$, consisting of lowercase Latin letters.

A template $$$t$$$ is string, consisting of lowercase Latin letters and asterisks (character '*'). A template is called asterisk-minor if the number of asterisks in it is less than or equal to the number of letters in it.

A string $$$s$$$ is said to be matching a template $$$t$$$ if you can replace each asterisk in $$$t$$$ with a string of lowercase Latin letters (possibly, an empty string) so that it becomes equal to $$$s$$$.

Find an asterisk-minor template such that both $$$a$$$ and $$$b$$$ match it, or report that such a template doesn't exist. If there are multiple answers, print any of them.

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

The first line of each testcase contains a string $$$a$$$ ($$$1 \le |a| \le 50$$$, where $$$|a|$$$ is the length of $$$a$$$), consisting of lowercase Latin letters.

The second line contains a string $$$b$$$ ($$$1 \le |b| \le 50$$$), consisting of lowercase Latin letters.

## Output Format
For each testcase, output "NO", if there doesn't exist an asterisk-minor template that both $$$a$$$ and $$$b$$$ match. Otherwise, print "YES" in the first line and the template in the second line. If there are multiple answers, print any of them.

A template should consist only of lowercase Latin letters and asterisks (character '*'). The number of asterisks should be less than or equal to the number of letters.

## Examples
```input
6
aaab
zzzb
codeforces
atcoder
codeforces
tokitlx
aaaa
aaaaaa
abcd
abcd
c
f
```
```output
YES
*b
YES
*co*
NO
YES
a*a*a*a
YES
abcd
NO
```

## Note
In the first testcase, for a template "*b", you can replace the only asterisk with "aaa" to get "aaab" (which is equal to $$$a$$$) or with "zzz" to get "zzzb" (which is equal to $$$b$$$).

In the third testcase, a template "*o*" is not asterisk-minor, as it contains more asterisks than letters. There are no asterisk-minor templates that both $$$a$$$ and $$$b$$$ match.

In the fourth testcase, for a template "a*a*a*a", you can replace all asterisks with empty strings to get "aaaa" (which is equal to $$$a$$$) or two of them with "a" and two of them with an empty string to get "aaaaaa" (which is equal to $$$b$$$).

In the fifth testcase, there are no asterisks in a template "abcd", so only "abcd" can match it (which is coincidentally both $$$a$$$ and $$$b$$$).

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
A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).

You are given two integers $$$l$$$ and $$$r$$$. Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$. You have to print two numbers:

- the maximum possible size of a beautiful set where all elements are from $$$l$$$ to $$$r$$$;
- the number of beautiful sets consisting of integers from $$$l$$$ to $$$r$$$ with the maximum possible size.

Since the second number can be very large, print it modulo $$$998244353$$$.

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

Each test case consists of one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^6$$$).

## Output Format
For each test case, print two integers — the maximum possible size of a beautiful set consisting of integers from $$$l$$$ to $$$r$$$, and the number of such sets with maximum possible size. Since the second number can be very large, print it modulo $$$998244353$$$.

## Examples
```input
4
3 11
13 37
1 22
4 100
```
```output
2 4
2 6
5 1
5 7
```

## Note
In the first test case, the maximum possible size of a beautiful set with integers from $$$3$$$ to $$$11$$$ is $$$2$$$. There are $$$4$$$ such sets which have the maximum possible size:

- $$$\{ 3, 6 \}$$$;
- $$$\{ 3, 9 \}$$$;
- $$$\{ 4, 8 \}$$$;
- $$$\{ 5, 10 \}$$$.

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

# Problem
Let's call a triple of positive integers ($$$a, b, n$$$) strange if the equality $$$\frac{an}{nb} = \frac{a}{b}$$$ holds, where $$$an$$$ is the concatenation of $$$a$$$ and $$$n$$$ and $$$nb$$$ is the concatenation of $$$n$$$ and $$$b$$$. For the purpose of concatenation, the integers are considered without leading zeroes.

For example, if $$$a = 1$$$, $$$b = 5$$$ and $$$n = 9$$$, then the triple is strange, because $$$\frac{19}{95} = \frac{1}{5}$$$. But $$$a = 7$$$, $$$b = 3$$$ and $$$n = 11$$$ is not strange, because $$$\frac{711}{113} \ne \frac{7}{3}$$$.

You are given three integers $$$A$$$, $$$B$$$ and $$$N$$$. Calculate the number of strange triples $$$(a, b, n$$$), such that $$$1 \le a < A$$$, $$$1 \le b < B$$$ and $$$1 \le n < N$$$.

## Input Format
The only line contains three integers $$$A$$$, $$$B$$$ and $$$N$$$ ($$$1 \le A, B \le 10^5$$$; $$$1 \le N \le 10^9$$$).

## Output Format
Print one integer — the number of strange triples $$$(a, b, n$$$) such that $$$1 \le a < A$$$, $$$1 \le b < B$$$ and $$$1 \le n < N$$$.

## Examples
```input
5 6 10
```
```output
7
```
-----
```input
10 10 100
```
```output
29
```
-----
```input
1 10 25
```
```output
0
```
-----
```input
4242 6969 133333337
```
```output
19536
```
-----
```input
94841 47471 581818184
```
```output
98715
```

## Note
In the first example, there are $$$7$$$ strange triples: $$$(1, 1, 1$$$), ($$$1, 4, 6$$$), ($$$1, 5, 9$$$), ($$$2, 2, 2$$$), ($$$2, 5, 6$$$), ($$$3, 3, 3$$$) and ($$$4, 4, 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a garland consisting of $$$4$$$ colored light bulbs, the color of the $$$i$$$-th light bulb is $$$s_i$$$.

Initially, all the light bulbs are turned off. Your task is to turn all the light bulbs on. You can perform the following operation any number of times: select a light bulb and switch its state (turn it on if it was off, and turn it off if it was on). The only restriction on the above operation is that you can apply the operation to a light bulb only if the previous operation was applied to a light bulb of a different color (the first operation can be applied to any light bulb).

Calculate the minimum number of operations to turn all the light bulbs on, or report that this is impossible.

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

The single line of each test case contains $$$s$$$ — a sequence of $$$4$$$ characters, where each character is a decimal digit. The $$$i$$$-th character denotes the color of the $$$i$$$-th light bulb.

## Output Format
For each test case, print one integer — the minimum number of operations to turn all the light bulbs on. If it is impossible to turn all the bulbs on, print -1.

## Examples
```input
3
9546
0000
3313
```
```output
4
-1
6
```

## Note
In the first example, all the colors are different, so you can just turn all the bulbs on in $$$4$$$ operations.

In the second example, it is impossible to turn all the bulbs on, because after you switch one light bulb, it is impossible to turn the others on.

In the third example, you can proceed as follows: turn the first light bulb on, turn the third light bulb on, turn the fourth light bulb on, turn the third light bulb off, turn the second light bulb on, turn the third light bulb on.

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
For an array $$$a = [a_1, a_2, \dots, a_n]$$$, let's denote its subarray $$$a[l, r]$$$ as the array $$$[a_l, a_{l+1}, \dots, a_r]$$$.

For example, the array $$$a = [1, -3, 1]$$$ has $$$6$$$ non-empty subarrays:

- $$$a[1,1] = [1]$$$;
- $$$a[1,2] = [1,-3]$$$;
- $$$a[1,3] = [1,-3,1]$$$;
- $$$a[2,2] = [-3]$$$;
- $$$a[2,3] = [-3,1]$$$;
- $$$a[3,3] = [1]$$$.

You are given two integers $$$n$$$ and $$$k$$$. Construct an array $$$a$$$ consisting of $$$n$$$ integers such that:

- all elements of $$$a$$$ are from $$$-1000$$$ to $$$1000$$$;
- $$$a$$$ has exactly $$$k$$$ subarrays with positive sums;
- the rest $$$\dfrac{(n+1) \cdot n}{2}-k$$$ subarrays of $$$a$$$ have negative sums.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 30$$$; $$$0 \le k \le \dfrac{(n+1) \cdot n}{2}$$$).

## Output Format
For each test case, print $$$n$$$ integers — the elements of the array meeting the constraints. It can be shown that the answer always exists. If there are multiple answers, print any of them.

## Examples
```input
4
3 2
2 0
2 2
4 6
```
```output
1 -3 1
-13 -42
-13 42
-3 -4 10 -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 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 binary string $$$s$$$ consisting of only characters 0 and/or 1.

You can perform several operations on this string (possibly zero). There are two types of operations:

- choose two consecutive elements and swap them. In order to perform this operation, you pay $$$10^{12}$$$ coins;
- choose any element from the string and remove it. In order to perform this operation, you pay $$$10^{12}+1$$$ coins.

Your task is to calculate the minimum number of coins required to sort the string $$$s$$$ in non-decreasing order (i. e. transform $$$s$$$ so that $$$s_1 \le s_2 \le \dots \le s_m$$$, where $$$m$$$ is the length of the string after applying all operations). An empty string is also considered sorted in non-decreasing order.

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

The only line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting of only characters 0 and/or 1.

The sum of lengths of all given strings doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum number of coins required to sort the string $$$s$$$ in non-decreasing order.

## Examples
```input
6
100
0
0101
00101101
1001101
11111
```
```output
1000000000001
0
1000000000000
2000000000001
2000000000002
0
```

## Note
In the first example, you have to remove the $$$1$$$-st element, so the string becomes equal to 00.

In the second example, the string is already sorted.

In the third example, you have to swap the $$$2$$$-nd and the $$$3$$$-rd elements, so the string becomes equal to 0011.

In the fourth example, you have to swap the $$$3$$$-rd and the $$$4$$$-th elements, so the string becomes equal to 00011101, and then remove the $$$7$$$-th element, so the string becomes equal to 0001111.

In the fifth example, you have to remove the $$$1$$$-st element, so the string becomes equal to 001101, and then remove the $$$5$$$-th element, so the string becomes equal to 00111.

In the sixth example, the string is already sorted.

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
Consider a tournament with $$$n$$$ participants. The rating of the $$$i$$$-th participant is $$$a_i$$$.

The tournament will be organized as follows. First of all, organizers will assign each participant an index from $$$1$$$ to $$$n$$$. All indices will be unique. Let $$$p_i$$$ be the participant who gets the index $$$i$$$.

Then, $$$n-1$$$ games will be held. In the first game, participants $$$p_1$$$ and $$$p_2$$$ will play. In the second game, the winner of the first game will play against $$$p_3$$$. In the third game, the winner of the second game will play against $$$p_4$$$, and so on — in the last game, the winner of the $$$(n-2)$$$-th game will play against $$$p_n$$$.

Monocarp wants to predict the results of all $$$n-1$$$ games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings $$$x$$$ and $$$y$$$ play, and $$$|x - y| > k$$$, the participant with the higher rating wins. But if $$$|x - y| \le k$$$, any of the two participants may win.

Among all $$$n!$$$ ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all $$$n-1$$$ games. Since the answer can be large, print it modulo $$$998244353$$$.

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

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

## Output Format
Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all $$$n-1$$$ games.

## Examples
```input
4 3
7 12 17 21
```
```output
24
```
-----
```input
3 7
4 9 28
```
```output
4
```
-----
```input
4 1
1 2 3 4
```
```output
0
```
-----
```input
4 1
1 2 2 4
```
```output
12
```
-----
```input
16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100
```
```output
527461297
```

## Note
In the first example, a match with any pair of players can be predicted by Monocarp, so all $$$24$$$ ways to assign indices should be counted.

In the second example, suitable ways are $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2$$$] and $$$[3, 2, 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
After holding one team contest, boy Yura got very tired and wanted to change his life and move to Japan. In honor of such a change, Yura changed his name to something nice.

Fascinated by this idea he already thought up a name $$$s$$$ consisting only of characters "_" and "^". But there's a problem — Yura likes smiley faces "^_^" and "^^". Therefore any character of the name must be a part of at least one such smiley. Note that only the consecutive characters of the name can be a smiley face.

More formally, consider all occurrences of the strings "^_^" and "^^" in the string $$$s$$$. Then all such occurrences must cover the whole string $$$s$$$, possibly with intersections. For example, in the string "^^__^_^^__^" the characters at positions $$$3,4,9,10$$$ and $$$11$$$ are not contained inside any smileys, and the other characters at positions $$$1,2,5,6,7$$$ and $$$8$$$ are contained inside smileys.

In one operation Jura can insert one of the characters "_" and "^" into his name $$$s$$$ (you can insert it at any position in the string). He asks you to tell him the minimum number of operations you need to do to make the name fit Yura's criteria.

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

The first and only line of each test case contains a single string $$$s$$$ ($$$1 \leq |s| \leq 100$$$), consisting of characters "_" and "^",  — the name to change.

## Output Format
For each test case, output a single integer — the minimum number of characters you need to add to the name to make it fit for Yura. If you don't need to change anything in the name, print $$$0$$$.

## Examples
```input
7
^______^
___^_^^^_^___^
^_
^
^_^^^^^_^_^^
___^^
_
```
```output
5
5
1
1
0
3
2
```

## Note
In the first test case, you can get the following name by adding $$$5$$$ characters:

^_^_^_^_^_^_^

In the third test case, we can add one character "^" to the end of the name, then we get the name:

^_^

In the fourth test case, we can add one character "^" to the end of the name, then we get the name:

^^

In the fifth test case, all of the characters are already contained in smiley faces, so the answer is $$$0$$$.

In the seventh test case, you can add one character "^" at the beginning of the name and one character "^" at the end of the name, then you get the name:

^_^

Now solve the problem and return the code.