vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Berland Gardeners United Inc. hired you for the project called "SmartGarden". The main feature of this project is automatic garden watering.

Formally the garden can be represented as a square of n × n cells with rows numbered 1 to n from top to bottom and columns numbered 1 to n from left to right. Each cell of the garden contains either a plant or a slab. 

It's known that slabs are located on the main diagonal of the matrix representing the garden, and in the cells that are below the main diagonal and share a side with at least one cell of the main diagonal. All the remaining cells of the garden are filled with plants.

<image> Example of the garden for n=5.

During implementation of the project you created a smart robot that takes a list of commands as an input, which are processed one by one. Each command contains: 

  * a list of horizontal lines (rows in the matrix representing the garden); 
  * a list of vertical lines (columns in the matrix representing the garden). 



While executing each command robot waters only cells in the intersection of specified rows and specified columns. So, if you specify r rows and c columns, then exactly r ⋅ c cells will be watered.

In the demo for the customer you have tuned robot in such a way that it waters all the garden. To do that you prepared a single command containing all n rows and all n columns.

Unfortunately, 5 hours before the demo for your customer it turned out that the CEO of Berland Gardeners United Inc. was going to take part in it. Moreover, most probably he will be standing on a garden slab during the demo!

Now you need to create a list of commands for the robot so that it waters all the plants and doesn't water any cell containing a slab. Since it's only a beta version of "SmartGarden", the total number of commands shouldn't exceed 50.

Create a program that, for a given size of the garden, will find a list of no more than 50 commands that allow the robot to water all the plants in the garden without watering the slabs. It is allowed to water a plant several times.

Input

The first and the only line of the input contains a single integer n (2 ≤ n ≤ 5000), where n is the size of the garden.

Output

In the first line print the total number of commands for the robot k (1 ≤ k ≤ 50). In the next 2 ⋅ k lines print all the commands. Each command should be specified by 2 lines. The first line of each command should describe rows in the command and the second line should describe columns in the command. Each of these 2 lines should have the following format:

  * the first number of the line should specify the total number of items x in the appropriate list; 
  * then x distinct numbers follow, where each number is in the range 1 ... n and describes a chosen row for the first line and a chosen column for the second line. 



If there are multiple ways to water the garden, print any of them.

Examples

Input


2

Output


2
1 1
1 2
1 1
1 2


Input


4

Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
K: Relief (Angel Relief)

Tenma, an angel, decides to save a city.

The city has a rectangular shape divided into north-south $ H $ parcels x east-west $ W $ parcels, with houses in each parcel.

The $ X $ th section from the north and the $ Y $ th section from the west are represented by $ (X, Y) $.

The house in parcel $ (i, j) $ is inhabited by $ A_ {i, j} $ people.

Tenshin chooses a rectangular area whose sides are parallel or vertical to north-south or east-west, and rescues all the people living in it one by one.

Tenshin does this for every possible rectangle.

Find the total number of times Tenma-san rescues people.

input

The integers $ H, W $ are given on the first line, separated by blanks.

Of the following $ H $ lines, the integers $ A_ {i, 1}, A_ {i, 2}, A_ {i, 3}, \ dots, A_ {i, W} $ are blank on the $ i $ line. Given as a delimiter.

output

Output the total number of times Tenma-san rescues people.

Constraint

* $ H, W $ are integers between $ 1 $ and $ 500 $
* $ A_ {i, j} $ are all integers greater than or equal to $ 1 $ and less than or equal to $ 9 $.



Input example 1


twenty two
1 2
4 8


Output example 1


60


For example, if you choose a rectangular area with $ (1, 1) $ in the upper left and $ (2, 2) $ in the lower right, you will rescue $ 15 $ people there one by one, so a total of $ 15 $ times. Relief.

$ 1, 2, 3, 4, 5, 8, 10, 12, 15 $ relief for each of the $ 9 $ rectangular areas, for a total of $ 60 $.

Input example 2


twenty three
one two Three
4 5 6


Output example 2


140






Example

Input

2 2
1 2
4 8


Output

60

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space.  These characters divide the square into contiguous regions.
(Note that backslash characters are escaped, so a \ is represented as "\\".)
Return the number of regions.
 













Example 1:
Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:



Example 2:
Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:



Example 3:
Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:



Example 4:
Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:



Example 5:
Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:


 
Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.
 
Example 1:
Input:
N = 3 
A[] = {1,2,3} 
Output:
-1
Explanation:
Since, each element in 
{1,2,3} appears only once so there 
is no majority element.
Example 2:
Input:
N = 5 
A[] = {3,1,3,3,2} 
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is 
the majority element.
Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A_{i} ≤ 10^{6}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Qwerty the Ranger took up a government job and arrived on planet Mars. He should stay in the secret lab and conduct some experiments on bacteria that have funny and abnormal properties. The job isn't difficult, but the salary is high.

At the beginning of the first experiment there is a single bacterium in the test tube. Every second each bacterium in the test tube divides itself into *k* bacteria. After that some abnormal effects create *b* more bacteria in the test tube. Thus, if at the beginning of some second the test tube had *x* bacteria, then at the end of the second it will have *kx*<=+<=*b* bacteria.

The experiment showed that after *n* seconds there were exactly *z* bacteria and the experiment ended at this point.

For the second experiment Qwerty is going to sterilize the test tube and put there *t* bacteria. He hasn't started the experiment yet but he already wonders, how many seconds he will need to grow at least *z* bacteria. The ranger thinks that the bacteria will divide by the same rule as in the first experiment. 

Help Qwerty and find the minimum number of seconds needed to get a tube with at least *z* bacteria in the second experiment.

Input Specification:
The first line contains four space-separated integers *k*, *b*, *n* and *t* (1<=≤<=*k*,<=*b*,<=*n*,<=*t*<=≤<=106) — the parameters of bacterial growth, the time Qwerty needed to grow *z* bacteria in the first experiment and the initial number of bacteria in the second experiment, correspondingly.

Output Specification:
Print a single number — the minimum number of seconds Qwerty needs to grow at least *z* bacteria in the tube.

Demo Input:
['3 1 3 5\n', '1 4 4 7\n', '2 2 4 100\n']

Demo Output:
['2', '3', '0']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Endo wanted to write the code that performs breadth-first search (BFS), which is a search algorithm to explore all vertices on an undirected graph. An example of pseudo code of BFS is as follows:


1: $current \leftarrow \{start\_vertex\}$
2: $visited \leftarrow current$
3: while $visited \ne $ the set of all the vertices
4:   $found \leftarrow \{\}$
5:   for $v$ in $current$
6:     for each $u$ adjacent to $v$
7:       $found \leftarrow found \cup\{u\}$
8:   $current \leftarrow found \setminus visited$
9:   $visited \leftarrow visited \cup found$


However, Mr. Endo apparently forgot to manage visited vertices in his code. More precisely, he wrote the following code:


1: $current \leftarrow \{start\_vertex\}$
2: while $current \ne $ the set of all the vertices
3:   $found \leftarrow \{\}$
4:   for $v$ in $current$
5:     for each $u$ adjacent to $v$
6:       $found \leftarrow found \cup \{u\}$
7:   $current \leftarrow found$


You may notice that for some graphs, Mr. Endo's program will not stop because it keeps running infinitely. Notice that it does not necessarily mean the program cannot explore all the vertices within finite steps. See example 2 below for more details.Your task here is to make a program that determines whether Mr. Endo's program will stop within finite steps for a given graph in order to point out the bug to him. Also, calculate the minimum number of loop iterations required for the program to stop if it is finite.



Input

The input consists of a single test case formatted as follows.


$N$ $M$
$U_1$ $V_1$
...
$U_M$ $V_M$


The first line consists of two integers $N$ ($2 \leq N \leq 100,000$) and $M$ ($1 \leq M \leq 100,000$), where $N$ is the number of vertices and $M$ is the number of edges in a given undirected graph, respectively. The $i$-th line of the following $M$ lines consists of two integers $U_i$ and $V_i$ ($1 \leq U_i, V_i \leq N$), which means the vertices $U_i$ and $V_i$ are adjacent in the given graph. The vertex 1 is the start vertex, i.e. $start\\_vertex$ in the pseudo codes. You can assume that the given graph also meets the following conditions.

* The graph has no self-loop, i.e., $U_i \ne V_i$ for all $1 \leq i \leq M$.
* The graph has no multi-edge, i.e., $\\{Ui,Vi\\} \ne \\{U_j,V_j\\}$ for all $1 \leq i < j \leq M$.
* The graph is connected, i.e., there is at least one path from $U$ to $V$ (and vice versa) for all vertices $1 \leq U, V \leq N$

Output

If Mr. Endo's wrong BFS code cannot stop within finite steps for the given input graph, print -1 in a line. Otherwise, print the minimum number of loop iterations required to stop.

Examples

Input

3 3
1 2
1 3
2 3


Output

2


Input

4 3
1 2
2 3
3 4


Output

-1


Input

4 4
1 2
2 3
3 4
4 1


Output

-1


Input

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


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a tree T with n nodes, how many subtrees (T') of T have at most K edges connected to (T - T')? 

Input Format

The first line contains two integers n and K followed by n-1 lines each containing two integers a & b denoting that there's an edge between a & b.

Constraints

1 <= K <= n <= 50 

Every node is indicated by a distinct number from 1 to n.

Output Format

A single integer which denotes the number of possible subtrees.

Sample Input
3 1
2 1
2 3

Sample Output
6

Explanation

There are 2^3 possible sub-trees:   

{} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

But: 

the sub-trees {2} and {1,3} are not valid. 
{2} isn't valid because it has 2 edges connecting to it's complement {1,3} whereas K = 1 in the sample test-case
{1,3} isn't valid because, well, it's not a sub-tree. The nodes aren't connected.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
Note: Unlike 0/1 knapsack, you are allowed to break the item. 
 
Example 1:
Input:
N = 3, W = 50
values[] = {60,100,120}
weight[] = {10,20,30}
Output:
240.00
Explanation:Total maximum value of item
we can have is 240.00 from the given
capacity of sack. 
Example 2:
Input:
N = 2, W = 50
values[] = {60,100}
weight[] = {10,20}
Output:
160.00
Explanation:
Total maximum value of item
we can have is 160.00 from the given
capacity of sack.
 
Your Task :
Complete the function fractionalKnapsack() that receives maximum capacity , array of structure/class and size n and returns a double value representing the maximum value in knapsack.
Note: The details of structure/class is defined in the comments above the given function.
Expected Time Complexity : O(NlogN)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= W <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
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:-----
5
1
2
3
4
5

-----Sample Output:-----
1
1
32
1
32
654
1
32
654
10987
1
32
654
10987
1514131211

-----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.
You are given a rooted tree, consisting of $n$ vertices. The vertices are numbered from $1$ to $n$, the root is the vertex $1$.

You can perform the following operation at most $k$ times:

choose an edge $(v, u)$ of the tree such that $v$ is a parent of $u$;

remove the edge $(v, u)$;

add an edge $(1, u)$ (i. e. make $u$ with its subtree a child of the root).

The height of a tree is the maximum depth of its vertices, and the depth of a vertex is the number of edges on the path from the root to it. For example, the depth of vertex $1$ is $0$, since it's the root, and the depth of all its children is $1$.

What's the smallest height of the tree that can be achieved?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $0 \le k \le n - 1$) — the number of vertices in the tree and the maximum number of operations you can perform.

The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$) — the parent of the $i$-th vertex. Vertex $1$ is the root.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the smallest height of the tree that can achieved by performing at most $k$ operations.


-----Examples-----

Input
5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1
Output
2
1
5
3
1


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko got an array of integers for his birthday from his grandmother Norma. As any other kid, he was hoping for some money, but got an array. Luckily, in his town there is a pawn shop that buys up arrays. The cost of an array of integers is $\min \cdot \max \cdot L$ kunas, where $\min $ is the minimal integer in the array, $\max $ is the maximal and $L$ is the array length. Mirko is going to sell a subsequence of consecutive numbers from his array. He calculated the average price of all such subsequences.

In order to check his result, he wants you to do the same. He will be pleased with only the last $9$ digits of the sum of all prices, so you don’t need to bother with large and real numbers.

-----Input-----
The first line of input contains an integer $N$ ($1 \leq N \leq 500000$).

Each of the following $N$ lines contains a member of Mirko’s array. The members of the array will be integers from the interval $[1, 10^8 ]$.

-----Output-----
The first and only line of output must contain an integer, the last $9$ digits of the required sum from the task. You don’t need to output the leading zeroes of that 9-digit integer.

-----Examples-----
Sample Input 1:
2
1
3
Sample Output 1:
16

Sample Input 2:
4
2
4
1
4
Sample Output 2:
109

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
City X consists of n vertical and n horizontal infinite roads, forming n × n intersections. Roads (both vertical and horizontal) are numbered from 1 to n, and the intersections are indicated by the numbers of the roads that form them.

Sand roads have long been recognized out of date, so the decision was made to asphalt them. To do this, a team of workers was hired and a schedule of work was made, according to which the intersections should be asphalted.

Road repairs are planned for n^2 days. On the i-th day of the team arrives at the i-th intersection in the list and if none of the two roads that form the intersection were already asphalted they asphalt both roads. Otherwise, the team leaves the intersection, without doing anything with the roads.

According to the schedule of road works tell in which days at least one road will be asphalted.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50) — the number of vertical and horizontal roads in the city. 

Next n^2 lines contain the order of intersections in the schedule. The i-th of them contains two numbers h_{i}, v_{i} (1 ≤ h_{i}, v_{i} ≤ n), separated by a space, and meaning that the intersection that goes i-th in the timetable is at the intersection of the h_{i}-th horizontal and v_{i}-th vertical roads. It is guaranteed that all the intersections in the timetable are distinct.


-----Output-----

In the single line print the numbers of the days when road works will be in progress in ascending order. The days are numbered starting from 1.


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

Output
1 4 

Input
1
1 1

Output
1 



-----Note-----

In the sample the brigade acts like that:  On the first day the brigade comes to the intersection of the 1-st horizontal and the 1-st vertical road. As none of them has been asphalted, the workers asphalt the 1-st vertical and the 1-st horizontal road;  On the second day the brigade of the workers comes to the intersection of the 1-st horizontal and the 2-nd vertical road. The 2-nd vertical road hasn't been asphalted, but as the 1-st horizontal road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the third day the brigade of the workers come to the intersection of the 2-nd horizontal and the 1-st vertical road. The 2-nd horizontal road hasn't been asphalted but as the 1-st vertical road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the fourth day the brigade come to the intersection formed by the intersection of the 2-nd horizontal and 2-nd vertical road. As none of them has been asphalted, the workers asphalt the 2-nd vertical and the 2-nd horizontal road.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two strings X and Y of lengths m and n respectively, find the length of the smallest string which has both, X and Y as its sub-sequences.
Note: X and Y can have both uppercase and lowercase letters.
Example 1
Input:
X = abcd, Y = xycd
Output: 6
Explanation: Shortest Common Supersequence
would be abxycd which is of length 6 and
has both the strings as its subsequences.
Example 2
Input:
X = efgh, Y = jghi
Output: 6
Explanation: Shortest Common Supersequence
would be ejfghi which is of length 6 and
has both the strings as its subsequences.
Your Task:
Complete shortestCommonSupersequence() function that takes X, Y, m, and n as arguments and returns the length of the required string.
Expected Time Complexity: O(Length(X) * Length(Y)).
Expected Auxiliary Space: O(Length(X) * Length(Y)).
Constraints:
1<= |X|, |Y| <= 100

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas.

Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yellow. On the one-dimensional canvas split into *n* consecutive segments, each segment needs to be painted in one of the colours.

Arkady has already painted some (possibly none or all) segments and passes the paintbrush to you. You are to determine whether there are at least two ways of colouring all the unpainted segments so that no two adjacent segments are of the same colour. Two ways are considered different if and only if a segment is painted in different colours in them.

Input Specification:
The first line contains a single positive integer *n* (1<=≤<=*n*<=≤<=100) — the length of the canvas.

The second line contains a string *s* of *n* characters, the *i*-th of which is either 'C' (denoting a segment painted in cyan), 'M' (denoting one painted in magenta), 'Y' (one painted in yellow), or '?' (an unpainted one).

Output Specification:
If there are at least two different ways of painting, output "Yes"; otherwise output "No" (both without quotes).

You can print each character in any case (upper or lower).

Demo Input:
['5\nCY??Y\n', '5\nC?C?Y\n', '5\n?CYC?\n', '5\nC??MM\n', '3\nMMY\n']

Demo Output:
['Yes\n', 'Yes\n', 'Yes\n', 'No\n', 'No\n']

Note:
For the first example, there are exactly two different ways of colouring: CYCMY and CYMCY.

For the second example, there are also exactly two different ways of colouring: CMCMY and CYCMY.

For the third example, there are four ways of colouring: MCYCM, MCYCY, YCYCM, and YCYCY.

For the fourth example, no matter how the unpainted segments are coloured, the existing magenta segments will prevent the painting from satisfying the requirements. The similar is true for the fifth example.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array *a* consisting of *n* elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.

For example, the imbalance value of array [1,<=4,<=1] is 9, because there are 6 different subsegments of this array: 
 -  [1] (from index 1 to index 1), imbalance value is 0; -  [1,<=4] (from index 1 to index 2), imbalance value is 3; -  [1,<=4,<=1] (from index 1 to index 3), imbalance value is 3; -  [4] (from index 2 to index 2), imbalance value is 0; -  [4,<=1] (from index 2 to index 3), imbalance value is 3; -  [1] (from index 3 to index 3), imbalance value is 0; 
You have to determine the imbalance value of the array *a*.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=106) — size of the array *a*.

The second line contains *n* integers *a*1,<=*a*2... *a**n* (1<=≤<=*a**i*<=≤<=106) — elements of the array.

Output Specification:
Print one integer — the imbalance value of *a*.

Demo Input:
['3\n1 4 1\n']

Demo Output:
['9\n']

Note:
none

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