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

# Problem
The good times at Heidi's library are over. Marmots finally got their internet connections and stopped coming to the library altogether. Not only that, but the bookstore has begun charging extortionate prices for some books. Namely, whereas in the previous versions each book could be bought for 1 CHF, now the price of book i is ci CHF.

## Input Format
The first line of input will contain two integers n and k ($${ 1 \leq n, k \leq 8 0 }$$). The second line will contain n integers a1, a2, ..., an (1 ≤ ai ≤ n) – the sequence of book requests. The third line contains n integers c1, c2, ..., cn (0 ≤ ci ≤ 106) – the costs of the books.

## Output Format
On a single line print the minimum cost of buying books at the store so as to satisfy all requests.

## Examples
```input
4 80
1 2 2 1
1 1 1 1
```
```output
2
```
-----
```input
4 1
1 2 2 1
1 1 1 1
```
```output
3
```
-----
```input
4 2
1 2 3 1
1 1 1 1
```
```output
3
```
-----
```input
7 2
1 2 3 1 1 1 2
1 10 1 0 0 0 0
```
```output
13
```

## Note
The first three sample cases are repeated, but the fourth one is new.

In the fourth test case, when buying book 3, Heidi should discard either book 1 or 2. Even though book 2 will be requested later than book 1, she should keep it, because it is so expensive to buy again.

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
As it's the first of April, Heidi is suspecting that the news she reads today are fake, and she does not want to look silly in front of all the contestants. She knows that a newspiece is fake if it contains heidi as a subsequence. Help Heidi assess whether the given piece is true, but please be discreet about it...

## Input Format
The first and only line of input contains a single nonempty string s of length at most 1000 composed of lowercase letters (a-z).

## Output Format
Output YES if the string s contains heidi as a subsequence and NO otherwise.

## Examples
```input
abcheaibcdi
```
```output
YES
```
-----
```input
hiedi
```
```output
NO
```

## Note
A string s contains another string p as a subsequence if it is possible to delete some characters from s and obtain p.

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
Thanks to your help, Heidi is confident that no one can fool her. She has now decided to post some fake news on the HC2 Facebook page. However, she wants to be able to communicate to the HC2 committee that the post is fake, using some secret phrase hidden in the post as a subsequence. To make this method foolproof, she wants the phrase to appear n times in the post. She is asking you to design a post (string) s and a hidden phrase p such that p appears in s as a subsequence exactly n times.

## Input Format
The first and only line of input contains a single integer n (1 ≤ n ≤ 1 000 000).

## Output Format
The output should contain two nonempty strings s and p separated by a single space. Each string should be composed of letters (a-z and A-Z: both lowercase and uppercase are allowed) and have length at most 200. The number of occurrences of p in s as a subsequence should be exactly n. If there are many possible solutions, output any of them. It is guaranteed that at least one solution exists.

## Examples
```input
2
```
```output
hHheidi Hei
```
-----
```input
4
```
```output
bbbba ba
```
-----
```input
6
```
```output
aaabb ab
```

## Note
An occurrence of p as a subsequence in s should be thought of as a set of positions in s such that the letters at these positions, in order, form p. The number of occurences is thus the number of such sets. For example, ab appears 6 times as a subsequence in aaabb, for the following sets of positions: {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5} (that is, we should choose one of the a's and one of the b's).

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
Karen is getting ready for a new school day!

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

## Input Format
The first and only line of input contains a single string in the format hh:mm (00 ≤  hh  ≤ 23, 00 ≤  mm  ≤ 59).

## Output Format
Output a single integer on a line by itself, the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome.

## Examples
```input
05:39
```
```output
11
```
-----
```input
13:31
```
```output
0
```
-----
```input
23:59
```
```output
1
```

## Note
In the first test case, the minimum number of minutes Karen should sleep for is 11. She can wake up at 05:50, when the time is a palindrome.

In the second test case, Karen can wake up immediately, as the current time, 13:31, is already a palindrome.

In the third test case, the minimum number of minutes Karen should sleep for is 1 minute. She can wake up at 00:00, when the time is a palindrome.

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

# Problem
One quite ordinary day Valera went to school (there's nowhere else he should go on a week day). In a maths lesson his favorite teacher Ms. Evans told students about divisors. Despite the fact that Valera loved math, he didn't find this particular topic interesting. Even more, it seemed so boring that he fell asleep in the middle of a lesson. And only a loud ringing of a school bell could interrupt his sweet dream.

Of course, the valuable material and the teacher's explanations were lost. However, Valera will one way or another have to do the homework. As he does not know the new material absolutely, he cannot do the job himself. That's why he asked you to help. You're his best friend after all, you just cannot refuse to help.

Valera's home task has only one problem, which, though formulated in a very simple way, has not a trivial solution. Its statement looks as follows: if we consider all positive integers in the interval [a;b] then it is required to count the amount of such numbers in this interval that their smallest divisor will be a certain integer k (you do not have to consider divisor equal to one). In other words, you should count the amount of such numbers from the interval [a;b], that are not divisible by any number between 2 and k - 1 and yet are divisible by k.

## Input Format
The first and only line contains three positive integers a, b, k (1 ≤ a ≤ b ≤ 2·109, 2 ≤ k ≤ 2·109).

## Output Format
Print on a single line the answer to the given problem.

## Examples
```input
1 10 2
```
```output
5
```
-----
```input
12 23 3
```
```output
2
```
-----
```input
6 19 5
```
```output
0
```

## Note
Comments to the samples from the statement:

In the first sample the answer is numbers 2, 4, 6, 8, 10.

In the second one — 15, 21

In the third one there are no such numbers.

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
On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {a1, a2, ..., an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let's define the compression function:

- f(empty sequence) = empty string
- f(s) = s.
- f(s1, s2) =  the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
- f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Valera faces a real challenge: he should divide the given sequence {a1, a2, ..., an} into two subsequences {b1, b2, ..., bk} and {c1, c2, ..., cm}, m + k = n, so that the value of S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don't have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.

## Input Format
The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.

## Output Format
Print a single number — the minimum possible value of S.

## Examples
```input
3
01
10
01
```
```output
4
```
-----
```input
4
000
111
110
001
```
```output
8
```
-----
```input
5
10101
01010
11111
01000
10010
```
```output
17
```

## Note
Detailed answers to the tests:

- The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
- The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
- The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

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
Where do odds begin, and where do they end? Where does hope emerge, and will they ever break?

Given an integer sequence a1, a2, ..., an of length n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.

A subsegment is a contiguous slice of the whole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence {1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.

## Input Format
The first line of input contains a non-negative integer n (1 ≤ n ≤ 100) — the length of the sequence.

The second line contains n space-separated non-negative integers a1, a2, ..., an (0 ≤ ai ≤ 100) — the elements of the sequence.

## Output Format
Output "Yes" if it's possible to fulfill the requirements, and "No" otherwise.

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

## Examples
```input
3
1 3 5
```
```output
Yes
```
-----
```input
5
1 0 1 5 1
```
```output
Yes
```
-----
```input
3
4 3 1
```
```output
No
```
-----
```input
4
3 9 9 3
```
```output
No
```

## Note
In the first example, divide the sequence into 1 subsegment: {1, 3, 5} and the requirements will be met.

In the second example, divide the sequence into 3 subsegments: {1, 0, 1}, {5}, {1}.

In the third example, one of the subsegments must start with 4 which is an even number, thus the requirements cannot be met.

In the fourth example, the sequence can be divided into 2 subsegments: {3, 9, 9}, {3}, but this is not a valid solution because 2 is an even number.

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
Connect the countless points with lines, till we reach the faraway yonder.

There are n points on a coordinate plane, the i-th of which being (i, yi).

Determine whether it's possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.

## Input Format
The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.

The second line contains n space-separated integers y1, y2, ..., yn ( - 109 ≤ yi ≤ 109) — the vertical coordinates of each point.

## Output Format
Output "Yes" (without quotes) if it's possible to fulfill the requirements, and "No" otherwise.

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

## Examples
```input
5
7 5 8 6 9
```
```output
Yes
```
-----
```input
5
-1 -2 0 0 -5
```
```output
No
```
-----
```input
5
5 4 3 2 1
```
```output
No
```
-----
```input
5
1000000000 0 0 0 0
```
```output
Yes
```

## Note
In the first example, there are five points: (1, 7), (2, 5), (3, 8), (4, 6) and (5, 9). It's possible to draw a line that passes through points 1, 3, 5, and another one that passes through points 2, 4 and is parallel to the first one.

In the second example, while it's possible to draw two lines that cover all points, they cannot be made parallel.

In the third example, it's impossible to satisfy both requirements at the same time.

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
Arpa is taking a geometry exam. Here is the last problem of the exam.

You are given three points a, b, c.

Find a point and an angle such that if we rotate the page around the point by the angle, the new position of a is the same as the old position of b, and the new position of b is the same as the old position of c.

Arpa is doubting if the problem has a solution or not (i.e. if there exists a point and an angle satisfying the condition). Help Arpa determine if the question has a solution or not.

## Input Format
The only line contains six integers ax, ay, bx, by, cx, cy (|ax|, |ay|, |bx|, |by|, |cx|, |cy| ≤ 109). It's guaranteed that the points are distinct.

## Output Format
Print "Yes" if the problem has a solution, "No" otherwise.

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

## Examples
```input
0 1 1 1 1 0
```
```output
Yes
```
-----
```input
1 1 0 0 1000 1000
```
```output
No
```

## Note
In the first sample test, rotate the page around (0.5, 0.5) by $$90^\circ$$.

In the second sample test, you can't find any solution.

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
Arkady words in a large company. There are n employees working in a system of a strict hierarchy. Namely, each employee, with an exception of the CEO, has exactly one immediate manager. The CEO is a manager (through a chain of immediate managers) of all employees.

Each employee has an integer rank. The CEO has rank equal to 1, each other employee has rank equal to the rank of his immediate manager plus 1.

Arkady has a good post in the company, however, he feels that he is nobody in the company's structure, and there are a lot of people who can replace him. He introduced the value of replaceability. Consider an employee a and an employee b, the latter being manager of a (not necessarily immediate). Then the replaceability r(a, b) of a with respect to b is the number of subordinates (not necessarily immediate) of the manager b, whose rank is not greater than the rank of a. Apart from replaceability, Arkady introduced the value of negligibility. The negligibility za of employee a equals the sum of his replaceabilities with respect to all his managers, i.e. $$z_{a} = \sum_{b} r(a,b)$$, where the sum is taken over all his managers b.

Arkady is interested not only in negligibility of himself, but also in negligibility of all employees in the company. Find the negligibility of each employee for Arkady.

## Input Format
The first line contains single integer n (1 ≤ n ≤ 5·105) — the number of employees in the company.

The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ n), where pi = 0 if the i-th employee is the CEO, otherwise pi equals the id of the immediate manager of the employee with id i. The employees are numbered from 1 to n. It is guaranteed that there is exactly one 0 among these values, and also that the CEO is a manager (not necessarily immediate) for all the other employees.

## Output Format
Print n integers — the negligibilities of all employees in the order of their ids: z1, z2, ..., zn.

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

## Note
Consider the first example:

- The CEO has no managers, thus z1 = 0.
- r(2, 1) = 2 (employees 2 and 4 suit the conditions, employee 3 has too large rank). Thus z2 = r(2, 1) = 2.
- Similarly, z4 = r(4, 1) = 2.
- r(3, 2) = 1 (employee 3 is a subordinate of 2 and has suitable rank). r(3, 1) = 3 (employees 2, 3, 4 suit the conditions). Thus z3 = r(3, 2) + r(3, 1) = 4.

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
A sequence of n integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let x and y be two adjacent numbers (x before y), then he can remove them and write x + 2y instead of them. He will perform these operations until one number is left. Sasha likes big numbers and will get the biggest possible number.

Nikita wants to get to the blackboard before Sasha and erase some of the numbers. He has q options, in the option i he erases all numbers to the left of the li-th number and all numbers to the right of ri-th number, i. e. all numbers between the li-th and the ri-th, inclusive, remain on the blackboard. For each of the options he wants to know how big Sasha's final number is going to be. This number can be very big, so output it modulo 109 + 7.

## Input Format
The first line contains two integers n and q (1 ≤ n, q ≤ 105) — the number of integers on the blackboard and the number of Nikita's options.

The next line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence on the blackboard.

Each of the next q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing Nikita's options.

## Output Format
For each option output Sasha's result modulo 109 + 7.

## Examples
```input
3 3
1 2 3
1 3
1 2
2 3
```
```output
17
5
8
```
-----
```input
3 1
1 2 -3
1 3
```
```output
1000000006
```
-----
```input
4 2
1 1 1 -1
1 4
3 4
```
```output
5
1000000006
```

## Note
In the second sample Nikita doesn't erase anything. Sasha first erases the numbers 1 and 2 and writes 5. Then he erases 5 and -3 and gets -1. -1 modulo 109 + 7 is 109 + 6.

Now solve the problem and return the code.