vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array a of length n that consists of zeros and ones.

You can perform the following operation multiple times. The operation consists of two steps: 

  1. Choose three integers 1 ≤ x < y < z ≤ n, that form an arithmetic progression (y - x = z - y). 
  2. Flip the values a_x, a_y, a_z (i.e. change 1 to 0, change 0 to 1). 



Determine if it is possible to make all elements of the array equal to zero. If yes, print the operations that lead the the all-zero state. Your solution should not contain more than (⌊ n/3 ⌋ + 12) operations. Here ⌊ q ⌋ denotes the number q rounded down. We can show that it is possible to make all elements equal to zero in no more than this number of operations whenever it is possible to do so at all.

Input

The first line contains a single integer n (3 ≤ n ≤ 10^5) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1) — the elements of the array.

Output

Print "YES" (without quotes) if the answer exists, otherwise print "NO" (without quotes). You can print each letter in any case (upper or lower).

If there is an answer, in the second line print an integer m (0 ≤ m ≤ (⌊ n/3 ⌋ + 12)) — the number of operations in your answer.

After that in (i + 2)-th line print the i-th operations — the integers x_i, y_i, z_i. You can print them in arbitrary order.

Examples

Input

5
1 1 0 1 1


Output

YES
2
1 3 5
2 3 4


Input

3
0 1 0


Output

NO

Note

In the first sample the shown output corresponds to the following solution: 

  * 1 1 0 1 1 (initial state); 
  * 0 1 1 1 0 (the flipped positions are the first, the third and the fifth elements); 
  * 0 0 0 0 0 (the flipped positions are the second, the third and the fourth elements). 



Other answers are also possible. In this test the number of operations should not exceed ⌊ 5/3 ⌋ + 12 = 1 + 12 = 13.

In the second sample the only available operation is to flip all the elements. This way it is only possible to obtain the arrays 0 1 0 and 1 0 1, but it is impossible to make all elements equal to zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your team is writing a fancy new text editor and you've been tasked with implementing the line numbering.

Write a function which takes a list of strings and returns each line prepended by the correct number.

The numbering starts at 1. The format is `n: string`. Notice the colon and space in between.

**Examples:**

```python
number([]) # => []
number(["a", "b", "c"]) # => ["1: a", "2: b", "3: c"]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given f(n)= [((1^2)x(nC1)^2) + ((2^2)x(nC2)^2) + ((3^2)x(nC3)^2) + ...... + ((n^2)x(nCn)^2)]%MOD.

Let there are k primes between 1 and n(inclusive) namely p1,p2,p3..pk.Your task is to find sum where:
sum=(f(p1) + f(p2) + f(p3) +...+f(pk))%MOD

Input:

t:testcases

for each test case n is given

Output:

Print the value of sum.

Constraints:

1 ≤ t ≤ 100

1 ≤ n ≤ 10^6

MOD: 10^9 + 7

SAMPLE INPUT
2
1
5

SAMPLE OUTPUT
0
1812

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Road Improvement

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In Berland there are *n* cities and *n*<=-<=1 bidirectional roads. Each road connects some pair of cities, from any city you can get to any other one using only the given roads.

In each city there is exactly one repair brigade. To repair some road, you need two teams based in the cities connected by the road to work simultaneously for one day. Both brigades repair one road for the whole day and cannot take part in repairing other roads on that day. But the repair brigade can do nothing on that day.

Determine the minimum number of days needed to repair all the roads. The brigades cannot change the cities where they initially are.

Input Specification:
The first line of the input contains a positive integer *n* (2<=≤<=*n*<=≤<=200<=000) — the number of cities in Berland.

Each of the next *n*<=-<=1 lines contains two numbers *u**i*, *v**i*, meaning that the *i*-th road connects city *u**i* and city *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*).

Output Specification:
First print number *k* — the minimum number of days needed to repair all the roads in Berland.

In next *k* lines print the description of the roads that should be repaired on each of the *k* days. On the *i*-th line print first number *d**i* — the number of roads that should be repaired on the *i*-th day, and then *d**i* space-separated integers — the numbers of the roads that should be repaired on the *i*-th day. The roads are numbered according to the order in the input, starting from one.

If there are multiple variants, you can print any of them.

Demo Input:
['4\n1 2\n3 4\n3 2\n', '6\n3 4\n5 4\n3 2\n1 3\n4 6\n']

Demo Output:
['2\n2 2 1\n1 3\n', '3\n1 1 \n2 2 3 \n2 4 5 \n']

Note:
In the first sample you can repair all the roads in two days, for example, if you repair roads 1 and 2 on the first day and road 3 — on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
According to the last order issued by the president of Berland every city of the country must have its own Ministry Defense building (their own Pentagon). A megapolis Berbourg was not an exception. This city has n junctions, some pairs of which are connected by two-way roads. Overall there are m roads in the city, no more than one between each pair of junctions.

At the moment choosing a location place for Pentagon in Berbourg is being discussed. It has been decided that Pentagon should cover the territory of five different junctions which are joined into a cycle by roads. In the order to build Pentagon a special wall will be built along the roads (with high-tension razor, high-voltage wire and other attributes). Thus, the number of possible ways of building Pentagon in the city is equal to the number of different cycles at lengths of 5, composed of junctions and roads.

Your task is to prints the number of ways of building Pentagon in Berbourg. Only well-optimized solutions will be accepted. Please, test your code on the maximal testcase.

Input

The first line contains two integers n and m (1 ≤ n ≤ 700;0 ≤ m ≤ n·(n - 1) / 2), where n represents the number of junctions and m is the number of roads in the city. Then follow m lines containing the road descriptions, one in each line. Every road is set by a number of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), where ai and bi represent the numbers of junctions, connected by the road. The junctions are numbered from 1 to n. It is not guaranteed that from any junction one can get to any other one moving along the roads.

Output

Print the single number which represents the required number of ways. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

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


Output

1


Input

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


Output

12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into 1 × 1 meter squares and call them cells, and numerate rows from 1 to n from up to down, and columns from 1 to m from left to right. And now, every cell can be described with a pair of two integers (x, y), where x — the number of the row, and y — the number of the column. Sasha knows that the level of silence in the cell (i, j) equals to f_{i,j}, and all f_{i,j} form a permutation of numbers from 1 to n ⋅ m. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment [l … r]. Denote S as the set of cells (i, j) that l ≤ f_{i,j} ≤ r. Then, the segment of silence [l … r] is pleasant if there is only one simple path between every pair of cells from S (path can't contain cells, which are not in S). In other words, set S should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments [l_1 … r_1], [l_2 … r_2] are different, if l_1 ≠ l_2 or r_1 ≠ r_2 or both at the same time.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1000, 1 ≤ n ⋅ m ≤ 2 ⋅ 10^5) — the size of the park.

Each from next n lines contains m integers f_{i,j} (1 ≤ f_{i,j} ≤ n ⋅ m) — the level of silence in the cell with number (i, j).

It is guaranteed, that all f_{i,j} are different.

Output

Print one integer — the number of pleasant segments of silence.

Examples

Input

1 5
1 2 3 4 5


Output

15

Input

2 3
1 2 3
4 5 6


Output

15

Input

4 4
4 3 2 16
1 13 14 15
5 7 8 12
6 11 9 10


Output

50

Note

In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You are a magician. You're going to perform a trick.

 You have `b` black marbles and `w` white marbles in your magic hat, and an infinite supply of black and white marbles that you can pull out of nowhere. 
 
 You ask your audience to repeatedly remove a pair of marbles from your hat and, for each pair removed, you add one marble to the hat according to the following rule until there is only 1 marble left. 

 If the marbles of the pair that is removed are of the same color, you add a white marble to the hat. Otherwise, if one is black and one is white, you add a black marble.
 
 Given the initial number of black and white marbles in your hat, your trick is to predict the color of the last marble.
 
 Note: A magician may confuse your eyes, but not your mind ;-)

# Input/Output


 - `[input]` integer `b`

  Initial number of black marbles in the hat. 
  
  `1 <= b <= 10^9`


 - `[input]` integer `w`

  Initial number of white marbles in the hat. 
  
  `1 <= w <= 10^9`


 - `[output]` a string

  `"Black"` or `"White"` if you can safely predict the color of the last marble. If not, return `"Unsure"`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An artist who wanted to create an installation where his works appeared to be floating in midair has cast a large cube of clear acrylic to serve as a base. Unfortunately, during the casting, some small flecks of dirt got into the mix, and now appear as a cluster of pinpoint flaws in the otherwise clear cube.

He wants to drill out the portion of the cube containing the flaws so that he can plug the removed volume with new, clear acrylic. He would prefer to do this in one drilling step. For stability’s sake, the drill must enter the cube only once, perpendicular to one of its faces. The cube’s faces are parallel to the coordinate axes.

Given the $(x,y,z)$ positions of the flaws, and treating the size of the flaws as negligible, what is the smallest diameter drill bit that can be used to remove the flaws in one operation??

-----Input-----
The first line of input contains an integer $N$ denoting the number of flaws. $3 \leq N \leq 5000$

This is followed by $N$ lines of input, each containing three real numbers in the range $-1000.0\ldots 1000.0$, denoting the $(x,y,z)$ coordinates of a single flaw. Each number contains at most $6$ digits following a decimal point. The decimal point may be omitted if all succeeding digits are zero.

-----Output-----
Print the diameter of the smallest drill bit that would remove all the flaws.

The answer is considered correct if the absolute or relative error is less than $10^{-4}$

-----Examples-----
Sample Input 1:
3
1.0 0.0 1.4
-1.0 0.0 -1.4
0.0 1.0 -0.2
Sample Output 1:
2.0000000000

Sample Input 2:
5
1.4 1.0 0.0
-0.4 -1.0 0.0
-0.1 -0.25 -0.5
-1.2 0.0 0.9
0.2 0.5 0.5
Sample Output 2:
2.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After being discouraged by 13 time-limit-exceeded verdicts on an ugly geometry problem, you decided to take a relaxing break for arts and crafts.

There is a piece of paper in the shape of a simple polygon with n vertices. The polygon may be non-convex, but we all know that proper origami paper has the property that any horizontal line intersects the boundary of the polygon in at most two points.

If you fold the paper along the vertical line x=f, what will be the area of the resulting shape? When you fold, the part of the paper to the left of the line is symmetrically reflected on the right side.

<image>

Your task is to answer q independent queries for values f_1,…,f_q.

Input

The first line contains two integers n, q (3≤ n≤ 10^5, 1≤ q≤ 10^5) — the number of polygon vertices and queries, respectively.

Each of the next n lines contains two integers x_i, y_i (|x_i|, |y_i|≤ 10^5) — the coordinates of the i-th point of the polygon. The polygon has an edge connecting each pair of adjacent points in the input, and also an edge between (x_1,y_1) and (x_n,y_n). It is guaranteed that the polygon is non-degenerate and that any horizontal line intersects the boundary of the polygon in at most two points. In particular, no boundary edge is strictly horizontal. Two adjacent sides may be collinear.

Each of the next q lines contains a single integer f_i (min_{j=1}^n(x_j)< f_i< max_{j=1}^n(x_j)) — the x-coordinate of the i-th fold query. It is guaranteed that all f_i are distinct.

Output

For each query, output the area A_i of the paper if you fold it along the line x=f_i.

Your answer is considered correct if its absolute or relative error does not exceed 10^{-4}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-4}.

Examples

Input


4 7
0 10
10 0
0 -10
-10 0
-9
-5
-1
0
1
5
9


Output


199.0000000000
175.0000000000
119.0000000000
100.0000000000
119.0000000000
175.0000000000
199.0000000000


Input


4 1
0 0
0 2
2 4
2 2
1


Output


3.0000000000


Input


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


Output


11.1250000000
11.7500000000
10.3446969697
11.3333333333

Note

The first test, with the fold f=-5:

<image>

The second test, with the fold f=1:

<image>

The third test, with the fold f=-1:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ketan and Dhruv are playing a very interesting game. They have 2 boxes - red and black. The red box contains all the natural numbers in increasing order(1,2,3,.....) and the black box contains all the natural numbers except "1" and each number is two times in the box in non-decreasing order(2,2,3,3,4,4,....).

The game is as follows :
In his chance the player takes out 1 number from red box and two numbers from black box and multiplies them. The result is added to the previous sum. If this is the 1st chance the previous sum is 0. Each player plays alternatively and Dhruv always starts the game. The person to make last move wins. If first chance is not possible game ends in a draw.

Note: You can only take out the numbers from top of the boxes.

You are given a number n, you need to find the number of chances such that achieved sum is strictly less than or equal to n. After that you need to tell the person who wins the game.

Input Format:-

First line contains t - number of test cases.

Next t lines contain a single integer n.

Output Format:-

Total 2*t lines, the first line of each test case contains the number of chances the game lasts for c and the next line contains the winner of the game.

If the winner is Ketan print "Ketan", if Dhruv print "Dhruv" and id the game is Drawn print "Draw", all without quotes.

Constrains:-

1 ≤ t ≤ 10^5

1 ≤ n ≤ 10^17

Author :- Nikhil Tekwani

SAMPLE INPUT
2
3
7

SAMPLE OUTPUT
0
Draw
1
Dhruv

Explanation

For the first test case, if Dhruv makes a move the sum becomes 1x2x2 = 4, which is greater than 3, thus no 1 is able to make a move and the game ends in a draw.

For the second test case, if Dhruv makes a move the sum becomes 1x2x2 = 4, and if Ketan makes a move the sum becomes 4 + 2x3x3 = 22. Since 4<7<22. Dhruv wins ans total chances is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob sees his younger brother, Jack, playing Stepping Stones. He is fascinated by the most interesting game and decides to play it.

Square boxes have been made on the ground with the help of chalk powder, and a number is assigned to each block. Bob is standing in front of these  blocks. From here, he will throw a stone 1 block far, move to that block; pick up the stone and then he will throw the stone two blocks far from here, move to that block; pick up the stone, and throw the stone three blocks far from here, move to that block, and so on. What's the catch of the game??. The catch of the game is to check if it is possible to reach $N^{\mbox{th}}$ block in this manner.  

Bob is a bit lazy. He will make a move only if he is sure that he can reach the $N^{\mbox{th}}$ block. So, tell him if he should make a move or not?  

Input Format 

First line of input contains an integer $\mathbf{T}$ denoting the number of times Bob plays this game. Each of the next $\mathbf{T}$ lines contains a single integer $N$ denoting the $N^{\mbox{th}}$ block.  

Output Format 

Output consists of several lines as per the following criteria: If bob is able to reach $N^{\mbox{th}}$ block, then print Go On Bob with the number of moves required to reach to the $N^{\mbox{th}}$ block both separated by a space. If Bob is not able to reach the $N^{\mbox{th}}$ block, then print Better Luck Next Time.

Constraints

$1\leq T\leq10^5$ 

$1\leq N\leq10^{18}$

Sample Input #00:

1
2

Sample Output #00:

Better Luck Next Time

Explanation: #00:

Bob can jump to the $1^{st}$ Block. From here, he is allowed to make a move to the $3^{rd}$ Block only. So,he cannot step onto $2^{nd}$ Block.  

Sample Input #01:  

1
3

Sample Output #01:

Go On Bob 2

Explanation: #01:

As explained in the previous test case, Bob can make a second move to reach to the $3^{rd}$ Block. So, he can step on $3^{rd}$ block in just 2 moves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward. Examples of numerical palindromes are:

2332 
110011 
54322345

You'll be given 2 numbers as arguments: ```(num,s)```.  Write a function which returns an array of ```s``` number of numerical palindromes that come after ```num```. If ```num``` is a palindrome itself, it should be included in the count. 

Return "Not valid" instead if any one of the inputs is not an integer or is less than 0.

For this kata, single digit numbers will NOT be considered numerical palindromes. 

```
palindrome(6,4) => [11,22,33,44]
palindrome(59,3) => [66,77,88]
palindrome(101,2) => [101,111]
palindrome("15651",5) => "Not valid" 
palindrome(1221,"8") => "Not valid" 
```

```Haskell

In Haskell, the return type is a Maybe which returns Nothing if either of the inputs is negative."
```


Other Kata in this Series:
Numerical Palindrome #1
Numerical Palindrome #1.5 
Numerical Palindrome #2
Numerical Palindrome #3
Numerical Palindrome #3.5
Numerical Palindrome #4
Numerical Palindrome #5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bizon the Champion is called the Champion for a reason. 

Bizon the Champion has recently got a present — a new glass cupboard with *n* shelves and he decided to put all his presents there. All the presents can be divided into two types: medals and cups. Bizon the Champion has *a*1 first prize cups, *a*2 second prize cups and *a*3 third prize cups. Besides, he has *b*1 first prize medals, *b*2 second prize medals and *b*3 third prize medals. 

Naturally, the rewards in the cupboard must look good, that's why Bizon the Champion decided to follow the rules:
 -  any shelf cannot contain both cups and medals at the same time; -  no shelf can contain more than five cups; -  no shelf can have more than ten medals. 
Help Bizon the Champion find out if we can put all the rewards so that all the conditions are fulfilled.

Input Specification:
The first line contains integers *a*1, *a*2 and *a*3 (0<=≤<=*a*1,<=*a*2,<=*a*3<=≤<=100). The second line contains integers *b*1, *b*2 and *b*3 (0<=≤<=*b*1,<=*b*2,<=*b*3<=≤<=100). The third line contains integer *n* (1<=≤<=*n*<=≤<=100).

The numbers in the lines are separated by single spaces.

Output Specification:
Print "YES" (without the quotes) if all the rewards can be put on the shelves in the described manner. Otherwise, print "NO" (without the quotes).

Demo Input:
['1 1 1\n1 1 1\n4\n', '1 1 3\n2 3 4\n2\n', '1 0 0\n1 0 0\n1\n']

Demo Output:
['YES\n', 'YES\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted array of positive integers. Your task is to rearrange the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.
Note: Modify the original array itself. Do it without using any extra space. You do not have to return anything.
Example 1:
Input:
n = 6
arr[] = {1,2,3,4,5,6}
Output: 6 1 5 2 4 3
Explanation: Max element = 6, min = 1, 
second max = 5, second min = 2, and 
so on... Modified array is : 6 1 5 2 4 3.
Example 2:
Input:
n = 11
arr[]={10,20,30,40,50,60,70,80,90,100,110}
Output:110 10 100 20 90 30 80 40 70 50 60
Explanation: Max element = 110, min = 10, 
second max = 100, second min = 20, and 
so on... Modified array is : 
110 10 100 20 90 30 80 40 70 50 60.
Your Task:
The task is to complete the function rearrange() which rearranges elements as explained above. Printing of the modified array will be handled by driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= n <= 10^6
1 <= arr[i] <= 10^7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chubby Yang is studying linear equations right now. He came up with a nice problem. In the problem you are given an n × n matrix W, consisting of integers, and you should find two n × n matrices A and B, all the following conditions must hold:   A_{ij} = A_{ji}, for all i, j (1 ≤ i, j ≤ n);  B_{ij} =  - B_{ji}, for all i, j (1 ≤ i, j ≤ n);  W_{ij} = A_{ij} + B_{ij}, for all i, j (1 ≤ i, j ≤ n). 

Can you solve the problem?


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 170). Each of the following n lines contains n integers. The j-th integer in the i-th line is W_{ij} (0 ≤ |W_{ij}| < 1717).


-----Output-----

The first n lines must contain matrix A. The next n lines must contain matrix B. Print the matrices in the format equal to format of matrix W in input. It is guaranteed that the answer exists. If there are multiple answers, you are allowed to print any of them.

The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 4}.


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

Output
1.00000000 3.50000000
3.50000000 2.00000000
0.00000000 0.50000000
-0.50000000 0.00000000

Input
3
1 2 3
4 5 6
7 8 9

Output
1.00000000 3.00000000 5.00000000
3.00000000 5.00000000 7.00000000
5.00000000 7.00000000 9.00000000
0.00000000 -1.00000000 -2.00000000
1.00000000 0.00000000 -1.00000000
2.00000000 1.00000000 0.00000000

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