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
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 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
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 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
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 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
Formula 1 officials decided to introduce new competition. Cars are replaced by space ships and number of points awarded can differ per race.

Given the current ranking in the competition and points distribution for the next race, your task is to calculate the best possible ranking for a given astronaut after the next race. It's guaranteed that given astronaut will have unique number of points before the race.

## Input Format
The first line contains two integer numbers $$$N$$$ ($$$1 \leq N \leq 200000$$$) representing number of F1 astronauts, and current position of astronaut $$$D$$$ ($$$1 \leq D \leq N$$$) you want to calculate best ranking for (no other competitor will have the same number of points before the race).

The second line contains $$$N$$$ integer numbers $$$S_k$$$ ($$$0 \leq S_k \leq 10^8$$$, $$$k=1...N$$$), separated by a single space, representing current ranking of astronauts. Points are sorted in non-increasing order.

The third line contains $$$N$$$ integer numbers $$$P_k$$$ ($$$0 \leq P_k \leq 10^8$$$, $$$k=1...N$$$), separated by a single space, representing point awards for the next race. Points are sorted in non-increasing order, so winner of the race gets the maximum number of points.

## Output Format
Output contains one integer number — the best possible ranking for astronaut after the race. If multiple astronauts have the same score after the race, they all share the best ranking.

## Examples
```input
4 3
50 30 20 10
15 10 7 3
```
```output
2
```

## Note
If the third ranked astronaut wins the race, he will have 35 points. He cannot take the leading position, but he can overtake the second position if the second ranked astronaut finishes the race at the last position.

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
Two friends are travelling through Bubble galaxy. They say "Hello!" via signals to each other if their distance is smaller or equal than $$$d_1$$$ and

- it's the first time they speak to each other or
- at some point in time after their last talk their distance was greater than $$$d_2$$$.

We need to calculate how many times friends said "Hello!" to each other. For $$$N$$$ moments, you'll have an array of points for each friend representing their positions at that moment. A person can stay in the same position between two moments in time, but if a person made a move we assume this movement as movement with constant speed in constant direction.

## Input Format
The first line contains one integer number $$$N$$$ ($$$2 \leq N \leq 100\,000$$$) representing number of moments in which we captured positions for two friends.

The second line contains two integer numbers $$$d_1$$$ and $$$d_2 \ (0 < d_1 < d_2 < 1000)$$$.

The next $$$N$$$ lines contains four integer numbers $$$A_x,A_y,B_x,B_y$$$ ($$$0 \leq A_x, A_y, B_x, B_y \leq 1000$$$) representing coordinates of friends A and B in each captured moment.

## Output Format
Output contains one integer number that represents how many times friends will say "Hello!" to each other.

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

## Note
Explanation: Friends should send signals 2 times to each other, first time around point $$$A2$$$ and $$$B2$$$ and second time during A's travel from point $$$A3$$$ to $$$A4$$$ while B stays in point $$$B3=B4$$$.

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
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 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
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 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
The night after the graduation ceremony graduate students of German University in Cairo (GUC) are playing darts. As there's no real dart board available, the photographs of members of the GUC upper management are being used.

So, n rectangular photos are placed on the wall. They can overlap arbitrary and even coincide. The photos are not necessarily placed horizontally or vertically, they could also be rotated before being pinned to the wall.

The score of one dart throw is simply the number of photos the dart went through.

Fatma has made a throw but her score was not recorded. She only remembers that she did make it into at least one photo.

Assuming that the probability distribution of the throw is equal across the whole wall, what would be the expectation of Fatma's score?

## Input Format
The first line of input contains integer n (1 ≤ n ≤ 500) — the number of photos on the wall. Then follow n lines describing the photos, each containing 8 single-space-separated integers (coordinates of 4 vertices): x1, y1, x2, y2, x3, y3, x4, y4. Each photo is a rectangle with a nonzero area. The coordinates are integers, not exceeding 104 by absolute value. The coordinates of the rectangle are given in either clockwise or counterclockwise order.

## Output Format
Print the expected score of the throw. The answer will be accepted if it has absolute or relative error not exceeding 10 - 6.

## Examples
```input
1
0 0 0 2 2 2 2 0
```
```output
1.0000000000
```
-----
```input
1
-1 0 0 1 1 0 0 -1
```
```output
1.0000000000
```
-----
```input
4
0 0 0 1 3 1 3 0
0 0 0 3 1 3 1 0
3 3 2 3 2 0 3 0
3 3 3 2 0 2 0 3
```
```output
1.5000000000
```
-----
```input
2
-1 0 0 1 1 0 0 -1
0 0 1 1 2 0 1 -1
```
```output
1.1428571429
```

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 is a house with $$$n$$$ flats situated on the main street of Berlatov. Vova is watching this house every night. The house can be represented as an array of $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i = 1$$$ if in the $$$i$$$-th flat the light is on and $$$a_i = 0$$$ otherwise.

Vova thinks that people in the $$$i$$$-th flats are disturbed and cannot sleep if and only if $$$1 < i < n$$$ and $$$a_{i - 1} = a_{i + 1} = 1$$$ and $$$a_i = 0$$$.

Vova is concerned by the following question: what is the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the lights then nobody will be disturbed? Your task is to find this number $$$k$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of flats in the house.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{0, 1\}$$$), where $$$a_i$$$ is the state of light in the $$$i$$$-th flat.

## Output Format
Print only one integer — the minimum number $$$k$$$ such that if people from exactly $$$k$$$ pairwise distinct flats will turn off the light then nobody will be disturbed.

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

## Note
In the first example people from flats $$$2$$$ and $$$7$$$ or $$$4$$$ and $$$7$$$ can turn off the light and nobody will be disturbed. It can be shown that there is no better answer in this example.

There are no disturbed people in second and third examples.

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
Polycarp has prepared $$$n$$$ competitive programming problems. The topic of the $$$i$$$-th problem is $$$a_i$$$, and some problems' topics may coincide.

Polycarp has to host several thematic contests. All problems in each contest should have the same topic, and all contests should have pairwise distinct topics. He may not use all the problems. It is possible that there are no contests for some topics.

Polycarp wants to host competitions on consecutive days, one contest per day. Polycarp wants to host a set of contests in such a way that:

- number of problems in each contest is exactly twice as much as in the previous contest (one day ago), the first contest can contain arbitrary number of problems;
- the total number of problems in all the contests should be maximized.

Your task is to calculate the maximum number of problems in the set of thematic contests. Note, that you should not maximize the number of contests.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of problems Polycarp has prepared.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) where $$$a_i$$$ is the topic of the $$$i$$$-th problem.

## Output Format
Print one integer — the maximum number of problems in the set of thematic contests.

## Examples
```input
18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10
```
```output
14
```
-----
```input
10
6 6 6 3 6 1000000000 3 3 6 6
```
```output
9
```
-----
```input
3
1337 1337 1337
```
```output
3
```

## Note
In the first example the optimal sequence of contests is: $$$2$$$ problems of the topic $$$1$$$, $$$4$$$ problems of the topic $$$2$$$, $$$8$$$ problems of the topic $$$10$$$.

In the second example the optimal sequence of contests is: $$$3$$$ problems of the topic $$$3$$$, $$$6$$$ problems of the topic $$$6$$$.

In the third example you can take all the problems with the topic $$$1337$$$ (the number of such problems is $$$3$$$ so the answer is $$$3$$$) and host a single contest.

Now solve the problem and return the code.