vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The world is made up of $10$ kinds of people, those who understand binary and those who do not. These different kinds of people do not always get along so well. Bob might ask for a $10000$ ounce coffee (meaning binary) and Alice might make misinterpret his request as being in decimal and give him a $10011100010000$ ounce coffee (binary). After Sue explains that this much coffee costs $100$ dollars (decimal), Bob might assume he only has to pay $4$ dollars (interpreting the price as being in binary). In response to these differences that are difficult to resolve, these two groups have divided the world into two regions, the binary-friendly zones and the decimal-friendly zones. They have even published a map like the following to help people keep up with where the areas are (they have used ones and zeros so nobody would have trouble reading it).1111100000

1111000000

1110000011

0111100111

0011111111

Users of binary have to stay in the zones marked with a zero. Users of decimal have to stay in the zones marked with a one. You have to figure out if it is possible for either type of person to get between various locations of interest. People can move north, south, east or west, but cannot move diagonally.

-----Input-----
Input starts with a line containing two positive integers, $1 \le r \le 1000$ and $1 \le c \le 1000$. The next $r$ input lines give the contents of the map, each line containing exactly $c$ characters (which are all chosen from $0$ or $1$).

The next line has an integer $0 \le n \le 1000$. The following $n$ lines each contain one query, given as four integers: $r_1,c_1$ and $r_2,c_2$. These two pairs indicate two locations on the map, and their limits are $1 \le r_1, r_2 \le r$ and $1 \le c_1, c_2 \le c$.

-----Output-----
For each query, output binary if a binary user can start from location $r_1, c_1$ and move to location $r_2, c_2$. Output decimal if a decimal user can move between the two locations. Otherwise, output neither.

-----Examples-----
Sample Input:
1 4
1100
2
1 1 1 4
1 1 1 1
Sample Output:
neither
decimal

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Borys likes to travel.
Now he has a vacation and wants to visit beautiful city Treebourg.
The city consists of n junctions and n-1 roads between them.
Treebourg is the best city for tourists because every junction contains an interesting sight to see.
As Treebourg was designed especially for tourists, there are no unnecessary roads — there is exactly one simple path between each pair of junctions (there is exactly one way to travel between a pair of junctions).

Borys also likes solving problems. Mayor of Treebourg is concerned about how interesting sightseeing tours in his city are. He asks Borys to help to make the tours more interesting.

Borys explored the sights and assigned each of them one integer, describing its beauty.
The i-th junction has a sight with beauty b_i.

Each tour is a simple path between some two distinct junctions.
So, there are \frac{n \cdot (n-1)}{2} tours in total.
A tour is considered interesting if the median (definition) of beauties of all sights in the tour is at least x.
If the number of sights is even then the median is greater of two middle values (any of them in case of a tie).
So, the median of (10, 20, 30, 40) is 30.
The median of (10,11,11,12) is 11.
The median of (10, 20, 30) is 20.

The city can allocate money on repairing at most one sight — its beauty will then increase to any value Mayor chooses.
Borys wants to solve the problem optimally.
He wants to repair a sight, in order to maximize the number of new interesting tours.
Help him to do that.

Find the maximum number of tours that become interesting.

Input format
The first line of the input contains two integers n and x — the number of junctions and the treshold for the tour to be interesting, respectively.

Next n - 1 lines describe the roads of Treebourg.
Each of them contains two integers — junctions connected by a road.
Junctions are numbered 1 through n.

The last line of the input contains n integers b_1, b_2, \ldots, b_n — beauties of sights.

Output format
Print a single integer — the maximum difference between the number of interesting tours after the repair and the initial number of interesting tours.

Constraints

2 ≤ n ≤ 300\,000
0 ≤ x, b_i ≤ 10^9

SAMPLE INPUT
3 3
1 2
2 3
1 2 3

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are some coins in the xy-plane. The positions of the coins are represented by a grid of characters with H rows and W columns. If the character at the i-th row and j-th column, s_{ij}, is `#`, there is one coin at point (i,j); if that character is `.`, there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

* Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.



Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

* 1 \leq H,W \leq 300
* s_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}


Output

Print the number of triples that satisfy the condition.

Examples

Input

5 4
#.##
.##.
#...
..##
...#


Output

3


Input

5 4
.##
.##.
...
..##
...#


Output

3


Input

13 27
......#.........#.......#..
...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
.#.#.#...###..
...........#...#...#######
..#######..#...#...#.....#
..#.....#..#...#...#.###.#
..#######..#...#...#.#.#.#
..........##...#...#.#####


Output

870

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from $1$ to $n$. For every edge $e$ of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge $e$ (and only this edge) is erased from the tree.

Monocarp has given you a list of $n - 1$ pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 1\,000$) — the number of vertices in the tree.

Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ each ($1 \le a_i < b_i \le n$) — the maximal indices of vertices in the components formed if the $i$-th edge is removed.


-----Output-----

If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).

Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next $n - 1$ lines. Each of the last $n - 1$ lines should contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) — vertices connected by an edge.

Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.


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

Output
YES
1 3
3 2
2 4

Input
3
1 3
1 3

Output
NO

Input
3
1 2
2 3

Output
NO



-----Note-----

Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Welcome to CODE FESTIVAL 2016! In order to celebrate this contest, find a string s that satisfies the following conditions:

* The length of s is between 1 and 5000, inclusive.
* s consists of uppercase letters.
* s contains exactly K occurrences of the string "FESTIVAL" as a subsequence. In other words, there are exactly K tuples of integers (i_0, i_1, ..., i_7) such that 0 ≤ i_0 < i_1 < ... < i_7 ≤ |s|-1 and s[i_0]='F', s[i_1]='E', ..., s[i_7]='L'.



It can be proved that under the given constraints, the solution always exists. In case there are multiple possible solutions, you can output any.

Constraints

* 1 ≤ K ≤ 10^{18}

Input

The input is given from Standard Input in the following format:


K


Output

Print a string that satisfies the conditions.

Examples

Input

7


Output

FESSSSSSSTIVAL


Input

256


Output

FFEESSTTIIVVAALL

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ButCoder Inc. is a startup company whose main business is the development and operation of the programming competition site "ButCoder".

There are N members of the company including the president, and each member except the president has exactly one direct boss. Each member has a unique ID number from 1 to N, and the member with the ID i is called Member i. The president is Member 1, and the direct boss of Member i (2 ≤ i ≤ N) is Member b_i (1 ≤ b_i < i).

All the members in ButCoder have gathered in the great hall in the main office to take a group photo. The hall is very large, and all N people can stand in one line. However, they have been unable to decide the order in which they stand. For some reason, all of them except the president want to avoid standing next to their direct bosses.

How many ways are there for them to stand in a line that satisfy their desires? Find the count modulo 10^9+7.

Constraints

* 2 ≤ N ≤ 2000
* 1 ≤ b_i < i (2 ≤ i ≤ N)

Input

Input is given from Standard Input in the following format:


N
b_2
b_3
:
b_N


Output

Print the number of ways for the N members to stand in a line, such that no member except the president is next to his/her direct boss, modulo 10^9+7.

Examples

Input

4
1
2
3


Output

2


Input

3
1
2


Output

0


Input

5
1
1
3
3


Output

8


Input

15
1
2
3
1
4
2
7
1
8
2
8
1
8
2


Output

97193524

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef was chatting with his friend who was a mathematician.
Chef said "Hi !".

His friend replied that '!' is the symbol of factorial.

Chef had never heard about it and he asked more about it. Then his friend taught him how to calculate the factorial of a number.

Chef loved that But as always he got tired after calculating a few values and asked you to do it for him.

-----Input-----
N : Number of inputs
then N lines with input T

N<10

T<=200

-----Output-----
The result for the corresponding value of T

-----Example-----
Input:
3
5
4
6

Output:
120
24
720

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's holiday. Mashmokh and his boss, Bimokh, are playing a game invented by Mashmokh. 

In this game Mashmokh writes sequence of n distinct integers on the board. Then Bimokh makes several (possibly zero) moves. On the first move he removes the first and the second integer from from the board, on the second move he removes the first and the second integer of the remaining sequence from the board, and so on. Bimokh stops when the board contains less than two numbers. When Bimokh removes numbers x and y from the board, he gets gcd(x, y) points. At the beginning of the game Bimokh has zero points.

Mashmokh wants to win in the game. For this reason he wants his boss to get exactly k points in total. But the guy doesn't know how choose the initial sequence in the right way. 

Please, help him. Find n distinct integers a1, a2, ..., an such that his boss will score exactly k points. Also Mashmokh can't memorize too huge numbers. Therefore each of these integers must be at most 109.

Input

The first line of input contains two space-separated integers n, k (1 ≤ n ≤ 105; 0 ≤ k ≤ 108).

Output

If such sequence doesn't exist output -1 otherwise output n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Examples

Input

5 2


Output

1 2 3 4 5


Input

5 3

Output

2 4 3 7 1

Input

7 2


Output

-1

Note

gcd(x, y) is greatest common divisor of x and y.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You can perfectly predict the price of a certain stock for the next N days. You would like to profit on this knowledge, but only want to transact one share of stock per day. That is, each day you will either buy one share, sell one share, or do nothing. Initially you own zero shares, and you cannot sell shares when you don't own any. At the end of the N days you would like to again own zero shares, but want to have as much money as possible.


-----Input-----

Input begins with an integer N (2 ≤ N ≤ 3·10^5), the number of days.

Following this is a line with exactly N integers p_1, p_2, ..., p_{N} (1 ≤ p_{i} ≤ 10^6). The price of one share of stock on the i-th day is given by p_{i}.


-----Output-----

Print the maximum amount of money you can end up with at the end of N days.


-----Examples-----
Input
9
10 5 4 7 9 12 6 2 10

Output
20

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

Output
41



-----Note-----

In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. Then buy at 2 and sell at 10. The total profit is  - 5 - 4 + 9 + 12 - 2 + 10 = 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The longer the code, the stronger the code. The power number (P) of a code determines the strength of a code.

While computing the power number of a code we should ignore the keywords in the code. A few sample key words would be int, unsigned, string, etc. The power of a code can be determined by the number of characters in the code that do not belong to any of the keywords.

More formally, for each keyword K, consider all the occurrences of K in the code, ignore all these matching substrings while computing the power. See the example for clarity.

Example: 

If you take a code to be

int main() { mlinteger a; return 0; }

The above code has 37 characters in total.

If the key words are

int
return
lint
integer

Then the power of the above code would be 20, spaces need to be counted:

" main() { "   --> 10
"m a; "         --> 5
" 0; }"        --> 5

The codes can be concatenated to be made more powerful. If we have two codes C1, C2 with power P1, P2, the power of code C1 $C2**(here**$ denotes concatenation) will be P1 + P2.

While concatenating two codes, a % character gets inseted in between the two codes. For example if C1 was print 5; and C2 was print 6;, C1 $ C2 = print 5;%print 6;

You are given N codes, K keywords, you can use each code as many number of times as you want. You are to output the largest power X, that can't be attained by concatinating the codes.

Note:

All the following operations are possible.

Two same codes can be concatenated with each other.
Some codes need not be used in the concatenation.
Each code can be used any number of times.

Input Format 

First line contains N. In the following N lines, the i^{th} line represents the code C_{i}. The following line contains K the number of keywords. The following K lines one keyword each.

Output Format 

Print a single line containing X as described above.

Constraints

1 <= N <= 10
1 <= |C_i| <= 100000
1 <= K <= 100
1 <= each keyword length <= 1000

Note:

Key words do not contain spaces. Both the code and the key words do not contain % character. They can contain any other ASCII character.
If the answer is infinite then print -1.

Sample Input: #1

5
lint maint lllint
int maint lllintl
lint maint lllint
lint maint lllint
lint maint lllint
2
int
lint

Sample Output: #1

29

Sample Input: #2

3
ababaac
babab
abcbab
1
bab

Sample Output: #2

5

Explanation:

In sample 1, the powers of codes are 6, 7, 6, 6. And hence the maximum unattainable power by combination is 29. In sample 2, the powers are 4, 0, 3, and hence the result is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jake is learning how to play the card game Dominion. In Dominion, you can buy a variety of treasure, action, and victory point cards – at the end of the game, the player with the most victory points wins!

Each turn, each player draws $5$ cards and can use their action and treasure cards to obtain buying power in order to buy more cards. Since Jake is just starting out, he’s decided to buy only treasure and victory point cards.

There are $3$ kinds of victory cards in Dominion:
 - Province (costs $8$, worth $6$ victory points)
 - Duchy (costs $5$, worth $3$ victory points)
 - Estate (costs $2$, worth $1$ victory point)

And, there are $3$ kinds of treasure cards:
 - Gold (costs $6$, worth $3$ buying power)
 - Silver (costs $3$, worth $2$ buying power)
 - Copper (costs $0$, worth $1$ buying power)

At the start of Jake’s turn, he draws $5$ of these cards. Given the number of Golds, Silvers, and Coppers in Jake’s hand, calculate the best victory card and best treasure card he could buy that turn. Note that Jake can buy only one card.

-----Input-----
The input consists of a single test case on a single line, which contains three non-negative integers $G$, $S$, $C$ ($G + S + C \le 5$) indicating the number of Golds, Silvers, and Coppers Jake draws in his hand.

-----Output-----
Output the best victory card (Province, Duchy, or Estate) and the best treasure card (Gold, Silver, or Copper) Jake can buy this turn, separated with " or ", in this order. If Jake cannot afford any victory cards, output only the best treasure card he can buy.

-----Sample Explanation-----
In Sample Input $1$, Jake has $1$ Silver in his hand, which means he has $2$ buying power. This would allow him to either buy an Estate or a Copper.

-----Examples-----
Sample Input 1:
0 1 0
Sample Output 1:
Estate or Copper

Sample Input 2:
2 1 0
Sample Output 2:
Province or Gold

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i. 
All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).
Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).
We want to calculate the probability that the two boxes have the same number of distinct balls.
 
Example 1:
Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:
Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:
Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:
Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:
Input: balls = [6,6,6,6,6,6]
Output: 0.90327

 
Constraints:

1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Volodya and Vlad play the following game. There are *k* pies at the cells of *n*<=<=×<=<=*m* board. Each turn Volodya moves one pie to the neighbouring (by side) cell. If the pie lies at the border of the board then Volodya can move it outside the board, get the pie and win. After Volodya's move, Vlad bans some edge at the border of the board of length 1 (between two knots of the board) so that Volodya is not able to move the pie outside the board through this edge anymore. The question is: will Volodya win this game? We suppose both players follow the optimal strategy.

Input Specification:
First line contains 3 integers, separated by space: 1<=≤<=*n*,<=*m*<=≤<=100 — dimensions of the board and 0<=≤<=*k*<=≤<=100 — the number of pies. Each of the next *k* lines contains 2 integers, separated by space: 1<=≤<=*x*<=≤<=*n*, 1<=≤<=*y*<=≤<=*m* — coordinates of the corresponding pie. There could be more than one pie at a cell.

Output Specification:
Output only one word: "YES" — if Volodya wins, "NO" — otherwise.

Demo Input:
['2 2 1\n1 2\n', '3 4 0\n', '100 50 2\n50 25\n50 25\n']

Demo Output:
['YES', 'NO', 'NO']

Note:
none

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