So, the third qualifying round of the international championship of programmers of the Russian Code Cup 2016 is over. As in the previous two rounds, the participants had to solve five problems within two hours. Both the accuracy and speed of the decision were taken into account. In the third qualifying round, 4379 people fought for the chance to reach the next final. But only 200 of them won the opportunity to get closer to winning the championship. And now, according to the established tradition, we will analyze the tasks of the round.

1. Rectangle and squares
2. Zeros and ones
3. New track
4. Tree
5. Barbarians

Problem A. Rectangle and squares

Condition
')
Time limit of 2 seconds
256 MB memory limit

Ilya went to his friend Phil and saw a surprisingly beautiful rectangle with sides A and B. Ilya realized that all his life he had dreamed of a rectangle of just such an area.

When he arrived home, he saw that his whole house was filled with C × C squares. Help him to collect a rectangle from squares C × C , which is as small as possible in the area from the rectangle seen from Phil. Namely: he wants the module of the difference between the area of ​​the Phil rectangle and the assembled rectangle to be as small as possible.

Squares can be laid parallel to the coordinate axes, without gaps and overlays. Obviously, Ilya will take at least one square.

For example, if Phil's rectangle has a size of 4 × 5, and Illya has 3 × 3 squares, then the rectangle with the area closest to Phil's rectangle that Ilya can collect is 3 × 6.

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 10 000).

Each test case is described in one line containing three integers A , B and C (1 ≤ A , B , C ≤ 10 ⁹ ).

Output format

For each test in a separate line print the answer to it - the area of ​​the rectangle collected by Illya from the squares of C × C , as little as possible different in area from what he saw in Phil.

If there are several answers, output any of them.

Examples

Input data
3
4 5 3
2 3 1
6 4 5

Output
18
6
25

Decision

In solving this problem, it should be noted that only the difference in the areas of the original rectangle and the collected one is important, and the shape can be any. Then it is obvious that a rectangle with sides C and nC is suitable as an answer, where n is a natural number.

The number n is easy to calculate. It is equal to the quotient A • B and C ² , rounded up or down. It remains to choose the most advantageous of these answers and remember to use at least one C × C square.

Problem B. Zeros and ones

Condition

Time limit of 2 seconds
256 MB memory limit

Today, Peter did not do his homework on computer science, so he was called to the blackboard as a punishment. The teacher wrote two lines of the same length on the blackboard, consisting of 0 and 1, and asked to make them equal, using only one operation: it is allowed to take two adjacent characters of any of the lines and invert them, while inverting, character 0 becomes equal to 1, and 1 - 0 .

Also, in order to complicate the task and even more punish Petya, the teacher asked to do it for the minimum number of applications of this operation.

Petya is confused and asks for your help, help him.

For example, let the teacher write the lines 0101 and 1111 on the blackboard. Then one of the best ways to make them equal is the following: first we invert the two central characters of the first line, we get the lines 0011 and 1111. Now we invert the first two characters of the second line, we get the lines 0011 and 0011. Note that there are other ways to achieve equal rows in two actions.

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 100).

Each of the following t tests is described as follows: the first line of the test description contains the number n (1 ≤ n ≤ 10 ⁵ ) - the length of the lines written by the teacher. The second and third lines of the test description contain the lines written by the teacher, two lines of length n from 0 and 1.

It is guaranteed that the sum of the numbers n in all tests does not exceed 10 ⁵ .

Output format

For each test in a separate line print the answer to it - the minimum number of applications of operations for which you can make the lines equal, or -1 if this is not possible.

Examples

Input data
2
four
0101
1111
3
011
111

Output
2
-one

Decision

It is easy to see that the inversion operation makes sense to apply only to one line: if, after applying inversions, the first and second lines match, then operations with the second line can be undone and applied to the first line, after that the lines will still be equal. Also note that operations can be applied in any order.

From this fact follows a simple greedy algorithm: we will go along the first line from left to right and maintain its current state. If in the i -th symbol s ₁ [ i ] ≠ s ₂ [ i ], then you should apply inversion to the i , i + 1 characters of the first line. If at the end s ₁ [ n ] ≠ s ₂ [ n ], then the desired sequence of inversions does not exist and the answer is -1.

Problem C. New track

Condition

Time limit of 2 seconds
256 MB memory limit

Route designer Ger Kilke received an order for a new Formula Y track. Ger plans to use his favorite way to build tracks. He introduced a coordinate system on the plane where the route will be located, in which the X axis is directed from left to right, and the Y axis is directed upwards, and wants to build a route with the following restrictions:

• The path must be an unlocked broken line of n segments parallel to the axes of coordinates.
• One of the ends of the broken line is the start, and the other is the finish, they must be at different points.
• The ends of the segments of the polyline should be in points with positive integer coordinates not exceeding 3000.
• The lengths of all segments must be non-zero.
• When moving along the polyline from the start to the finish, the angle between the directions of two consecutive runs should be 90 degrees clockwise.
• The end of any segment cannot be on another segment, besides the previous one and the next one in the polyline. In particular, segments that are not adjacent to the polyline cannot have common fragments of nonzero length.

Ger is going to make a new route of n segments, so that she has exactly k self-intersections. Mathematicians explained to him that this is possible if 0 ≤ k ≤ n ₂ ( n ₂ - 1) / 2, where n ₂ is equal to n / 2, rounded down. Of course, Ger chose such a value of k . Help Gera design a new track.

Input Format

The input contains several test cases. The first line of the file contains one positive integer t - the number of tests.

Each of the t following lines contains two natural numbers: n and k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n ₂ ( n ₂ - 1) / 2, where n ₂ is equal to n / 2, rounded down) - the number of segments in broken line and the number of self-intersections.

The sum n in all tests of one input data does not exceed 10 ⁴ .

Output format

The output file should contain the answers for each of the t tests.

Each answer must contain n + 1 lines, the i -th of which contains the coordinates of the i -th vertex in the polyline. Show vertices should be in the order of traversing a broken line from start to finish. Coordinates must be positive integers not exceeding 3000.

It is guaranteed that with the above restrictions, the desired polyline exists.

Examples

Input data
2
4 1
thirty

Output
13
3 3
3 1
2 1
2 5
3 9
3 1
eleven
14

Decision

This is the task of constructive example construction.

We first show how to build an example with a maximum value of k . Let's start with a horizontal segment, and then with each successive vertical segment we will cross all previous perpendicular to it, except for the one that goes directly in front of it. An example for 14 segments is shown in the figure.



To get exactly k , you need to take 2 l segments, so that l ( l - 1) ≥ 2 k > ( l - 1) ( l - 2), and build a maximum example, although it is possible, having completed the last segment in advance. The remaining n - 2 l segments add to the beginning of the route, placing around in a spiral. An example is shown in the figure for n = 17 and k = 9.



The restriction on k is taken for a reason. This is the maximum number of intersections for a fixed n . Those who wish can prove it themselves, hint: consider the number of intersections of a pair of segments n and n - 1 with pairs n - 3 and n - 4, n - 5 and n - 6, ..., 2 and 1 (or just segment 1, if n is even).

Problem D. Tree

Condition

Time limit of 2 seconds
256 MB memory limit

Kolya was presented with a hanging tree of n vertices for his birthday.

Recall that a hanging tree is a connected non-oriented graph without cycles, in which one of the vertices is a root. The parent of a peak is its neighbor, closest to the root, the root has no parent. The remaining neighbors of the summit are called her children. The vertices of the tree presented to Cole are numbered from 1 to n , the vertex with number 1 is its root.

Kohl decided to play with his tree. He selects some vertex u , deletes it, and hangs all her children to her former parent u . Kohl never removes the root. But just to delete vertices is not interesting, so he asked you to sometimes find the distance between the vertices in the current graph. Answer all the questions of the cunning Kohl.

Input Format

The first line contains a single integer n (1 ≤ n ≤ 100 000) - the number of vertices in the source tree. The second line contains n - 1 integers p _i (1 ≤ p _i ≤ n ) - the numbers of the vertices, which are originally the parents of the 2, 3, ..., n vertices.

The third line contains one integer q (1 ≤ q ≤ 100 000) - the number of queries. The following q lines contain the description of the queries. Each query starts with an integer that is 1 or 2. If the first number in the query is 1, then two numbers a and b follow (1 ≤ a , b ≤ n ) - two vertices, the distance between which needs to be found. Otherwise, the next is followed by one number v (1 ≤ v ≤ n ) - the number of the vertex to be deleted.

It is guaranteed that the source tree is set correctly, the vertices in the queries have not previously been deleted and the root is never deleted.

Output format

For each request of the second type in the new line print the distance between the vertices.

Examples

Input data
eight
1 5 2 1 2 5 5
7
2 4
1 7 6
2 5
1 3 8
1 8 6
2 2
1 8 6

Output
four
2
3
2

Decision

We make the tree weighted and initially set the weight of all the edges to 1. Now, if instead of removing the vertex, if we change the weight of the edge that goes from it to its parent, then the answer to the search query will be equal to the distance between the vertices from the weighted query edges in the source tree.

We will learn how to solve a new problem, we need to change the weight of the edge in the tree and find the distance between the vertices. To begin with, we will find the distances from the root to all vertices in the source tree and write these distances into an array in order to traverse the tree with DFS. With each change in the weight of the edge, we will maintain these distances. Note that all vertices, the distance to which will change when the weight of an edge changes, correspond to a continuous segment in the array. Therefore, in order to process a request, you need to add a constant on the segment in this array. For this purpose, for example, you can build a tree of segments on this array.

Then the distance between the vertices can be found as follows: d _ab = d _a + d _b - 2 d _lca , where lca is the smallest common ancestor of a and b , and d _v is the distance from the root to v .

Problem E. Barbarians

Condition

Time limit 4 seconds
256 MB memory limit

It turns out that life on the islands is sometimes not so pleasant! Recently, the country, whose territory consists of n islands, was attacked by barbarians. The islands of this country were connected by bridges in such a way that between any two islands there was a single path that does not pass through any island twice.

Barbarians understood that bridges are a weak point of this state. Therefore, they began to destroy them one by one! At the same time, residents' discontent grew and grew. Initially, discontent of the inhabitants of island i was equal to a _i .

Consider how the discontent of the inhabitants of some island x is changing after the destruction of the next bridge. We denote the number of islands to which residents of x before the destruction of the bridge could reach a , and after destruction, b . Then dissatisfaction increased a - b + 1 times.

You are invited to develop a system to determine the current dissatisfaction of residents. Your program will receive requests in the format of a pair of numbers u and v . Such a request indicates that the bridge that connects the cities u + res and v + res (where res is the answer to the last request) was destroyed. In this case, we must assume that at the beginning the answer to the last request is 0.

Let, after the destruction of the next bridge, the discontent of the inhabitants of the island i is equal to b _i , then you need to make res equal to the remainder of dividing the sum of all b _i by 10 ⁹ + 7, and also output this value.

For a better understanding of the format of the input and output data, consider what happens in the example.

Initially, residents are dissatisfied

1 2 3 4 5

After removing the bridge between islands 1 and 3, discontent of the inhabitants of islands 1 and 2 increased 4 times, and residents of other cities 3 times. That is, discontent after the destruction of the bridge became equal

4 8 9 12 15

and the total dissatisfaction of all is 48. After that, the bridge between –47 + 48 = 1 and –46 + 48 = 2 was destroyed. Accordingly, the discontent became equal

8 16 9 12 15

and total dissatisfaction is 60. After that, the bridge connecting Islands 3 and 5 was destroyed. Discontent became equal

8 16 18 24 45

and the total dissatisfaction reached 111. After the destruction of the last bridge, the discontent became equal

8 16 36 48 45

which is a total of 153.

Input Format

The first line contains an integer n (2 ≤ n ≤ 2 • 10 ⁵ ) - the number of islands.

The next line contains n numbers ai (1 ≤ a _i ≤ 10 ₉ + 6) - the initial discontent of the residents.

The following n - 1 lines contain pairs of numbers u _i , v _i (1 ≤ u _i , v _i ≤ n ). Such a pair means that the islands u _i and v _{i are} connected by a bridge. It is guaranteed that from each island to each other you can walk across the bridges in exactly one way.

Each of the following n - 1 lines contains requests in the format described in the statement. For a better understanding, see the explanation for the example in the condition. It is guaranteed that any bridge existed at the time of its destruction.

Output format

Print the answer to each request in a separate line.

Examples

Input data
five
1 2 3 4 5
12
13
3 4
3 5
3 1
-47 -46
-57 -55
-108 -107

Output
48
60
111
153

Decision

Note that the discontent of the inhabitants of the islands, which are in one component of connectivity, is equal to their initial discontent multiplied by a certain amount common to all these islands. We will support these values ​​for all components.

Let's learn how to handle edge removal in time proportional to the size of the smaller component. Then the total running time of the algorithm will be O ( n log n ). This can be proved as follows. For some vertex, consider the size of the component in which it is located. Then each time it is considered, the size of this component is reduced at least twice. Note that each vertex will be considered O (log n ) times.

If, when deleting an edge, we know which of the components is smaller, then we can go around all its vertices and move them to another component (recalculating all the necessary sums). To find the smaller of the components, run two width trails in the two components at the same time. And when one of them visits all the vertices in its component, we will not continue the work of the second round in width. This algorithm works for a time proportional to the size of the smaller of the components.

***
The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at the development of the Russian IT industry and integrated with the IT.Mail.Ru resource. The IT.Mail.Ru platform is designed for those who are keen on IT and are seeking to develop professionally in this area. The project combines the championships of the Russian Ai Cup, the Russian Code Cup and the Russian Developers Cup, educational projects Technopark in MSTU. Bauman, Technosphere at Moscow State University. MV Lomonosov and Tehnotrek MIPT. In addition, using IT.Mail.Ru, you can use tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from specialized events and lectures on IT topics.