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

# Problem
You are given a binary string $$$s$$$.

Find the number of distinct cyclical binary strings of length $$$n$$$ which contain $$$s$$$ as a substring.

The cyclical string $$$t$$$ contains $$$s$$$ as a substring if there is some cyclical shift of string $$$t$$$, such that $$$s$$$ is a substring of this cyclical shift of $$$t$$$.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the target string $$$t$$$.

The next line contains the string $$$s$$$ ($$$1 \le |s| \le n$$$) — the string which must be a substring of cyclical string $$$t$$$. String $$$s$$$ contains only characters '0' and '1'.

## Output Format
Print the only integer — the number of distinct cyclical binary strings $$$t$$$, which contain $$$s$$$ as a substring.

## Examples
```input
2
0
```
```output
3
```
-----
```input
4
1010
```
```output
2
```
-----
```input
20
10101010101010
```
```output
962
```

## Note
In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

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
There are $$$n$$$ benches in the Berland Central park. It is known that $$$a_i$$$ people are currently sitting on the $$$i$$$-th bench. Another $$$m$$$ people are coming to the park and each of them is going to have a seat on some bench out of $$$n$$$ available.

Let $$$k$$$ be the maximum number of people sitting on one bench after additional $$$m$$$ people came to the park. Calculate the minimum possible $$$k$$$ and the maximum possible $$$k$$$.

Nobody leaves the taken seat during the whole process.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number of benches in the park.

The second line contains a single integer $$$m$$$ $$$(1 \le m \le 10\,000)$$$ — the number of people additionally coming to the park.

Each of the next $$$n$$$ lines contains a single integer $$$a_i$$$ $$$(1 \le a_i \le 100)$$$ — the initial number of people on the $$$i$$$-th bench.

## Output Format
Print the minimum possible $$$k$$$ and the maximum possible $$$k$$$, where $$$k$$$ is the maximum number of people sitting on one bench after additional $$$m$$$ people came to the park.

## Examples
```input
4
6
1
1
1
1
```
```output
3 7
```
-----
```input
1
10
5
```
```output
15 15
```
-----
```input
3
6
1
6
5
```
```output
6 12
```
-----
```input
3
7
1
6
5
```
```output
7 13
```

## Note
In the first example, each of four benches is occupied by a single person. The minimum $$$k$$$ is $$$3$$$. For example, it is possible to achieve if two newcomers occupy the first bench, one occupies the second bench, one occupies the third bench, and two remaining — the fourth bench. The maximum $$$k$$$ is $$$7$$$. That requires all six new people to occupy the same bench.

The second example has its minimum $$$k$$$ equal to $$$15$$$ and maximum $$$k$$$ equal to $$$15$$$, as there is just a single bench in the park and all $$$10$$$ people will occupy it.

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
Petya has an array $$$a$$$ consisting of $$$n$$$ integers. He has learned partial sums recently, and now he can calculate the sum of elements on any segment of the array really fast. The segment is a non-empty sequence of elements standing one next to another in the array.

Now he wonders what is the number of segments in his array with the sum less than $$$t$$$. Help Petya to calculate this number.

More formally, you are required to calculate the number of pairs $$$l, r$$$ ($$$l \le r$$$) such that $$$a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 200\,000, |t| \le 2\cdot10^{14}$$$).

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$|a_{i}| \le 10^{9}$$$) — the description of Petya's array. Note that there might be negative, zero and positive elements.

## Output Format
Print the number of segments in Petya's array with the sum of elements less than $$$t$$$.

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

## Note
In the first example the following segments have sum less than $$$4$$$:

- $$$[2, 2]$$$, sum of elements is $$$-1$$$
- $$$[2, 3]$$$, sum of elements is $$$2$$$
- $$$[3, 3]$$$, sum of elements is $$$3$$$
- $$$[4, 5]$$$, sum of elements is $$$3$$$
- $$$[5, 5]$$$, sum of elements is $$$-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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an undirected tree, consisting of $$$n$$$ vertices.

The vertex is called a leaf if it has exactly one vertex adjacent to it.

The distance between some pair of vertices is the number of edges in the shortest path between them.

Let's call some set of leaves beautiful if the maximum distance between any pair of leaves in it is less or equal to $$$k$$$.

You want to split all leaves into non-intersecting beautiful sets. What is the minimal number of sets in such a split?

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 10^6$$$, $$$1 \le k \le 10^6$$$) — the number of vertices in the tree and the maximum distance between any pair of leaves in each beautiful set.

Each of the next $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the description of the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

## Output Format
Print a single integer — the minimal number of beautiful sets the split can have.

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

## Note
Here is the graph for 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: 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 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
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 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: 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 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
You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters.

A substring of string $$$s$$$ is a continuous segment of letters from $$$s$$$. For example, "defor" is a substring of "codeforces" and "fors" is not.

The length of the substring is the number of letters in it.

Let's call some string of length $$$n$$$ diverse if and only if there is no letter to appear strictly more than $$$\frac n 2$$$ times. For example, strings "abc" and "iltlml" are diverse and strings "aab" and "zz" are not.

Your task is to find any diverse substring of string $$$s$$$ or report that there is none. Note that it is not required to maximize or minimize the length of the resulting substring.

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

The second line is the string $$$s$$$, consisting of exactly $$$n$$$ lowercase Latin letters.

## Output Format
Print "NO" if there is no diverse substring in the string $$$s$$$.

Otherwise the first line should contain "YES". The second line should contain any diverse substring of string $$$s$$$.

## Examples
```input
10
codeforces
```
```output
YES
code
```
-----
```input
5
aaaaa
```
```output
NO
```

## Note
The first example has lots of correct answers.

Please, restrain yourself from asking if some specific answer is correct for some specific test or not, these questions always lead to "No comments" answer.

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
Vasya has got $$$n$$$ books, numbered from $$$1$$$ to $$$n$$$, arranged in a stack. The topmost book has number $$$a_1$$$, the next one — $$$a_2$$$, and so on. The book at the bottom of the stack has number $$$a_n$$$. All numbers are distinct.

Vasya wants to move all the books to his backpack in $$$n$$$ steps. During $$$i$$$-th step he wants to move the book number $$$b_i$$$ into his backpack. If the book with number $$$b_i$$$ is in the stack, he takes this book and all the books above the book $$$b_i$$$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $$$[1, 2, 3]$$$ (book $$$1$$$ is the topmost), and Vasya moves the books in the order $$$[2, 1, 3]$$$, then during the first step he will move two books ($$$1$$$ and $$$2$$$), during the second step he will do nothing (since book $$$1$$$ is already in the backpack), and during the third step — one book (the book number $$$3$$$). Note that $$$b_1, b_2, \dots, b_n$$$ are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.

## Input Format
The first line contains one integer $$$n~(1 \le n \le 2 \cdot 10^5)$$$ — the number of books in the stack.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(1 \le a_i \le n)$$$ denoting the stack of books.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n~(1 \le b_i \le n)$$$ denoting the steps Vasya is going to perform.

All numbers $$$a_1 \dots a_n$$$ are distinct, the same goes for $$$b_1 \dots b_n$$$.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of books Vasya moves to his backpack during the $$$i$$$-th step.

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

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

In the second example, during the first step Vasya will move the books $$$[3, 1, 4]$$$. After that only books $$$2$$$ and $$$5$$$ remain in the stack ($$$2$$$ is above $$$5$$$). During the second step Vasya will take the books $$$2$$$ and $$$5$$$. After that the stack becomes empty, so during next steps Vasya won't move any books.

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
XXI Berland Annual Fair is coming really soon! Traditionally fair consists of $$$n$$$ booths, arranged in a circle. The booths are numbered $$$1$$$ through $$$n$$$ clockwise with $$$n$$$ being adjacent to $$$1$$$. The $$$i$$$-th booths sells some candies for the price of $$$a_i$$$ burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most $$$T$$$ burles at the fair. However, he has some plan in mind for his path across the booths:

- at first, he visits booth number $$$1$$$;
- if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;
- then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not).

Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.

## Input Format
The first line contains two integers $$$n$$$ and $$$T$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le T \le 10^{18}$$$) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the price of the single candy at booth number $$$i$$$.

## Output Format
Print a single integer — the total number of candies Polycarp will buy.

## Examples
```input
3 38
5 2 5
```
```output
10
```
-----
```input
5 21
2 4 100 2 6
```
```output
6
```

## Note
Let's consider the first example. Here are Polycarp's moves until he runs out of money:

1. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 33$$$;
2. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 31$$$;
3. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 26$$$;
4. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 21$$$;
5. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 19$$$;
6. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 14$$$;
7. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 9$$$;
8. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 7$$$;
9. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 2$$$;
10. Booth $$$1$$$, buys no candy, not enough money;
11. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 0$$$.

No candy can be bought later. The total number of candies bought is $$$10$$$.

In the second example he has $$$1$$$ burle left at the end of his path, no candy can be bought with this amount.

Now solve the problem and return the code.