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

# Problem
At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than $$$10^6$$$ in total, each one is colored in one of $$$k$$$ colors. We can perform the following operation: choose $$$k-1$$$ balloons such that they are of $$$k-1$$$ different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least $$$k-1$$$ different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo $$$998244353$$$.

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

The second line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) —initial configuration of balloons. $$$a_i$$$ is number of balloons of color $$$i$$$. The total number of balloons doesn't exceed $$$10^6$$$. In other words,

$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$.

## Output Format
Output number of possible configurations modulo $$$998244353$$$.

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

## Note
In the first example, there are $$$3$$$ configurations we can get: $$$[0, 1, 2]$$$, $$$[2, 0, 1]$$$, $$$[1, 2, 0]$$$.

In the second example, we can apply the operation not more than once, and possible configurations are: $$$[1, 1, 1, 1]$$$, $$$[0, 0, 0, 4]$$$, $$$[0, 0, 4, 0]$$$, $$$[0, 4, 0, 0]$$$, $$$[4, 0, 0, 0]$$$.

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

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 problem differs from the previous one only in the absence of the constraint on the equal length of all numbers $$$a_1, a_2, \dots, a_n$$$.

A team of SIS students is going to make a trip on a submarine. Their target is an ancient treasure in a sunken ship lying on the bottom of the Great Rybinsk sea. Unfortunately, the students don't know the coordinates of the ship, so they asked Meshanya (who is a hereditary mage) to help them. He agreed to help them, but only if they solve his problem.

Let's denote a function that alternates digits of two numbers $$$f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)$$$, where $$$a_1 \dots a_p$$$ and $$$b_1 \dots b_q$$$ are digits of two integers written in the decimal notation without leading zeros.

In other words, the function $$$f(x, y)$$$ alternately shuffles the digits of the numbers $$$x$$$ and $$$y$$$ by writing them from the lowest digits to the older ones, starting with the number $$$y$$$. The result of the function is also built from right to left (that is, from the lower digits to the older ones). If the digits of one of the arguments have ended, then the remaining digits of the other argument are written out. Familiarize with examples and formal definitions of the function below.

For example: $$$$$$f(1111, 2222) = 12121212$$$$$$ $$$$$$f(7777, 888) = 7787878$$$$$$ $$$$$$f(33, 44444) = 4443434$$$$$$ $$$$$$f(555, 6) = 5556$$$$$$ $$$$$$f(111, 2222) = 2121212$$$$$$

Formally,

- if $$$p \ge q$$$ then $$$f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$;
- if $$$p < q$$$ then $$$f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$.

Mishanya gives you an array consisting of $$$n$$$ integers $$$a_i$$$, your task is to help students to calculate $$$\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)$$$ modulo $$$998\,244\,353$$$.

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of elements in the array. The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

## Output Format
Print the answer modulo $$$998\,244\,353$$$.

## Examples
```input
3
12 3 45
```
```output
12330
```
-----
```input
2
123 456
```
```output
1115598
```

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 playing a variation of game 2048. Initially you have a multiset $$$s$$$ of $$$n$$$ integers. Every integer in this multiset is a power of two.

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from $$$s$$$, remove them from $$$s$$$ and insert the number equal to their sum into $$$s$$$.

For example, if $$$s = \{1, 2, 1, 1, 4, 2, 2\}$$$ and you choose integers $$$2$$$ and $$$2$$$, then the multiset becomes $$$\{1, 1, 1, 4, 4, 2\}$$$.

You win if the number $$$2048$$$ belongs to your multiset. For example, if $$$s = \{1024, 512, 512, 4\}$$$ you can win as follows: choose $$$512$$$ and $$$512$$$, your multiset turns into $$$\{1024, 1024, 4\}$$$. Then choose $$$1024$$$ and $$$1024$$$, your multiset turns into $$$\{2048, 4\}$$$ and you win.

You have to determine if you can win this game.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line contains one integer $$$q$$$ ($$$1 \le q \le 100$$$) – the number of queries.

The first line of each query contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in multiset.

The second line of each query contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 2^{29}$$$) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.

## Output Format
For each query print YES if it is possible to obtain the number $$$2048$$$ in your multiset, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

## Examples
```input
6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096
```
```output
YES
YES
NO
NO
YES
YES
```

## Note
In the first query you can win as follows: choose $$$512$$$ and $$$512$$$, and $$$s$$$ turns into $$$\{1024, 64, 1024\}$$$. Then choose $$$1024$$$ and $$$1024$$$, and $$$s$$$ turns into $$$\{2048, 64\}$$$ and you win.

In the second query $$$s$$$ contains $$$2048$$$ initially.

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 chess board with $$$n$$$ rows and $$$n$$$ columns. Initially all cells of the board are empty, and you have to put a white or a black knight into each cell of the board.

A knight is a chess piece that can attack a piece in cell ($$$x_2$$$, $$$y_2$$$) from the cell ($$$x_1$$$, $$$y_1$$$) if one of the following conditions is met:

- $$$|x_1 - x_2| = 2$$$ and $$$|y_1 - y_2| = 1$$$, or
- $$$|x_1 - x_2| = 1$$$ and $$$|y_1 - y_2| = 2$$$.

Here are some examples of which cells knight can attack. In each of the following pictures, if the knight is currently in the blue cell, it can attack all red cells (and only them).

A duel of knights is a pair of knights of different colors such that these knights attack each other. You have to put a knight (a white one or a black one) into each cell in such a way that the number of duels is maximum possible.

## Input Format
The first line contains one integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of rows (and columns) in the board.

## Output Format
Print $$$n$$$ lines with $$$n$$$ characters in each line. The $$$j$$$-th character in the $$$i$$$-th line should be W, if the cell ($$$i$$$, $$$j$$$) contains a white knight, or B, if it contains a black knight. The number of duels should be maximum possible. If there are multiple optimal answers, print any of them.

## Examples
```input
3
```
```output
WBW
BBB
WBW
```

## Note
In the first example, there are $$$8$$$ duels:

1. the white knight in ($$$1$$$, $$$1$$$) attacks the black knight in ($$$3$$$, $$$2$$$);
2. the white knight in ($$$1$$$, $$$1$$$) attacks the black knight in ($$$2$$$, $$$3$$$);
3. the white knight in ($$$1$$$, $$$3$$$) attacks the black knight in ($$$3$$$, $$$2$$$);
4. the white knight in ($$$1$$$, $$$3$$$) attacks the black knight in ($$$2$$$, $$$1$$$);
5. the white knight in ($$$3$$$, $$$1$$$) attacks the black knight in ($$$1$$$, $$$2$$$);
6. the white knight in ($$$3$$$, $$$1$$$) attacks the black knight in ($$$2$$$, $$$3$$$);
7. the white knight in ($$$3$$$, $$$3$$$) attacks the black knight in ($$$1$$$, $$$2$$$);
8. the white knight in ($$$3$$$, $$$3$$$) attacks the black knight in ($$$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 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 have a fence consisting of $$$n$$$ vertical boards. The width of each board is $$$1$$$. The height of the $$$i$$$-th board is $$$a_i$$$. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from $$$2$$$ to $$$n$$$, the condition $$$a_{i-1} \neq a_i$$$ holds.

Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the $$$i$$$-th board by $$$1$$$, but you have to pay $$$b_i$$$ rubles for it. The length of each board can be increased any number of times (possibly, zero).

Calculate the minimum number of rubles you have to spend to make the fence great again!

You have to answer $$$q$$$ independent queries.

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

The first line of each query contains one integers $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of boards in the fence.

The following $$$n$$$ lines of each query contain the descriptions of the boards. The $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — the length of the $$$i$$$-th board and the price for increasing it by $$$1$$$, respectively.

It is guaranteed that sum of all $$$n$$$ over all queries not exceed $$$3 \cdot 10^5$$$.

It is guaranteed that answer to each query will not exceed $$$10^{18}$$$.

## Output Format
For each query print one integer — the minimum number of rubles you have to spend to make the fence great.

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

## Note
In the first query you have to increase the length of second board by $$$2$$$. So your total costs if $$$2 \cdot b_2 = 2$$$.

In the second query you have to increase the length of first board by $$$1$$$ and the length of third board by $$$1$$$. So your total costs if $$$1 \cdot b_1 + 1 \cdot b_3 = 9$$$.

In the third query the fence is great initially, so you don't need to spend rubles.

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

# Problem
You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. You have to write a number on each vertex of this graph, each number should be either $$$0$$$ or $$$1$$$. After that, you write a number on each edge equal to the sum of numbers on vertices incident to that edge.

You have to choose the numbers you will write on the vertices so that there is at least one edge with $$$0$$$ written on it, at least one edge with $$$1$$$ and at least one edge with $$$2$$$. How many ways are there to do it? Two ways to choose numbers are different if there exists at least one vertex which has different numbers written on it in these two ways.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 40$$$, $$$0 \le m \le \frac{n(n - 1)}{2}$$$) — the number of vertices and the number of edges, respectively.

Then $$$m$$$ lines follow, each line contains two numbers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge. It is guaranteed that each pair of vertices is connected by at most one edge.

## Output Format
Print one integer — the number of ways to write numbers on all vertices so that there exists at least one edge with $$$0$$$ written on it, at least one edge with $$$1$$$ and at least one edge with $$$2$$$.

## Examples
```input
6 5
1 2
2 3
3 4
4 5
5 1
```
```output
20
```
-----
```input
4 4
1 2
2 3
3 4
4 1
```
```output
4
```
-----
```input
35 29
1 2
2 3
3 1
4 1
4 2
3 4
7 8
8 9
9 10
10 7
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
```
```output
34201047040
```

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 maze is represented by a tree (an undirected graph, where exactly one way exists between each pair of vertices). In the maze the entrance vertex and the exit vertex are chosen with some probability. The exit from the maze is sought by Deep First Search. If there are several possible ways to move, the move is chosen equiprobably. Consider the following pseudo-code:

V(x) is the list vertices adjacent to x. The flag array is initially filled as FALSE. DFS initially starts with a parameter of an entrance vertex. When the search is finished, variable count will contain the number of moves.

Your task is to count the mathematical expectation of the number of moves one has to do to exit the maze.

## Input Format
The first line determines the number of vertices in the graph n (1 ≤ n ≤ 105). The next n - 1 lines contain pairs of integers ai and bi, which show the existence of an edge between ai and bi vertices (1 ≤ ai, bi ≤ n). It is guaranteed that the given graph is a tree.

Next n lines contain pairs of non-negative numbers xi and yi, which represent the probability of choosing the i-th vertex as an entrance and exit correspondingly. The probabilities to choose vertex i as an entrance and an exit equal $$x_i / \sum_{j=1}^{n} x_j$$ and $$y_i / \sum_{j=1}^{n} y_j$$ correspondingly. The sum of all xi and the sum of all yi are positive and do not exceed 106.

## Output Format
Print the expectation of the number of moves. The absolute or relative error should not exceed 10 - 9.

## Examples
```input
2
1 2
0 1
1 0
```
```output
1.00000000000000000000
```
-----
```input
3
1 2
1 3
1 0
0 2
0 3
```
```output
2.00000000000000000000
```
-----
```input
7
1 2
1 3
2 4
2 5
3 6
3 7
1 1
1 1
1 1
1 1
1 1
1 1
1 1
```
```output
4.04081632653
```

## Note
In the first sample the entrance vertex is always 1 and the exit vertex is always 2.

In the second sample the entrance vertex is always 1 and the exit vertex with the probability of 2/5 will be 2 of with the probability if 3/5 will be 3. The mathematical expectations for the exit vertices 2 and 3 will be equal (symmetrical cases). During the first move one can go to the exit vertex with the probability of 0.5 or to go to a vertex that's not the exit vertex with the probability of 0.5. In the first case the number of moves equals 1, in the second one it equals 3. The total mathematical expectation is counted as 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
Kolya has a turtle and a field of size $$$2 \times n$$$. The field rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom, while the columns are numbered from $$$1$$$ to $$$n$$$ from left to right.

Suppose in each cell of the field there is a lettuce leaf. The energy value of lettuce leaf in row $$$i$$$ and column $$$j$$$ is equal to $$$a_{i,j}$$$. The turtle is initially in the top left cell and wants to reach the bottom right cell. The turtle can only move right and down and among all possible ways it will choose a way, maximizing the total energy value of lettuce leaves (in case there are several such paths, it will choose any of them).

Kolya is afraid, that if turtle will eat too much lettuce, it can be bad for its health. So he wants to reorder lettuce leaves in the field, so that the energetic cost of leaves eaten by turtle will be minimized.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 25$$$) — the length of the field.

The second line contains $$$n$$$ integers $$$a_{1, i}$$$ ($$$0 \le a_{1, i} \le 50\,000$$$), the energetic cost of lettuce leaves in the first row of the field.

The third line contains $$$n$$$ integers $$$a_{2, i}$$$ ($$$0 \le a_{2, i} \le 50\,000$$$), the energetic cost of lettuce leaves in the second row of the field.

## Output Format
Print two lines with $$$n$$$ integers in each — the optimal reordering of lettuce from the input data.

In case there are several optimal ways to reorder lettuce, print any of them.

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

## Note
In the first example, after reordering, the turtle will eat lettuce with total energetic cost $$$1+4+2 = 7$$$.

In the second example, the turtle will eat lettuce with energetic cost equal $$$0$$$.

In the third example, after reordering, the turtle will eat lettuce with total energetic cost equal $$$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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
There is a string $$$s$$$ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $$$c$$$ and a direction (left or right). The cursor is then moved to the closest occurence of $$$c$$$ in the chosen direction. If there is no letter $$$c$$$ in that direction, the cursor stays in place. For example, if $$$s = \mathtt{abaab}$$$ with the cursor on the second character ($$$\mathtt{a[b]aab}$$$), then:

- moving to the closest letter $$$\mathtt{a}$$$ to the left places the cursor on the first character ($$$\mathtt{[a]baab}$$$);
- moving to the closest letter $$$\mathtt{a}$$$ to the right places the cursor the third character ($$$\mathtt{ab[a]ab}$$$);
- moving to the closest letter $$$\mathtt{b}$$$ to the right places the cursor on the fifth character ($$$\mathtt{abaa[b]}$$$);
- any other operation leaves the cursor in place.

Let $$$\mathrm{dist}(i, j)$$$ be the smallest number of operations needed to move the cursor from the $$$i$$$-th character to the $$$j$$$-th character. Compute $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

## Input Format
The only line contains a non-empty string $$$s$$$ of at most $$$10^5$$$ lowercase English letters.

## Output Format
Print a single integer $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

## Examples
```input
abcde
```
```output
20
```
-----
```input
abacaba
```
```output
58
```

## Note
In the first sample case, $$$\mathrm{dist}(i, j) = 0$$$ for any pair $$$i = j$$$, and $$$1$$$ for all other pairs.

Now solve the problem and return the code.