B. Brother Louie
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In August 2015, coach Fegla was visiting Syria for a training camp in AAST, Lattakia Branch, as Noura and Fegla are very close friends, she asked him whether her brother Tamim can attend the camp since he has been a contestant for a year. Tamim was very interested in the coach's topics. One day, Tamim was trying to implement a binary tree drawing software, he asked the coach for some hints, and the coach suggested the following technique:

Given a rooted full binary tree (each node, except the leaves, has exactly two children nodes), the program must draw a tree where the nodes are circles with radius r, and the center of the root is located at (0, 0).

The drawn tree should satisfy the following conditions:

  • The distance between a node and its left child is equal to the distance between the node and its right child.
  • The horizontal distance between two subtrees rooted at two nodes with the same parent node must be equal to H.
  • The horizontal distance between two subtrees is the difference between the X coordinate of the rightmost point on the circumference of a node in the left subtree, and the X coordinate of the left most point on the circumference of a node in the right subtree.
  • The vertical distance between a node and its children must be equal to V, this distance is calculated between the circumferences as in the horizontal distance.
Help Tamim test his program by answering queries about the coordinates of some node U after his program has drawn the tree using the given parameters; r, V, H.
Input

The first line of input contains an integer T (1 ≤ T ≤ 64), the number of test cases.

The first line of each test case contains two integers N and q (1 ≤ N, q ≤ 105), the number of nodes and the number of queries. Each of the following N lines contains .

  • If k = 0 then the ith node is a leaf node.
  • If k = 2 then the ith node is a parent node and two integers will follow, the left child L, then the right child R (1 ≤ L, R ≤ N).
Then q lines follow, each line will represent a query. Each query will be given in the format: r V H U, (1 ≤ r, V, H ≤ 104), (1 ≤ U ≤ N)
Output

For each test case, print q lines, each line should contain the coordinates of the given node U rounded to 4 decimal places.

Examples
Input
1
9 4
2 4 5
2 6 7
2 1 2
0
0
2 9 8
0
0
0
1 2 1 2
1 2 1 9
2 2 2 5
2 2 2 7
Output
4.1250 -4.0000
0.3750 -12.0000
-5.2500 -12.0000
12.7500 -12.0000
Note

Warning: large Input/Output data, be careful with certain languages.