# Second qualification round completed

"A" Very Important Persons
Time limit 1 second 256 megabytes

Opening ceremony of the new campus of N State University will be visited by nm very important persons. The ceremony will take place in a hall that has the form of a rectangle, seats in the hall are arranged in n rows, m seats in each row. Rows are numbered from 1 to n, seats in each row are numbered from 1 to m, the j-th seat of the i-th row is denoted as (i, j).

The organizers of the ceremony have numbered the guests from 1 to nm in accordance with their importance — the greater, the more important. The most important guest, the mayor of the city, gets the number nm. The mayor is planning to take seat (1, 1). Now the other guests must be assigned seats. The guests must be arranged according to their importance, there must be no situation that a guest with greater number is seating further from the mayor than a guest with smaller number. The distance between two seats (r1, s1) and (r2, s2) is measured as |r1 - r2| + |s1 - s2|.

Help the organizers to assign guests to seats.

Input format

Input contains several test cases. The first line contains the number of test cases t (1 ≤ t ≤ 400).

Each test case is specified with a line that contains two integers: n and m (1 ≤ n, m ≤ 20).

Output format

For each test case output the hall plan after the seats are assigned to guests.

Output n lines, each line must contain m integers, the j-th integer of the i-th line must be equal to the importance of the guest that will be assigned the seat (i, j).

If there are several valid ways to assign seats to guests, output any of them.

Examples
Input data
```2
2 3
3 2
```
Output data
```6 4 2
5 3 1
6 4
5 2
3 1
```
"B" Least Common Multiple
Time limit 2 seconds 256 megabytes

Least common multiple is a well known term in math, it is the smallest number that is divisible by any of the given numbers. The concept of least common multiple can be generalized to other objects in math, for example to fractions.

You are given two irreducible fractions. Find their least common multiple — the smallest positive irreducible fraction p / q such that the result of the division of p / q to any of the given fractions is integer.

Input format

Input contains several test cases. The first line of input contains integer t — the number of test cases (1 ≤ t ≤ 50 000).

Each test case is described as a single line that contains four positive integers a, b, c, d, that correspond to irreducible fractions a / b and c / d (1 ≤ a, b, c, d ≤ 109). It is guaranteed that a / b and c / d are both irreducible.

Output format

For each test case output one line. Print two integers: numerator and denominator of the fraction that is a least common multiple of the given a / b and c / d fractions.

Examples
Input data
```2
9 5 12 5
1 10 3 100
```
Output data
```36 5
3 10
```
Time limit 2 seconds 256 megabytes

Little Dima has a nice pattern at the floor of his room, it consists of n dots arranged in a row. Strange coincidence, but Dima also has n toy cubes that he likes to play, they have weights of 1, 2, ..., n grams, respectively. Dima has finished playing with his cubes and put them on a floor at the dots, one cube at each dot. Now he is going to reorder them in such way that their weight increased from left to right. However, he took a break before doing so, meanwhile bad boy Vadim entered the room.

Vadim knows that Dima will use the following way to rearrange the cubes. Each time he will look for the cube with the smallest weight that is at wrong dot yet, and swap it with the one that occupies its dot.

Vadim is very vicious, so he wants to force Dima to make the maximum number of swaps. He took some cubes out of the Dima's row and now he is planning to put them back. He wants to put them back in such way, that there still was exactly one cube at each dot, cubes that were not taken before stayed at their places, and Dima needed maximum possible number of swaps to sort the cubes using his method.

How should Vadim put the cubes back to the row?

Input format

Input data contains several test cases. The first line of input contains the number of test cases t.

Each test is described in the following way.

The first line of the description contains an integer n — the number of cubes (1 ≤ n ≤ 105). The following line contains n integers ai (0 ≤ ai ≤ n)

If ai is equal to 0, that means that the cube from the i-th dot was taken away by Vadim, this dot is now empty. In the other case ai is the weight of the cube at the i-th dot.

It is guaranteed that all remaining cubes have different weights, Vadim must return exactly the cubes that are currently missing from the line.

The sum of n in all test cases of one input data doesn't exceed 105.

Output format

Output two lines for each test case.

The first line must contain the maximum number of swaps that Vadim can force Dima to make.

The second line must contain n integers — weights of cubes in order they will be arranged after Vadim puts cubes he has taken away back. Note, that cubes that were not taken away must remain at their current positions.

If there are several possible arrangements that force Dima to make maximum number of swaps, output any of them.

Examples
Input data
```3
2
0 0
4
4 0 0 3
5
0 4 0 2 5
```
Output data
```1
2 1
3
4 1 2 3
2
3 4 1 2 5
```
"D" Red-Black Tree
Time limit 3 seconds 256 megabytes

Did you now that most standard libraries use red-black tree to implement "set" data structure? In this problem you have to find the number of ways to color the vertices of the given binary tree so that it became red-black. Print the answer modulo 109 + 7.

Consider a binary tree. If the vertex has less than two children, add fake vertices to the potential places of the missing children. The tree is called a red-black tree if the following constraints are satisfied:

1. Each vertex is colored one of the two colors: red or black.
2. The root of the tree and added fake vertices are colored black.
3. The parent of a red vertex is black.
4. All paths the root to fake leafs contain the same number of black vertices.

Note that the parent of a black vertex can be black itself.

Two ways to color the tree are different if there is a vertex that has different colors.

The picture shows two ways to color the tree from the second test case. Input format

The first line contains one integer n — the number of vertices in a tree (1 ≤ n ≤ 500 000).

The following n lines describe a tree. The i-th of these lines contains two integers li and ri — the indices of the left and the right child of the i-th vertex, or 0 if the corresponding child is missing (li = 0 or i < li ≤ n; ri = 0 or i < ri ≤ n). The root of the tree has number 1. Input describes the correct tree.

Output format

Output one integer — the number of ways to color the given tree so that it was a correct red-black tree. The answer must be printed modulo 109 + 7.

Examples
Input data
```3
2 3
0 0
0 0
```
Output data
```2
```
Input data
```6
2 4
3 0
0 0
5 6
0 0
0 0
```
Output data
```2
```
"E" Array Study
Time limit 2 seconds 256 megabytes

Vasya likes to study arrays. Recently his parents presented him with an array a that contains elements equal to 1 and  - 1. Vasya immediately started to study it.

Additionally Vasya likes zeroes. So he decided to consider various subarrays a[li, ..., ri] of array a. For each subarray he tries to find the maximum length of its subarray with the sum equal to 0. If there is no such subarray, he considers the answer to be 0. Vasya has written down q subarray requests [li, ri], and now he wants to find the sum of answers to them.

For example, let us consider sample test.

• subarray [1, 5]: the maximal subarray with sum 0 — [2, 5];
• subarray [1, 3]: the maximal subarray with sum 0 — [2, 3];
• subarray [2, 4]: the maximal subarray with sum 0 — [2, 3];
• subarray [3, 4]: no subarray with sum 0;
• subarray [3, 5]: the maximal subarray with sum 0 — [4, 5].

So the sum of answers for the sample test is 4 + 2 + 2 + 0 + 2 = 10.

Input format

Input data contains several test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000).

Each of t test cases is described in the following way: the first line of the description contains n — the number of elements of the array (1 ≤ n ≤ 105).

The following line contains n integers ai — elements of the array (ai =  - 1 or ai = 1).

The following line contains q — the number of subarrays that Vasya is interested in (1 ≤ q ≤ 105).

Each of the following q lines contains two integers li, ri — left and right border of the i-th subarray (1 ≤ li ≤ ri ≤ n)

It is guaranteed that the sum of n in all test cases of one input data doesn't exceed 105, the sum of q in all test cases of one input data doesn't exceed 105.

Output format

For each test output one integer — the sum of answers for the given q subarrays.

Examples
Input data
```1
5
1 -1 1 1 -1
5
1 5
1 3
2 4
3 4
3 5
```
Output data
```10
```

### Send solution

Maximal size is 256kb 