vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Paths in a Complete Binary Tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
*T* is a complete binary tree consisting of *n* vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn't have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So *n* is a number such that *n*<=+<=1 is a power of 2.

In the picture you can see a complete binary tree with *n*<==<=15.

Vertices are numbered from 1 to *n* in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.

You have to write a program that for given *n* answers *q* queries to the tree.

Each query consists of an integer number *u**i* (1<=≤<=*u**i*<=≤<=*n*) and a string *s**i*, where *u**i* is the number of vertex, and *s**i* represents the path starting from this vertex. String *s**i* doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from *s**i* have to be processed from left to right, considering that *u**i* is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by *s**i* ends.

For example, if *u**i*<==<=4 and *s**i*<==<=«UURL», then the answer is 10.

Input Specification:
The first line contains two integer numbers *n* and *q* (1<=≤<=*n*<=≤<=1018, *q*<=≥<=1). *n* is such that *n*<=+<=1 is a power of 2.

The next 2*q* lines represent queries; each query consists of two consecutive lines. The first of these two lines contains *u**i* (1<=≤<=*u**i*<=≤<=*n*), the second contains non-empty string *s**i*. *s**i* doesn't contain any characters other than 'L', 'R' and 'U'.

It is guaranteed that the sum of lengths of *s**i* (for each *i* such that 1<=≤<=*i*<=≤<=*q*) doesn't exceed 105.

Output Specification:
Print *q* numbers, *i*-th number must be the answer to the *i*-th query.

Demo Input:
['15 2\n4\nUURL\n8\nLRLLLLLLLL\n']

Demo Output:
['10\n5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While browsing YouTube videos, you commonly use the handy dandy tool that is Add Video to Watch Later. One day you finally decide that ‘Later’ has finally arrived and you have SO many videos in your list.

You have a list of videos with different types. For example, some might be bouldering videos, some might be cat videos, and so on. You want to watch all videos of the same type before you watch videos of a different type, but you are allowed to watch the video types in any order you wish. For example, you might want to watch all bouldering videos before watching any cat videos.

To start watching, you have to click on a video to play it. You may click on any video in your list to start watching that video. Whenever a video finishes playing, it is automatically deleted from the list. The order of the remaining videos does not change when a video finishes playing. Also, the next video in the list is automatically played if it is of the same type as the video you just watched. If it is of a different type, or if there is no video after the one you just watched, you must click on another video in the list to watch more videos (unless you have watched all videos).

Given the description of your Watch Later list, what is the minimum number of clicks needed to watch every video with the restrictions described above?

-----Input-----
The first line of the input contains two integers $n$ ($1 \leq n \leq 400$), the number of videos in your Watch Later list, and $k$ ($1 \leq k \leq 20$), the number of different video types in the list.

The second line of input contains a string of length $n$ which describes the Watch Later list. The $i^\textrm {th}$ character in the string is a lowercase English letter which describes the type of the $i^\textrm {th}$ video. Two videos are of the same type only if they are denoted by the same letter.

-----Output-----
Output a single integer on a line, indicating the minimum number of clicks required to watch all videos currently in your Watch Later list.

-----Examples-----
Sample Input:
4 2
abba
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is a very experienced and well-known cook. He has participated in many cooking competitions in the past — so many that he does not even remember them all.
One of these competitions lasted for a certain number of days. The first day of the competition was day $S$ of the week (i.e. Monday, Tuesday etc.) and the last day was day $E$ of the week. Chef remembers that the duration of the competition (the number of days between the first and last day, inclusive) was between $L$ days and $R$ days inclusive. Is it possible to uniquely determine the exact duration of the competition? If so, what is this duration?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated strings $S$ and $E$, followed by a space and two space-separated integers $L$ and $R$.

-----Output-----
For each test case, print a single line containing:
- the string "impossible" if there is no duration consistent with all given information
- the string "many" if there is more than one possible duration
- one integer — the duration of the competition, if its duration is unique

-----Constraints-----
- $1 \le T \le 10,000$
- $1 \le L \le R \le 100$
- $S$ is one of the strings "saturday", "sunday", "monday", "tuesday", "wednesday", "thursday" or "friday"
- $E$ is one of the strings "saturday", "sunday", "monday", "tuesday", "wednesday", "thursday" or "friday"

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
3
saturday sunday 2 4
monday wednesday 1 20
saturday sunday 3 5

-----Example Output-----
2
many
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Several days ago you bought a new house and now you are planning to start a renovation. Since winters in your region can be very cold you need to decide how to heat rooms in your house.

Your house has $n$ rooms. In the $i$-th room you can install at most $c_i$ heating radiators. Each radiator can have several sections, but the cost of the radiator with $k$ sections is equal to $k^2$ burles.

Since rooms can have different sizes, you calculated that you need at least $sum_i$ sections in total in the $i$-th room. 

For each room calculate the minimum cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 1000$) — the number of rooms.

Each of the next $n$ lines contains the description of some room. The $i$-th line contains two integers $c_i$ and $sum_i$ ($1 \le c_i, sum_i \le 10^4$) — the maximum number of radiators and the minimum total number of sections in the $i$-th room, respectively.


-----Output-----

For each room print one integer — the minimum possible cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.


-----Example-----
Input
4
1 10000
10000 1
2 6
4 6

Output
100000000
1
18
10



-----Note-----

In the first room, you can install only one radiator, so it's optimal to use the radiator with $sum_1$ sections. The cost of the radiator is equal to $(10^4)^2 = 10^8$.

In the second room, you can install up to $10^4$ radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.

In the third room, there $7$ variants to install radiators: $[6, 0]$, $[5, 1]$, $[4, 2]$, $[3, 3]$, $[2, 4]$, $[1, 5]$, $[0, 6]$. The optimal variant is $[3, 3]$ and it costs $3^2+ 3^2 = 18$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has two integers X and Y.
He computed X + Y and X - Y, and the results were A and B, respectively.
Now he cannot remember what X and Y were. Find X and Y for him.

-----Constraints-----
 - -100 \leq A, B \leq 100
 - For the given integers A and B, there uniquely exist integers X and Y such that X + Y = A and X - Y = B.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print X and Y.

-----Sample Input-----
2 -2

-----Sample Output-----
0 2

If X = 0 and Y = 2, they match the situation: 0 + 2 = 2 and 0 - 2 = -2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N-1 or smaller.

* Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.



It can be proved that the largest element in the sequence becomes N-1 or smaller after a finite number of operations.

You are given an integer K. Find an integer sequence a_i such that the number of times we will perform the above operation is exactly K. It can be shown that there is always such a sequence under the constraints on input and output in this problem.

Constraints

* 0 ≤ K ≤ 50 \times 10^{16}

Input

Input is given from Standard Input in the following format:


K


Output

Print a solution in the following format:


N
a_1 a_2 ... a_N


Here, 2 ≤ N ≤ 50 and 0 ≤ a_i ≤ 10^{16} + 1000 must hold.

Examples

Input

0


Output

4
3 3 3 3


Input

1


Output

3
1 0 3


Input

2


Output

2
2 2


Input

3


Output

7
27 0 0 0 0 0 0


Input

1234567894848


Output

10
1000 193 256 777 0 1 1192 1234567891011 48 425

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array nums[] of N positive integers. Find the minimum number of operations required to modify the array such that array elements are in strictly increasing order (A[i] < A[i+1]).
Changing a number to greater or lesser than original number is counted as one operation.
Example 1:
Input: nums[] = [1, 2, 3, 6, 5, 4]
Output: 2
Explanation: By decreasing 6 by 2 and
increasing 4 by 2, arr will be like
[1, 2, 3, 4, 5, 6] which is stricly 
increasing.
Example 2:
Input: nums[] = [1, 2, 3, 4]
Output: 0
Explanation: Arrays is already strictly
increasing.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function min_opeartions() which takes the array nums[] as input parameter and returns the minimum number of opeartion needed to make the array strictly increasing.
 
Expected Time Complexity: O(n^2)
Expected Space Complexity: O(n)
 
Constraints: 
1 <= length of array <= 1000
1 <= arr[i] <= 1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are $n$ voters, and two ways to convince each of them to vote for you. The first way to convince the $i$-th voter is to pay him $p_i$ coins. The second way is to make $m_i$ other voters vote for you, and the $i$-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with $m_1 = 1$, $m_2 = 2$, $m_3 = 2$, $m_4 = 4$, $m_5 = 5$, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: ${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$.

Calculate the minimum number of coins you have to spend so that everyone votes for you.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 5000$) — the number of voters.

The next $n$ lines contains the description of voters. $i$-th line contains two integers $m_i$ and $p_i$ ($1 \le p_i \le 10^9, 0 \le m_i < n$).

It is guaranteed that the sum of all $n$ over all test cases does not exceed $5000$.


-----Output-----

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.


-----Example-----
Input
3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5

Output
8
0
7



-----Note-----

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: ${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$.

In the second example you don't need to buy votes. The set of people voting for you will change as follows: ${1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}$.

In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: ${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kristen loves playing with and comparing numbers. She thinks that if she takes two different positive numbers, the one whose digits sum to a larger number is better than the other. If the sum of digits is equal for both numbers, then she thinks the smaller number is better. For example, Kristen thinks that $13$ is better than $31$ and that $12$ is better than ${11}$.

Given an integer, $n$, can you find the divisor of $n$ that Kristin will consider to be the best?

Input Format

A single integer denoting $n$.

Constraints

$0<n\leq10^5$

Output Format

Print an integer denoting the best divisor of $n$.  

Sample Input 0
12

Sample Output 0
6

Explanation 0

The set of divisors of $12$ can be expressed as $\{1,2,3,4,6,12\}$. The divisor whose digits sum to the largest number is ${6}$ (which, having only one digit, sums to itself). Thus, we print ${6}$ as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Domino

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera has got *n* domino pieces in a row. Each piece consists of two halves — the upper one and the lower one. Each of the halves contains a number from 1 to 6. Valera loves even integers very much, so he wants the sum of the numbers on the upper halves and the sum of the numbers on the lower halves to be even.

To do that, Valera can rotate the dominoes by 180 degrees. After the rotation the upper and the lower halves swap places. This action takes one second. Help Valera find out the minimum time he must spend rotating dominoes to make his wish come true.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100), denoting the number of dominoes Valera has. Next *n* lines contain two space-separated integers *x**i*,<=*y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=6). Number *x**i* is initially written on the upper half of the *i*-th domino, *y**i* is initially written on the lower half.

Output Specification:
Print a single number — the minimum required number of seconds. If Valera can't do the task in any time, print <=-<=1.

Demo Input:
['2\n4 2\n6 4\n', '1\n2 3\n', '3\n1 4\n2 3\n4 4\n']

Demo Output:
['0\n', '-1\n', '1\n']

Note:
In the first test case the sum of the numbers on the upper halves equals 10 and the sum of the numbers on the lower halves equals 6. Both numbers are even, so Valera doesn't required to do anything.

In the second sample Valera has only one piece of domino. It is written 3 on the one of its halves, therefore one of the sums will always be odd.

In the third case Valera can rotate the first piece, and after that the sum on the upper halves will be equal to 10, and the sum on the lower halves will be equal to 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in the Kingdom of Autumn, numbered from 1 to n. People can travel between any two cities using n-1 two-directional roads.

This year, the government decides to separate the kingdom. There will be regions of different levels. The whole kingdom will be the region of level 1. Each region of i-th level should be separated into several (at least two) regions of i+1-th level, unless i-th level is the last level. Each city should belong to exactly one region of each level and for any two cities in the same region, it should be possible to travel between them passing the cities in the same region only.

According to research, for each city i, there is a value a_i, which describes the importance of this city. All regions of the same level should have an equal sum of city importances.

Your task is to find how many plans there are to determine the separation of the regions that all the conditions are satisfied. Two plans are considered different if and only if their numbers of levels are different or there exist two cities in the same region of one level in one plan but in different regions of this level in the other plan. Since the answer may be very large, output it modulo 10^9+7.

Input

The first line contains one integer n (1 ≤ n ≤ 10^6) — the number of the cities.

The second line contains n integers, the i-th of which is a_i (1 ≤ a_i ≤ 10^9) — the value of each city.

The third line contains n-1 integers, p_1, p_2, …, p_{n-1}; p_i (p_i ≤ i) describes a road between cities p_i and i+1.

Output

Print one integer — the number of different plans modulo 10^9+7.

Examples

Input

4
1 1 1 1
1 2 3


Output

4

Input

4
1 1 1 1
1 2 2


Output

2

Input

4
1 2 1 2
1 1 3


Output

3

Note

For the first example, there are 4 different plans:

Plan 1: Level-1: \{1,2,3,4\}.

Plan 2: Level-1: \{1,2,3,4\}, Level-2: \{1,2\},\{3,4\}.

Plan 3: Level-1: \{1,2,3,4\}, Level-2: \{1\},\{2\},\{3\},\{4\}.

Plan 4: Level-1: \{1,2,3,4\}, Level-2: \{1,2\},\{3,4\}, Level-3: \{1\},\{2\},\{3\},\{4\}.

For the second example, there are 2 different plans:

Plan 1: Level-1: \{1,2,3,4\}.

Plan 2: Level-1: \{1,2,3,4\}, Level-2: \{1\},\{2\},\{3\},\{4\}.

For the third example, there are 3 different plans:

Plan 1: Level-1: \{1,2,3,4\}.

Plan 2: Level-1: \{1,2,3,4\}, Level-2: \{1,2\},\{3,4\}.

Plan 3: Level-1: \{1,2,3,4\}, Level-2: \{1,3\},\{2\},\{4\}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One particularly well-known fact about zombies is that they move and think terribly slowly. While we still don't know why their movements are so sluggish, the problem of laggy thinking has been recently resolved. It turns out that the reason is not (as previously suspected) any kind of brain defect – it's the opposite! Independent researchers confirmed that the nervous system of a zombie is highly complicated – it consists of n brains (much like a cow has several stomachs). They are interconnected by brain connectors, which are veins capable of transmitting thoughts between brains. There are two important properties such a brain network should have to function properly:   It should be possible to exchange thoughts between any two pairs of brains (perhaps indirectly, through other brains).  There should be no redundant brain connectors, that is, removing any brain connector would make property 1 false. 

If both properties are satisfied, we say that the nervous system is valid. Unfortunately (?), if the system is not valid, the zombie stops thinking and becomes (even more) dead. Your task is to analyze a given nervous system of a zombie and find out whether it is valid.


-----Input-----

The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 1000) denoting the number of brains (which are conveniently numbered from 1 to n) and the number of brain connectors in the nervous system, respectively. In the next m lines, descriptions of brain connectors follow. Every connector is given as a pair of brains a b it connects (1 ≤ a, b ≤ n, a ≠ b).


-----Output-----

The output consists of one line, containing either yes or no depending on whether the nervous system is valid.


-----Examples-----
Input
4 4
1 2
2 3
3 1
4 1

Output
no

Input
6 5
1 2
2 3
3 4
4 5
3 6

Output
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Manao is working for a construction company. Recently, an order came to build wall bars in a children's park. Manao was commissioned to develop a plan of construction, which will enable the company to save the most money.

After reviewing the formal specifications for the wall bars, Manao discovered a number of controversial requirements and decided to treat them to the company's advantage. His resulting design can be described as follows:

  * Let's introduce some unit of length. The construction center is a pole of height n. 
  * At heights 1, 2, ..., n exactly one horizontal bar sticks out from the pole. Each bar sticks in one of four pre-fixed directions. 
  * A child can move from one bar to another if the distance between them does not exceed h and they stick in the same direction. If a child is on the ground, he can climb onto any of the bars at height between 1 and h. In Manao's construction a child should be able to reach at least one of the bars at heights n - h + 1, n - h + 2, ..., n if he begins at the ground. 

<image> The figure to the left shows what a common set of wall bars looks like. The figure to the right shows Manao's construction

Manao is wondering how many distinct construction designs that satisfy his requirements exist. As this number can be rather large, print the remainder after dividing it by 1000000009 (109 + 9). Two designs are considered distinct if there is such height i, that the bars on the height i in these designs don't stick out in the same direction.

Input

A single line contains two space-separated integers, n and h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(n, 30)).

Output

In a single line print the remainder after dividing the number of designs by 1000000009 (109 + 9).

Examples

Input

5 1


Output

4


Input

4 2


Output

148


Input

4 3


Output

256


Input

5 2


Output

376

Note

Consider several designs for h = 2. A design with the first bar sticked out in direction d1, the second — in direction d2 and so on (1 ≤ di ≤ 4) is denoted as string d1d2...dn.

Design "1231" (the first three bars are sticked out in different directions, the last one — in the same as first). A child can reach neither the bar at height 3 nor the bar at height 4.

Design "414141". A child can reach the bar at height 5. To do this, he should first climb at the first bar, then at the third and then at the fifth one. He can also reach bar at height 6 by the route second  →  fourth  →  sixth bars.

Design "123333". The child can't reach the upper two bars.

Design "323323". The bar at height 6 can be reached by the following route: first  →  third  →  fourth  →  sixth bars.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.