{"raw_statement":[{"iden":"statement","content":"Geographic Information Systems (SIGs, in Portuguese) are becoming more and more important and useful in our lives. These systems are used in countries' national defense systems, for the analysis of public health data, in archaeology, and even in climate studies. In China, these systems are changing the way companies analyze and plan their business strategies. This development comes together with a bigger investment in R&D related to such technology. For this reason, the Chinese Association of Geographic Information Systems (ACSIG, in Portuguese) wants to attract students to work on projects related to this technology.\n\nACSIG knows that, in 2018, the brightest young minds in the planet will travel to Beijing to compete in the ACM ICPC World Finals. Given this event's reputation, ACSIG wants to recruit some of these contestants to be part of future projects. Now they are planning the problems they will use in their recruiting process. One of these problems is as follows.\n\nGiven the map of a certain geographic region and the subdivision of this region into sub-regions, we want to find a rectangle that contains in its interior all the points that define the subdivision. Now let's define the problem more formally. Consider that the map is the usual Cartesian plane, and the subdivision is given by a set of N straight lines. We want to find the rectangle with axis-aligned sides with the smallest area, and which contains all the vertices of the subdivision (the intersection points of the set of lines). Consider that the points in the boundary of the rectangle are also part of its interior.\n\nACSIG would like to test your knowledge, and asked you to solve this problem.\n\nThe first line contains an integer, N, the number of straight lines that define the subdivision. The i-th of the next N lines contains two real numbers, mi, and bi. These numbers represent the straight line mix - bi. It is guaranteed that at least one pair of these lines intersect.\n\nPrint a line containing four real numbers , where  are the coordinates of the bottom left vertex of the rectangle and (xr, yr) are the coordinates of the top right vertex. Absolute or relative errors of up to 10 - 4 are accepted.\n\n"},{"iden":"input","content":"The first line contains an integer, N, the number of straight lines that define the subdivision. The i-th of the next N lines contains two real numbers, mi, and bi. These numbers represent the straight line mix - bi. It is guaranteed that at least one pair of these lines intersect.  1 ≤ N ≤ 105  0 < |mi| ≤ 107  0 ≤ |bi| ≤ 107 "},{"iden":"output","content":"Print a line containing four real numbers , where  are the coordinates of the bottom left vertex of the rectangle and (xr, yr) are the coordinates of the top right vertex. Absolute or relative errors of up to 10 - 4 are accepted."},{"iden":"examples","content":"Input20.444444 -9.0000-0.125 -11.0000Output3.51220 10.56098 3.51220 10.56098Input5-0.4444 -9.0000-0.1250 -11.00000.5000 -7.0000-0.5000 -2.0000-0.2000 -5.0000Output-125.89928 1.72668 16.36661 64.94964Input63 53 93 153 19-2 3-2 -6Output0.40000 -9.40000 5.00000 1.60000"}],"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, let $ a, b \\in \\mathbb{Z} $ with $ 0 \\leq b < a \\leq 10^5 $, where:  \n- $ a $ is the length of the path (number of edges),  \n- $ b $ is the number of direction changes in the path.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^5 $  \n2. For each test case: $ 0 \\leq b < a \\leq 10^5 $  \n\n**Objective**  \nFor each test case, compute the number of paths of length $ a $ in an infinite binary tree with exactly $ b $ direction changes, modulo $ 10^9 + 7 $.  \n\nA direction change occurs when a move from parent to child switches from left to right or right to left. The first move has no prior direction, so it does not count as a change.  \n\nLet $ P(a, b) $ denote the number of such paths. Then:  \n$$\nP(a, b) = 2 \\cdot \\binom{a-1}{b} \\mod (10^9 + 7)\n$$","simple_statement":"Count the number of paths of length `a` in an infinite binary tree that change direction exactly `b` times. Print the answer modulo 10^9 + 7.","has_page_source":false}