Graph Outline

5-year-old Rebecca loves to draw. She has recently shifted to a new house. She notices a bunch of cardboard boxes kept in a row. Shes bored and starts drawing the boxes on paper as rectangles on a common baseline. After drawing them, she wants to find the top outline of the rectangles shes drawn. She needs your help! Shes 5 after all. A precocious child to be sure, but a child nonetheless. But she doesnt want to show you the drawing until its complete. So she gives you the information about the drawing as a series of triples (x,y,z) x is the left end of a rectangle, y is the right end of the rectangle, and z is the height. She wants the points of the outline output as (p,h) pairs where p starts from the leftmost end and moves towards the right. Here h is the height of the outline at position p on the base line. Only the points where there is a drop or rise in the height of the outline are to be given. Your task is simple. Provide the outline as a series of (p,h) points when provided with a series of (x,y,z) points. Constraints 1. 1 <= t <= 1000 2. 1 <= n < 20 3. 0 <= x < y <= 1000 4. 1 <= z <= 1000 Input Format The first Line contains t which gives the number of test cases. It is followed by t-test cases where each test case contains two lines of input: A line containing an integer n which gives the number of boxes in one line The second line with n space-separated triplets (x,y,z) Output Format: For each test case, the output contains space-separated pairs (p,h) that give the top outline of the box. Sample Input 1 4 (1,5,10) (4,6,8) (10,15,10) (11,12,8) Sample Output (1,10) (5,8) (6,0) (10,10) (15,0) Explanation alt text As shown in the figure, the first point where the outline raises/drops is at 1 where the outline rises from 0 to 10. Then at 5, the outline drops from 10 to 8. Similarly, at 6, outline drops from 8 to 0; at 10, the outline rises from 0 to 10; at 15, the outline drops from 10 to 0. Therefore, these points can be added in the output to represent the complete outline of the boxes (you have to print the new points where the height changes example: form 6-10 height = 0 and at x = 10 height changes from 0 to 10 thats why we print (10,10) new point ).