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

# Problem
An array $$$a$$$ is called ugly if it contains at least one element which is equal to the sum of all elements before it. If the array is not ugly, it is beautiful.

For example:

- the array $$$[6, 3, 9, 6]$$$ is ugly: the element $$$9$$$ is equal to $$$6 + 3$$$;
- the array $$$[5, 5, 7]$$$ is ugly: the element $$$5$$$ (the second one) is equal to $$$5$$$;
- the array $$$[8, 4, 10, 14]$$$ is beautiful: $$$8 \ne 0$$$, $$$4 \ne 8$$$, $$$10 \ne 8 + 4$$$, $$$14 \ne 8 + 4 + 10$$$, so there is no element which is equal to the sum of all elements before it.

You are given an array $$$a$$$ such that $$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$. You have to reorder the elements of $$$a$$$ in such a way that the resulting array is beautiful. Note that you are not allowed to insert new elements or erase existing ones, you can only change the order of elements of $$$a$$$. You are allowed to keep the array $$$a$$$ unchanged, if it is beautiful.

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 100$$$).

## Output Format
For each test case, print the answer as follows:

- if it is impossible to reorder the elements of $$$a$$$ in such a way that it becomes beautiful, print NO;
- otherwise, in the first line, print YES. In the second line, print $$$n$$$ integers — any beautiful array which can be obtained from $$$a$$$ by reordering its elements. If there are multiple such arrays, print any of them.

## Examples
```input
4
4
3 3 6 6
2
10 10
5
1 2 3 4 5
3
1 4 4
```
```output
YES
3 6 3 6
NO
YES
2 4 1 5 3
YES
1 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 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: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers.

You have to perform the sequence of $$$n-2$$$ operations on this array:

- during the first operation, you either add $$$a_2$$$ to $$$a_1$$$ and subtract $$$a_2$$$ from $$$a_3$$$, or add $$$a_2$$$ to $$$a_3$$$ and subtract $$$a_2$$$ from $$$a_1$$$;
- during the second operation, you either add $$$a_3$$$ to $$$a_2$$$ and subtract $$$a_3$$$ from $$$a_4$$$, or add $$$a_3$$$ to $$$a_4$$$ and subtract $$$a_3$$$ from $$$a_2$$$;
- ...
- during the last operation, you either add $$$a_{n-1}$$$ to $$$a_{n-2}$$$ and subtract $$$a_{n-1}$$$ from $$$a_n$$$, or add $$$a_{n-1}$$$ to $$$a_n$$$ and subtract $$$a_{n-1}$$$ from $$$a_{n-2}$$$.

So, during the $$$i$$$-th operation, you add the value of $$$a_{i+1}$$$ to one of its neighbors, and subtract it from the other neighbor.

For example, if you have the array $$$[1, 2, 3, 4, 5]$$$, one of the possible sequences of operations is:

- subtract $$$2$$$ from $$$a_3$$$ and add it to $$$a_1$$$, so the array becomes $$$[3, 2, 1, 4, 5]$$$;
- subtract $$$1$$$ from $$$a_2$$$ and add it to $$$a_4$$$, so the array becomes $$$[3, 1, 1, 5, 5]$$$;
- subtract $$$5$$$ from $$$a_3$$$ and add it to $$$a_5$$$, so the array becomes $$$[3, 1, -4, 5, 10]$$$.

So, the resulting array is $$$[3, 1, -4, 5, 10]$$$.

An array is reachable if it can be obtained by performing the aforementioned sequence of operations on $$$a$$$. You have to calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).

## Output Format
Print one integer — the number of reachable arrays. Since the answer can be very large, print its remainder modulo $$$998244353$$$.

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

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

# Problem
You are given two permutations $$$a$$$ and $$$b$$$, both of size $$$n$$$. A permutation of size $$$n$$$ is an array of $$$n$$$ elements, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. The elements in each permutation are indexed from $$$1$$$ to $$$n$$$.

You can perform the following operation any number of times:

- choose an integer $$$i$$$ from $$$1$$$ to $$$n$$$;
- let $$$x$$$ be the integer such that $$$a_x = i$$$. Swap $$$a_i$$$ with $$$a_x$$$;
- let $$$y$$$ be the integer such that $$$b_y = i$$$. Swap $$$b_i$$$ with $$$b_y$$$.

Your goal is to make both permutations sorted in ascending order (i. e. the conditions $$$a_1 < a_2 < \dots < a_n$$$ and $$$b_1 < b_2 < \dots < b_n$$$ must be satisfied) using minimum number of operations. Note that both permutations must be sorted after you perform the sequence of operations you have chosen.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$; all $$$a_i$$$ are distinct).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$; all $$$b_i$$$ are distinct).

## Output Format
First, print one integer $$$k$$$ ($$$0 \le k \le 2n$$$) — the minimum number of operations required to sort both permutations. Note that it can be shown that $$$2n$$$ operations are always enough.

Then, print $$$k$$$ integers $$$op_1, op_2, \dots, op_k$$$ ($$$1 \le op_j \le n$$$), where $$$op_j$$$ is the value of $$$i$$$ you choose during the $$$j$$$-th operation.

If there are multiple answers, print any of them.

## Examples
```input
5
1 3 2 4 5
2 1 3 4 5
```
```output
1
2
```
-----
```input
2
1 2
1 2
```
```output
0
```
-----
```input
4
1 3 4 2
4 3 2 1
```
```output
2
3 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 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: 6.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree of $$$n$$$ vertices and $$$n - 1$$$ edges. The $$$i$$$-th vertex has an initial weight $$$a_i$$$.

Let the distance $$$d_v(u)$$$ from vertex $$$v$$$ to vertex $$$u$$$ be the number of edges on the path from $$$v$$$ to $$$u$$$. Note that $$$d_v(u) = d_u(v)$$$ and $$$d_v(v) = 0$$$.

Let the weighted distance $$$w_v(u)$$$ from $$$v$$$ to $$$u$$$ be $$$w_v(u) = d_v(u) + a_u$$$. Note that $$$w_v(v) = a_v$$$ and $$$w_v(u) \neq w_u(v)$$$ if $$$a_u \neq a_v$$$.

Analogically to usual distance, let's define the eccentricity $$$e(v)$$$ of vertex $$$v$$$ as the greatest weighted distance from $$$v$$$ to any other vertex (including $$$v$$$ itself), or $$$e(v) = \max\limits_{1 \le u \le n}{w_v(u)}$$$.

Finally, let's define the radius $$$r$$$ of the tree as the minimum eccentricity of any vertex, or $$$r = \min\limits_{1 \le v \le n}{e(v)}$$$.

You need to perform $$$m$$$ queries of the following form:

- $$$v_j$$$ $$$x_j$$$ — assign $$$a_{v_j} = x_j$$$.

After performing each query, print the radius $$$r$$$ of the current tree.

## Input Format
The first line contains the single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the initial weights of vertices.

Next $$$n - 1$$$ lines contain edges of tree. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — the corresponding edge. The given edges form a tree.

The next line contains the single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of queries.

Next $$$m$$$ lines contain queries — one query per line. The $$$j$$$-th query contains two integers $$$v_j$$$ and $$$x_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le x_j \le 10^6$$$) — a vertex and it's new weight.

## Output Format
Print $$$m$$$ integers — the radius $$$r$$$ of the tree after performing each query.

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

## Note
After the first query, you have the following tree:

The tree after the second query:

After the third query, the radius $$$r = e(2) = 5$$$:

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
You were walking down the street and heard a sound. The sound was described by the string $$$s$$$ consisting of lowercase and uppercase Latin characters. Now you want to find out if the sound was a cat meowing.

For the sound to be a meowing, the string can only contain the letters 'm', 'e', 'o' and 'w', in either uppercase or lowercase. Also:

- string must start with non-empty sequence consisting only of characters 'm' or 'M'
- it must be immediately followed by non-empty sequence consisting only of characters 'e' or 'E'
- it must be immediately followed by non-empty sequence consisting only of characters 'o' or 'O'
- it must be immediately followed by non-empty sequence consisting only of characters 'w' or 'W', this sequence ends the string, after it immediately comes the string end

For example, strings "meow", "mmmEeOWww", "MeOooOw" describe a meowing, but strings "Mweo", "MeO", "moew", "MmEW", "meowmeow" do not.

Determine whether the sound you heard was a cat meowing or something else.

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

The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 50$$$) — the length of the string describing the sound.

The second line of each test case contains a string $$$s$$$ of $$$n$$$ characters. The string describes the sound you heard and consists only of lowercase and uppercase Latin letters.

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

- YES if the sound was a cat meowing;
- NO otherwise.

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

## Examples
```input
7
4
meOw
14
mMmeoOoWWWwwwW
3
mew
7
MmeEeUw
4
MEOW
6
MmyaVW
5
meowA
```
```output
YES
YES
NO
NO
YES
NO
NO
```

## Note
In the first test case, the string consists of a sequence of characters 'm', 'e', 'O', 'w', which satisfies the definition of meowing.

In the second test case, the string consists of a sequence of $$$3$$$ characters 'm' and 'M', one 'e', a sequence of $$$3$$$ characters 'o' and 'O' and a sequence of $$$7$$$ characters 'w' and 'W', which satisfies the definition of meowing.

In the third test case, the string does not describe a meowing because it lacks a sequence of 'o' or 'O' characters between 'e' and 'w'.

In the fourth test case, the string contains the character 'U', so it does not describe a meowing.

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
This is an easy version of the problem. It differs from the hard one only by constraints on $$$n$$$ and $$$t$$$.

There is a deck of $$$n$$$ cards, each of which is characterized by its power. There are two types of cards:

- a hero card, the power of such a card is always equal to $$$0$$$;
- a bonus card, the power of such a card is always positive.

You can do the following with the deck:

- take a card from the top of the deck;
- if this card is a bonus card, you can put it on top of your bonus deck or discard;
- if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of cards in the deck.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — card powers in top-down order.

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

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

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

## Note
In the first sample, you can take bonuses $$$1$$$ and $$$2$$$. Both hero cards will receive $$$3$$$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $$$2$$$ and $$$3$$$ bonuses and get $$$6$$$ total power.

In the fourth sample, you can take bonuses $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ and skip the bonus $$$6$$$, then the hero $$$4$$$ will be enhanced with a bonus $$$3$$$ by $$$5$$$, and the hero $$$7$$$ with a bonus $$$5$$$ by $$$4$$$. $$$4+5=9$$$.

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
This is a hard version of the problem. It differs from the easy one only by constraints on $$$n$$$ and $$$t$$$.

There is a deck of $$$n$$$ cards, each of which is characterized by its power. There are two types of cards:

- a hero card, the power of such a card is always equal to $$$0$$$;
- a bonus card, the power of such a card is always positive.

You can do the following with the deck:

- take a card from the top of the deck;
- if this card is a bonus card, you can put it on top of your bonus deck or discard;
- if this card is a hero card, then the power of the top card from your bonus deck is added to his power (if it is not empty), after that the hero is added to your army, and the used bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of cards in the deck.

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) — card powers in top-down order.

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

## Output Format
Output $$$t$$$ numbers, each of which is the answer to the corresponding test case — the maximum possible total power of the army that can be achieved.

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

## Note
In the first sample, you can take bonuses $$$1$$$ and $$$2$$$. Both hero cards will receive $$$3$$$ power. If you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest can be powered up with $$$2$$$ and $$$3$$$ bonuses and get $$$6$$$ total power.

In the fourth sample, you can take bonuses $$$1$$$, $$$2$$$, $$$3$$$, $$$5$$$ and skip the bonus $$$6$$$, then the hero $$$4$$$ will be enhanced with a bonus $$$3$$$ by $$$5$$$, and the hero $$$7$$$ with a bonus $$$5$$$ by $$$4$$$. $$$4+5=9$$$.

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
Dmitry has a string $$$s$$$, consisting of lowercase Latin letters.

Dmitry decided to remove two consecutive characters from the string $$$s$$$ and you are wondering how many different strings can be obtained after such an operation.

For example, Dmitry has a string "aaabcc". You can get the following different strings: "abcc"(by deleting the first two or second and third characters), "aacc"(by deleting the third and fourth characters),"aaac"(by deleting the fourth and the fifth character) and "aaab" (by deleting the last two).

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

The descriptions of the test cases follow.

The first line of the description of each test case contains an integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

The second line of the description of each test case contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters.

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

## Output Format
For each test case print one integer — the number of distinct strings that can be obtained by removing two consecutive letters.

## Examples
```input
7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa
```
```output
4
1
5
3
3
3
1
```

## Note
The first example is explained in the statement.

In the third example, the following strings are obtained: "cdef", "adef", "abef", "abcf", "abcd".

In the seventh example, any deletion will result in the string "aba".

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

# Problem
Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought $$$n$$$ words consisting of small latin letters $$$s_1, s_2, \ldots, s_n$$$ to the lyceum. Since that day, Dasha has been tormented by nightmares.

Consider some pair of integers $$$\langle i, j \rangle$$$ ($$$1 \le i \le j \le n$$$). A nightmare is a string for which it is true:

- It is obtained by concatenation $$$s_{i}s_{j}$$$;
- Its length is odd;
- The number of different letters in it is exactly $$$25$$$;
- The number of occurrences of each letter that is in the word is odd.

For example, if $$$s_i=$$$ "abcdefg" and $$$s_j=$$$ "ijklmnopqrstuvwxyz", the pair $$$\langle i, j \rangle$$$ creates a nightmare.

Dasha will stop having nightmares if she counts their number. There are too many nightmares, so Dasha needs your help. Count the number of different nightmares.

Nightmares are called different if the corresponding pairs $$$\langle i, j \rangle$$$ are different. The pairs $$$\langle i_1, j_1 \rangle$$$ and $$$\langle i_2, j_2 \rangle$$$ are called different if $$$i_1 \neq i_2$$$ or $$$j_1 \neq j_2$$$.

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

The following $$$n$$$ lines contain the words $$$s_1, s_2, \ldots, s_n$$$, consisting of small latin letters.

It is guaranteed that the total length of words does not exceed $$$5 \cdot 10^6$$$.

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

## Examples
```input
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz
```
```output
5
```

## Note
In the first test, nightmares are created by pairs $$$\langle 1, 3 \rangle$$$, $$$\langle 2, 5 \rangle$$$, $$$\langle 3, 4 \rangle$$$, $$$\langle 6, 7 \rangle$$$, $$$\langle 9, 10 \rangle$$$.

Now solve the problem and return the code.