{"raw_statement":[{"iden":"statement","content":"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:\n\nGiven 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).\n\nThe drawn tree should satisfy the following conditions:  \n\nThe first line of input contains an integer T (1 ≤ T ≤ 64), the number of test cases.\n\nThe 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 . \n\nFor each test case, print q lines, each line should contain the coordinates of the given node U rounded to 4 decimal places.\n\nWarning: large Input/Output data, be careful with certain languages.\n\n"},{"iden":"input","content":"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)"},{"iden":"output","content":"For each test case, print q lines, each line should contain the coordinates of the given node U rounded to 4 decimal places."},{"iden":"examples","content":"Input19 42 4 52 6 72 1 2002 9 80001 2 1 21 2 1 92 2 2 52 2 2 7Output4.1250 -4.00000.3750 -12.0000-5.2500 -12.000012.7500 -12.0000"},{"iden":"note","content":"Warning: large Input/Output data, be careful with certain languages."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of nodes in a rooted full binary tree.  \n- Let $ q \\in \\mathbb{Z} $ be the number of queries.  \n- The tree has nodes labeled $ 1 $ to $ N $, with node $ 1 $ as the root.  \n- Each non-leaf node has exactly two children: left child $ 2i $, right child $ 2i+1 $.  \n- Node radius is $ r $ (constant, but unspecified in input).  \n- Root node (node 1) is centered at $ (0, 0) $.  \n- Children of a node at depth $ d $ are placed at depth $ d+1 $, horizontally separated by $ 2r $, vertically by $ 2r $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 64 $  \n2. $ 1 \\leq N, q \\leq 10^5 $  \n3. For each query, $ 1 \\leq U \\leq N $\n\n**Objective**  \nFor each query $ U $, compute and output the coordinates $ (x_U, y_U) $ of the center of node $ U $, rounded to 4 decimal places, assuming:  \n- Vertical spacing between levels: $ 2r $  \n- Horizontal spacing between siblings: $ 2r $  \n- Root at $ (0, 0) $  \n- Left child offset: $ -r \\cdot 2^{\\text{depth}} $, right child offset: $ +r \\cdot 2^{\\text{depth}} $ from parent’s horizontal position.  \n\nLet $ d = \\lfloor \\log_2 U \\rfloor $ be the depth of node $ U $.  \nLet $ p = U - 2^d $ be the 0-based index at depth $ d $.  \nThen:  \n$$\nx_U = r \\cdot (2p + 1 - 2^d) \\\\\ny_U = -r \\cdot 2d\n$$","simple_statement":"Given a full binary tree with N nodes, root at (0, 0), and each node as a circle of radius r. For q queries, find and print the coordinates of each queried node rounded to 4 decimal places.","has_page_source":false}