apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Students from many different parts of Russia and abroad come to Summer Informatics School. You marked the hometowns of the SIS participants on a map.

Now you decided to prepare an interesting infographic based on this map. The first thing you chose to do is to find three cities on this map, such that they form a triangle with area $$$S$$$.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$S$$$ ($$$3 \le n \le 2000$$$, $$$1 \le S \le 2 \cdot 10^{18}$$$) — the number of cities on the map and the area of the triangle to be found.

The next $$$n$$$ lines contain descriptions of the cities, one per line. Each city is described by its integer coordinates $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$).

It is guaranteed that all cities are located at distinct points. It is also guaranteed that no three cities lie on the same line.

## Output Format
If the solution doesn't exist — print «No».

Otherwise, print «Yes», followed by three pairs of coordinates $$$(x, y)$$$ — the locations of the three cities, which form the triangle of area $$$S$$$.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a table of size $$$n \times m$$$, initially fully white. Rows are numbered $$$1$$$ through $$$n$$$ from top to bottom, columns $$$1$$$ through $$$m$$$ from left to right. Some square inside the table with odd side length was painted black. Find the center of this square.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 115$$$) — the number of rows and the number of columns in the table.

The $$$i$$$-th of the next $$$n$$$ lines contains a string of $$$m$$$ characters $$$s_{i1} s_{i2} \ldots s_{im}$$$ ($$$s_{ij}$$$ is 'W' for white cells and 'B' for black cells), describing the $$$i$$$-th row of the table.

## Output Format
Output two integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le n$$$, $$$1 \le c \le m$$$) separated by a space — the row and column numbers of the center of the black square.

## Examples
```input
5 6
WWBBBW
WWBBBW
WWBBBW
WWWWWW
WWWWWW
```
```output
2 4
```
-----
```input
3 3
WWW
BWW
WWW
```
```output
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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let $$$s(x)$$$ be sum of digits in decimal representation of positive integer $$$x$$$. Given two integers $$$n$$$ and $$$m$$$, find some positive integers $$$a$$$ and $$$b$$$ such that

- $$$s(a) \ge n$$$,
- $$$s(b) \ge n$$$,
- $$$s(a + b) \le m$$$.

## Input Format
The only line of input contain two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1129$$$).

## Output Format
Print two lines, one for decimal representation of $$$a$$$ and one for decimal representation of $$$b$$$. Both numbers must not contain leading zeros and must have length no more than $$$2230$$$.

## Examples
```input
6 5
```
```output
6
7
```
-----
```input
8 16
```
```output
35
53
```

## Note
In the first sample, we have $$$n = 6$$$ and $$$m = 5$$$. One valid solution is $$$a = 6$$$, $$$b = 7$$$. Indeed, we have $$$s(a) = 6 \ge n$$$ and $$$s(b) = 7 \ge n$$$, and also $$$s(a + b) = s(13) = 4 \le m$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
While discussing a proper problem A for a Codeforces Round, Kostya created a cyclic array of positive integers $$$a_1, a_2, \ldots, a_n$$$. Since the talk was long and not promising, Kostya created a new cyclic array $$$b_1, b_2, \ldots, b_{n}$$$ so that $$$b_i = (a_i \mod a_{i + 1})$$$, where we take $$$a_{n+1} = a_1$$$. Here $$$mod$$$ is the modulo operation. When the talk became interesting, Kostya completely forgot how array $$$a$$$ had looked like. Suddenly, he thought that restoring array $$$a$$$ from array $$$b$$$ would be an interesting problem (unfortunately, not A).

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 140582$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_{n}$$$ ($$$0 \le b_i \le 187126$$$).

## Output Format
If it is possible to restore some array $$$a$$$ of length $$$n$$$ so that $$$b_i = a_i \mod a_{(i \mod n) + 1}$$$ holds for all $$$i = 1, 2, \ldots, n$$$, print «YES» in the first line and the integers $$$a_1, a_2, \ldots, a_n$$$ in the second line. All $$$a_i$$$ should satisfy $$$1 \le a_i \le 10^{18}$$$. We can show that if an answer exists, then an answer with such constraint exists as well.

It it impossible to restore any valid $$$a$$$, print «NO» in one line.

You can print each letter in any case (upper or lower).

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

## Note
In the first example:

- $$$1 \mod 3 = 1$$$
- $$$3 \mod 5 = 3$$$
- $$$5 \mod 2 = 1$$$
- $$$2 \mod 1 = 0$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Oleg came to see the maze of mirrors. The maze is a $$$n$$$ by $$$n$$$ room in which each cell is either empty or contains a mirror connecting opposite corners of this cell. Mirrors in this maze reflect light in a perfect way, which causes the interesting visual effects and contributes to the loss of orientation in the maze.

Oleg is a person of curious nature, so he decided to install $$$n$$$ lasers facing internal of the maze on the south wall of the maze. On the north wall of the maze, Oleg installed $$$n$$$ receivers, also facing internal of the maze. Let's number lasers and receivers from west to east with distinct integers from $$$1$$$ to $$$n$$$. Each laser sends a beam of some specific kind and receiver with number $$$a_i$$$ should receive the beam sent from laser number $$$i$$$. Since two lasers' beams can't come to the same receiver, these numbers form a permutation — each of the receiver numbers occurs exactly once.

You came to the maze together with Oleg. Help him to place the mirrors in the initially empty maze so that the maximum number of lasers' beams will come to the receivers they should. There are no mirrors outside the maze, so if the laser beam leaves the maze, it will not be able to go back.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the maze.

The second line contains a permutation of $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ defines the number of the receiver, to which the beam from $$$i$$$-th laser should come.

## Output Format
In the first line print the maximum possible number of laser beams, which can come to the receivers they should.

In the next $$$n$$$ lines of length $$$n$$$ print the arrangement of mirrors, causing such number of laser beams to come where they should. If the corresponding cell is empty, print ".", otherwise print "/" or "\", depending on the orientation of the mirror.

In your output north should be above, south should be below, and west and east should be on left and on the right respectively.

It is allowed for laser beams to come not to the receivers they correspond to, but they are not counted in the answer.

If there are multiple arrangements of mirrors leading to the optimal answer — print any of them.

## Examples
```input
4
4 1 3 2
```
```output
3
.\..
\\..
/../
...\
```

## Note
The picture illustrates the arrangements of the mirrors in the first example.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 512.0 MB

# Problem
We call a sequence of strings t1, ..., tk a journey of length k, if for each i > 1 ti is a substring of ti - 1 and length of ti is strictly less than length of ti - 1. For example, {ab, b} is a journey, but {ab, c} and {a, a} are not.

Define a journey on string s as journey t1, ..., tk, such that all its parts can be nested inside s in such a way that there exists a sequence of strings u1, ..., uk + 1 (each of these strings can be empty) and s = u1 t1 u2 t2... uk tk uk + 1. As an example, {ab, b} is a journey on string abb, but not on bab because the journey strings ti should appear from the left to the right.

The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string s.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 500 000) — the length of string s.

The second line contains the string s itself, consisting of n lowercase Latin letters.

## Output Format
Print one number — the maximum possible length of string journey on s.

## Examples
```input
7
abcdbcc
```
```output
3
```
-----
```input
4
bbcb
```
```output
2
```

## Note
In the first sample, the string journey of maximum length is {abcd, bc, c}.

In the second sample, one of the suitable journeys is {bb, b}.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Let's define rank of undirected graph as rank of its adjacency matrix in $$$\mathbb{R}^{n \times n}$$$.

Given a tree. Each edge of this tree will be deleted with probability $$$1/2$$$, all these deletions are independent. Let $$$E$$$ be the expected rank of resulting forest. Find $$$E \cdot 2^{n-1}$$$ modulo $$$998244353$$$ (it is easy to show that $$$E \cdot 2^{n-1}$$$ is an integer).

## Input Format
First line of input contains $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — number of vertices.

Next $$$n-1$$$ lines contains two integers $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

## Output Format
Print one integer — answer to the problem.

## Examples
```input
3
1 2
2 3
```
```output
6
```
-----
```input
4
1 2
1 3
1 4
```
```output
14
```
-----
```input
4
1 2
2 3
3 4
```
```output
18
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.

The current state of the wall can be respresented by a sequence $$$a$$$ of $$$n$$$ integers, with $$$a_i$$$ being the height of the $$$i$$$-th part of the wall.

Vova can only use $$$2 \times 1$$$ bricks to put in the wall (he has infinite supply of them, however).

Vova can put bricks horizontally on the neighboring parts of the wall of equal height. It means that if for some $$$i$$$ the current height of part $$$i$$$ is the same as for part $$$i + 1$$$, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part $$$1$$$ of the wall or to the right of part $$$n$$$ of it).

The next paragraph is specific to the version 1 of the problem.

Vova can also put bricks vertically. That means increasing height of any part of the wall by 2.

Vova is a perfectionist, so he considers the wall completed when:

- all parts of the wall has the same height;
- the wall has no empty spaces inside it.

Can Vova complete the wall using any amount of bricks (possibly zero)?

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial heights of the parts of the wall.

## Output Format
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.

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

## Note
In the first example Vova can put a brick on parts 2 and 3 to make the wall $$$[2, 2, 2, 2, 5]$$$ and then put 3 bricks on parts 1 and 2 and 3 bricks on parts 3 and 4 to make it $$$[5, 5, 5, 5, 5]$$$.

In the second example Vova can put a brick vertically on part 3 to make the wall $$$[4, 5, 5]$$$, then horizontally on parts 2 and 3 to make it $$$[4, 6, 6]$$$ and then vertically on part 1 to make it $$$[6, 6, 6]$$$.

In the third example the wall is already complete.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.

The current state of the wall can be respresented by a sequence $$$a$$$ of $$$n$$$ integers, with $$$a_i$$$ being the height of the $$$i$$$-th part of the wall.

Vova can only use $$$2 \times 1$$$ bricks to put in the wall (he has infinite supply of them, however).

Vova can put bricks only horizontally on the neighbouring parts of the wall of equal height. It means that if for some $$$i$$$ the current height of part $$$i$$$ is the same as for part $$$i + 1$$$, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part $$$1$$$ of the wall or to the right of part $$$n$$$ of it).

Note that Vova can't put bricks vertically.

Vova is a perfectionist, so he considers the wall completed when:

- all parts of the wall has the same height;
- the wall has no empty spaces inside it.

Can Vova complete the wall using any amount of bricks (possibly zero)?

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial heights of the parts of the wall.

## Output Format
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).

Print "NO" otherwise.

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

## Note
In the first example Vova can put a brick on parts 2 and 3 to make the wall $$$[2, 2, 2, 2, 5]$$$ and then put 3 bricks on parts 1 and 2 and 3 bricks on parts 3 and 4 to make it $$$[5, 5, 5, 5, 5]$$$.

In the second example Vova can put no bricks in the wall.

In the third example the wall is already complete.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a forest — an undirected graph with $$$n$$$ vertices such that each its connected component is a tree.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

You task is to add some edges (possibly zero) to the graph so that it becomes a tree and the diameter of the tree is minimal possible.

If there are multiple correct answers, print any of them.

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

Each of the next $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) — the descriptions of the edges.

It is guaranteed that the given graph is a forest.

## Output Format
In the first line print the diameter of the resulting tree.

Each of the next $$$(n - 1) - m$$$ lines should contain two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) — the descriptions of the added edges.

The resulting graph should be a tree and its diameter should be minimal possible.

For $$$m = n - 1$$$ no edges are added, thus the output consists of a single integer — diameter of the given tree.

If there are multiple correct answers, print any of them.

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

## Note
In the first example adding edges (1, 4) or (3, 4) will lead to a total diameter of 3. Adding edge (2, 4), however, will make it 2.

Edge (1, 2) is the only option you have for the second example. The diameter is 1.

You can't add any edges in the third example. The diameter is already 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 c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree consisting exactly of $$$n$$$ vertices. Tree is a connected undirected graph with $$$n-1$$$ edges. Each vertex $$$v$$$ of this tree has a value $$$a_v$$$ assigned to it.

Let $$$dist(x, y)$$$ be the distance between the vertices $$$x$$$ and $$$y$$$. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $$$v$$$. Then the cost of the tree is $$$\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$$$.

Your task is to calculate the maximum possible cost of the tree if you can choose $$$v$$$ arbitrarily.

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

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the value of the vertex $$$i$$$.

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the maximum possible cost of the tree if you can choose any vertex as $$$v$$$.

## Examples
```input
8
9 4 1 7 10 1 6 5
1 2
2 3
1 4
1 5
5 6
5 7
5 8
```
```output
121
```
-----
```input
1
1337
```
```output
0
```

## Note
Picture corresponding to the first example:

You can choose the vertex $$$3$$$ as a root, then the answer will be $$$2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$$$.

In the second example tree consists only of one vertex so the answer is always $$$0$$$.

Now solve the problem and return the code.