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 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 .
For each test case, print q lines, each line should contain the coordinates of the given node U rounded to 4 decimal places.
Warning: large Input/Output data, be careful with certain languages.
## 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.
[samples]
## Note
Warning: large Input/Output data, be careful with certain languages.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N \in \mathbb{Z} $ be the number of nodes in a rooted full binary tree.
- Let $ q \in \mathbb{Z} $ be the number of queries.
- The tree has nodes labeled $ 1 $ to $ N $, with node $ 1 $ as the root.
- Each non-leaf node has exactly two children: left child $ 2i $, right child $ 2i+1 $.
- Node radius is $ r $ (constant, but unspecified in input).
- Root node (node 1) is centered at $ (0, 0) $.
- Children of a node at depth $ d $ are placed at depth $ d+1 $, horizontally separated by $ 2r $, vertically by $ 2r $.
**Constraints**
1. $ 1 \leq T \leq 64 $
2. $ 1 \leq N, q \leq 10^5 $
3. For each query, $ 1 \leq U \leq N $
**Objective**
For each query $ U $, compute and output the coordinates $ (x_U, y_U) $ of the center of node $ U $, rounded to 4 decimal places, assuming:
- Vertical spacing between levels: $ 2r $
- Horizontal spacing between siblings: $ 2r $
- Root at $ (0, 0) $
- Left child offset: $ -r \cdot 2^{\text{depth}} $, right child offset: $ +r \cdot 2^{\text{depth}} $ from parent’s horizontal position.
Let $ d = \lfloor \log_2 U \rfloor $ be the depth of node $ U $.
Let $ p = U - 2^d $ be the 0-based index at depth $ d $.
Then:
$$
x_U = r \cdot (2p + 1 - 2^d) \\
y_U = -r \cdot 2d
$$