vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
*Chef is moving to a new house!*

*Unfortunately, this means he now has to pack up his things so that they can be moved too. Currently, Chef is packing up his (rather impressive) book collection into cardboard boxes.*

Chef has X shelves of books, each of which contains exactly Y books. Each cardboard box can hold at most Z books. In order to not mess up the organization of the books, Chef will also ensure that books from different shelves will not be placed in the same box.

Under these conditions, what is the minimum number of boxes needed to pack all the books?

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of one line of input, containing three space-separated integers X, Y, and Z: the values described in the statement.

------ Output Format ------ 

For each test case, output on a new line one integer: the minimum number of boxes needed to pack all the books.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ X, Y, Z ≤ 1000$

----- Sample Input 1 ------ 
4
5 9 9
5 9 7
2 3 2
22 34 12

----- Sample Output 1 ------ 
5
10
4
66

----- explanation 1 ------ 
Test case $1$: Each box can hold $9$ books, and each shelf has $9$ books. So, Chef needs only five boxes: one for each shelf.

Test case $2$: Each box can hold $7$ books, and each shelf has $9$ books. So, Chef needs two boxes to hold all the books of one shelf (for example, one holding $4$ books and another one holding $5$). There are five shelves, so the total number of boxes needed is $5\times 2 = 10$.

Test case $3$: Each box can hold $2$ books, and each shelf has $3$ books. So, Chef needs two boxes to hold all the books of one shelf (for example, one holding $2$ books and another one holding $1$). There are two shelves, so the total number of boxes needed is $2\times 2 = 4$.

Test case $4$: Each shelf needs $3$ boxes to pack all its books. There are $22$ shelves, so the answer is $22\times 3 = 66$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya sometimes has to water his field. To water the field, Petya needs a tank with exactly *V* ml of water.

Petya has got *N* tanks, *i*-th of them initially containing *a**i* ml of water. The tanks are really large, any of them can contain any amount of water (no matter how large this amount is).

Also Petya has got a scoop that can contain up to *K* ml of water (initially the scoop is empty). This scoop can be used to get some water from some tank, and after that pour it all into some tank (it is impossible to get water from multiple tanks without pouring it, or leave some water in the scoop when pouring it). When Petya tries to get some water from a tank, he gets *min*(*v*,<=*K*) water, where *v* is the current volume of water in the tank.

Is it possible to obtain a tank with exactly *V* ml of water using these operations? If it is possible, print a sequence of operations that allows to do it. If there are multiple ways to obtain needed amount of water in some tank, print any of them.

Input Specification:
The first line contains 3 integers: *N* (2<=≤<=*N*<=≤<=5000), *K* (1<=≤<=*K*<=≤<=5000), and *V* (0<=≤<=*V*<=≤<=109) — the number of tanks, the maximum volume of water the scoop can contain, and the required amount of water in some tank, respectively.

The second line contains *N* integers *a**i* (0<=≤<=*a**i*<=≤<=105), where *a**i* is initial volume of water in *i*-th tank.

Output Specification:
If it is impossible to obtain a tank with exactly *V* ml of water, print NO. 

Otherwise print YES in the first line, and beginning from the second line, print the sequence of operations in the following format: 

Each line has to contain 3 numbers denoting a compressed operation: "*cnt* *x* *y*" (1<=≤<=*cnt*<=≤<=109,<=1<=≤<=*x*,<=*y*<=≤<=*N*), where *x* is the index of the tank where we get water, *y* is the index of the tank where we pour water, and *cnt* is the number of times we transfer water from tank *x* to tank *y*. 

The number of these lines must not exceed *N*<=+<=5.

Demo Input:
['2 3 5\n2 3\n', '2 3 4\n2 3\n', '5 2 0\n1 3 5 7 9\n']

Demo Output:
['YES\n1 2 1\n', 'NO\n', 'YES\n2 2 1\n3 3 1\n4 4 1\n5 5 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer L. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.
 - The number of vertices, N, is at most 20. The vertices are given ID numbers from 1 to N.
 - The number of edges, M, is at most 60. Each edge has an integer length between 0 and 10^6 (inclusive).
 - Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, 1,2,...,N is one possible topological order of the vertices.
 - There are exactly L different paths from Vertex 1 to Vertex N. The lengths of these paths are all different, and they are integers between 0 and L-1.
Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.

-----Constraints-----
 - 2 \leq L \leq 10^6
 - L is an integer.

-----Input-----
Input is given from Standard Input in the following format:
L

-----Output-----
In the first line, print N and M, the number of the vertices and edges in your graph.
In the i-th of the following M lines, print three integers u_i,v_i and w_i, representing the starting vertex, the ending vertex and the length of the i-th edge.
If there are multiple solutions, any of them will be accepted.

-----Sample Input-----
4

-----Sample Output-----
8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1

In the graph represented by the sample output, there are four paths from Vertex 1 to N=8:
 - 1 → 2 → 3 → 4 → 8 with length 0
 - 1 → 2 → 3 → 7 → 8 with length 1
 - 1 → 2 → 6 → 7 → 8 with length 2
 - 1 → 5 → 6 → 7 → 8 with length 3
There are other possible solutions.

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

Russian Version

You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation. 

The update query is of the format

i j X

This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input)

The retrieval query is of the format

i j

You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433. 

Input Format 

The first line contains two integers (N and R respectively) separated by a space. 

In the next N-1 lines, the$ i^{th}$ line describes the $i^{th} $edge: a line with two integers a b separated by a single space denotes an edge between a, b. 

The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow. 

U lines follow. Each of the next U lines contains 3 space separated integers (i,j, and X respectively). 

Each of the next Q lines contains 2 space separated integers, i and j respectively. 

Output Format 

It contains exactly Q lines and each line containing the answer of the$ i^{th}$ query.

Constraints

2 <= N <= 100000 

2 <= R <= $10^{9}$ 

1 <= U <= 100000 

1 <= Q <= 100000 

1 <= X <= 10 

1 <= a, b, i, j <= N  

Sample Input  

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

Sample Output

31
18

Explanation

The node values after the first updation becomes :  

3 6 0 0 0 12  

The node values after second updation becomes :  

3 6 20 10 5 12  

Answer to Query #1: 12 + 6 + 3 + 10 = 31 

Answer to Query #2: 5 + 10 +3 = 18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array containing positive and negative numbers. The array represents checkpoints from one end to other end of street. Positive and negative values represent amount of energy at that checkpoint. Positive numbers increase the energy and negative numbers decrease. Find the minimum initial energy required to cross the street such that Energy level never becomes 0 or less than 0.
Note :  The value of minimum initial energy required will be 1 even if we cross street successfully without loosing energy to less than and equal to 0 at any checkpoint. The 1 is required for initial check point.
 
Example 1:
Input
N = 5
A[] = {4, -10, 4, 4, 4}
Output
7
Explanation
By having an initial energy of 7 we can
make sure that all the checkpoints are
visited and the fuel never reaches 0
or less value.
 
Example 2:
Input
N = 5
A[] = {3, 5, 2, 6, 1}
Output
1
Explanation
We need at least 1 initial energy
to reach first checkpoint.
Your Task:
You don't need to print anything, printing is done by the driver code itself. You need to complete the function minEnergy() which takes the array A[] and its size N as inputs and returns the minimum initial energy required to cross the street.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
-10^{3} ≤ A[i] ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The mythical planet, El-gă-rizm, comprises $m$ islands surrounded by water. There are $n$ different natural resources to be found at various locations on the islands. Interestingly, each of the $n$ natural resources is present on exactly two islands; thus there are $2n$ total occurrences of resources on El-gă-rizm.

Both the Zax and Xaz beings simultaneously attempt to colonize the islands of El-gă-rizm. The Zax and Xaz mistrust each other. They will share the planet but refuse to share any individual island or any resources on an island. Thus each island is populated by only Zax or Xaz, never both. Collectively, the Zax have access to all natural resources on islands they populate. The Xaz also have access to all natural resources on islands that they populate. In order to survive on El-gă-rizm, a being needs access to all $n$ natural resources.

Can the Zax and Xaz coexist on El-gă-rizm?

-----Input-----
The first line contains the positive integers $m$ and $n$, separated by a space, representing the number of islands and the number of different natural resources, respectively. Following that are $m$ lines. The $i$-th such line specifies the natural resources present on the $i$-th island, as a sequence of integers, separated by spaces. The different natural resources are represented by the integers $1, 2, 3, \ldots , n$. The last value on each of the $m$ lines is always $0$. The value $0$ does not represent a natural resource; it only indicates that there are no more subsequent values on that line.

You may assume that $m$ and $n$ are each no greater than $1000000$.

-----Output-----
The output should be a single line consisting of the string YES if the Zax and Xaz can coexist on El-gă-rizm, or the string NO otherwise.

-----Examples-----
Sample Input:
8 8
0
2 4 0
1 8 0
8 5 0
4 3 7 0
5 2 6 0
1 6 0
7 3 0
Sample Output:
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef recently learned about concept of periodicity of strings. A string is said to have a period P, if P divides N and for each i, the i-th of character of the string is same as i-Pth character (provided it exists), e.g. "abab" has a period P = 2, It also has a period of P = 4, but it doesn't have a period of 1 or 3.
Chef wants to construct a string of length N that is a palindrome and has a period P. It's guaranteed that N is divisible by P. This string can only contain character 'a' or 'b'. Chef doesn't like the strings that contain all a's or all b's.
Given the values of N, P, can you construct one such palindromic string that Chef likes? If it's impossible to do so, output "impossible" (without quotes)

-----Input-----
The first line of the input contains an integer T denoting the number of test cases.
The only line of each test case contains two space separated integers N, P.

-----Output-----
For each test case, output a single line containing the answer of the problem, i.e. the valid string if it exists otherwise "impossible"  (without quotes). If there are more than possible answers, you can output any.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ P, N ≤ 105

-----Subtasks-----
- Subtask #1 (25 points) : P = N
- Subtask #2 (75 points) : No additional constraints

-----Example-----
Input
5
3 1
2 2
3 3
4 4
6 3

Output
impossible
impossible
aba
abba
abaaba

-----Explanation-----
Example 1: The only strings possible are either aaa or bbb, which Chef doesn't like. So, the answer is impossible.
Example 2: There are four possible strings, aa, ab, ba, bb. Only aa and bb are palindromic, but Chef doesn't like these strings. Hence, the answer is impossible.
Example 4: The string abba is a palindrome and has a period of 4.
Example 5: The string abaaba is a palindrome and has a period of length 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu wants to decorate his garden with flowers. He has purchased n boxes, where the i-th box contains fi flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color.

Now Devu wants to select exactly s flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (109 + 7). 

Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways.

Input

The first line of input contains two space-separated integers n and s (1 ≤ n ≤ 20, 0 ≤ s ≤ 1014).

The second line contains n space-separated integers f1, f2, ... fn (0 ≤ fi ≤ 1012).

Output

Output a single integer — the number of ways in which Devu can select the flowers modulo (109 + 7).

Examples

Input

2 3
1 3


Output

2


Input

2 4
2 2


Output

1


Input

3 5
1 3 2


Output

3

Note

Sample 1. There are two ways of selecting 3 flowers: {1, 2} and {0, 3}.

Sample 2. There is only one way of selecting 4 flowers: {2, 2}.

Sample 3. There are three ways of selecting 5 flowers: {1, 2, 2}, {0, 3, 2}, and {1, 3, 1}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a cube of size k × k × k, which consists of unit cubes. Two unit cubes are considered neighbouring, if they have common face.

Your task is to paint each of k3 unit cubes one of two colours (black or white), so that the following conditions must be satisfied:

  * each white cube has exactly 2 neighbouring cubes of white color; 
  * each black cube has exactly 2 neighbouring cubes of black color. 

Input

The first line contains integer k (1 ≤ k ≤ 100), which is size of the cube.

Output

Print -1 if there is no solution. Otherwise, print the required painting of the cube consequently by layers. Print a k × k matrix in the first k lines, showing how the first layer of the cube should be painted. In the following k lines print a k × k matrix — the way the second layer should be painted. And so on to the last k-th layer. Note that orientation of the cube in the space does not matter.

Mark a white unit cube with symbol "w" and a black one with "b". Use the format of output data, given in the test samples. You may print extra empty lines, they will be ignored.

Examples

Input

1


Output

-1


Input

2


Output

bb
ww

bb
ww

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Integer array A[] of n elements. Your task is to complete the function PalinArray. Which will return 1 if all the elements of the Array are palindrome otherwise it will return 0.
Example 1:
Input:
5
111 222 333 444 555
Output:
1
Explanation:
A[0] = 111 //which is a palindrome number.
A[1] = 222 //which is a palindrome number.
A[2] = 333 //which is a palindrome number.
A[3] = 444 //which is a palindrome number.
A[4] = 555 //which is a palindrome number.
As all numbers are palindrome so This will return 1.
Example 2:
Input:
3
121 131 20
 
Output:
0
Explanation:
20 is not a palindrome hence the output is 0.
Constraints:
1 <=T<= 50
1 <=n<= 20
1 <=A[]<= 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:


Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.


Example 2:


Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
NOTE: All quotes are for clarity

You are given one n x m grid and q queries. Each cell of grid will have a value assigned to it. Each query will be of type "x y d". Read below on how you have to process them.

For each query, the grid is initially plain white. Now, for query "x y d" the cell (x, y) will be colored black. Your job, now, is to color each cell in the grid to black, such that at least one of its adjacent cell is colored black and the absolute difference of value between current cell and adjacent colored cell is ≤ d. (Adjacent cells are right, left, up and down to current cell). You have to keep coloring as long as you can find such cells. You have to tell after each query, how many cells are colored black.

INPUT

Each test file will have a single test case. The first line on input will have three integers n, m, and q.
Next n lines, each having m integers will be given. The j^th  integer on i^th  line will indicate the value of cell (i, j).
Then q lines of type "x y d" follow, each denoting a single query, as explained in problem statement.

OUTPUT

Output for each query a single integer on a separate line, denoting the number of colored cells for that particular query.

CONSTRAINTS

1 ≤ n,m ≤ 100

1 ≤ q ≤ 100

1 ≤ x ≤ n

1 ≤ y ≤ m

1 ≤ d ≤ 100000

-100000 ≤ The value of each cell of grid ≤ 100000

SAMPLE INPUT
4 4 3
0 0 1 0
1 2 1 0
0 0 1 0
1 0 1 0
4 4 0
4 3 1
2 2 2

SAMPLE OUTPUT
4
16
16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly ai cities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: <image>.

Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them. 

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

Examples

Input

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 1 1 1 1 1 1 1 1


Output

1.5000000000 2.5000000000
1.5000000000 2.5000000000


Input

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


Output

-3.5000000000 2.0000000000
3.5000000000 -1.0000000000


Input

10
-2 10
6 0
-16 -6
-4 13
-4 -2
-17 -10
9 15
18 16
-5 2
10 -5
2 1 1 1 1 1 1 1 1


Output

-1

Note

The solution for the first sample test is shown below:

<image>

The solution for the second sample test is shown below:

<image>

There is no solution for the third sample test.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges going outside this vertex. 

Yesterday Ivan learned Landau's criterion: there is tournament with scores d1 ≤ d2 ≤ ... ≤ dn if and only if <image> for all 1 ≤ k < n and <image>.

Now, Ivan wanna solve following problem: given a set of numbers S = {a1, a2, ..., am}, is there a tournament with given set of scores? I.e. is there tournament with sequence of scores d1, d2, ..., dn such that if we remove duplicates in scores, we obtain the required set {a1, a2, ..., am}? 

Find a tournament with minimum possible number of vertices. 

Input

The first line contains a single integer m (1 ≤ m ≤ 31).

The next line contains m distinct integers a1, a2, ..., am (0 ≤ ai ≤ 30) — elements of the set S. It is guaranteed that all elements of the set are distinct.

Output

If there are no such tournaments, print string "=(" (without quotes).

Otherwise, print an integer n — the number of vertices in the tournament.

Then print n lines with n characters — matrix of the tournament. The j-th element in the i-th row should be 1 if the edge between the i-th and the j-th vertices is oriented towards the j-th vertex, and 0 otherwise. The main diagonal should contain only zeros.

Examples

Input

2
1 2


Output

4
0011
1001
0100
0010


Input

2
0 3


Output

6
000111
100011
110001
011001
001101
000000

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