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

# Problem
Chiyuu has a bracket sequence$$$^\dagger$$$ $$$s$$$ of length $$$n$$$. Let $$$k$$$ be the minimum number of characters that Chiyuu has to remove from $$$s$$$ to make $$$s$$$ balanced$$$^\ddagger$$$.

Now, Koxia wants you to count the number of ways to remove $$$k$$$ characters from $$$s$$$ so that $$$s$$$ becomes balanced, modulo $$$998\,244\,353$$$.

Note that two ways of removing characters are considered distinct if and only if the set of indices removed is different.

$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".

$$$^\ddagger$$$ A bracket sequence is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are balanced, while )(, ((), and (()))( are not.

## Input Format
The first line of input contains a string $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot {10}^5$$$) — the bracket sequence.

It is guaranteed that $$$s$$$ only contains the characters "(" and ")".

## Output Format
Output a single integer — the number of ways to remove $$$k$$$ characters from $$$s$$$ so that $$$s$$$ becomes balanced, modulo $$$998\,244\,353$$$.

## Examples
```input
())(()
```
```output
4
```
-----
```input
(
```
```output
1
```

## Note
In the first test case, it can be proved that the minimum number of characters that Chiyuu has to remove is $$$2$$$. There are $$$4$$$ ways to remove $$$2$$$ characters to make $$$s$$$ balanced as follows. Deleted characters are noted as red.

- $$$\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$$$.

In the second test case, the only way to make $$$s$$$ balanced is by deleting the only character to get an empty bracket sequence, which is considered balanced.

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
There are two towers consisting of blocks of two colors: red and blue. Both towers are represented by strings of characters B and/or R denoting the order of blocks in them from the bottom to the top, where B corresponds to a blue block, and R corresponds to a red block.

These two towers are represented by strings BRBB and RBR.

You can perform the following operation any number of times: choose a tower with at least two blocks, and move its top block to the top of the other tower.

The pair of towers is beautiful if no pair of touching blocks has the same color; i. e. no red block stands on top of another red block, and no blue block stands on top of another blue block.

You have to check if it is possible to perform any number of operations (possibly zero) to make the pair of towers beautiful.

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

Each test case consists of three lines:

- the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 20$$$) — the number of blocks in the first tower and the number of blocks in the second tower, respectively;
- the second line contains $$$s$$$ — a string of exactly $$$n$$$ characters B and/or R, denoting the first tower;
- the third line contains $$$t$$$ — a string of exactly $$$m$$$ characters B and/or R, denoting the second tower.

## Output Format
For each test case, print YES if it is possible to perform several (possibly zero) operations in such a way that the pair of towers becomes beautiful; otherwise print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

## Examples
```input
4
4 3
BRBB
RBR
4 7
BRBR
RRBRBRB
3 4
RBR
BRBR
5 4
BRBRR
BRBR
```
```output
YES
YES
YES
NO
```

## Note
In the first test case, you can move the top block from the first tower to the second tower (see the third picture).

In the second test case, you can move the top block from the second tower to the first tower $$$6$$$ times.

In the third test case, the pair of towers is already beautiful.

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 are given $$$n$$$ one-dimensional segments (each segment is denoted by two integers — its endpoints).

Let's define the function $$$f(x)$$$ as the number of segments covering point $$$x$$$ (a segment covers the point $$$x$$$ if $$$l \le x \le r$$$, where $$$l$$$ is the left endpoint and $$$r$$$ is the right endpoint of the segment).

An integer point $$$x$$$ is called ideal if it belongs to more segments than any other integer point, i. e. $$$f(y) < f(x)$$$ is true for any other integer point $$$y$$$.

You are given an integer $$$k$$$. Your task is to determine whether it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 50$$$).

Then $$$n$$$ lines follow, $$$i$$$-th line of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i, r_i \le 50$$$; $$$l_i \le r_i$$$) — the endpoints of the $$$i$$$-th segment.

## Output Format
For each test case, print YES if it is possible to remove some (possibly zero) segments, so that the given point $$$k$$$ becomes ideal, otherwise print NO.

You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

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

## Note
In the first example, the point $$$3$$$ is already ideal (it is covered by three segments), so you don't have to delete anything.

In the fourth example, you can delete everything except the segment $$$[5, 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an undirected graph consisting of $$$n$$$ vertices and $$$n$$$ edges, where $$$n$$$ is divisible by $$$6$$$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $$$\frac{n}{3}$$$ triples of vertices, the first triple consisting of vertices $$$1, 2, 3$$$, the second triple consisting of vertices $$$4, 5, 6$$$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $$$\frac{n}{2}$$$ red vertices and $$$\frac{n}{2}$$$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $$$W$$$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $$$W$$$, and print it modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$6 \le n \le 3 \cdot 10^5$$$, $$$n$$$ is divisible by $$$6$$$).

The second line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — the weights of the edges. Edge $$$1$$$ connects vertices $$$1$$$ and $$$2$$$, edge $$$2$$$ connects vertices $$$1$$$ and $$$3$$$, edge $$$3$$$ connects vertices $$$2$$$ and $$$3$$$, edge $$$4$$$ connects vertices $$$4$$$ and $$$5$$$, edge $$$5$$$ connects vertices $$$4$$$ and $$$6$$$, edge $$$6$$$ connects vertices $$$5$$$ and $$$6$$$, and so on.

## Output Format
Print one integer — the number of valid colorings with maximum possible weight, taken modulo $$$998244353$$$.

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

## Note
The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $$$31$$$.

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 an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

You can make this operation multiple (possibly zero) times:

- Choose two indices $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$).
- Assign $$$a_i := \lceil \frac{a_i}{a_j} \rceil$$$. Here $$$\lceil x \rceil$$$ denotes $$$x$$$ rounded up to the smallest integer $$$\geq x$$$.

Is it possible to make all array elements equal by some sequence of operations (possibly empty)? If yes, print any way to do it in at most $$$30n$$$ operations.

It can be proven, that under the problem constraints, if some way exists to make all elements equal, there exists a way with at most $$$30n$$$ operations.

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

The first line of each test case description contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$).

The second line of each test case description contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed, that the sum of $$$n$$$ for all test cases does not exceed $$$1000$$$.

## Output Format
For each test case print a single integer $$$q$$$ ($$$-1 \leq q \leq 30n$$$). If $$$q=-1$$$, there is no solution, otherwise $$$q$$$ is equal to the number of operations.

If $$$q \geq 0$$$, on the next $$$q$$$ lines print two integers $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) — descriptions of operations.

If there are multiple solutions, you can print any.

## Examples
```input
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55
```
```output
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4
```

## Note
In the first and second, fourth test cases all numbers are equal, so it is possible to do nothing.

In the third test case, it is impossible to make all numbers equal.

In the fifth test case: $$$[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$$$.

In the sixth test case: $$$[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$$$.

Here the red numbers are $$$i$$$ indices (that will be assigned), blue numbers are $$$j$$$ indices.

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 are given a string $$$s$$$. You can reorder the characters to form a string $$$t$$$. Define $$$t_{\mathrm{max}}$$$ to be the lexicographical maximum of $$$t$$$ and $$$t$$$ in reverse order.

Given $$$s$$$ determine the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

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

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

The first and only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$). $$$s$$$ consists of only lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case print the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$.

## Examples
```input
12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba
```
```output
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba
```

## Note
For the first test case, there is only one reordering of $$$s$$$, namely "a".

For the second test case, there are three reorderings of $$$s$$$.

- $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$
- $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$
- $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$

The lexicographical minimum of $$$t_{\mathrm{max}}$$$ over all cases is "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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ people that will participate in voting. Each person has exactly one vote.

$$$i$$$-th person has a team $$$t_i$$$ ($$$1 \leq t_i \leq n$$$) where $$$t_i = t_j$$$ means $$$i$$$, $$$j$$$ are in the same team. By the rules each person should vote for the person from the different team. Note that it automatically means that each person can't vote for himself.

Each person knows the number of votes $$$c_i$$$ he wants to get. How many possible votings exists, such that each person will get the desired number of votes? Due to this number can be big, find it by modulo $$$998\,244\,353$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$) — the number of people.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq n$$$) — desired number of votes. It is guaranteed, that $$$\sum\limits_{i=1}^{n} c_i = n$$$.

The third line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \leq t_i \leq n$$$) — team numbers.

## Output Format
Print a single integer — the number of possible votings by modulo $$$998\,244\,353$$$.

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

## Note
In the first test there are two possible votings: $$$(2, 3, 1)$$$, $$$(3, 1, 2)$$$.

In the third test there are five possible votings: $$$(3, 3, 2, 2, 1)$$$, $$$(2, 3, 2, 3, 1)$$$, $$$(3, 3, 1, 2, 2)$$$, $$$(3, 1, 2, 3, 2)$$$, $$$(2, 3, 1, 3, 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 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 a tree with $$$n$$$ vertices.

A hero $$$k$$$ times do the following operation:

- Choose some edge.
- Remove it.
- Take one of the two remaining parts and delete it.
- Write the number of vertices in the remaining part.

You are given an initial tree and the a sequence of written numbers. Find the number of ways to make operations such that the written numbers are equal to the given numbers. Due to the answer can be big, find it by modulo $$$998\,244\,353$$$. Two ways are considered different, if on some operation edge or remaining part are selected differently.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 5000$$$) — the number of vertices.

Each of the next $$$n-1$$$ lines contains two integers $$$s$$$, $$$f$$$ ($$$1 \leq s, f \leq n$$$, $$$s \neq f$$$) — description of edge $$$(s, f)$$$.

Next line contains a single integer $$$k$$$ ($$$1 \leq k \leq \min{(6, n - 1)}$$$) — the number of operations.

Next line contains $$$k$$$ integers $$$s_1, s_2, \ldots, s_k$$$ ($$$n > s_1 > s_2 > \ldots > s_k \geq 1$$$) — written numbers.

## Output Format
Print a single integer — the answer to the problem by modulo $$$998\,244\,353$$$.

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

## Note
In the first test there are four possible ways to make operations:

- Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$. Remove the edge $$$(2, 3)$$$ and delete vertex $$$2$$$.
- Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$. Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$.
- Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$. Remove the edge $$$(1, 2)$$$ and delete vertex $$$1$$$.
- Remove the edge $$$(3, 2)$$$ and delete vertex $$$3$$$. Remove the edge $$$(2, 1)$$$ and delete vertex $$$2$$$.

In the second test there are two possible ways to make operations:

- Remove the edge $$$(4, 1)$$$ and delete the part with vertex $$$4$$$. Remove the edge $$$(2, 3)$$$ and delete the part with vertex $$$2$$$.
- Remove the edge $$$(4, 1)$$$ and delete the part with vertex $$$4$$$. Remove the edge $$$(3, 2)$$$ and delete the part with vertex $$$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
Patrick has just finished writing a message to his sweetheart Stacey when he noticed that the message didn't look fancy. Patrick was nervous while writing the message, so some of the letters there were lowercase and some of them were uppercase.

Patrick believes that a message is fancy if any uppercase letter stands to the left of any lowercase one. In other words, this rule describes the strings where first go zero or more uppercase letters, and then — zero or more lowercase letters.

To make the message fancy, Patrick can erase some letter and add the same letter in the same place in the opposite case (that is, he can replace an uppercase letter with the lowercase one and vice versa). Patrick got interested in the following question: what minimum number of actions do we need to make a message fancy? Changing a letter's case in the message counts as one action. Patrick cannot perform any other actions.

## Input Format
The only line of the input contains a non-empty string consisting of uppercase and lowercase letters. The string's length does not exceed 105.

## Output Format
Print a single number — the least number of actions needed to make the message fancy.

## Examples
```input
PRuvetSTAaYA
```
```output
5
```
-----
```input
OYPROSTIYAOPECHATALSYAPRIVETSTASYA
```
```output
0
```
-----
```input
helloworld
```
```output
0
```

Now solve the problem and return the code.