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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integer arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can reverse at most one subarray (continuous subsegment) of the array $$$a$$$.

Your task is to reverse such a subarray that the sum $$$\sum\limits_{i=1}^n a_i \cdot b_i$$$ is maximized.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^7$$$).

## Output Format
Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of $$$a$$$.

## Examples
```input
5
2 3 2 1 3
1 3 2 4 2
```
```output
29
```
-----
```input
2
13 37
2 4
```
```output
174
```
-----
```input
6
1 8 7 6 3 6
5 9 6 8 8 6
```
```output
235
```

## Note
In the first example, you can reverse the subarray $$$[4, 5]$$$. Then $$$a = [2, 3, 2, 3, 1]$$$ and $$$2 \cdot 1 + 3 \cdot 3 + 2 \cdot 2 + 3 \cdot 4 + 1 \cdot 2 = 29$$$.

In the second example, you don't need to use the reverse operation. $$$13 \cdot 2 + 37 \cdot 4 = 174$$$.

In the third example, you can reverse the subarray $$$[3, 5]$$$. Then $$$a = [1, 8, 3, 6, 7, 6]$$$ and $$$1 \cdot 5 + 8 \cdot 9 + 3 \cdot 6 + 6 \cdot 8 + 7 \cdot 8 + 6 \cdot 6 = 235$$$.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
One day little Vasya found mom's pocket book. The book had n names of her friends and unusually enough, each name was exactly m letters long. Let's number the names from 1 to n in the order in which they are written.

As mom wasn't home, Vasya decided to play with names: he chose three integers i, j, k (1 ≤ i < j ≤ n, 1 ≤ k ≤ m), then he took names number i and j and swapped their prefixes of length k. For example, if we take names "CBDAD" and "AABRD" and swap their prefixes with the length of 3, the result will be names "AABAD" and "CBDRD".

You wonder how many different names Vasya can write instead of name number 1, if Vasya is allowed to perform any number of the described actions. As Vasya performs each action, he chooses numbers i, j, k independently from the previous moves and his choice is based entirely on his will. The sought number can be very large, so you should only find it modulo 1000000007 (109 + 7).

## Input Format
The first input line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of names and the length of each name, correspondingly. Then n lines contain names, each name consists of exactly m uppercase Latin letters.

## Output Format
Print the single number — the number of different names that could end up in position number 1 in the pocket book after the applying the procedures described above. Print the number modulo 1000000007 (109 + 7).

## Examples
```input
2 3
AAB
BAA
```
```output
4
```
-----
```input
4 5
ABABA
BCGDG
AAAAA
YABSA
```
```output
216
```

## Note
In the first sample Vasya can get the following names in the position number 1: "AAB", "AAA", "BAA" and "BAB".

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
One day Vasya got hold of a sheet of checkered paper n × m squares in size. Our Vasya adores geometrical figures, so he painted two rectangles on the paper. The rectangles' sides are parallel to the coordinates' axes, also the length of each side of each rectangle is no less than 3 squares and the sides are painted by the grid lines. The sides can also be part of the sheet of paper's edge. Then Vasya hatched all squares on the rectangles' frames.

Let's define a rectangle's frame as the set of squares inside the rectangle that share at least one side with its border.

A little later Vasya found a sheet of paper of exactly the same size and couldn't guess whether it is the same sheet of paper or a different one. So, he asked you to check whether the sheet of paper he had found contains two painted frames and nothing besides them.

Please note that the frames painted by Vasya can arbitrarily intersect, overlap or even completely coincide.

The coordinates on the sheet of paper are introduced in such a way that the X axis goes from top to bottom, the x coordinates of the squares' numbers take values from 1 to n and the Y axis goes from the left to the right and the y coordinates of the squares' numbers take values from 1 to m.

## Input Format
The first input line contains two integers n and m (3 ≤ n, m ≤ 1000) — the sizes of the sheet of paper Vasya found. Next n lines, each consisting of m symbols "." (dot) and "#" (number sign), describe the found sheet of paper. The symbol "#" represents a hatched square and the symbol "." represents a non-hatched square.

## Output Format
In the first line print the single word "YES" or "NO", meaning whether it is true that the found sheet of paper has two frames painted on it. If the answer is positive, then print in the second line 4 integers: the coordinates of the upper left and lower right corners of the first frame. In the third line print 4 integers: the coordinates of the upper left and the lower right corners of the second frame. If there are multiple answers, print any of them.

## Examples
```input
4 5
#####
#.#.#
###.#
#####
```
```output
YES
1 1 3 3
1 1 4 5
```
-----
```input
5 6
...###
...###
#####.
#...#.
#####.
```
```output
NO
```

## Note
In the first sample there are two frames on the picture. The first one is:

The second one is:

In the second sample the painted figures are not frames. Note that the height and width of valid frames is no less than 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 python3.

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:
```python
<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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A string $$$s$$$ of length $$$n$$$, consisting of lowercase letters of the English alphabet, is given.

You must choose some number $$$k$$$ between $$$0$$$ and $$$n$$$. Then, you select $$$k$$$ characters of $$$s$$$ and permute them however you want. In this process, the positions of the other $$$n-k$$$ characters remain unchanged. You have to perform this operation exactly once.

For example, if $$$s=\texttt{"andrea"}$$$, you can choose the $$$k=4$$$ characters $$$\texttt{"a_d_ea"}$$$ and permute them into $$$\texttt{"d_e_aa"}$$$ so that after the operation the string becomes $$$\texttt{"dneraa"}$$$.

Determine the minimum $$$k$$$ so that it is possible to sort $$$s$$$ alphabetically (that is, after the operation its characters appear in alphabetical order).

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

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

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

## Output Format
For each test case, output the minimum $$$k$$$ that allows you to obtain a string sorted alphabetically, through the operation described above.

## Examples
```input
4
3
lol
10
codeforces
5
aaaaa
4
dcba
```
```output
2
6
0
4
```

## Note
In the first test case, we can choose the $$$k=2$$$ characters $$$\texttt{"_ol"}$$$ and rearrange them as $$$\texttt{"_lo"}$$$ (so the resulting string is $$$\texttt{"llo"}$$$). It is not possible to sort the string choosing strictly less than $$$2$$$ characters.

In the second test case, one possible way to sort $$$s$$$ is to consider the $$$k=6$$$ characters $$$\texttt{"_o__force_"}$$$ and rearrange them as $$$\texttt{"_c__efoor_"}$$$ (so the resulting string is $$$\texttt{"ccdeefoors"}$$$). One can show that it is not possible to sort the string choosing strictly less than $$$6$$$ characters.

In the third test case, string $$$s$$$ is already sorted (so we can choose $$$k=0$$$ characters).

In the fourth test case, we can choose all $$$k=4$$$ characters $$$\texttt{"dcba"}$$$ and reverse the whole string (so the resulting string is $$$\texttt{"abcd"}$$$).

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
On a circle lie $$$2n$$$ distinct points, with the following property: however you choose $$$3$$$ chords that connect $$$3$$$ disjoint pairs of points, no point strictly inside the circle belongs to all $$$3$$$ chords. The points are numbered $$$1, \, 2, \, \dots, \, 2n$$$ in clockwise order.

Initially, $$$k$$$ chords connect $$$k$$$ pairs of points, in such a way that all the $$$2k$$$ endpoints of these chords are distinct.

You want to draw $$$n - k$$$ additional chords that connect the remaining $$$2(n - k)$$$ points (each point must be an endpoint of exactly one chord).

In the end, let $$$x$$$ be the total number of intersections among all $$$n$$$ chords. Compute the maximum value that $$$x$$$ can attain if you choose the $$$n - k$$$ chords optimally.

Note that the exact position of the $$$2n$$$ points is not relevant, as long as the property stated in the first paragraph holds.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le n$$$) — half the number of points and the number of chords initially drawn.

Then $$$k$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, \, y_i \le 2n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th chord. It is guaranteed that the $$$2k$$$ numbers $$$x_1, \, y_1, \, x_2, \, y_2, \, \dots, \, x_k, \, y_k$$$ are all distinct.

## Output Format
For each test case, output the maximum number of intersections that can be obtained by drawing $$$n - k$$$ additional chords.

## Examples
```input
4
4 2
8 2
1 5
1 1
2 1
2 0
10 6
14 6
2 20
9 10
13 18
15 12
11 7
```
```output
4
0
1
14
```

## Note
In the first test case, there are three ways to draw the $$$2$$$ additional chords, shown below (black chords are the ones initially drawn, while red chords are the new ones):

We see that the third way gives the maximum number of intersections, namely $$$4$$$.

In the second test case, there are no more chords to draw. Of course, with only one chord present there are no intersections.

In the third test case, we can make at most one intersection by drawing chords $$$1-3$$$ and $$$2-4$$$, as shown below:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a sequence of $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$.

Does there exist a sequence of $$$n$$$ integers $$$b_1, \, b_2, \, \dots, \, b_n$$$ such that the following property holds?

- For each $$$1 \le i \le n$$$, there exist two (not necessarily distinct) indices $$$j$$$ and $$$k$$$ ($$$1 \le j, \, k \le n$$$) such that $$$a_i = b_j - b_k$$$.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10$$$).

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

## Output Format
For each test case, output a line containing YES if a sequence $$$b_1, \, \dots, \, b_n$$$ satisfying the required property exists, and NO otherwise.

## Examples
```input
5
5
4 -7 -1 5 10
1
0
3
1 10 100
4
-3 2 10 2
9
25 -171 250 174 152 242 100 -205 -258
```
```output
YES
YES
NO
YES
YES
```

## Note
In the first test case, the sequence $$$b = [-9, \, 2, \, 1, \, 3, \, -2]$$$ satisfies the property. Indeed, the following holds:

- $$$a_1 = 4 = 2 - (-2) = b_2 - b_5$$$;
- $$$a_2 = -7 = -9 - (-2) = b_1 - b_5$$$;
- $$$a_3 = -1 = 1 - 2 = b_3 - b_2$$$;
- $$$a_4 = 5 = 3 - (-2) = b_4 - b_5$$$;
- $$$a_5 = 10 = 1 - (-9) = b_3 - b_1$$$.

In the second test case, it is sufficient to choose $$$b = [0]$$$, since $$$a_1 = 0 = 0 - 0 = b_1 - b_1$$$.

In the third test case, it is possible to show that no sequence $$$b$$$ of length $$$3$$$ satisfies the property.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The numbers $$$1, \, 2, \, \dots, \, n \cdot k$$$ are colored with $$$n$$$ colors. These colors are indexed by $$$1, \, 2, \, \dots, \, n$$$. For each $$$1 \le i \le n$$$, there are exactly $$$k$$$ numbers colored with color $$$i$$$.

Let $$$[a, \, b]$$$ denote the interval of integers between $$$a$$$ and $$$b$$$ inclusive, that is, the set $$$\{a, \, a + 1, \, \dots, \, b\}$$$. You must choose $$$n$$$ intervals $$$[a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]$$$ such that:

- for each $$$1 \le i \le n$$$, it holds $$$1 \le a_i < b_i \le n \cdot k$$$;
- for each $$$1 \le i \le n$$$, the numbers $$$a_i$$$ and $$$b_i$$$ are colored with color $$$i$$$;
- each number $$$1 \le x \le n \cdot k$$$ belongs to at most $$$\left\lceil \frac{n}{k - 1} \right\rceil$$$ intervals.

One can show that such a family of intervals always exists under the given constraints.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) — the number of colors and the number of occurrences of each color.

The second line contains $$$n \cdot k$$$ integers $$$c_1, \, c_2, \, \dots, \, c_{nk}$$$ ($$$1 \le c_j \le n$$$), where $$$c_j$$$ is the color of number $$$j$$$. It is guaranteed that, for each $$$1 \le i \le n$$$, it holds $$$c_j = i$$$ for exactly $$$k$$$ distinct indices $$$j$$$.

## Output Format
Output $$$n$$$ lines. The $$$i$$$-th line should contain the two integers $$$a_i$$$ and $$$b_i$$$.

If there are multiple valid choices of the intervals, output any.

## Examples
```input
4 3
2 4 3 1 1 4 2 3 2 1 3 4
```
```output
4 5
1 7
8 11
6 12
```
-----
```input
1 2
1 1
```
```output
1 2
```
-----
```input
3 3
3 1 2 3 2 1 2 1 3
```
```output
6 8
3 7
1 4
```
-----
```input
2 3
2 1 1 1 2 2
```
```output
2 3
5 6
```

## Note
In the first sample, each number can be contained in at most $$$\left\lceil \frac{4}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:

In the second sample, the only interval to be chosen is forced to be $$$[1, \, 2]$$$, and each number is indeed contained in at most $$$\left\lceil \frac{1}{2 - 1} \right\rceil = 1$$$ interval.

In the third sample, each number can be contained in at most $$$\left\lceil \frac{3}{3 - 1} \right\rceil = 2$$$ intervals. The output is described by the following picture:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are the organizer of the famous "Zurich Music Festival". There will be $$$n$$$ singers who will perform at the festival, identified by the integers $$$1$$$, $$$2$$$, $$$\dots$$$, $$$n$$$. You must choose in which order they are going to perform on stage.

You have $$$m$$$ friends and each of them has a set of favourite singers. More precisely, for each $$$1\le i\le m$$$, the $$$i$$$-th friend likes singers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$.

A friend of yours is happy if the singers he likes perform consecutively (in an arbitrary order). An ordering of the singers is valid if it makes all your friends happy.

Compute the number of valid orderings modulo $$$998\,244\,353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,\,m\le 100$$$) — the number of singers and the number of friends correspondingly.

The $$$i$$$-th of the next $$$m$$$ lines contains the integer $$$q_i$$$ ($$$1\le q_i\le n$$$) — the number of favorite singers of the $$$i$$$-th friend – followed by the $$$q_i$$$ integers $$$s_{i,1}, \, s_{i, 2}, \, \dots, \,s_{i, q_i}$$$ ($$$1\le s_{i,1}<s_{i,2}<\cdots<s_{i,q_i}\le n$$$) — the indexes of his favorite singers.

## Output Format
Print the number of valid orderings of the singers modulo $$$998\,244\,353$$$.

## Examples
```input
3 1
2 1 3
```
```output
4
```
-----
```input
5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5
```
```output
0
```
-----
```input
100 1
1 50
```
```output
35305197
```
-----
```input
5 1
5 1 2 3 4 5
```
```output
120
```
-----
```input
2 5
1 2
1 2
1 2
1 1
1 1
```
```output
2
```
-----
```input
11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11
```
```output
384
```

## Note
Explanation of the first sample: There are $$$3$$$ singers and only $$$1$$$ friend. The friend likes the two singers $$$1$$$ and $$$3$$$. Thus, the $$$4$$$ valid orderings are:

- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2

Explanation of the second sample: There are $$$5$$$ singers and $$$5$$$ friends. One can show that no ordering is valid.

Explanation of the third sample: There are $$$100$$$ singers and only $$$1$$$ friend. The friend likes only singer $$$50$$$, hence all the $$$100!$$$ possible orderings are valid.

Explanation of the fourth sample: There are $$$5$$$ singers and only $$$1$$$ friend. The friend likes all the singers, hence all the $$$5!=120$$$ possible orderings are valid.

Now solve the problem and return the code.