vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string.  Letters cannot be rearranged.  Given two strings of equal length, what's the longest string  that can be constructed such that it is a child of both?  

Example   

$\boldsymbol{s1=\text{'ABCD'}}$ 

$s2=\text{'ABDC'}$   

These strings have two children with maximum length 3, ABC and ABD.  They can be formed by eliminating either the D or C from both strings.  Return $3$.  

Function Description

Complete the commonChild function in the editor below.  

commonChild has the following parameter(s):

string s1:  a string
string s2:  another string   

Returns   

int: the length of the longest string which is a common child of the input strings 

Input Format

There are two lines, each with a string, $\mbox{sI}$ and $\mbox{s2}$. 

Constraints

$1\leq|s1|,\:|s2|\leq5000$ where $\left|s\right|$ means "the length of $\boldsymbol{\mathrm{~S~}}$"     
All characters are upper case in the range ascii[A-Z].

Sample Input
HARRY
SALLY

Sample Output
 2

Explanation

The longest string that can be formed by deleting zero or more characters from $\textit{HARRY}$ and $\textit{SALLY}$ is $\mbox{AY}$, whose length is 2.

Sample Input 1

AA
BB

Sample Output 1

0

Explanation 1

$\boldsymbol{AA}$ and $\textit{BB}$ have no characters in common and hence the output is 0.

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

3

Explanation 2

The longest string that can be formed between $\textit{SHINCHAN}$ and $\textit{NOHARAAA}$ while maintaining the order is $NHA$.

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

2

Explanation 3 

$\textit{BD}$ is the longest child of the given strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to teach a lesson of sharing to the students.
There are $N$ students (numbered from $1$ to $N$ from left to right) who are asked to stand in a row. Initially Chef gave $A$$i$ candies to the $i$$th$ child. In one operation any child can give any number of candies to the child standing to his immediate left (i.e. $i$$th$ child can give any amount of candies to the $(i-1)$$th$ child. In particular 1st child cannot give his candies to anyone).  
He asked them to minimize the maximum value of candies a student can possess after performing any number of operations (possibly zero). 
Help the students finding such maximum value.

-----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.
- First line of each test case contains a single integer $N$ denoting the number of students.
- Second line contains $N$ space-separated integers $A$$1$,$A$$2$,$.....$ $A$$N$ denoting the initial amount of candies chef gave to them.

-----Output:-----
- For each test case, print a single line containing one integer ― maximum value after sharing.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^5$
- $0$ $\leq$ $A$$i$ $\leq$ $10^9$
- Sum of $N$ over all Test Cases does not exceed $10^5$

-----Sample Input-----
2 
5 
1 2 3 4 5 
5
5 4 3 2 1

-----Sample Output-----
3 
5  

-----Explanation-----
- 
For First Test Case:
The $5$$th$ student will give $2$ candies to $4$$th$ student and $4$$th$ will give $3$ candies to $3$$rd$ and $3$$rd$ will give $3$ candies to $2$$nd$ and $2$$nd$ will give $2$ candies to $1$$st$. So finally the number of candies that they will have are 
$[3,3,3,3,3]$ and the value of maximum candies is $3$.
- 
For Second Test Case:
Sharing to the left student will not change the maximum value as $1$$st$ cannot share to anyone. So the maximum value will remain $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a self-playing game called Gather on the Clock.

At the beginning of a game, a number of cards are placed on a ring. Each card is labeled by a value.

In each step of a game, you pick up any one of the cards on the ring and put it on the next one in clockwise order. You will gain the score by the difference of the two values. You should deal with the two cards as one card in the later steps. You repeat this step until only one card is left on the ring, and the score of the game is the sum of the gained scores.

Your task is to write a program that calculates the maximum score for the given initial state, which specifies the values of cards and their placements on the ring.

The figure shown below is an example, in which the initial state is illustrated on the left, and the subsequent states to the right. The picked cards are 1, 3 and 3, respectively, and the score of this game is 6.

<image>

Figure 6: An illustrative play of Gather on the Clock



Input

The input consists of multiple test cases. The first line contains the number of cases. For each case, a line describing a state follows. The line begins with an integer n (2 ≤ n ≤ 100), the number of cards on the ring, and then n numbers describing the values of the cards follow. Note that the values are given in clockwise order. You can assume all these numbers are non-negative and do not exceed 100. They are separated by a single space character.

Output

For each case, output the maximum score in a line.

Example

Input

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


Output

6
34

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bureaucrats love bureaucracy. This assertion seems fairly obvious but a less obvious observation is the amount of paperwork this means!

When paperwork is complete, a bureaucrat stamps the official document with their official stamp of office. Some bureaucrats are extra thorough and stamp the document multiple times. We are interested primarily in bureaucrats that stamp their documents exactly twice.

A bureaucrat stamp takes up some rectangular area. For example, the below is a bureaucrat stamp:

       ..#..#.. .######. ..#..#..

When the bureaucrat stamps the paper twice it is potentially moved to a different location on the paper, but it is not rotated. The stamp will always be axis aligned. The ’#’ symbol on a stamp covers the paper with black ink at the cell on the paper that is pressed. A ’.’ doesn’t leave any marks on the paper nor does it remove a mark. If a cell of the paper is marked twice it is not discernable from a cell that is marked once.

You will be given a mark on a paper that was stamped twice by a stamp. Your task is to determine the minimum number of nubs (’#’ symbols) that could have possibly been on the original stamp. The paper is guaranteed to be stamped twice by the entire stamp. (All of the stamp will be on the paper in both stampings)

Consider the following mark on paper:

       ..#..#.. .######. .######. ..#..#..

It could have been made with the first stamp example, with the second stamping exactly one cell below the first. Or, it could have been made with a stamp that looks like this, stamped side-by-side:

       ..#.. .###. .###. ..#..

In this case, 8 would be the correct answer.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers, $n$ and $m$ ($1 \le n, m \le 500$) indicating the height and width of the mark on the paper. Each of the next $n$ lines will have exactly $m$ characters, consisting only of ‘#’ and ‘.’, representing the mark. Every test case will have at least one ‘#’.

-----Output-----
Output a single line with a single integer, indicating the minimum number of nubs of a bureaucrat’s stamp that could have possibly made the input mark by stamping exactly twice.

-----Examples-----
Sample Input 1:
4 8
..#..#..
.######.
.######.
..#..#..
Sample Output 1:
8

Sample Input 2:
3 3
...
.#.
...
Sample Output 2:
1

Sample Input 3:
2 6
.#####
#####.
Sample Output 3:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as possible. After all, the country is in crisis!

The computers bought for the room were different. Some of them had only USB ports, some — only PS/2 ports, and some had both options.

You have found a price list of a certain computer shop. In it, for m mouses it is specified the cost and the type of the port that is required to plug the mouse in (USB or PS/2). Each mouse from the list can be bought at most once.

You want to buy some set of mouses from the given price list in such a way so that you maximize the number of computers equipped with mouses (it is not guaranteed that you will be able to equip all of the computers), and in case of equality of this value you want to minimize the total cost of mouses you will buy.


-----Input-----

The first line contains three integers a, b and c (0 ≤ a, b, c ≤ 10^5)  — the number of computers that only have USB ports, the number of computers, that only have PS/2 ports, and the number of computers, that have both options, respectively.

The next line contains one integer m (0 ≤ m ≤ 3·10^5)  — the number of mouses in the price list.

The next m lines each describe another mouse. The i-th line contains first integer val_{i} (1 ≤ val_{i} ≤ 10^9)  — the cost of the i-th mouse, then the type of port (USB or PS/2) that is required to plug the mouse in.


-----Output-----

Output two integers separated by space — the number of equipped computers and the total cost of the mouses you will buy.


-----Example-----
Input
2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2

Output
3 14



-----Note-----

In the first example you can buy the first three mouses. This way you will equip one of the computers that has only a USB port with a USB mouse, and the two PS/2 mouses you will plug into the computer with PS/2 port and the computer with both ports.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem description
As a holiday gift, Tojo received a probability problem. The problem read as follows
Consider an N by M grid. Rows are numbered 1 to N, from top to bottom. Columns are numbered 1 to M, from left to right. You are initially at cell (1, 1) and want to go to cell (N, M). From any cell you can move to the cell below it or to the cell right to it. You should never go out of the grid. At any point you should consider all the possibilities of movement with equal probability
Let P[i][j] be the probability of visiting cell (i, j). You need to calculate the sum of P[i][j] for 1 ≤ i ≤ N, 1 ≤ i ≤ M.
As we all know, Tojo really hates probability related problems. He wants you to solve this task

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.Only line of each test case has two integer N and M.

Output
For each test case, output a single line containing the required answer. Answers within an absolute or relative error of 10^-6 will be accepted.

Constraints

1 ≤ T ≤ 1000
1 ≤ N ≤ 1000
1 ≤ M ≤ 1000


Example
Input:
2
2 2
1 6

Output:
3.000000
6.000000

Explanation
Example case 1
Probability matrix P for N=2, M=2 is
1.0 0.5
0.5 1.0
You are at (1, 1) initially. So the probablity of visiting (1, 1) is 1. At (1, 1) you have 2 options, move below to (2, 1) or to right cell (1, 2). Probablity of going to (1, 2) is 0.5. Probability of going to (2, 1) is 0.5. You always end up at (2, 2), so P[2][2] is 1. Required sum = 1.0 + 0.5 + 0.5 + 1.0 = 3.0
Example case 2
Probability matrix P for N=1, M=6 is
1.0 1.0 1.0 1.0 1.0 1.0
Because at any position there is only one possible next position.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A binary heap is a Binary Tree with the following properties:
1) Its a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.
You are given an empty Binary Min Heap and some queries and your task is to implement the three methods insertKey,  deleteKey,  and extractMin on the Binary Min Heap and call them as per the query given below:
1) 1  x  (a query of this type means to insert an element in the min-heap with value x )
2) 2  x  (a query of this type means to remove an element at position x from the min-heap)
3) 3  (a query like this removes the min element from the min-heap and prints it ).
Example 1:
Input:
Q = 7
Queries:
insertKey(4)
insertKey(2)
extractMin()
insertKey(6)
deleteKey(0)
extractMin()
extractMin()
Output: 2 6 - 1
Explanation: In the first test case for
query 
insertKey(4) the heap will have  {4}  
insertKey(2) the heap will be {2 4}
extractMin() removes min element from 
             heap ie 2 and prints it
             now heap is {4} 
insertKey(6) inserts 6 to heap now heap
             is {4 6}
deleteKey(0) delete element at position 0
             of the heap,now heap is {6}
extractMin() remove min element from heap
             ie 6 and prints it  now the
             heap is empty
extractMin() since the heap is empty thus
             no min element exist so -1
             is printed.
Example 2:
Input:
Q = 5
Queries:
insertKey(8)
insertKey(9)
deleteKey(1)
extractMin()
extractMin()
Output: 8 -1
Your Task:
You are required to complete the 3 methods insertKey() which take one argument the value to be inserted, deleteKey() which takes one argument the position from where the element is to be deleted and extractMin() which returns the minimum element in the heap(-1 if the heap is empty)
Expected Time Complexity: O(Q*Log(size of Heap) ).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Q <= 10^{4}
1 <= x <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Timothy (age: 16) really likes to smoke. Unfortunately, he is too young to buy his own cigarettes and that's why he has to be extremely efficient in smoking.

It's now your task to create a function that calculates how many cigarettes Timothy can smoke out of the given amounts of `bars` and `boxes`:

- a bar has 10 boxes of cigarettes,
- a box has 18 cigarettes,
- out of 5 stubs (cigarettes ends) Timothy is able to roll a new one,
- of course the self made cigarettes also have an end which can be used to create a new one...

Please note that Timothy never starts smoking cigarettes that aren't "full size" so the amount of smoked cigarettes is always an integer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A lighthouse keeper Peter commands an army of $n$ battle lemmings. He ordered his army to stand in a line and numbered the lemmings from $1$ to $n$ from left to right. Some of the lemmings hold shields. Each lemming cannot hold more than one shield.

The more protected Peter's army is, the better. To calculate the protection of the army, he finds the number of protected pairs of lemmings, that is such pairs that both lemmings in the pair don't hold a shield, but there is a lemming with a shield between them.

Now it's time to prepare for defence and increase the protection of the army. To do this, Peter can give orders. He chooses a lemming with a shield and gives him one of the two orders:   give the shield to the left neighbor if it exists and doesn't have a shield;  give the shield to the right neighbor if it exists and doesn't have a shield. 

In one second Peter can give exactly one order.

It's not clear how much time Peter has before the defence. So he decided to determine the maximal value of army protection for each $k$ from $0$ to $\frac{n(n-1)}2$, if he gives no more that $k$ orders. Help Peter to calculate it!


-----Input-----

First line contains a single integer $n$ ($1 \le n \le 80$), the number of lemmings in Peter's army.

Second line contains $n$ integers $a_i$ ($0 \le a_i \le 1$). If $a_i = 1$, then the $i$-th lemming has a shield, otherwise $a_i = 0$.


-----Output-----

Print $\frac{n(n-1)}2 + 1$ numbers, the greatest possible protection after no more than $0, 1, \dots, \frac{n(n-1)}2$ orders.


-----Examples-----
Input
5
1 0 0 0 1

Output
0 2 3 3 3 3 3 3 3 3 3 

Input
12
0 0 0 0 1 1 1 1 0 1 1 0

Output
9 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 



-----Note-----

Consider the first example.

The protection is initially equal to zero, because for each pair of lemmings without shields there is no lemmings with shield.

In one second Peter can order the first lemming give his shield to the right neighbor. In this case, the protection is two, as there are two protected pairs of lemmings, $(1, 3)$ and $(1, 4)$.

In two seconds Peter can act in the following way. First, he orders the fifth lemming to give a shield to the left neighbor. Then, he orders the first lemming to give a shield to the right neighbor. In this case Peter has three protected pairs of lemmings — $(1, 3)$, $(1, 5)$ and $(3, 5)$.

You can make sure that it's impossible to give orders in such a way that the protection becomes greater than three.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a matrix containing lower alphabetical characters only of size n*m. We need to count the number of palindromic paths in the given matrix.
A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell.
 
Example 1:
Input: matrix = {{a,a,a,b},{b,a,a,a},{a,b,b,a}}
Output: 3
Explanation: Number of palindromic paths are 3 
from top-left to bottom-right.
aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> 
(1, 3) -> (2, 3)    
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> 
(1, 3) -> (2, 3)    
abaaba (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> 
(2, 2) -> (2, 3)
Example 2:
Input: matrix = {{a,b},{c,d}}
Output: 0
Explanation: There is no palindromic paths.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function countPalindromicPaths() which takes the matrix as input parameter and returns the total nuumber of palindromic paths modulo 10^{9} + 7.
 
Expected Time Complexity: O(n^{2}*m^{2})
Space Complexity: O(n*m)
 
Constraints:
1 ≤ n, m ≤ 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rooted tree. Let's denote d(x) as depth of node x: depth of the root is 1, depth of any other node x is d(y) + 1, where y is a parent of x.

The tree has the following property: every node x with d(x) = i has exactly ai children. Maximum possible depth of a node is n, and an = 0.

We define fk as the number of unordered pairs of vertices in the tree such that the number of edges on the simple path between them is equal to k.

Calculate fk modulo 109 + 7 for every 1 ≤ k ≤ 2n - 2.

Input

The first line of input contains an integer n (2 ≤ n ≤ 5 000) — the maximum depth of a node.

The second line of input contains n - 1 integers a1, a2, ..., an - 1 (2 ≤ ai ≤ 109), where ai is the number of children of every node x such that d(x) = i. Since an = 0, it is not given in the input.

Output

Print 2n - 2 numbers. The k-th of these numbers must be equal to fk modulo 109 + 7.

Examples

Input

4
2 2 2


Output

14 19 20 20 16 16 

Input

3
2 3


Output

8 13 6 9 

Note

This the tree from the first sample: 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer n. Output its prime factorization.

If n = a1b1 a2b2 ... akbk (bi > 0), where ak are prime numbers, the output of your program should look as follows: a1*...*a1*a2*...*a2*...*ak*...*ak, where the factors are ordered in non-decreasing order, and each factor ai is printed bi times.

Input

The only line of input contains an integer n (2 ≤ n ≤ 10000).

Output

Output the prime factorization of n, as described above.

Examples

Input

245


Output

5*7*7


Input

19


Output

19

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata you are given an array to sort but you're expected to start sorting from a specific position of the array (in ascending order) and optionally you're given the number of items to sort.

#### Examples:

```python
sect_sort([1, 2, 5, 7, 4, 6, 3, 9, 8], 2) //=> [1, 2, 3, 4, 5, 6, 7, 8, 9]
sect_sort([9, 7, 4, 2, 5, 3, 1, 8, 6], 2, 5) //=> [9, 7, 1, 2, 3, 4, 5, 8, 6]
```

#### Documentation:

```python
sect_sort(array, start, length);
```

- array - array to sort
- start - position to begin sorting
- length - number of items to sort (optional)

if the **length** argument is not passed or is zero, you sort all items to the right of the start postiton in the array

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bizon the Champion isn't just a bison. He also is a favorite of the "Bizons" team.

At a competition the "Bizons" got the following problem: "You are given two distinct words (strings of English letters), s and t. You need to transform word s into word t". The task looked simple to the guys because they know the suffix data structures well. Bizon Senior loves suffix automaton. By applying it once to a string, he can remove from this string any single character. Bizon Middle knows suffix array well. By applying it once to a string, he can swap any two characters of this string. The guys do not know anything about the suffix tree, but it can help them do much more. 

Bizon the Champion wonders whether the "Bizons" can solve the problem. Perhaps, the solution do not require both data structures. Find out whether the guys can solve the problem and if they can, how do they do it? Can they solve it either only with use of suffix automaton or only with use of suffix array or they need both structures? Note that any structure may be used an unlimited number of times, the structures may be used in any order.


-----Input-----

The first line contains a non-empty word s. The second line contains a non-empty word t. Words s and t are different. Each word consists only of lowercase English letters. Each word contains at most 100 letters.


-----Output-----

In the single line print the answer to the problem. Print "need tree" (without the quotes) if word s cannot be transformed into word t even with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print "array" (without the quotes) if you need only the suffix array to solve the problem. Print "both" (without the quotes), if you need both data structures to solve the problem.

It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix automaton.


-----Examples-----
Input
automaton
tomat

Output
automaton

Input
array
arary

Output
array

Input
both
hot

Output
both

Input
need
tree

Output
need tree



-----Note-----

In the third sample you can act like that: first transform "both" into "oth" by removing the first character using the suffix automaton and then make two swaps of the string using the suffix array and get "hot".

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