vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
2
24
68
246
81012
141618
2468
10121416
18202224
26283032

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: How Many Squares?

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
You are given a 0-1 rectangular matrix. What is the number of squares in it? A square is a solid square frame (border) with linewidth equal to 1. A square should be at least 2<=×<=2. We are only interested in two types of squares: 
 1.  squares with each side parallel to a side of the matrix; 1.  squares with each side parallel to a diagonal of the matrix. 
Regardless of type, a square must contain at least one 1 and can't touch (by side or corner) any foreign 1. Of course, the lengths of the sides of each square should be equal.

How many squares are in the given matrix?

Input Specification:
The first line contains integer *t* (1<=≤<=*t*<=≤<=10000), where *t* is the number of test cases in the input. Then test cases follow. Each case starts with a line containing integers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=250), where *n* is the number of rows and *m* is the number of columns. The following *n* lines contain *m* characters each (0 or 1).

The total number of characters in all test cases doesn't exceed 106 for any input file.

Output Specification:
You should output exactly *t* lines, with the answer to the *i*-th test case on the *i*-th line.

Demo Input:
['2\n8 8\n00010001\n00101000\n01000100\n10000010\n01000100\n00101000\n11010011\n11000011\n10 10\n1111111000\n1000001000\n1011001000\n1011001010\n1000001101\n1001001010\n1010101000\n1001001000\n1000001000\n1111111000\n', '1\n12 11\n11111111111\n10000000001\n10111111101\n10100000101\n10101100101\n10101100101\n10100000101\n10100000101\n10111111101\n10000000001\n11111111111\n00000000000\n']

Demo Output:
['1\n2\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is very fond of playing the game Minesweeper. Recently he found a similar game and there are such rules.

There are mines on the field, for each the coordinates of its location are known ($x_i, y_i$). Each mine has a lifetime in seconds, after which it will explode. After the explosion, the mine also detonates all mines vertically and horizontally at a distance of $k$ (two perpendicular lines). As a result, we get an explosion on the field in the form of a "plus" symbol ('+'). Thus, one explosion can cause new explosions, and so on.

Also, Polycarp can detonate anyone mine every second, starting from zero seconds. After that, a chain reaction of explosions also takes place. Mines explode instantly and also instantly detonate other mines according to the rules described above.

Polycarp wants to set a new record and asks you to help him calculate in what minimum number of seconds all mines can be detonated.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

An empty line is written in front of each test suite.

Next comes a line that contains integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) — the number of mines and the distance that hit by mines during the explosion, respectively.

Then $n$ lines follow, the $i$-th of which describes the $x$ and $y$ coordinates of the $i$-th mine and the time until its explosion ($-10^9 \le x, y \le 10^9$, $0 \le timer \le 10^9$). It is guaranteed that all mines have different coordinates.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ lines, each of the lines must contain the answer to the corresponding set of input data  — the minimum number of seconds it takes to explode all the mines.


-----Examples-----

Input
3

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

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

6 1
1 -1 3
0 -1 9
0 1 7
-1 0 1
-1 1 9
-1 -1 7
Output
2
1
0


-----Note-----

Picture from examples

First example:

$0$ second: we explode a mine at the cell $(2, 2)$, it does not detonate any other mine since $k=0$.

$1$ second: we explode the mine at the cell $(0, 1)$, and the mine at the cell $(0, 0)$ explodes itself.

$2$ second: we explode the mine at the cell $(1, 1)$, and the mine at the cell $(1, 0)$ explodes itself.

Second example:

$0$ second: we explode a mine at the cell $(2, 2)$ we get:

$1$ second: the mine at coordinate $(0, 0)$ explodes and since $k=2$ the explosion detonates mines at the cells $(0, 1)$ and $(1, 0)$, and their explosions detonate the mine at the cell $(1, 1)$ and there are no mines left on the field.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has been a very good boy, so he got exactly what he wanted for his birthday, a “Young physicist” kit! In the kit, there are $N$ types of resistors, connecting wires and an ohmmeter. If a resistor is of type $i$, it provides a resistance of precisely $R_ i$ ohms.

As we all know, resistors can be connected in two different ways, in series and parallel. Also, we know that the complete circuit of resistors can be replaced with one resistor of the resistance equal to the equivalent resistance of the circuit. When the circuit is series, it is written as (R1-R2-R3-…-RK) and the following formula holds:\begin{equation*} R_{\mathrm{eq}} = R_1 + R_2 + R_3 + \cdots + R_ K \quad . \end{equation*}

When the circuit is parallel, it is written as (R1|R2|R3|…|RK) and the following formula holds:\begin{equation*} R_{\mathrm{eq}} = \frac{1}{1/R_1 + 1/R_2 + 1/R_3 + \cdots + 1/R_ K} \quad . \end{equation*}

Mirko was excited to bring his new toy to school, where he showed it to all his friends. Unfortunately for him, the teacher also noticed the toy. She quickly connected a circuit and is now asking Mirko to tell her the equivalent resistance of the circuit. Help Mirko and answer the teacher’s question!

-----Input-----
The first line of input contains the integer $N$ ($1 \leq $N$ \leq 9$) from the task. The following line contains $N$ real numbers $R_ i$ ($0 < R_ i < 100$) from the task. The last line contains the circuit $S$, that will not be longer than $100000$ characters. $S$ will only consist of the following characters: ‘R’, ‘1’–‘9’, ‘(’, ‘)’, ‘-’ and ‘|’. The number of pairs of brackets will be minimal, and the brackets will be paired properly. Inside of a pair of brackets, there will not be the character ‘-’ and the character ‘|’ at the same time. The circuit will only consist of the resistors from the kit and it is possible that not all types of resistors are used, or that one type of resistor is used several times.

-----Output-----
The first and only line of output must contain the number from the task. An absolute error up to $10^{-5}$ will be accepted.

-----Examples-----
Sample Input 1:
3
2 3 6
(R1-R2-R3)
Sample Output 1:
11.00000

Sample Input 2:
3
2 3 6
(R1|R2|R3)
Sample Output 2:
1.00000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write
```python
smaller(arr)
```
that given an array ```arr```, you have to return the amount of numbers that are smaller than ```arr[i]``` to the right.

For example:
```python
smaller([5, 4, 3, 2, 1]) == [4, 3, 2, 1, 0]
smaller([1, 2, 0]) == [1, 1, 0]
```
``` haskell
smaller [5,4,3,2,1]  `shouldBe` [4,3,2,1,0]
smaller [1,2,3]      `shouldBe` [0,0,0]
smaller [1, 2, 0]    `shouldBe` [1, 1, 0]
```
If you've completed this one and you feel like testing your performance tuning of this same kata, head over to the much tougher version How many are smaller than me II?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is a number of elements in the array.

You are given an array a consisting of n integers. The value of the i-th element of the array is a_i.

You are also given a set of m segments. The j-th segment is [l_j; r_j], where 1 ≤ l_j ≤ r_j ≤ n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a = [0, 0, 0, 0, 0] and the given segments are [1; 3] and [2; 4] then you can choose both of them and the array will become b = [-1, -2, -2, -1, 0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array a and obtain the array b then the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 300) — the length of the array a and the number of segments, respectively.

The second line of the input contains n integers a_1, a_2, ..., a_n (-10^6 ≤ a_i ≤ 10^6), where a_i is the value of the i-th element of the array a.

The next m lines are contain two integers each. The j-th of them contains two integers l_j and r_j (1 ≤ l_j ≤ r_j ≤ n), where l_j and r_j are the ends of the j-th segment.

Output

In the first line of the output print one integer d — the maximum possible value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i if b is the array obtained by applying some subset of the given segments to the array a.

In the second line of the output print one integer q (0 ≤ q ≤ m) — the number of segments you apply.

In the third line print q distinct integers c_1, c_2, ..., c_q in any order (1 ≤ c_k ≤ m) — indices of segments you apply to the array a in such a way that the value max_{i=1}^{n}b_i - min_{i=1}^{n}b_i of the obtained array b is maximum possible.

If there are multiple answers, you can print any.

Examples

Input


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


Output


6
2
4 1 


Input


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


Output


7
2
3 2 


Input


1 0
1000000


Output


0
0

Note

In the first example the obtained array b will be [0, -4, 1, 1, 2] so the answer is 6.

In the second example the obtained array b will be [2, -3, 1, -1, 4] so the answer is 7.

In the third example you cannot do anything so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him. 

<image>

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:

  * Empty string is a correct bracket sequence. 
  * if s is a correct bracket sequence, then (s) is also a correct bracket sequence. 
  * if s and t are correct bracket sequences, then st (concatenation of s and t) is also a correct bracket sequence. 



A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string s consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (l, r) such that 1 ≤ l ≤ r ≤ |s| and the string slsl + 1... sr is pretty, where si is i-th character of s.

Joyce doesn't know anything about bracket sequences, so she asked for your help.

Input

The first and only line of input contains string s, consisting only of characters '(', ')' and '?' (2 ≤ |s| ≤ 5000).

Output

Print the answer to Will's puzzle in the first and only line of output.

Examples

Input

((?))


Output

4


Input

??()??


Output

7

Note

For the first sample testcase, the pretty substrings of s are:

  1. "(?" which can be transformed to "()". 
  2. "?)" which can be transformed to "()". 
  3. "((?)" which can be transformed to "(())". 
  4. "(?))" which can be transformed to "(())". 



For the second sample testcase, the pretty substrings of s are:

  1. "??" which can be transformed to "()". 
  2. "()". 
  3. "??()" which can be transformed to "()()". 
  4. "?()?" which can be transformed to "(())". 
  5. "??" which can be transformed to "()". 
  6. "()??" which can be transformed to "()()". 
  7. "??()??" which can be transformed to "()()()". 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You got an old map, which turned out to be drawn by the infamous pirate "Captain Q". It shows the locations of a lot of treasure chests buried in an island.

The map is divided into square sections, each of which has a digit on it or has no digit. The digit represents the number of chests in its 9 neighboring sections (the section itself and its 8 neighbors). You may assume that there is at most one chest in each section.

Although you have the map, you can't determine the sections where the chests are buried. Even the total number of chests buried in the island is unknown. However, it is possible to calculate the minimum number of chests buried in the island. Your mission in this problem is to write a program that calculates it.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

h w
map

The first line of a dataset consists of two positive integers h and w. h is the height of the map and w is the width of the map. You may assume 1≤h≤15 and 1≤w≤15.

The following h lines give the map. Each line consists of w characters and corresponds to a horizontal strip of the map. Each of the characters in the line represents the state of a section as follows.

'.': The section is not a part of the island (water). No chest is here.

'*': The section is a part of the island, and the number of chests in its 9 neighbors is not known.

'0'-'9': The section is a part of the island, and the digit represents the number of chests in its 9 neighbors.

You may assume that the map is not self-contradicting, i.e., there is at least one arrangement of chests. You may also assume the number of sections with digits is at least one and at most 15.

A line containing two zeros indicates the end of the input.

Output

For each dataset, output a line that contains the minimum number of chests. The output should not contain any other character.

Examples

Input

5 6


Output

6


Input

5 6
*2.2**
..*...
..2...
..*...
*2.2**
6 5
.*2*.
..*..
..*..
..2..
..*..
.*2*.
5 6
.1111.
**...*
33....
**...0
.*2**.
6 9
....1....
...1.1...
....1....
.1..*..1.
1.1***1.1
.1..*..1.
9 9
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4***
*********
0 0


Output

6
5
5
6
23

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
> "Even a broken clock is right twice a day"

For those unfamiliar with the above proverb, the statement refers to a stopped 12 hour clock. The time it shows happens to coincide with the true time twice every 24 hours.

Chef has a useless clock which does not run properly. More specifically, it runs at $K$ times the rate of a correct clock, where $K \ne 1$. It may even be that $K$ is negative, which means the clock runs backwards. Chef also has a clock which precisely shows the current time without error.

At 12 am on day $1$ Chef sets the useless clock to point to 12:00. Of course Chef's correct clock already points to 12:00. Chef wonders on which day the time shown by the useless clock will coincide with the correct clock for the $N^{th}$ time. 

Can you help him find the answer without having to wait for that many days?   
Note that 12 am of day $d$ is considered the first instant of day $d$. Since the clocks initially show the same time at 12 am of day $1$, that is counted as the first time they coincide.

------ Input: ------
First line will contain $T$, the number of test cases.
The next $T$ lines each contain 3 integers $p$, $q$ and $N$, where $\frac{p}{q} = K$.

------ Output: ------
For each test case, output a single integer which is the day on which the times of the clocks coincide for the $N^{th}$ time.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$-100 ≤ K ≤ 100$
$K \ne 1$
$1 ≤ q ≤ 10^{4}$
$1 ≤ N ≤ 10^{6}$

------ Sample Input: ------
4
0 1 5
-1 2 3
2 1 10
99 100 2

------ Sample Output: ------
3
1
5
51
	
------ Explanation: ------
Case 1: Here $K = 0$. A broken clock is right twice a day. So it will be right for the fifth time on day $3$.
Case 2: Here $K = -1/2$. The clock moves backwards at half the rate of the correct clock. The time displayed will coincide with the true time first at 12 am, then at 8 am and for the third time at 4 pm on day $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a member of the Senate of an ancient empire governed by a mighty dictator. You have joined a bipartisan secret committee of the Senate that is plotting to overthrow the dictator.

In order for the plot to succeed, it is crucial that all the states in the empire ultimately support the plan–and to accomplish this, the governors of all the states need to be members of the same Party.

Right now, each state governor is a member of either the Orange Party or the Purple Party. Since you are confident that you can get either party to back the plot, it does not matter which party ultimately prevails.

The secret committee has studied the political situation and determined that two governors will influence each other if they are friends with each other and members of the same Party. To get all the state governors on board, each month a lobbyist will do whatever it takes to get one governor to switch parties. When this happens, all the friends of the governor who are members of the same Party will also switch affiliation, as will the friends of the friends within the party, and so on. To avoid suspicion, the secret committee will alternate Orange/Purple lobbyists each month. They may start the ball rolling with either party in the first month.

The secret committee also knows which governors are friends with each other, that each governor is friends with at least one other governor, and that there are no isolated groups that are only friends with each other.

Your task is to determine the minimum number of months required for all the state governors to be members of the same party. Once this occurs, the next steps in the plot can take place.

-----Input-----
There will be a single test case in the input. This test case will begin with a line with two integers, $n$ ($1 \le n \le 100$) and $m$ ($n-1 \le m \le n(n-1)/2$), where $n$ is the number of governors, and $m$ is the number of known friendships. On the next line will be $n$ integers, either $0$ or $1$, indicating the current party affiliation of the governors, in order ($0=\text {ORANGE}, 1=\text {PURPLE}$). On each of the following $m$ lines will be two integers, $a$ and $b$ ($1 \le a < b \le n$) indicating that governor $a$ and governor $b$ are friends. As in life, friendships go both ways: if $a$ is a friend of $b$, then $b$ is also a friend of $a$. All $m$ $(a,b)$ pairs will be unique.

-----Output-----
Output a single integer, indicating the minimum number of months necessary for every governor to belong to the same party.

-----Examples-----
Sample Input:
4 3
0 1 0 0
1 2
2 3
2 4
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n villages in a Chefland. Some of the villages have electricity facilities, other doesn't. You can consider the villages arranged in line in the order 1 to n from left to right. i-th of village can be considered at xi coordinates.

Chef decided that electricity should be provided to all the villages. So, he decides to buy some amount of electric wires to connect the villeges without electricity to some villages with electricity. As Chef does not want to spend too much amount of money on wires, can you find out minimum amount of length of wire Chef should buy.

-----Input-----
First line of the input contains an integer T denoting the number of test cases. T test cases follow.
First line of each test case contains an integer n denoting number of villages in Chefland.
Second line will contain a string of length n containing '0' or '1's only. If i-th character of the string is '1', then it denotes that i-th village has electricity.
Next line contains n space separated integers denoting the x coordinates of the villages in the order from village 1 to n

-----Output-----
For each test case, output a single line containing a integer corresponding to the minimum length of wire Chef needs to buy.

-----Constraints-----
- 1 ≤ T ≤ 10
- It is guaranteed that there will be at least one village which will have electricity.
- 1 ≤ x1 <  x2 <  ... < xn ≤ 109

-----Subtasks-----
Subtask #1 : 30 points
- 1 ≤ N ≤ 1000

Subtask #2 : 70 points
- 1 ≤ N ≤ 105

-----Example-----
Input
2
2
01
1 2
3
100
1 5 6
Output:
1
5

-----Explanation-----
In the first example, first village does not have electricity. If we put a wire between village 1 and 2 of length 1, then both the villages will have electricity.

In the second example,
We can a draw a wire from first village to third village, passing through second village. Its total length will be 5. Now all the villages will have electricity. This is the minimum length of wire you will require.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, $n$ people ($n$ is an even number) met on a plaza and made two round dances, each round dance consists of exactly $\frac{n}{2}$ people. Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people. Each person should belong to exactly one of these two round dances.

Round dance is a dance circle consisting of $1$ or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances $[1, 3, 4, 2]$, $[4, 2, 1, 3]$ and $[2, 1, 3, 4]$ are indistinguishable.

For example, if $n=2$ then the number of ways is $1$: one round dance consists of the first person and the second one of the second person.

For example, if $n=4$ then the number of ways is $3$. Possible options:  one round dance — $[1,2]$, another — $[3,4]$;  one round dance — $[2,4]$, another — $[3,1]$;  one round dance — $[4,1]$, another — $[3,2]$. 

Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people.


-----Input-----

The input contains one integer $n$ ($2 \le n \le 20$), $n$ is an even number.


-----Output-----

Print one integer — the number of ways to make two round dances. It is guaranteed that the answer fits in the $64$-bit integer data type.


-----Examples-----
Input
2

Output
1

Input
4

Output
3

Input
8

Output
1260

Input
20

Output
12164510040883200

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