Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3243
Diamonds

Time Limit: 1 Second      Memory Limit: 32768 KB      Special Judge

Task

Formally, a diamond with radius r, centered at (x,y), is the set of points whose manhattan distance to (x,y) is no more than r. Given n points p1, p2, ..., pn on the plane, your task is to draw n diamonds, so that pi lies in the interior or on the border of the i-th diamond, and each diamond, except the first one, encloses the previous one.

Input

The first line contains a single integer T (T <= 50), the number of test cases. Each case begins with a single integers n (1 <= n <= 200), the number of diamonds. Each of the following n lines contains three integers x, y, r (1 <= x, y <= 100000, 1 <= r <= 10000), indicating that the i-th diamond should cover (x,y), with radius r.

Output

For each test case, print the case number in the first line. Each of the following n lines contains two integers x, y, indicating the i-th diamond is centered at (x,y). If there is more than one solution, any one will do. Every test case is solvable.

Sample Input

2
1
1 1 1
2
1 1 1
4 1 2

Sample Output

Case 1:
1 1
Case 2:
1 1
2 1

Author: Liu, Rujia
Source: The 2009 ACM-ICPC Asia Ningbo Regional Online Contest
Submit    Status