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

# Problem
Mr Keks is a typical white-collar in Byteland.

He has a bookshelf in his office with some books on it, each book has an integer positive price.

Mr Keks defines the value of a shelf as the sum of books prices on it.

Miraculously, Mr Keks was promoted and now he is moving into a new office.

He learned that in the new office he will have not a single bookshelf, but exactly $$$k$$$ bookshelves. He decided that the beauty of the $$$k$$$ shelves is the bitwise AND of the values of all the shelves.

He also decided that he won't spend time on reordering the books, so he will place several first books on the first shelf, several next books on the next shelf and so on. Of course, he will place at least one book on each shelf. This way he will put all his books on $$$k$$$ shelves in such a way that the beauty of the shelves is as large as possible. Compute this maximum possible beauty.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 50$$$) — the number of books and the number of shelves in the new office.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$, ($$$0 < a_i < 2^{50}$$$) — the prices of the books in the order they stand on the old shelf.

## Output Format
Print the maximum possible beauty of $$$k$$$ shelves in the new office.

## Examples
```input
10 4
9 14 28 1 7 13 15 29 2 31
```
```output
24
```
-----
```input
7 3
3 14 15 92 65 35 89
```
```output
64
```

## Note
In the first example you can split the books as follows:

$$$$$$(9 + 14 + 28 + 1 + 7) \& (13 + 15) \& (29 + 2) \& (31) = 24.$$$$$$

In the second example you can split the books as follows:

$$$$$$(3 + 14 + 15 + 92) \& (65) \& (35 + 89) = 64.$$$$$$

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
It's marriage season in Ringland!

Ringland has a form of a circle's boundary of length $$$L$$$. There are $$$n$$$ bridegrooms and $$$n$$$ brides, and bridegrooms decided to marry brides.

Of course, each bridegroom should choose exactly one bride, and each bride should be chosen by exactly one bridegroom.

All objects in Ringland are located on the boundary of the circle, including the capital, bridegrooms' castles and brides' palaces. The castle of the $$$i$$$-th bridegroom is located at the distance $$$a_i$$$ from the capital in clockwise direction, and the palace of the $$$i$$$-th bride is located at the distance $$$b_i$$$ from the capital in clockwise direction.

Let's define the inconvenience of a marriage the maximum distance that some bride should walk along the circle from her palace to her bridegroom's castle in the shortest direction (in clockwise or counter-clockwise direction).

Help the bridegrooms of Ringland to choose brides in such a way that the inconvenience of the marriage is the smallest possible.

## Input Format
The first line contains two integers $$$n$$$ and $$$L$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$, $$$1 \leq L \leq 10^{9}$$$) — the number of bridegrooms and brides and the length of Ringland.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < L$$$) — the distances from the capital to the castles of bridegrooms in clockwise direction.

The next line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i < L$$$) — the distances from the capital to the palaces of brides in clockwise direction.

## Output Format
In the only line print the smallest possible inconvenience of the wedding, where the inconvenience is the largest distance traveled by a bride.

## Examples
```input
2 4
0 1
2 3
```
```output
1
```
-----
```input
10 100
3 14 15 92 65 35 89 79 32 38
2 71 82 81 82 84 5 90 45 23
```
```output
27
```

## Note
In the first example the first bridegroom should marry the second bride, the second bridegroom should marry the first bride. This way, the second bride should walk the distance of $$$1$$$, and the first bride should also walk the same distance. Thus, the inconvenience is equal to $$$1$$$.

In the second example let $$$p_i$$$ be the bride the $$$i$$$-th bridegroom will marry. One of optimal $$$p$$$ is the following: $$$(6,8,1,4,5,10,3,2,7,9)$$$.

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
Allen is playing Number Clicker on his phone.

He starts with an integer $$$u$$$ on the screen. Every second, he can press one of 3 buttons.

1. Turn $$$u \to u+1 \pmod{p}$$$.
2. Turn $$$u \to u+p-1 \pmod{p}$$$.
3. Turn $$$u \to u^{p-2} \pmod{p}$$$.

Allen wants to press at most 200 buttons and end up with $$$v$$$ on the screen. Help him!

## Input Format
The first line of the input contains 3 positive integers: $$$u, v, p$$$ ($$$0 \le u, v \le p-1$$$, $$$3 \le p \le 10^9 + 9$$$). $$$p$$$ is guaranteed to be prime.

## Output Format
On the first line, print a single integer $$$\ell$$$, the number of button presses. On the second line, print integers $$$c_1, \dots, c_\ell$$$, the button presses. For $$$1 \le i \le \ell$$$, $$$1 \le c_i \le 3$$$.

We can show that the answer always exists.

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

## Note
In the first example the integer on the screen changes as $$$1 \to 2 \to 3$$$.

In the second example the integer on the screen changes as $$$3 \to 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
Allen, having graduated from the MOO Institute of Techcowlogy (MIT), has started a startup! Allen is the president of his startup. He also hires $$$n-1$$$ other employees, each of which is assigned a direct superior. If $$$u$$$ is a superior of $$$v$$$ and $$$v$$$ is a superior of $$$w$$$ then also $$$u$$$ is a superior of $$$w$$$. Additionally, there are no $$$u$$$ and $$$v$$$ such that $$$u$$$ is the superior of $$$v$$$ and $$$v$$$ is the superior of $$$u$$$. Allen himself has no superior. Allen is employee number $$$1$$$, and the others are employee numbers $$$2$$$ through $$$n$$$.

Finally, Allen must assign salaries to each employee in the company including himself. Due to budget constraints, each employee's salary is an integer between $$$1$$$ and $$$D$$$. Additionally, no employee can make strictly more than his superior.

Help Allen find the number of ways to assign salaries. As this number may be large, output it modulo $$$10^9 + 7$$$.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$D$$$ ($$$1 \le n \le 3000$$$, $$$1 \le D \le 10^9$$$).

The remaining $$$n-1$$$ lines each contain a single positive integer, where the $$$i$$$-th line contains the integer $$$p_i$$$ ($$$1 \le p_i \le i$$$). $$$p_i$$$ denotes the direct superior of employee $$$i+1$$$.

## Output Format
Output a single integer: the number of ways to assign salaries modulo $$$10^9 + 7$$$.

## Examples
```input
3 2
1
1
```
```output
5
```
-----
```input
3 3
1
2
```
```output
10
```
-----
```input
2 5
1
```
```output
15
```

## Note
In the first sample case, employee 2 and 3 report directly to Allen. The three salaries, in order, can be $$$(1,1,1)$$$, $$$(2,1,1)$$$, $$$(2,1,2)$$$, $$$(2,2,1)$$$ or $$$(2,2,2)$$$.

In the second sample case, employee 2 reports to Allen and employee 3 reports to employee 2. In order, the possible salaries are $$$(1,1,1)$$$, $$$(2,1,1)$$$, $$$(2,2,1)$$$, $$$(2,2,2)$$$, $$$(3,1,1)$$$, $$$(3,2,1)$$$, $$$(3,2,2)$$$, $$$(3,3,1)$$$, $$$(3,3,2)$$$, $$$(3,3,3)$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Mishka started participating in a programming contest. There are $$$n$$$ problems in the contest. Mishka's problem-solving skill is equal to $$$k$$$.

Mishka arranges all problems from the contest into a list. Because of his weird principles, Mishka only solves problems from one of the ends of the list. Every time, he chooses which end (left or right) he will solve the next problem from. Thus, each problem Mishka solves is either the leftmost or the rightmost problem in the list.

Mishka cannot solve a problem with difficulty greater than $$$k$$$. When Mishka solves the problem, it disappears from the list, so the length of the list decreases by $$$1$$$. Mishka stops when he is unable to solve any problem from any end of the list.

How many problems can Mishka solve?

## Input Format
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 100$$$) — the number of problems in the contest and Mishka's problem-solving skill.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the difficulty of the $$$i$$$-th problem. The problems are given in order from the leftmost to the rightmost in the list.

## Output Format
Print one integer — the maximum number of problems Mishka can solve.

## Examples
```input
8 4
4 2 3 1 5 1 6 4
```
```output
5
```
-----
```input
5 2
3 1 2 1 3
```
```output
0
```
-----
```input
5 100
12 34 55 43 21
```
```output
5
```

## Note
In the first example, Mishka can solve problems in the following order: $$$[4, 2, 3, 1, 5, 1, 6, 4] \rightarrow [2, 3, 1, 5, 1, 6, 4] \rightarrow [2, 3, 1, 5, 1, 6] \rightarrow [3, 1, 5, 1, 6] \rightarrow [1, 5, 1, 6] \rightarrow [5, 1, 6]$$$, so the number of solved problems will be equal to $$$5$$$.

In the second example, Mishka can't solve any problem because the difficulties of problems from both ends are greater than $$$k$$$.

In the third example, Mishka's solving skill is so amazing that he can solve all the problems.

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
A string $$$s$$$ of length $$$n$$$ can be encrypted by the following algorithm:

- iterate over all divisors of $$$n$$$ in decreasing order (i.e. from $$$n$$$ to $$$1$$$),
- for each divisor $$$d$$$, reverse the substring $$$s[1 \dots d]$$$ (i.e. the substring which starts at position $$$1$$$ and ends at position $$$d$$$).

For example, the above algorithm applied to the string $$$s$$$="codeforces" leads to the following changes: "codeforces" $$$\to$$$ "secrofedoc" $$$\to$$$ "orcesfedoc" $$$\to$$$ "rocesfedoc" $$$\to$$$ "rocesfedoc" (obviously, the last reverse operation doesn't change the string because $$$d=1$$$).

You are given the encrypted string $$$t$$$. Your task is to decrypt this string, i.e., to find a string $$$s$$$ such that the above algorithm results in string $$$t$$$. It can be proven that this string $$$s$$$ always exists and is unique.

## Input Format
The first line of input consists of a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the string $$$t$$$. The second line of input consists of the string $$$t$$$. The length of $$$t$$$ is $$$n$$$, and it consists only of lowercase Latin letters.

## Output Format
Print a string $$$s$$$ such that the above algorithm results in $$$t$$$.

## Examples
```input
10
rocesfedoc
```
```output
codeforces
```
-----
```input
16
plmaetwoxesisiht
```
```output
thisisexampletwo
```
-----
```input
1
z
```
```output
z
```

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

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 string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters. Polycarp wants to remove exactly $$$k$$$ characters ($$$k \le n$$$) from the string $$$s$$$. Polycarp uses the following algorithm $$$k$$$ times:

- if there is at least one letter 'a', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
- if there is at least one letter 'b', remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
- ...
- remove the leftmost occurrence of the letter 'z' and stop the algorithm.

This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly $$$k$$$ times, thus removing exactly $$$k$$$ characters.

Help Polycarp find the resulting string.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 4 \cdot 10^5$$$) — the length of the string and the number of letters Polycarp will remove.

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

## Output Format
Print the string that will be obtained from $$$s$$$ after Polycarp removes exactly $$$k$$$ letters using the above algorithm $$$k$$$ times.

If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).

## Examples
```input
15 3
cccaabababaccbc
```
```output
cccbbabaccbc
```
-----
```input
15 9
cccaabababaccbc
```
```output
cccccc
```
-----
```input
1 1
u
```
```output

```

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
There are $$$n$$$ cities and $$$m$$$ roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.

## Input Format
The first line of input consists of three integers $$$n$$$, $$$m$$$ and $$$s$$$ ($$$1 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le n$$$) — the number of cities, the number of roads and the index of the capital. Cities are indexed from $$$1$$$ to $$$n$$$.

The following $$$m$$$ lines contain roads: road $$$i$$$ is given as a pair of cities $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$). For each pair of cities $$$(u, v)$$$, there can be at most one road from $$$u$$$ to $$$v$$$. Roads in opposite directions between a pair of cities are allowed (i.e. from $$$u$$$ to $$$v$$$ and from $$$v$$$ to $$$u$$$).

## Output Format
Print one integer — the minimum number of extra roads needed to make all the cities reachable from city $$$s$$$. If all the cities are already reachable from $$$s$$$, print 0.

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

## Note
The first example is illustrated by the following:

For example, you can add roads ($$$6, 4$$$), ($$$7, 9$$$), ($$$1, 7$$$) to make all the cities reachable from $$$s = 1$$$.

The second example is illustrated by the following:

In this example, you can add any one of the roads ($$$5, 1$$$), ($$$5, 2$$$), ($$$5, 3$$$), ($$$5, 4$$$) to make all the cities reachable from $$$s = 5$$$.

Now solve the problem and return the code.