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

# Problem
Today is Mashtali's birthday! He received a Hagh tree from Haj Davood as his birthday present!

A directed tree is called a Hagh tree iff:

- The length of the longest directed path in it is exactly $$$n$$$.
- Every vertex has at most three edges attached to it independent of their orientation.
- Let's call vertices $$$u$$$ and $$$v$$$ friends if one of them has a directed path to the other. For every pair of vertices $$$u$$$ and $$$v$$$ that are not friends, there should exist a vertex $$$w$$$ that is friends with both $$$u$$$ and $$$v$$$ (a mutual friend).

After opening his gift, Mashtali found out that the labels on the vertices were gone.

Immediately, he asked himself: how many different unlabeled Hagh trees are there? That is, how many possible trees could he have received as his birthday present?

At the first glance, the number of such trees seemed to be infinite since there was no limit on the number of vertices; but then he solved the problem and proved that there's a finite number of unlabeled Hagh trees!

Amazed by this fact, he shared the task with you so that you could enjoy solving it as well. Since the answer can be rather large he asked you to find the number of different unlabeled Hagh trees modulo $$$998244353$$$.

Here two trees are considered different, if they are not isomorphic: if there is no way to map nodes of one tree to the second tree, so that edges are mapped to edges preserving the orientation.

Some examples for $$$n = 2$$$:

Directed trees $$$D$$$ and $$$E$$$ are Hagh. $$$C$$$ is not Hagh because it has a vertex with $$$4$$$ edges attached to it. $$$A$$$ and $$$B$$$ are not Hagh because their longest directed paths are not equal to $$$n$$$. Also in $$$B$$$ the leftmost and rightmost vertices are not friends neither do they have a mutual friend.

## Input Format
The first line of input contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$.

## Output Format
Print a single integer, the answer to Mashtali's task modulo $$$998244353$$$.

## Examples
```input
1
```
```output
5
```
-----
```input
2
```
```output
31
```
-----
```input
344031
```
```output
272040628
```

## Note
All the five Hagh trees for $$$n = 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Four players participate in the playoff tournament. The tournament is held according to the following scheme: the first player will play with the second, and the third player with the fourth, then the winners of the pairs will play in the finals of the tournament.

It is known that in a match between two players, the one whose skill is greater will win. The skill of the $$$i$$$-th player is equal to $$$s_i$$$ and all skill levels are pairwise different (i. e. there are no two identical values in the array $$$s$$$).

The tournament is called fair if the two players with the highest skills meet in the finals.

Determine whether the given tournament is fair.

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

A single line of test case contains four integers $$$s_1, s_2, s_3, s_4$$$ ($$$1 \le s_i \le 100$$$) — skill of the players. It is guaranteed that all the numbers in the array are different.

## Output Format
For each testcase, output YES if the tournament is fair, or NO otherwise.

## Examples
```input
4
3 7 9 5
4 5 6 9
5 3 8 1
6 5 3 2
```
```output
YES
NO
YES
NO
```

## Note
Consider the example:

1. in the first test case, players $$$2$$$ and $$$3$$$ with skills $$$7$$$ and $$$9$$$ advance to the finals;
2. in the second test case, players $$$2$$$ and $$$4$$$ with skills $$$5$$$ and $$$9$$$ advance to the finals. The player with skill $$$6$$$ does not advance, but the player with skill $$$5$$$ advances to the finals, so the tournament is not fair;
3. in the third test case, players $$$1$$$ and $$$3$$$ with skills $$$5$$$ and $$$8$$$ advance to the finals;
4. in the fourth test case, players $$$1$$$ and $$$3$$$ with skills $$$6$$$ and $$$3$$$ advance to the finals. The player with skill $$$5$$$ does not advance, but the player with skill $$$3$$$ advances to the finals, so the tournament is not fair.

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 $$$a$$$ consisting of $$$n$$$ integers.

Let's call a pair of indices $$$i$$$, $$$j$$$ good if $$$1 \le i < j \le n$$$ and $$$\gcd(a_i, 2a_j) > 1$$$ (where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$).

Find the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.

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

The first line of the test case contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of elements in the array.

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

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

## Output Format
For each test case, output a single integer — the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.

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

## Note
In the first example, the array elements can be rearranged as follows: $$$[6, 3, 5, 3]$$$.

In the third example, the array elements can be rearranged as follows: $$$[4, 4, 2, 1, 1]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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$$$ consisting of the characters 0, 1, and ?.

Let's call a string unstable if it consists of the characters 0 and 1 and any two adjacent characters are different (i. e. it has the form 010101... or 101010...).

Let's call a string beautiful if it consists of the characters 0, 1, and ?, and you can replace the characters ? to 0 or 1 (for each character, the choice is independent), so that the string becomes unstable.

For example, the strings 0??10, 0, and ??? are beautiful, and the strings 00 and ?1??1 are not.

Calculate the number of beautiful contiguous substrings of the string $$$s$$$.

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

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

It is guaranteed that the sum of the string lengths over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of beautiful substrings of the string $$$s$$$.

## Examples
```input
3
0?10
???
?10??1100
```
```output
8
6
25
```

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
$$$2^k$$$ teams participate in a playoff tournament. The tournament consists of $$$2^k - 1$$$ games. They are held as follows: first of all, the teams are split into pairs: team $$$1$$$ plays against team $$$2$$$, team $$$3$$$ plays against team $$$4$$$ (exactly in this order), and so on (so, $$$2^{k-1}$$$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $$$2^{k-1}$$$ teams remain. If only one team remains, it is declared the champion; otherwise, $$$2^{k-2}$$$ games are played: in the first one of them, the winner of the game "$$$1$$$ vs $$$2$$$" plays against the winner of the game "$$$3$$$ vs $$$4$$$", then the winner of the game "$$$5$$$ vs $$$6$$$" plays against the winner of the game "$$$7$$$ vs $$$8$$$", and so on. This process repeats until only one team remains.

For example, this picture describes the chronological order of games with $$$k = 3$$$:

Let the string $$$s$$$ consisting of $$$2^k - 1$$$ characters describe the results of the games in chronological order as follows:

- if $$$s_i$$$ is 0, then the team with lower index wins the $$$i$$$-th game;
- if $$$s_i$$$ is 1, then the team with greater index wins the $$$i$$$-th game;
- if $$$s_i$$$ is ?, then the result of the $$$i$$$-th game is unknown (any team could win this game).

Let $$$f(s)$$$ be the number of possible winners of the tournament described by the string $$$s$$$. A team $$$i$$$ is a possible winner of the tournament if it is possible to replace every ? with either 1 or 0 in such a way that team $$$i$$$ is the champion.

You are given the initial state of the string $$$s$$$. You have to process $$$q$$$ queries of the following form:

- $$$p$$$ $$$c$$$ — replace $$$s_p$$$ with character $$$c$$$, and print $$$f(s)$$$ as the result of the query.

## Input Format
The first line contains one integer $$$k$$$ ($$$1 \le k \le 18$$$).

The second line contains a string consisting of $$$2^k - 1$$$ characters — the initial state of the string $$$s$$$. Each character is either ?, 0, or 1.

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, the $$$i$$$-th line contains an integer $$$p$$$ and a character $$$c$$$ ($$$1 \le p \le 2^k - 1$$$; $$$c$$$ is either ?, 0, or 1), describing the $$$i$$$-th query.

## Output Format
For each query, print one integer — $$$f(s)$$$.

## Examples
```input
3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1
```
```output
1
2
3
3
5
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: 1024.0 MB

# Problem
Suppose you are given two strings $$$a$$$ and $$$b$$$. You can apply the following operation any number of times: choose any contiguous substring of $$$a$$$ or $$$b$$$, and sort the characters in it in non-descending order. Let $$$f(a, b)$$$ the minimum number of operations you have to apply in order to make them equal (or $$$f(a, b) = 1337$$$ if it is impossible to make $$$a$$$ and $$$b$$$ equal using these operations).

For example:

- $$$f(\text{ab}, \text{ab}) = 0$$$;
- $$$f(\text{ba}, \text{ab}) = 1$$$ (in one operation, we can sort the whole first string);
- $$$f(\text{ebcda}, \text{ecdba}) = 1$$$ (in one operation, we can sort the substring of the second string starting from the $$$2$$$-nd character and ending with the $$$4$$$-th character);
- $$$f(\text{a}, \text{b}) = 1337$$$.

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_k$$$ having equal length. Calculate $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of strings.

Then $$$n$$$ lines follow, each line contains one of the strings $$$s_i$$$, consisting of lowercase Latin letters. $$$|s_1| = |s_2| = \ldots = |s_n|$$$, and $$$n \cdot |s_1| \le 2 \cdot 10^5$$$. All these strings are pairwise distinct.

## Output Format
Print one integer: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

## Examples
```input
4
zzz
bac
abc
acb
```
```output
4015
```
-----
```input
2
a
b
```
```output
1337
```

Now solve the problem and return the code.