vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Friends Alex and Bob live in Bertown. In this town there are n crossroads, some of them are connected by bidirectional roads of equal length. Bob lives in a house at the crossroads number 1, Alex — in a house at the crossroads number n.

One day Alex and Bob had a big quarrel, and they refused to see each other. It occurred that today Bob needs to get from his house to the crossroads n and Alex needs to get from his house to the crossroads 1. And they don't want to meet at any of the crossroads, but they can meet in the middle of the street, when passing it in opposite directions. Alex and Bob asked you, as their mutual friend, to help them with this difficult task.

Find for Alex and Bob such routes with equal number of streets that the guys can follow these routes and never appear at the same crossroads at the same time. They are allowed to meet in the middle of the street when moving toward each other (see Sample 1). Among all possible routes, select such that the number of streets in it is the least possible. Until both guys reach their destinations, none of them can stay without moving. 

The guys are moving simultaneously with equal speeds, i.e. it is possible that when one of them reaches some of the crossroads, the other one leaves it. For example, Alex can move from crossroad 1 to crossroad 2, while Bob moves from crossroad 2 to crossroad 3.

If the required routes don't exist, your program should output -1.

Input

The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) — the amount of crossroads and the amount of roads. Each of the following m lines contains two integers — the numbers of crossroads connected by the road. It is guaranteed that no road connects a crossroads with itself and no two crossroads are connected by more than one road.

Output

If the required routes don't exist, output -1. Otherwise, the first line should contain integer k — the length of shortest routes (the length of the route is the amount of roads in it). The next line should contain k + 1 integers — Bob's route, i.e. the numbers of k + 1 crossroads passed by Bob. The last line should contain Alex's route in the same format. If there are several optimal solutions, output any of them.

Examples

Input

2 1
1 2


Output

1
1 2 
2 1 


Input

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


Output

-1


Input

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


Output

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive number $x$ of length $n$ in base $p$ ($2 \le p \le 10^9$) is written on the blackboard. The number $x$ is given as a sequence $a_1, a_2, \dots, a_n$ ($0 \le a_i < p$) — the digits of $x$ in order from left to right (most significant to least significant).

Dmitry is very fond of all the digits of this number system, so he wants to see each of them at least once.

In one operation, he can:

take any number $x$ written on the board, increase it by $1$, and write the new value $x + 1$ on the board.

For example, $p=5$ and $x=234_5$.

Initially, the board contains the digits $2$, $3$ and $4$;

Dmitry increases the number $234_5$ by $1$ and writes down the number $240_5$. On the board there are digits $0, 2, 3, 4$;

Dmitry increases the number $240_5$ by $1$ and writes down the number $241_5$. Now the board contains all the digits from $0$ to $4$.

Your task is to determine the minimum number of operations required to make all the digits from $0$ to $p-1$ appear on the board at least once.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 2 \cdot 10^3$) — the number of test cases. The descriptions of the input test cases follow.

The first line of description of each test case contains two integers $n$ ($1 \le n \le 100$) and $p$ ($2 \le p \le 10^9$) — the length of the number and the base of the number system.

The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < p$) — digits of $x$ in number system with base $p$

It is guaranteed that the number $x$ does not contain leading zeros (that is, $a_1>0$).


-----Output-----

For each test case print a single integer — the minimum number of operations required for Dmitry to get all the digits on the board from $0$ to $p-1$.

It can be shown that this always requires a finite number of operations.


-----Examples-----

Input
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
Output
1
1
0
0
7
995
2
1
1
1
2


-----Note-----

None

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

There is a dial-type padlock. This Nanjing lock has five dials and an enter button.

Rotate the five dials to create a five-digit integer in hexadecimal, press the enter button to enter it, and if the entered value and password match, it will open. For each of the five dials

0,1,2,3,4,5,6,7,8,9, a, b, c, d, e, f, 0,1,2,3,4,5,6,7,8, 9,a, b, c, d, e, f, 0,1,2, ...

It is written so that the characters appear in the order of.

The owner has forgotten the password. However, I remember that out of the five digits of the password, only one digit was even and the other four were odd. However, even numbers are 0,2,4,6,8, a, c, e, and odd numbers are 1,3,5,7,9, b, d, f.

It is also known that this key is defective and will open even if you enter a number different from the password under the following conditions. Originally, the key cannot be opened unless the entered integer and password match for all five digits. However, if the even-numbered digits of the password are the i-digits, the i-digits will match even if the odd numbers before and after the even-numbered numbers are entered when determining the match of the i-digits. It will be misjudged.

For example, if the password is a padlock of "57677", there are odd numbers of '5' and '7' before and after '6', so even if you enter "57577" or "57777" in addition to "57677" It will open. Similarly, if the password is a padlock with "130bd", when you enter "13fbd" or "131bd" in addition to "130bd" because there are odd numbers of "1" and "f" before and after "0". But it opens.

We now know that there are N password candidates, one of which is the correct password. The owner decided to enter an integer many times and keep trying until the key was unlocked. The owner wants to press the enter button as few times as possible.

How many times do you have to press the enter button when the owner takes the best strategy? Print that number. Also, output the set of integers to be input when it actually reaches the maximum in ascending order. If the answer is not uniquely determined, output the smallest one in lexicographical order.

Constraints

* 1 ≤ N ≤ 6000
* passwordi ≠ passwordj (i <j)
* The string consists of 5 numbers from 0 to 9 or lowercase letters a to f, one of which is even and the other four are odd.

Input

The input is given in the following format.


N
password1
password2
...
passwordN

N is given on the first line.
The string passwordi, which represents a 5-digit hexadecimal number representing a password candidate, is given to the i-th line from the second line to the N + 1 line.

Output

Output the maximum number of times the enter button is pressed when the optimal strategy is taken before the key is unlocked on one line. Then, output the set of integers to be input at the maximum in ascending order. If the answer is not unique, output the smallest one in lexicographical order.

Examples

Input

1
0111f


Output

1
0111f


Input

3
57567
57587
0d351


Output

2
0d351
57577


Input

6
1811b
1a11b
f3b1e
f3b1c
b0df3
bedf3


Output

3
1911b
bfdf3
f3b1d

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The following problem is well-known: given integers n and m, calculate $2^{n} \operatorname{mod} m$, 

where 2^{n} = 2·2·...·2 (n factors), and $x \operatorname{mod} y$ denotes the remainder of division of x by y.

You are asked to solve the "reverse" problem. Given integers n and m, calculate $m \operatorname{mod} 2^{n}$. 


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^8).

The second line contains a single integer m (1 ≤ m ≤ 10^8).


-----Output-----

Output a single integer — the value of $m \operatorname{mod} 2^{n}$.


-----Examples-----
Input
4
42

Output
10

Input
1
58

Output
0

Input
98765432
23456789

Output
23456789



-----Note-----

In the first example, the remainder of division of 42 by 2^4 = 16 is equal to 10.

In the second example, 58 is divisible by 2^1 = 2 without remainder, and the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a matrix A of size x × y filled with integers. For every $i \in [ 1 . . x ]$, $j \in [ 1 . . y ]$ A_{i}, j = y(i - 1) + j. Obviously, every integer from [1..xy] occurs exactly once in this matrix. 

You have traversed some path in this matrix. Your path can be described as a sequence of visited cells a_1, a_2, ..., a_{n} denoting that you started in the cell containing the number a_1, then moved to the cell with the number a_2, and so on.

From the cell located in i-th line and j-th column (we denote this cell as (i, j)) you can move into one of the following cells: (i + 1, j) — only if i < x;  (i, j + 1) — only if j < y;  (i - 1, j) — only if i > 1;  (i, j - 1) — only if j > 1.

Notice that making a move requires you to go to an adjacent cell. It is not allowed to stay in the same cell. You don't know x and y exactly, but you have to find any possible values for these numbers such that you could start in the cell containing the integer a_1, then move to the cell containing a_2 (in one step), then move to the cell containing a_3 (also in one step) and so on. Can you choose x and y so that they don't contradict with your sequence of moves?


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of cells you visited on your path (if some cell is visited twice, then it's listed twice).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the integers in the cells on your path.


-----Output-----

If all possible values of x and y such that 1 ≤ x, y ≤ 10^9 contradict with the information about your path, print NO.

Otherwise, print YES in the first line, and in the second line print the values x and y such that your path was possible with such number of lines and columns in the matrix. Remember that they must be positive integers not exceeding 10^9.


-----Examples-----
Input
8
1 2 3 6 9 8 5 2

Output
YES
3 3

Input
6
1 2 1 2 5 3

Output
NO

Input
2
1 10

Output
YES
4 9



-----Note-----

The matrix and the path on it in the first test looks like this: [Image] 

Also there exist multiple correct answers for both the first and the third examples.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You and your friend are participating in a TV show "Run For Your Prize".

At the start of the show n prizes are located on a straight line. i-th prize is located at position a_{i}. Positions of all prizes are distinct. You start at position 1, your friend — at position 10^6 (and there is no prize in any of these two positions). You have to work as a team and collect all prizes in minimum possible time, in any order.

You know that it takes exactly 1 second to move from position x to position x + 1 or x - 1, both for you and your friend. You also have trained enough to instantly pick up any prize, if its position is equal to your current position (and the same is true for your friend). Carrying prizes does not affect your speed (or your friend's speed) at all.

Now you may discuss your strategy with your friend and decide who will pick up each prize. Remember that every prize must be picked up, either by you or by your friend.

What is the minimum number of seconds it will take to pick up all the prizes?


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^6 - 1) — the positions of the prizes. No two prizes are located at the same position. Positions are given in ascending order.


-----Output-----

Print one integer — the minimum number of seconds it will take to collect all prizes.


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

Output
8

Input
2
2 999995

Output
5



-----Note-----

In the first example you take all the prizes: take the first at 1, the second at 2 and the third at 8.

In the second example you take the first prize in 1 second and your friend takes the other in 5 seconds, you do this simultaneously, so the total time is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is same as the previous one, but has larger constraints.

Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse.

There are n planets in the Catniverse, numbered from 1 to n. At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs k - 1 moves, where in each move Neko is moved from the current planet x to some other planet y such that:

  * Planet y is not visited yet. 
  * 1 ≤ y ≤ x + m (where m is a fixed constant given in the input) 



This way, Neko will visit exactly k different planets. Two ways of visiting planets are called different if there is some index i such that, the i-th planet visited in the first way is different from the i-th planet visited in the second way.

What is the total number of ways to visit k planets this way? Since the answer can be quite large, print it modulo 10^9 + 7.

Input

The only line contains three integers n, k and m (1 ≤ n ≤ 10^9, 1 ≤ k ≤ min(n, 12), 1 ≤ m ≤ 4) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant m.

Output

Print exactly one integer — the number of different ways Neko can visit exactly k planets. Since the answer can be quite large, print it modulo 10^9 + 7.

Examples

Input


3 3 1


Output


4


Input


4 2 1


Output


9


Input


5 5 4


Output


120


Input


100 1 2


Output


100

Note

In the first example, there are 4 ways Neko can visit all the planets:

  * 1 → 2 → 3 
  * 2 → 3 → 1 
  * 3 → 1 → 2 
  * 3 → 2 → 1 



In the second example, there are 9 ways Neko can visit exactly 2 planets:

  * 1 → 2 
  * 2 → 1 
  * 2 → 3 
  * 3 → 1 
  * 3 → 2 
  * 3 → 4 
  * 4 → 1 
  * 4 → 2 
  * 4 → 3 



In the third example, with m = 4, Neko can visit all the planets in any order, so there are 5! = 120 ways Neko can visit all the planets.

In the fourth example, Neko only visit exactly 1 planet (which is also the planet he initially located), and there are 100 ways to choose the starting planet for Neko.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a *khm*mad*khm* scientist and you decided to play with electron distribution among atom's shells.
You know that basic idea of electron distribution is that electrons should fill a shell untill it's holding the maximum number of electrons.


  ---
Rules:  
  - Maximum number of electrons in a shell is distributed with a rule of 2n^2 (n being position of a shell). 
  - For example, maximum number of electrons in 3rd shield is 2*3^2 = 18.
  - Electrons should fill the lowest level shell first.
  - If the electrons have completely filled the lowest level shell, the other unoccupied electrons will fill the higher level shell and so on.  
  ---
        
```
Ex.:    atomicNumber(1); should return [1]
        atomicNumber(10); should return [2, 8]
        atomicNumber(11); should return [2, 8, 1]
        atomicNumber(47); should return [2, 8, 18, 19]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.

In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.

You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input

The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.

Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output

Print m integers — the answers to the queries in the order the queries appear in the input.

Examples

Input

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


Output

2
2
1
0
1


Input

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


Output

4

Note

A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Padovan sequence is the sequence of integers `P(n)` defined by the initial values

`P(0)=P(1)=P(2)=1`

and the recurrence relation

`P(n)=P(n-2)+P(n-3)`

The first few values of `P(n)` are

`1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ...`

### Task 

The task is to write a method that returns i-th Padovan number

```python
> padovan(0) == 1
> padovan(1) == 1
> padovan(2) == 1
> padovan(n) = padovan(n-2) + padovan(n-3)
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two numbers A and B. The task is to compute the last digit of the resulting F, where F= B! / A! .
Example 1:
Input: A = 2, B = 4
Output: 2
Explaination: The value of F = 12. So the 
last digit is 2.
Example 2:
Input: A = 3, B = 8
Output: 0
Explaination: F is 6720. So the last value 
is 0.
Your Task:
You do not need to read the input or print anything. Your task is to complete the function lastDigit() which takes A and B and returns the last value of F.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints: 
1 ≤ A ≤ B ≤ 10^{18}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The length of the longest common prefix of two strings s = s_1 s_2 … s_n and t = t_1 t_2 … t_m is defined as the maximum integer k (0 ≤ k ≤ min(n,m)) such that s_1 s_2 … s_k equals t_1 t_2 … t_k.

Koa the Koala initially has n+1 strings s_1, s_2, ..., s_{n+1}.

For each i (1 ≤ i ≤ n) she calculated a_i — the length of the longest common prefix of s_i and s_{i+1}.

Several days later Koa found these numbers, but she couldn't remember the strings.

So Koa would like to find some strings s_1, s_2, ..., s_{n+1} which would have generated numbers a_1, a_2, ..., a_n. Can you help her?

If there are many answers print any. We can show that answer always exists for the given constraints. 

Input

Each test contains multiple test cases. The first line contains t (1 ≤ t ≤ 100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 100) — the number of elements in the list a.

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 50) — the elements of a.

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

Output

For each test case:

Output n+1 lines. In the i-th line print string s_i (1 ≤ |s_i| ≤ 200), consisting of lowercase Latin letters. Length of the longest common prefix of strings s_i and s_{i+1} has to be equal to a_i.

If there are many answers print any. We can show that answer always exists for the given constraints.

Example

Input


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


Output


aeren
ari
arousal
around
ari
monogon
monogamy
monthly
kevinvu
kuroni
kurioni
korone
anton
loves
adhoc
problems

Note

In the 1-st test case one of the possible answers is s = [aeren, ari, arousal, around, ari].

Lengths of longest common prefixes are:

  * Between \color{red}{a}eren and \color{red}{a}ri → 1 
  * Between \color{red}{ar}i and \color{red}{ar}ousal → 2 
  * Between \color{red}{arou}sal and \color{red}{arou}nd → 4 
  * Between \color{red}{ar}ound and \color{red}{ar}i → 2 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got an array, consisting of n integers: a1, a2, ..., an. Your task is to quickly run the queries of two types:

  1. Assign value x to all elements from l to r inclusive. After such query the values of the elements of array al, al + 1, ..., ar become equal to x.
  2. Calculate and print sum <image>, where k doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (109 + 7).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 109) — the initial values of the array elements.

Then m queries follow, one per line:

  1. The assign query has the following format: "<image>", (1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 109).
  2. The query to calculate the sum has the following format: "<image>", (1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5).



All numbers in the input are integers.

Output

For each query to calculate the sum print an integer — the required sum modulo 1000000007 (109 + 7).

Examples

Input

4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5


Output

25
43
1300


Input

3 1
1000000000 1000000000 1000000000
? 1 3 0


Output

999999986

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given positive integers N, K and M, solve the following problem for every integer x between 1 and N (inclusive):
 - Find the number, modulo M, of non-empty multisets containing between 0 and K (inclusive) instances of each of the integers 1, 2, 3 \cdots, N such that the average of the elements is x.

-----Constraints-----
 - 1 \leq N, K \leq 100
 - 10^8 \leq M \leq 10^9 + 9
 - M is prime.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K M

-----Output-----
Use the following format:
c_1
c_2
:
c_N

Here, c_x should be the number, modulo M, of multisets such that the average of the elements is x.

-----Sample Input-----
3 1 998244353

-----Sample Output-----
1
3
1

Consider non-empty multisets containing between 0 and 1 instance(s) of each of the integers between 1 and 3. Among them, there are:
 - one multiset such that the average of the elements is k = 1: \{1\};
 - three multisets such that the average of the elements is k = 2: \{2\}, \{1, 3\}, \{1, 2, 3\};
 - one multiset such that the average of the elements is k = 3: \{3\}.

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

```python
function combine()
```

that combines arrays by alternatingly taking elements passed to it.

E.g

```python
combine(['a', 'b', 'c'], [1, 2, 3]) == ['a', 1, 'b', 2, 'c', 3]
combine(['a', 'b', 'c'], [1, 2, 3, 4, 5]) == ['a', 1, 'b', 2, 'c', 3, 4, 5]
combine(['a', 'b', 'c'], [1, 2, 3, 4, 5], [6, 7], [8]) == ['a', 1, 6, 8, 'b', 2, 7, 'c', 3, 4, 5]
```

Arrays can have different lengths.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
 
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

 
Constraints:

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

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