vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A chip was placed on a field with coordinate system onto point (0, 0).

Every second the chip moves randomly. If the chip is currently at a point (x, y), after a second it moves to the point (x - 1, y) with probability p1, to the point (x, y - 1) with probability p2, to the point (x + 1, y) with probability p3 and to the point (x, y + 1) with probability p4. It's guaranteed that p1 + p2 + p3 + p4 = 1. The moves are independent.

Find out the expected time after which chip will move away from origin at a distance greater than R (i.e. <image> will be satisfied).

Input

First line contains five integers R, a1, a2, a3 and a4 (0 ≤ R ≤ 50, 1 ≤ a1, a2, a3, a4 ≤ 1000).

Probabilities pi can be calculated using formula <image>.

Output

It can be shown that answer for this problem is always a rational number of form <image>, where <image>.

Print P·Q - 1 modulo 109 + 7. 

Examples

Input

0 1 1 1 1


Output

1

Input

1 1 1 1 1


Output

666666674

Input

1 1 2 1 2


Output

538461545

Note

In the first example initially the chip is located at a distance 0 from origin. In one second chip will move to distance 1 is some direction, so distance to origin will become 1.

Answers to the second and the third tests: <image> and <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us calculate the sum of k-th powers of natural numbers from 1 to n. As the result can be quite large, output the result modulo some integer p.

------ Input ------ 

First t≤10 - the number of test cases.
Each test case consist of numbers: 1≤n≤1000000000, 1≤k≤100, 1≤p≤1000000000.

------ Output ------ 

For each test case, output the value: (1^{k}+2^{k}+...+n^{k}) mod p.

----- Sample Input 1 ------ 
4
10 1 1000000
10 2 1000000
10 3 1000000
10 4 1000000
----- Sample Output 1 ------ 
55
385
3025
25333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Days of Floral Colours

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.

On the rim of the Floral Clock are 2*n* flowers, numbered from 1 to 2*n* clockwise, each of which has a colour among all *n* possible ones. For each colour, there are exactly two flowers with it, the distance between which either is less than or equal to 2, or equals *n*. Additionally, if flowers *u* and *v* are of the same colour, then flowers opposite to *u* and opposite to *v* should be of the same colour as well — symmetry is beautiful!

Formally, the distance between two flowers is 1 plus the number of flowers on the minor arc (or semicircle) between them. Below is a possible arrangement with *n*<==<=6 that cover all possibilities.

The beauty of an arrangement is defined to be the product of the lengths of flower segments separated by all opposite flowers of the same colour. In other words, in order to compute the beauty, we remove from the circle all flowers that have the same colour as flowers opposite to them. Then, the beauty is the product of lengths of all remaining segments. Note that we include segments of length 0 in this product. If there are no flowers that have the same colour as flower opposite to them, the beauty equals 0. For instance, the beauty of the above arrangement equals 1<=×<=3<=×<=1<=×<=3<==<=9 — the segments are {2}, {4,<=5,<=6}, {8} and {10,<=11,<=12}.

While keeping the constraints satisfied, there may be lots of different arrangements. Find out the sum of beauty over all possible arrangements, modulo 998<=244<=353. Two arrangements are considered different, if a pair (*u*,<=*v*) (1<=≤<=*u*,<=*v*<=≤<=2*n*) exists such that flowers *u* and *v* are of the same colour in one of them, but not in the other.

Input Specification:
The first and only line of input contains a lonely positive integer *n* (3<=≤<=*n*<=≤<=50<=000) — the number of colours present on the Floral Clock.

Output Specification:
Output one integer — the sum of beauty over all possible arrangements of flowers, modulo 998<=244<=353.

Demo Input:
['3\n', '4\n', '7\n', '15\n']

Demo Output:
['24\n', '4\n', '1316\n', '3436404\n']

Note:
With *n* = 3, the following six arrangements each have a beauty of 2 × 2 = 4.

While many others, such as the left one in the figure below, have a beauty of 0. The right one is invalid, since it's asymmetric.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\\{1, 7, 7, 4, 8, 1, 6\\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\\{1, 7, 7\\}$, $\\{7, 7, 4\\}$, $\\{7, 4, 8\\}$, $\\{4, 8, 1\\}$, $\\{8, 1, 6\\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.

Constraints

* $1 \leq N \leq 10^6$
* $1 \leq L \leq 10^6$
* $1 \leq a_i \leq 10^9$
* $L \leq N$

Input

The input is given in the following format.

$N$ $L$
$a_1$ $a_2$ ... $a_N$

Output

Print a sequence of the minimum in a line. Print a space character between adjacent elements.

Example

Input

7 3
1 7 7 4 8 1 6


Output

1 4 4 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Berland faces federalization requests more and more often. The proponents propose to divide the country into separate states. Moreover, they demand that there is a state which includes exactly k towns.

Currently, Berland has n towns, some pairs of them are connected by bilateral roads. Berland has only n - 1 roads. You can reach any city from the capital, that is, the road network forms a tree.

The Ministry of Roads fears that after the reform those roads that will connect the towns of different states will bring a lot of trouble.

Your task is to come up with a plan to divide the country into states such that:

  * each state is connected, i.e. for each state it is possible to get from any town to any other using its roads (that is, the roads that connect the state towns), 
  * there is a state that consisted of exactly k cities, 
  * the number of roads that connect different states is minimum. 

Input

The first line contains integers n, k (1 ≤ k ≤ n ≤ 400). Then follow n - 1 lines, each of them describes a road in Berland. The roads are given as pairs of integers xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — the numbers of towns connected by the road. Assume that the towns are numbered from 1 to n.

Output

The the first line print the required minimum number of "problem" roads t. Then print a sequence of t integers — their indices in the found division. The roads are numbered starting from 1 in the order they follow in the input. If there are multiple possible solutions, print any of them.

If the solution shows that there are no "problem" roads at all, print a single integer 0 and either leave the second line empty or do not print it at all.

Examples

Input

5 2
1 2
2 3
3 4
4 5


Output

1
2


Input

5 3
1 2
1 3
1 4
1 5


Output

2
3 4


Input

1 1


Output

0

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

You have an airline route map of a certain region. All the airports in the region and all the non-stop routes between them are on the map. Here, a non-stop route is a flight route that provides non-stop flights in both ways.

Named after the great mathematician Leonhard Euler, an Eulerian tour is an itinerary visiting all the airports in the region taking a single flight of every non-stop route available in the region. To be precise, it is a list of airports, satisfying all of the following.

* The list begins and ends with the same airport.
* There are non-stop routes between pairs of airports adjacent in the list.
* All the airports in the region appear at least once in the list. Note that it is allowed to have some airports appearing multiple times.
* For all the airport pairs with non-stop routes in between, there should be one and only one adjacent appearance of two airports of the pair in the list in either order.



It may not always be possible to find an Eulerian tour only with the non-stop routes listed in the map. Adding more routes, however, may enable Eulerian tours. Your task is to find a set of additional routes that enables Eulerian tours.

Input

The input consists of a single test case.


$n$ $m$
$a_1$ $b_1$
...
$a_m$ $b_m$


$n$ ($3 \leq n \leq 100$) is the number of airports. The airports are numbered from 1 to $n$. $m$ ($0 \leq m \leq \frac{n(n-1)}{2}$) is the number of pairs of airports that have non-stop routes. Among the $m$ lines following it, integers $a_i$ and $b_i$ on the $i$-th line of them ($1 \leq i \leq m$) are airport numbers between which a non-stop route is operated. You can assume $1 \leq a_i < b_i \leq n$, and for any $i \ne j$, either $a_i \ne a_j$ or $b_i \ne b_j$ holds.

Output

Output a set of additional non-stop routes that enables Eulerian tours. If two or more different sets will do, any one of them is acceptable. The output should be in the following format.


$k$
$c_1$ $d_1$
...
$c_k$ $d_k$


$k$ is the number of non-stop routes to add, possibly zero. Each of the following $k$ lines should have a pair of integers, separated by a space. Integers $c_i$ and $d_i$ in the $i$-th line ($c_i < d_i$) are airport numbers specifying that a non-stop route is to be added between them. These pairs, ($c_i, d_i$) for $1 \leq i \leq k$, should be distinct and should not appear in the input.

If adding new non-stop routes can never enable Eulerian tours, output -1 in a line.

Sample Input 1


4 2
1 2
3 4


Sample Output 1


2
1 4
2 3


Sample Input 2


6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6


Sample Output 2


-1


Sample Input 3


6 7
1 2
1 3
1 4
2 3
4 5
4 6
5 6


Sample Output 3


3
1 5
2 4
2 5


Sample Input 4


4 3
2 3
2 4
3 4


Sample Output 4


-1


Sample Input 5


5 5
1 3
1 4
2 4
2 5
3 5


Sample Output 5


0






Example

Input

4 2
1 2
3 4


Output

2
1 4
2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. X has come up with a new string compression algorithm. Consider a string of length N which contains up to K distinct characters. The compression algorithm works as follows: Replace each maximal contiguous substring containing only one distinct character (repeated an arbitrary number of times) and replace it by 2 values: the character and the length of the substring.
For example, the string "aabbaaa" will be compressed to "a, 2, b, 2, a, 3". Thus the length of the compressed string is 6.

Since Mr. X is living in advanced times, the length of any integer is considered to be 1. For example, if a string is compressed to "a, 111, b, 13", then its length after compression is considered to be 4.

To test his algorithm, he needs to know the expected length of the compressed string for given N and K if the input string is randomly uniformly chosen from all possibilities. He wants to run this experiment multiple times for different N, K and needs your help.

-----Input-----
The first line of the input contains an integer T denoting the number of queries. The description of T test cases follows.
The first and only line of each test case contains two integers N and K denoting the number of letters in the input string and the maximum number of distinct characters that can be present in the string.

-----Output-----

For each test case, output a single line containing the expected length of the compressed string. 
Your answer will be considered correct if the absolute error is less than 10-2

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ N, K ≤ 109

-----Example-----
Input:
2
3 1
3 2
Output:
2.0
4.0

-----Explanation-----Example case 1:

There is only one string: aaa with compressed string = a, 3. Therefore length = 2
Example case 2

Input strings:

"aaa": "a, 3". Length = 2

"aab": "a, 2, b, 1". Length = 4 

"aba": "a, 1, b, 1, a, 1". Length = 6

"abb": "a, 1, b, 2". Length = 4

"baa": "b, 1, a, 2". Length = 4

"bab": "b, 1, a, 1, b, 1". Length = 6

"bba": "b, 2, a, 1". Length = 4

"bbb": "b, 3". Length = 2

Expected value = (2+4+6+4+4+6+4+2)/8 = 32/8 = 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree $T$ and an integer $K$. You can choose arbitrary distinct two vertices $u$ and $v$ on $T$. Let $P$ be the simple path between $u$ and $v$. Then, remove vertices in $P$, and edges such that one or both of its end vertices is in $P$ from $T$. Your task is to choose $u$ and $v$ to maximize the number of connected components with $K$ or more vertices of $T$ after that operation.



Input

The input consists of a single test case formatted as follows.


$N$ $K$
$u_1$ $v_1$
:
$u_{N-1}$ $v_{N-1}$


The first line consists of two integers $N, K$ ($2 \leq N \leq 100,000, 1 \leq K \leq N$). The following $N-1$ lines represent the information of edges. The ($i+1$)-th line consists of two integers $u_i, v_i$ ($1 \leq u_i, v_i \leq N$ and $u_i \ne v_i $ for each $i$). Each $\\{u_i, v_i\\}$ is an edge of $T$. It's guaranteed that these edges form a tree.

Output

Print the maximum number of connected components with $K$ or more vertices in one line.

Examples

Input

2 1
1 2


Output

0


Input

7 3
1 2
2 3
3 4
4 5
5 6
6 7


Output

1


Input

12 2
1 2
2 3
3 4
4 5
3 6
6 7
7 8
8 9
6 10
10 11
11 12


Output

4


Input

3 1
1 2
2 3


Output

1


Input

3 2
1 2
2 3


Output

0


Input

9 3
1 2
1 3
1 4
4 5
4 6
4 7
7 8
7 9


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the hard version of the problem. The only difference is in the constraint on q. You can make hacks only if all versions of the problem are solved.

Zookeeper has been teaching his q sheep how to write and how to add. The i-th sheep has to write exactly k non-negative integers with the sum n_i.

Strangely, sheep have superstitions about digits and believe that the digits 3, 6, and 9 are lucky. To them, the fortune of a number depends on the decimal representation of the number; the fortune of a number is equal to the sum of fortunes of its digits, and the fortune of a digit depends on its value and position and can be described by the following table. For example, the number 319 has fortune F_{2} + 3F_{0}. 

<image>

Each sheep wants to maximize the sum of fortune among all its k written integers. Can you help them?

Input

The first line contains a single integer k (1 ≤ k ≤ 999999): the number of numbers each sheep has to write. 

The next line contains six integers F_0, F_1, F_2, F_3, F_4, F_5 (1 ≤ F_i ≤ 10^9): the fortune assigned to each digit. 

The next line contains a single integer q (1 ≤ q ≤ 100 000): the number of sheep.

Each of the next q lines contains a single integer n_i (1 ≤ n_i ≤ 999999): the sum of numbers that i-th sheep has to write.

Output

Print q lines, where the i-th line contains the maximum sum of fortune of all numbers of the i-th sheep.

Example

Input


3
1 2 3 4 5 6
2
57
63


Output


11
8

Note

In the first test case, 57 = 9 + 9 + 39. The three 9's contribute 1 ⋅ 3 and 3 at the tens position contributes 2 ⋅ 1. Hence the sum of fortune is 11.

In the second test case, 63 = 35 + 19 + 9. The sum of fortune is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is climbing stairs. There are total N stairs. She climbs A stairs upwards in day and she comes downstairs in night by B stairs. Find number of days she will take to reach the top of staircase.   

Input: 
First and only line contains three space separated integers denoting A, B, N.

Output: 
Print only one line of output denoting the answer to the question.

Constraints: 
1 ≤ B<A≤N ≤ 10^9

SAMPLE INPUT
5 1 6

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times:  Choose a pair of two neighboring equal elements $a_i = a_{i + 1}$ (if there is at least one such pair).  Replace them by one element with value $a_i + 1$. 

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $a$ you can get?


-----Input-----

The first line contains the single integer $n$ ($1 \le n \le 500$) — the initial length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — the initial array $a$.


-----Output-----

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.


-----Examples-----
Input
5
4 3 2 2 3

Output
2

Input
7
3 3 4 4 4 3 3

Output
2

Input
3
1 3 5

Output
3

Input
1
1000

Output
1



-----Note-----

In the first test, this is one of the optimal sequences of operations: $4$ $3$ $2$ $2$ $3$ $\rightarrow$ $4$ $3$ $3$ $3$ $\rightarrow$ $4$ $4$ $3$ $\rightarrow$ $5$ $3$.

In the second test, this is one of the optimal sequences of operations: $3$ $3$ $4$ $4$ $4$ $3$ $3$ $\rightarrow$ $4$ $4$ $4$ $4$ $3$ $3$ $\rightarrow$ $4$ $4$ $4$ $4$ $4$ $\rightarrow$ $5$ $4$ $4$ $4$ $\rightarrow$ $5$ $5$ $4$ $\rightarrow$ $6$ $4$.

In the third and fourth tests, you can't perform the operation at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inna and Dima decided to surprise Sereja. They brought a really huge candy matrix, it's big even for Sereja! Let's number the rows of the giant matrix from 1 to n from top to bottom and the columns — from 1 to m, from left to right. We'll represent the cell on the intersection of the i-th row and j-th column as (i, j). Just as is expected, some cells of the giant candy matrix contain candies. Overall the matrix has p candies: the k-th candy is at cell (x_{k}, y_{k}).

The time moved closer to dinner and Inna was already going to eat p of her favourite sweets from the matrix, when suddenly Sereja (for the reason he didn't share with anyone) rotated the matrix x times clockwise by 90 degrees. Then he performed the horizontal rotate of the matrix y times. And then he rotated the matrix z times counterclockwise by 90 degrees. The figure below shows how the rotates of the matrix looks like. [Image] 

Inna got really upset, but Duma suddenly understood two things: the candies didn't get damaged and he remembered which cells contained Inna's favourite sweets before Sereja's strange actions. Help guys to find the new coordinates in the candy matrix after the transformation Sereja made!


-----Input-----

The first line of the input contains fix integers n, m, x, y, z, p (1 ≤ n, m ≤ 10^9; 0 ≤ x, y, z ≤ 10^9; 1 ≤ p ≤ 10^5).

Each of the following p lines contains two integers x_{k}, y_{k} (1 ≤ x_{k} ≤ n; 1 ≤ y_{k} ≤ m) — the initial coordinates of the k-th candy. Two candies can lie on the same cell.


-----Output-----

For each of the p candies, print on a single line its space-separated new coordinates.


-----Examples-----
Input
3 3 3 1 1 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Output
1 3
1 2
1 1
2 3
2 2
2 1
3 3
3 2
3 1



-----Note-----

Just for clarity. Horizontal rotating is like a mirroring of the matrix. For matrix:

QWER      REWQ 

ASDF  ->  FDSA

ZXCV      VCXZ

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string check if it is Pangram or not. A pangram is a sentence containing every letter in the English Alphabet (either lowercase or uppercase or both). For example, we say the letter A is present in the string if either 'a' is present or 'A' is present.
Example 1:
Input:
S = Bawds jog, flick quartz, vex nymph
Output: 1
Explanation: In the given input, there
are all the letters of the English
alphabet. Hence, the output is 1.
Example 2:
Input:
S = sdfs
Output: 0
Explanation: In the given input, there
aren't all the letters present in the
English alphabet. Hence, the output
is 0.
Your Task:
 You need to complete the function checkPangram() that takes a string as a parameter and returns true if the string is a pangram, or else it returns false.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Number of distinct characters).
Constraints:
1 ≤ |S| ≤ 10^{4}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Hamed has recently found a string *t* and suddenly became quite fond of it. He spent several days trying to find all occurrences of *t* in other strings he had. Finally he became tired and started thinking about the following problem. Given a string *s* how many ways are there to extract *k*<=≥<=1 non-overlapping substrings from it such that each of them contains string *t* as a substring? More formally, you need to calculate the number of ways to choose two sequences *a*1,<=*a*2,<=...,<=*a**k* and *b*1,<=*b*2,<=...,<=*b**k* satisfying the following requirements:
 -  *k*<=≥<=1 -   -   -   -    *t* is a substring of string *s**a**i**s**a**i*<=+<=1... *s**b**i* (string *s* is considered as 1-indexed). 
As the number of ways can be rather large print it modulo 109<=+<=7.

Input Specification:
Input consists of two lines containing strings *s* and *t* (1<=≤<=|*s*|,<=|*t*|<=≤<=105). Each string consists of lowercase Latin letters.

Output Specification:
Print the answer in a single line.

Demo Input:
['ababa\naba\n', 'welcometoroundtwohundredandeightytwo\nd\n', 'ddd\nd\n']

Demo Output:
['5\n', '274201\n', '12\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Supermarket Dilemma
Chef is going to local supermarket but there appears a problem with chef as he is confused about which Supermarket he can choose to go as he is not able to decide whether he can park his car in that particular supermarket’s parking lot or not! There are N parking slots in each supermarket which are marked from 1,2,3,4…N.
Chef will go to that supermarket in which he gets to know that there is exactly 1 empty parking slot having number K that exactly divides the total number of slots (N) available in that supermarket.
The 1st and Nth parking slots are always occupied by the staff of every supermarket. Rest parking slots are empty as Chef is arriving early morning to the supermarket.
Now Chef needs your help in determining whether he can park his car in a supermarket or not!
Input
The first line contains the single integer N showing how many supermarkets are there for the chef to choose.
The next N lines contain a number ‘ai’ which represents the total parking slots available in ith supermarket.
Output
You need to output "YES" (without the quotes), if a supermarket can be reached by Chef, and "NO" (without the quotes), if it can't.
Constraints
1<=N<=10^5
1<=ai<=10^12
Sample Input :
2
4
5
Sample Output :
YES
NO

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