vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
After hard work Igor decided to have some rest.

He decided to have a snail. He bought an aquarium with a slippery tree trunk in the center, and put a snail named Julia into the aquarium.

Igor noticed that sometimes Julia wants to climb onto the trunk, but can't do it because the trunk is too slippery. To help the snail Igor put some ropes on the tree, fixing the lower end of the i-th rope on the trunk on the height li above the ground, and the higher end on the height ri above the ground.

For some reason no two ropes share the same position of the higher end, i.e. all ri are distinct. Now Julia can move down at any place of the trunk, and also move up from the lower end of some rope to its higher end. Igor is proud of his work, and sometimes think about possible movements of the snail. Namely, he is interested in the following questions: «Suppose the snail is on the trunk at height x now. What is the highest position on the trunk the snail can get on if it would never be lower than x or higher than y?» Please note that Julia can't move from a rope to the trunk before it reaches the higher end of the rope, and Igor is interested in the highest position on the tree trunk.

Igor is interested in many questions, and not always can answer them. Help him, write a program that answers these questions.

Input

The first line contains single integer n (1 ≤ n ≤ 100000) — the height of the trunk.

The second line contains single integer m (1 ≤ m ≤ 100000) — the number of ropes.

The next m lines contain information about the ropes.

The i-th of these lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the heights on which the lower and the higher ends of the i-th rope are fixed, respectively. It is guaranteed that all ri are distinct.

The next line contains single integer q (1 ≤ q ≤ 100000) — the number of questions.

The next q lines contain information about the questions.

Each of these lines contain two integers x and y (1 ≤ x ≤ y ≤ n), where x is the height where Julia starts (and the height Julia can't get lower than), and y is the height Julia can't get higher than.

Output

For each question print the maximum reachable for Julia height.

Examples

Input

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


Output

2
2
5
5
7


Input

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


Output

2
7
3
3
2
2
5
3
7
10

Note

The picture of the first sample is on the left, the picture of the second sample is on the right. Ropes' colors are just for clarity, they don't mean anything.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are currently n hot topics numbered from 0 to n-1 at your local bridge club and 2^n players numbered from 0 to 2^n-1. Each player holds a different set of views on those n topics, more specifically, the i-th player holds a positive view on the j-th topic if i\ \&\ 2^j > 0, and a negative view otherwise. Here \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

You are going to organize a bridge tournament capable of accommodating at most k pairs of players (bridge is played in teams of two people). You can select teams arbitrarily while each player is in at most one team, but there is one catch: two players cannot be in the same pair if they disagree on 2 or more of those n topics, as they would argue too much during the play.

You know that the i-th player will pay you a_i dollars if they play in this tournament. Compute the maximum amount of money that you can earn if you pair the players in your club optimally.

Input

The first line contains two integers n, k (1 ≤ n ≤ 20, 1 ≤ k ≤ 200) — the number of hot topics and the number of pairs of players that your tournament can accommodate.

The second line contains 2^n integers a_0, a_1, ..., a_{2^n-1} (0 ≤ a_i ≤ 10^6) — the amounts of money that the players will pay to play in the tournament.

Output

Print one integer: the maximum amount of money that you can earn if you pair the players in your club optimally under the above conditions.

Examples

Input


3 1
8 3 5 7 1 10 3 2


Output


13


Input


2 3
7 4 5 7


Output


23


Input


3 2
1 9 1 5 7 8 1 1


Output


29

Note

In the first example, the best we can do is to pair together the 0-th player and the 2-nd player resulting in earnings of 8 + 5 = 13 dollars. Although pairing the 0-th player with the 5-th player would give us 8 + 10 = 18 dollars, we cannot do this because those two players disagree on 2 of the 3 hot topics.

In the second example, we can pair the 0-th player with the 1-st player and pair the 2-nd player with the 3-rd player resulting in earnings of 7 + 4 + 5 + 7 = 23 dollars.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose there is a $h \times w$ grid consisting of empty or full cells. Let's make some definitions:

  $r_{i}$ is the number of consecutive full cells connected to the left side in the $i$-th row ($1 \le i \le h$). In particular, $r_i=0$ if the leftmost cell of the $i$-th row is empty.  $c_{j}$ is the number of consecutive full cells connected to the top end in the $j$-th column ($1 \le j \le w$). In particular, $c_j=0$ if the topmost cell of the $j$-th column is empty. 

In other words, the $i$-th row starts exactly with $r_i$ full cells. Similarly, the $j$-th column starts exactly with $c_j$ full cells.

 [Image] These are the $r$ and $c$ values of some $3 \times 4$ grid. Black cells are full and white cells are empty. 

You have values of $r$ and $c$. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of $r$ and $c$. Since the answer can be very large, find the answer modulo $1000000007\,(10^{9} + 7)$. In other words, find the remainder after division of the answer by $1000000007\,(10^{9} + 7)$.


-----Input-----

The first line contains two integers $h$ and $w$ ($1 \le h, w \le 10^{3}$) — the height and width of the grid.

The second line contains $h$ integers $r_{1}, r_{2}, \ldots, r_{h}$ ($0 \le r_{i} \le w$) — the values of $r$.

The third line contains $w$ integers $c_{1}, c_{2}, \ldots, c_{w}$ ($0 \le c_{j} \le h$) — the values of $c$.


-----Output-----

Print the answer modulo $1000000007\,(10^{9} + 7)$.


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

Output
2

Input
1 1
0
1

Output
0

Input
19 16
16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12
6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4

Output
797922655



-----Note-----

In the first example, this is the other possible case.

 [Image] 

In the second example, it's impossible to make a grid to satisfy such $r$, $c$ values.

In the third example, make sure to print answer modulo $(10^9 + 7)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n arrays that can have different sizes. You also have a table with w columns and n rows. The i-th array is placed horizontally in the i-th row. You can slide each array within its row as long as it occupies several consecutive cells and lies completely inside the table.

You need to find the maximum sum of the integers in the j-th column for each j from 1 to w independently.

<image> Optimal placements for columns 1, 2 and 3 are shown on the pictures from left to right.

Note that you can exclude any array out of a column provided it remains in the window. In this case its value is considered to be zero.

Input

The first line contains two integers n (1 ≤ n ≤ 10^{6}) and w (1 ≤ w ≤ 10^{6}) — the number of arrays and the width of the table.

Each of the next n lines consists of an integer l_{i} (1 ≤ l_{i} ≤ w), the length of the i-th array, followed by l_{i} integers a_{i1}, a_{i2}, …, a_{il_i} (-10^{9} ≤ a_{ij} ≤ 10^{9}) — the elements of the array.

The total length of the arrays does no exceed 10^{6}.

Output

Print w integers, the i-th of them should be the maximum sum for column i.

Examples

Input


3 3
3 2 4 8
2 2 5
2 6 3


Output


10 15 16 


Input


2 2
2 7 8
1 -8


Output


7 8 

Note

Illustration for the first example is in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tribonacci numbers are a sequence of numbers, defined as follows:

  * t0 = t1 = 0,
  * t2 = 1,
  * ti = ti - 1 + ti - 2 + ti - 3.



You are given n; calculate n-th tribonacci number modulo 26.

Input

The only line of input contains an integer n (1 ≤ n ≤ 1000).

Output

Output n-th tribonacci number modulo 26.

Examples

Input

4


Output

2


Input

9


Output

18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n workers in a company, each of them has a unique id from 1 to n. Exaclty one of them is a chief, his id is s. Each worker except the chief has exactly one immediate superior.

There was a request to each of the workers to tell how how many superiors (not only immediate). Worker's superiors are his immediate superior, the immediate superior of the his immediate superior, and so on. For example, if there are three workers in the company, from which the first is the chief, the second worker's immediate superior is the first, the third worker's immediate superior is the second, then the third worker has two superiors, one of them is immediate and one not immediate. The chief is a superior to all the workers except himself.

Some of the workers were in a hurry and made a mistake. You are to find the minimum number of workers that could make a mistake.


-----Input-----

The first line contains two positive integers n and s (1 ≤ n ≤ 2·10^5, 1 ≤ s ≤ n) — the number of workers and the id of the chief.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1), where a_{i} is the number of superiors (not only immediate) the worker with id i reported about.


-----Output-----

Print the minimum number of workers that could make a mistake.


-----Examples-----
Input
3 2
2 0 2

Output
1

Input
5 3
1 0 0 4 1

Output
2



-----Note-----

In the first example it is possible that only the first worker made a mistake. Then:   the immediate superior of the first worker is the second worker,  the immediate superior of the third worker is the first worker,  the second worker is the chief.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Given a sorted array of integers `A`, find such an integer x that the value of `abs(A[0] - x) + abs(A[1] - x) + ... + abs(A[A.length - 1] - x)`
is the smallest possible (here abs denotes the `absolute value`).

 If there are several possible answers, output the smallest one.

# Example

 For `A = [2, 4, 7]`, the output should be `4`.

# Input/Output


 - `[input]` integer array `A`

    A non-empty array of integers, sorted in ascending order.

    Constraints:

    `1 ≤ A.length ≤ 200,`

    `-1000000 ≤ A[i] ≤ 1000000.`


 - `[output]` an integer

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Piegirl is buying stickers for a project. Stickers come on sheets, and each sheet of stickers contains exactly n stickers. Each sticker has exactly one character printed on it, so a sheet of stickers can be described by a string of length n. Piegirl wants to create a string s using stickers. She may buy as many sheets of stickers as she wants, and may specify any string of length n for the sheets, but all the sheets must be identical, so the string is the same for all sheets. Once she attains the sheets of stickers, she will take some of the stickers from the sheets and arrange (in any order) them to form s. Determine the minimum number of sheets she has to buy, and provide a string describing a possible sheet of stickers she should buy.


-----Input-----

The first line contains string s (1 ≤ |s| ≤ 1000), consisting of lowercase English characters only. The second line contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

On the first line, print the minimum number of sheets Piegirl has to buy. On the second line, print a string consisting of n lower case English characters. This string should describe a sheet of stickers that Piegirl can buy in order to minimize the number of sheets. If Piegirl cannot possibly form the string s, print instead a single line with the number -1.


-----Examples-----
Input
banana
4

Output
2
baan

Input
banana
3

Output
3
nab

Input
banana
2

Output
-1



-----Note-----

In the second example, Piegirl can order 3 sheets of stickers with the characters "nab". She can take characters "nab" from the first sheet, "na" from the second, and "a" from the third, and arrange them to from "banana".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata you are to implement a function that parses a string which is composed from tokens of the form 'n1-n2,n3,n4-n5:n6' where 'nX' is a positive integer. Each token represent a different range:

'n1-n2' represents the range n1 to n2 (inclusive in both ends).
'n3' represents the single integer n3.
'n4-n5:n6' represents the range n4 to n5 (inclusive in both ends) but only includes every other n6 integer.

Notes:
1. The input string doesn't not have to include all the token types.
2. All integers are assumed to be positive.
3. Tokens may be separated by `','`, `', '` or ` , `.

Some examples:

'1-10,14, 20-25:2' -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 20, 22, 24]

'5-10' -> [5, 6, 7, 8, 9, 10]

'2' -> [2]

The output should be a list of integers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix has a string $s$ consisting of lowercase Latin letters. He wants to distribute all the letters of his string into $k$ non-empty strings $a_1, a_2, \dots, a_k$ such that every letter of $s$ goes to exactly one of the strings $a_i$. The strings $a_i$ do not need to be substrings of $s$. Phoenix can distribute letters of $s$ and rearrange the letters within each string $a_i$ however he wants.

For example, if $s = $ baba and $k=2$, Phoenix may distribute the letters of his string in many ways, such as:   ba and ba  a and abb  ab and ab  aa and bb 

But these ways are invalid:   baa and ba  b and ba  baba and empty string ($a_i$ should be non-empty) 

Phoenix wants to distribute the letters of his string $s$ into $k$ strings $a_1, a_2, \dots, a_k$ to minimize the lexicographically maximum string among them, i. e. minimize $max(a_1, a_2, \dots, a_k)$. Help him find the optimal distribution and print the minimal possible value of $max(a_1, a_2, \dots, a_k)$.

String $x$ is lexicographically less than string $y$ if either $x$ is a prefix of $y$ and $x \ne y$, or there exists an index $i$ ($1 \le i \le min(|x|, |y|))$ such that $x_i$ < $y_i$ and for every $j$ $(1 \le j < i)$ $x_j = y_j$. Here $|x|$ denotes the length of the string $x$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Each test case consists of two lines.

The first line of each test case consists of two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of string $s$ and the number of non-empty strings, into which Phoenix wants to distribute letters of $s$, respectively.

The second line of each test case contains a string $s$ of length $n$ consisting only of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases is $\le 10^5$.


-----Output-----

Print $t$ answers — one per test case. The $i$-th answer should be the minimal possible value of $max(a_1, a_2, \dots, a_k)$ in the $i$-th test case.


-----Example-----
Input
6
4 2
baba
5 2
baacb
5 3
baacb
5 3
aaaaa
6 4
aaxxzz
7 1
phoenix

Output
ab
abbc
b
aa
x
ehinopx



-----Note-----

In the first test case, one optimal solution is to distribute baba into ab and ab. 

In the second test case, one optimal solution is to distribute baacb into abbc and a.

In the third test case, one optimal solution is to distribute baacb into ac, ab, and b.

In the fourth test case, one optimal solution is to distribute aaaaa into aa, aa, and a.

In the fifth test case, one optimal solution is to distribute aaxxzz into az, az, x, and x.

In the sixth test case, one optimal solution is to distribute phoenix into ehinopx.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. Jump ability is the maximum possible length of his jump. 

Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his jump ability.

<image> The picture corresponds to the first example.

The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'.

Input

The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100. 

Output

Print single integer a — the minimum jump ability of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels.

Examples

Input

ABABBBACFEYUKOTT


Output

4

Input

AAA


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an H \times W grid, where each square is painted white or black in the initial state. Given are strings A_1, A_2, ..., A_H representing the colors of the squares in the initial state. For each pair (i, j) (1 \leq i \leq H, 1 \leq j \leq W), if the j-th character of A_i is `.`, the square at the i-th row and j-th column is painted white; if that character is `#`, that square is painted black.

Among the 2^{HW} ways for each square in the grid to be painted white or black, how many can be obtained from the initial state by performing the operations below any number of times (possibly zero) in any order? Find this count modulo 998,244,353.

* Choose one row, then paint all the squares in that row white.
* Choose one row, then paint all the squares in that row black.
* Choose one column, then paint all the squares in that column white.
* Choose one column, then paint all the squares in that column black.

Constraints

* 1 \leq H, W \leq 10
* |A_i| = W (1 \leq i \leq H)
* All strings A_i consist of `.` and `#`.
* H and W are integers.

Input

Input is given from Standard Input in the following format:


H W
A_1
A_2
\vdots
A_H


Output

Print the answer.

Examples

Input

2 2
#.
.#


Output

15


Input

2 2
.
.#


Output

15


Input

3 3
...
...
...


Output

230


Input

2 4
...
...#


Output

150


Input

6 7
.......
.......
.#.....
..#....
.#.#...
.......


Output

203949910

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Vasya likes very much to play with sets consisting of positive integers. To make the game more interesting, Vasya chose n non-empty sets in such a way, that no two of them have common elements.

One day he wanted to show his friends just how interesting playing with numbers is. For that he wrote out all possible unions of two different sets on n·(n - 1) / 2 pieces of paper. Then he shuffled the pieces of paper. He had written out the numbers in the unions in an arbitrary order.

For example, if n = 4, and the actual sets have the following form {1, 3}, {5}, {2, 4}, {7}, then the number of set pairs equals to six. The six pieces of paper can contain the following numbers: 

  * 2, 7, 4. 
  * 1, 7, 3; 
  * 5, 4, 2; 
  * 1, 3, 5; 
  * 3, 1, 2, 4; 
  * 5, 7. 



Then Vasya showed the pieces of paper to his friends, but kept the n sets secret from them. His friends managed to calculate which sets Vasya had thought of in the first place. And how about you, can you restore the sets by the given pieces of paper?

Input

The first input file line contains a number n (2 ≤ n ≤ 200), n is the number of sets at Vasya's disposal. Then follow sets of numbers from the pieces of paper written on n·(n - 1) / 2 lines. Each set starts with the number ki (2 ≤ ki ≤ 200), which is the number of numbers written of the i-th piece of paper, and then follow ki numbers aij (1 ≤ aij ≤ 200). All the numbers on the lines are separated by exactly one space. It is guaranteed that the input data is constructed according to the above given rules from n non-intersecting sets.

Output

Print on n lines Vasya's sets' description. The first number on the line shows how many numbers the current set has. Then the set should be recorded by listing its elements. Separate the numbers by spaces. Each number and each set should be printed exactly once. Print the sets and the numbers in the sets in any order. If there are several answers to that problem, print any of them.

It is guaranteed that there is a solution.

Examples

Input

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


Output

1 7 
2 2 4 
2 1 3 
1 5 


Input

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


Output

3 7 8 9 
2 6 100 
1 1 
1 2 


Input

3
2 1 2
2 1 3
2 2 3


Output

1 1 
1 2 
1 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock Holmes suspects his archenemy Professor Moriarty is once again plotting something diabolical. Sherlock's companion, Dr. Watson, suggests Moriarty may be responsible for MI6's recent issues with their supercomputer, The Beast. 

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beast with a virus.  He also gives him a clue:  an integer. Sherlock determines the key to removing the virus is to find the largest Decent Number having that number of digits.

A Decent Number has the following properties:

Its digits can only be 3's and/or 5's.
The number of 3's it contains is divisible by 5.
The number of 5's it contains is divisible by 3.
It is the largest such number for its length. 

Moriarty's virus shows a clock counting down to The Beast's destruction, and time is running out fast. Your task is to help Sherlock find the key before The Beast is destroyed!

For example, the numbers $55533333$ and $555555$ are both decent numbers because there are $3$ $5$'s and $5$ $3$'s in the first, and $6$ $5$'s in the second.  They are the largest values for those length numbers that have proper divisibility of digit occurrences.  

Function Description

Complete the decentNumber function in the editor below.     

decentNumber has the following parameter(s):  

int n: the length of the decent number to create  

Prints  

Print the decent number for the given length, or $-1$ if a decent number of that length cannot be formed. No return value is expected.  

Input Format

The first line is an integer, $t$, the number of test cases. 

The next $t$ lines each contain an integer $n$, the number of digits in the number to create.

Constraints

$1\leq t\leq20$ 

$1\leq n\leq10000$  

Sample Input
STDIN   Function
-----   --------
4       t = 4
1       n = 1 (first test case)
3       n = 3 (second test case)
5
11

Sample Output
-1
555
33333
55555533333

Explanation

For $n=1$, there is no Decent Number having $1$ digit, so print $-1$. 

For $n=3$, $555$ is the only possible number. (Decent Number Property 3). 

For $n=5$, $33333$ is the only possible number. (Decent Number Property 2). 

For $n=11$, $55555533333$ is the Decent Number.  All other permutations of these digits are not decent (Decent Number Property 4).

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