vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment $0$ and turn power off at moment $M$. Moreover, the lamp allows you to set a program of switching its state (states are "lights on" and "lights off"). Unfortunately, some program is already installed into the lamp.

The lamp allows only good programs. Good program can be represented as a non-empty array $a$, where $0 < a_1 < a_2 < \dots < a_{|a|} < M$. All $a_i$ must be integers. Of course, preinstalled program is a good program.

The lamp follows program $a$ in next manner: at moment $0$ turns power and light on. Then at moment $a_i$ the lamp flips its state to opposite (if it was lit, it turns off, and vice versa). The state of the lamp flips instantly: for example, if you turn the light off at moment $1$ and then do nothing, the total time when the lamp is lit will be $1$. Finally, at moment $M$ the lamp is turning its power off regardless of its state.

Since you are not among those people who read instructions, and you don't understand the language it's written in, you realize (after some testing) the only possible way to alter the preinstalled program. You can insert at most one element into the program $a$, so it still should be a good program after alteration. Insertion can be done between any pair of consecutive elements of $a$, or even at the begining or at the end of $a$.

Find such a way to alter the program that the total time when the lamp is lit is maximum possible. Maybe you should leave program untouched. If the lamp is lit from $x$ till moment $y$, then its lit for $y - x$ units of time. Segments of time when the lamp is lit are summed up.


-----Input-----

First line contains two space separated integers $n$ and $M$ ($1 \le n \le 10^5$, $2 \le M \le 10^9$) — the length of program $a$ and the moment when power turns off.

Second line contains $n$ space separated integers $a_1, a_2, \dots, a_n$ ($0 < a_1 < a_2 < \dots < a_n < M$) — initially installed program $a$.


-----Output-----

Print the only integer — maximum possible total time when the lamp is lit.


-----Examples-----
Input
3 10
4 6 7

Output
8

Input
2 12
1 10

Output
9

Input
2 7
3 4

Output
6



-----Note-----

In the first example, one of possible optimal solutions is to insert value $x = 3$ before $a_1$, so program will be $[3, 4, 6, 7]$ and time of lamp being lit equals $(3 - 0) + (6 - 4) + (10 - 7) = 8$. Other possible solution is to insert $x = 5$ in appropriate place.

In the second example, there is only one optimal solution: to insert $x = 2$ between $a_1$ and $a_2$. Program will become $[1, 2, 10]$, and answer will be $(1 - 0) + (10 - 2) = 9$.

In the third example, optimal answer is to leave program untouched, so answer will be $(3 - 0) + (7 - 4) = 6$.

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

We have hidden a permutation p_1, p_2, ..., p_n of numbers from 1 to n from you, where n is even. You can try to guess it using the following queries:

? k a_1 a_2 ... a_k.

In response, you will learn if the average of elements with indexes a_1, a_2, ..., a_k is an integer. In other words, you will receive 1 if \frac{p_{a_1} + p_{a_2} + ... + p_{a_k}}{k} is integer, and 0 otherwise. 

You have to guess the permutation. You can ask not more than 18n queries.

Note that permutations [p_1, p_2, ..., p_k] and [n + 1 - p_1, n + 1 - p_2, ..., n + 1 - p_k] are indistinguishable. Therefore, you are guaranteed that p_1 ≤ n/2.

Note that the permutation p is fixed before the start of the interaction and doesn't depend on your queries. In other words, interactor is not adaptive.

Note that you don't have to minimize the number of queries.

Input

The first line contains a single integer n (2 ≤ n ≤ 800, n is even).

Interaction

You begin the interaction by reading n.

To ask a question about elements on positions a_1, a_2, ..., a_k, in a separate line output

? k a_1 a_2 ... a_k

Numbers in the query have to satisfy 1 ≤ a_i ≤ n, and all a_i have to be different. Don't forget to 'flush', to get the answer.

In response, you will receive 1 if \frac{p_{a_1} + p_{a_2} + ... + p_{a_k}}{k} is integer, and 0 otherwise. 

In case your query is invalid or you asked more than 18n queries, the program will print -1 and will finish interaction. You will receive a Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you determine permutation, output 

! p_1 p_2 ... p_n

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hack format

For the hacks use the following format:

The first line has to contain a single integer n (2 ≤ n ≤ 800, n is even).

In the next line output n integers p_1, p_2, ..., p_n — the valid permutation of numbers from 1 to n. p_1 ≤ n/2 must hold.

Example

Input


2
1 2


Output


? 1 2
? 1 1
! 1 2 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing a game on strings.

Initially, they have some string t. In one move the first player selects the character c present in t and erases all it's occurrences in t, thus splitting t into many smaller strings. The game then goes independently with each of the strings — to make the move player selects one of the strings and one of the characters there, deletes all occurrences and adds the remaining string back to the game.

Alice always starts the game, and then Alice and Bob take turns making moves. The player who is unable to make a move (because there is no string left) loses.

Alice and Bob used to always start with a string s, but recently they found out that this became too boring. Now before each game they choose two integers l and r such that 1 ≤ l ≤ r ≤ |s| and play the game with the string s_{l} s_{l+1} s_{l+2} … s_{r} instead.

Given the string s and integers l, r for each game. Find who is going to win each game assuming they are smart and are playing optimally.

Input

The first line contains the string s (1 ≤ |s| ≤ 10^5) consisting of lowercase English letters. This is the string Alice and Bob used to start with.

The second line contains a single integer m (1 ≤ m ≤ 10^5) — the number of games to analyze.

Each of the next m lines contains two integers l and r (1 ≤ l ≤ r ≤ |s|) — the bounds of the starting substring in the string s.

Output

For each game output a single line containing the name of the winner — "Alice" or "Bob" respectively.

Examples

Input

aaab
2
1 2
1 4


Output

Alice
Bob


Input

aaccbdb
2
5 7
1 7


Output

Alice
Alice

Note

In the first example, 

  1. In the first game the string "aa" is selected. Alice deletes character 'a' and Bob is unable to move. 
  2. In the second game the string "aaab" is selected. No matter what character Alice will delete, Bob deletes the other one and Alice is unable to move. 



In the second example Alice wins both game "bdb" and "aaccbdb".

To win game "bdb" Alice can erase symbol 'd', the game then goes independently on strings "b" and "b". Bob deletes one of this strings and the Alice deletes the other one and Bob is unable to move.

To win game "aaccbdb" Alice can erase symbol 'd', the game then goes independently on strings "aaccb" and "b". It is possible to show, that no matter what are the moves, the remaining game can only finish in exactly 4 moves, so the Bob will be unable to move after that.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Anton and Fairy Tale

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Anton likes to listen to fairy tales, especially when Danik, Anton's best friend, tells them. Right now Danik tells Anton a fairy tale:

"Once upon a time, there lived an emperor. He was very rich and had much grain. One day he ordered to build a huge barn to put there all his grain. Best builders were building that barn for three days and three nights. But they overlooked and there remained a little hole in the barn, from which every day sparrows came through. Here flew a sparrow, took a grain and flew away..."

More formally, the following takes place in the fairy tale. At the beginning of the first day the barn with the capacity of *n* grains was full. Then, every day (starting with the first day) the following happens:
 -  *m* grains are brought to the barn. If *m* grains doesn't fit to the barn, the barn becomes full and the grains that doesn't fit are brought back (in this problem we can assume that the grains that doesn't fit to the barn are not taken into account). -  Sparrows come and eat grain. In the *i*-th day *i* sparrows come, that is on the first day one sparrow come, on the second day two sparrows come and so on. Every sparrow eats one grain. If the barn is empty, a sparrow eats nothing. 
Anton is tired of listening how Danik describes every sparrow that eats grain from the barn. Anton doesn't know when the fairy tale ends, so he asked you to determine, by the end of which day the barn will become empty for the first time. Help Anton and write a program that will determine the number of that day!

Input Specification:
The only line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1018) — the capacity of the barn and the number of grains that are brought every day.

Output Specification:
Output one integer — the number of the day when the barn will become empty for the first time. Days are numbered starting with one.

Demo Input:
['5 2\n', '8 1\n']

Demo Output:
['4\n', '5\n']

Note:
In the first sample the capacity of the barn is five grains and two grains are brought every day. The following happens:
 -  At the beginning of the first day grain is brought to the barn. It's full, so nothing happens. -  At the end of the first day one sparrow comes and eats one grain, so 5 - 1 = 4 grains remain. -  At the beginning of the second day two grains are brought. The barn becomes full and one grain doesn't fit to it. -  At the end of the second day two sparrows come. 5 - 2 = 3 grains remain. -  At the beginning of the third day two grains are brought. The barn becomes full again. -  At the end of the third day three sparrows come and eat grain. 5 - 3 = 2 grains remain. -  At the beginning of the fourth day grain is brought again. 2 + 2 = 4 grains remain. -  At the end of the fourth day four sparrows come and eat grain. 4 - 4 = 0 grains remain. The barn is empty. 
So the answer is 4, because by the end of the fourth day the barn becomes empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$n$ fishermen have just returned from a fishing vacation. The $i$-th fisherman has caught a fish of weight $a_i$.

Fishermen are going to show off the fish they caught to each other. To do so, they firstly choose an order in which they show their fish (each fisherman shows his fish exactly once, so, formally, the order of showing fish is a permutation of integers from $1$ to $n$). Then they show the fish they caught according to the chosen order. When a fisherman shows his fish, he might either become happy, become sad, or stay content.

Suppose a fisherman shows a fish of weight $x$, and the maximum weight of a previously shown fish is $y$ ($y = 0$ if that fisherman is the first to show his fish). Then:

  if $x \ge 2y$, the fisherman becomes happy;  if $2x \le y$, the fisherman becomes sad;  if none of these two conditions is met, the fisherman stays content. 

Let's call an order in which the fishermen show their fish emotional if, after all fishermen show their fish according to this order, each fisherman becomes either happy or sad. Calculate the number of emotional orders modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 5000$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print one integer — the number of emotional orders, taken modulo $998244353$.


-----Examples-----
Input
4
1 1 4 9

Output
20

Input
4
4 3 2 1

Output
0

Input
3
4 2 1

Output
6

Input
8
42 1337 13 37 420 666 616 97

Output
19200

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer num consisting only of digits 6 and 9.
Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).
 
Example 1:
Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:
Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.
Example 3:
Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.
 
Constraints:

1 <= num <= 10^4
num's digits are 6 or 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a matrix of size n x m with 0’s and 1’s , you enter the matrix at cell (0,0) in left to right direction. whenever you encounter a 0 you retain in same direction , if you encounter a 1’s you have to change direction to right of current direction and change that 1 value to 0, you have to find out from which index you will leave the matrix at the end.
 
Example 1:
Input: matrix = {{0, 1, 0},
{0, 1, 1}, {0, 0, 0}}
Output: 1 0
Explanation: We enter at 0,0 then move towards 
0,1 and we encountered a 1 so we turned right 
and moved towards 1,1 and again we encountered 
a 1 so we turned right and moved towards 1,0 after
which we leave the matrix.
Example 2:
Input: matrix = {{0, 0}}
Output: 0 1
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function FindExitPoint() which takes the matrix as input parameter and returns a list containg the exit point.
 
Expected Time Complexity: O(n * m) where n is number of rows and m is number of columns.
Expected Space Complexity: O(1)
 
Constraints:
1 <= n, m <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is playing a game called "Dungeon 2" which is the sequel to the popular "Dungeon" released last year. The game is played on a map consisting of $N$ rooms and $N-1$ roads connecting them. The roads allow bidirectional traffic and the player can start his tour from any room and reach any other room by way of multiple of roads. A point is printed in each of the rooms.

Bob tries to accumulate the highest score by visiting the rooms by cleverly routing his character "Tora-Tora." He can add the point printed in a room to his score only when he reaches the room for the first time. He can also add the points on the starting and ending rooms of Tora-Tora’s journey. The score is reduced by one each time Tora-Tore passes a road. Tora-Tora can start from any room and end his journey in any room.

Given the map information, make a program to work out the maximum possible score Bob can gain.



Input

The input is given in the following format.


$N$
$p_1$
$p_2$
$...$
$p_N$
$s_1$ $t_1$
$s_2$ $t_2$
$...$
$s_{N-1}$ $t_{N-1}$


The first line provides the number of rooms $N$ ($1 \leq N \leq 100,000$). Each of the subsequent $N$ lines provides the point of the $i$-th room $p_i$ ($-100 \leq p_i \leq 100$) in integers. Each of the subsequent lines following these provides the information on the road directly connecting two rooms, where $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) represent the numbers of the two rooms connected by it. Not a single pair of rooms are connected by more than one road.

Output

Output the maximum possible score Bob can gain.

Examples

Input

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


Output

10


Input

4
5
0
1
1
1 2
2 3
2 4


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jaggi and Jojo are interested in problems related with Grids. They were trying different problem on grids, when they found this one. Given a grid of size NXN. Its bottom-left point is (0,0) and  top-right element is (N-1,N-1).

We can traverse the grid in either top or right direction. You have to find the number of ways to traverse from the bottom-left to top-right point. There are some checkpoints which you have to visit in every path. There is atleast one valid path.

Input

The input file consists of several cases T (1 ≤ T ≤ 5). 
The first line of each case contains a positive integer N (1 ≤ N ≤ 1000) specifying the size of grid and the number of checkpoints Q (0 ≤ Q ≤ 100).
In next line there are Q space separated co-ordinates (a,b) of the checkpoints. Checkpoints are 0-Indexed.

Output

For every testcase, you have to print the answer modulo 1000000007.

SAMPLE INPUT
2
3 0
5 1
2 2

SAMPLE OUTPUT
6
36

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're playing a game with a friend involving a bag of marbles. In the bag are ten marbles:

* 1 smooth red marble
* 4 bumpy red marbles
* 2 bumpy yellow marbles
* 1 smooth yellow marble
* 1 bumpy green marble
* 1 smooth green marble

You can see that the probability of picking a smooth red marble from the bag is `1 / 10` or `0.10` and the probability of picking a bumpy yellow marble is `2 / 10` or `0.20`.

The game works like this: your friend puts her hand in the bag, chooses a marble (without looking at it) and tells you whether it's bumpy or smooth. Then you have to guess which color it is before she pulls it out and reveals whether you're correct or not.

You know that the information about whether the marble is bumpy or smooth changes the probability of what color it is, and you want some help with your guesses.

Write a function `color_probability()` that takes two arguments: a color (`'red'`, `'yellow'`, or `'green'`) and a texture (`'bumpy'` or `'smooth'`) and returns the probability as a decimal fraction accurate to two places.

The probability should be a string and should discard any digits after the 100ths place. For example, `2 / 3` or `0.6666666666666666` would become the string `'0.66'`. Note this is different from rounding.

As a complete example, `color_probability('red', 'bumpy')` should return the string `'0.57'`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Santa has prepared boxes with presents for n kids, one box for each kid. There are m kinds of presents: balloons, sweets, chocolate bars, toy cars... A child would be disappointed to receive two presents of the same kind, so all kinds of presents in one box are distinct.

Having packed all the presents, Santa realized that different boxes can contain different number of presents. It would be unfair to the children, so he decided to move some presents between boxes, and make their sizes similar. After all movements, the difference between the maximal and the minimal number of presents in a box must be as small as possible. All presents in each box should still be distinct. Santa wants to finish the job as fast as possible, so he wants to minimize the number of movements required to complete the task.

Given the sets of presents in each box, find the shortest sequence of movements of presents between boxes that minimizes the difference of sizes of the smallest and the largest box, and keeps all presents in each box distinct.

Input

The first line of input contains two integers n, m (1 ≤ n, m ≤ 100\ 000), the number of boxes and the number of kinds of the presents. Denote presents with integers from 1 to m.

Each of the following n lines contains the description of one box. It begins with an integer s_i (s_i ≥ 0), the number of presents in the box, s_i distinct integers between 1 and m follow, denoting the kinds of presents in that box.

The total number of presents in all boxes does not exceed 500 000.

Output

Print one integer k at the first line of output, the number of movements in the shortest sequence that makes the sizes of the boxes differ by at most one. Then print k lines that describe movements in the same order in which they should be performed. Each movement is described by three integers from_i, to_i, kind_i. It means that the present of kind kind_i is moved from the box with number from_i to the box with number to_i. Boxes are numbered from one in the order they are given in the input.

At the moment when the movement is performed the present with kind kind_i must be present in the box with number from_i. After performing all moves each box must not contain two presents of the same kind.

If there are several optimal solutions, output any of them.

Example

Input


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


Output


2
1 3 5
1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree with n vertices numbered 1, …, n. A tree is a connected simple graph without cycles.

Let dist(u, v) be the number of edges in the unique simple path connecting vertices u and v.

Let diam(l, r) = max dist(u, v) over all pairs u, v such that l ≤ u, v ≤ r.

Compute ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The next n - 1 lines describe the tree edges. Each of these lines contains two integers u, v (1 ≤ u, v ≤ n) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

Output

Print a single integer — ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Examples

Input


4
1 2
2 4
3 2


Output


10


Input


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


Output


224

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