401575: GYM100495 G Spells once again!

Magicians can be really annoying at University. I am not sure if you have seen those types of people, but if you saw them, you would know that their favourite hobby is to throw their cast magic balls to the wall. The balls even gain some power from other magic balls!

If you asked why it is a problem, the answer is that it bothers both students (because their can't sleep during lectures as the balls have a lot of power) and a lady who needs to clear the wall every time.

Some non-magicians who are tired just because of the balls of power want to take some revenge. Of course, it is dangerous to approach all magicians, who throw balls, at once, so they want to sort things out with the magician who owns the widest range of power.

Let's call the power of the ball P.

As all magicians are unique, they can throw balls of different power (P_initial). The number of previously thrown balls which are simultaneously located to the right and above the thrown ball is added to its power. So it can become quite powerful after that!

More formally, the final power of the ball P_final = P_initial + |{i|X < x_i and Y < y_i}|, where (X;Y) describes the current ball coordinates, (x_i;y_i) describes the i-th (previously thrown) ball coordinates, for each possible i, and |S| shows the size of the set S.

It is said that the magician currently owns the range of power between 1 and P_final. All magicians who threw balls before can't own any power in this range (they lose some part of their range if this is the case).

For example, if the first magician owns a range (5; 7) and the second magician throws a ball of power P = 6, the first magician owns a range (6; 7) (the width is equal to 1), while the second one (1; 6) (the width is equal to 5).

You are given a list (which has size n) with the following information

• the id of the magician;
• the place where he casts and throws his ball of power.

You are supposed to answer which magician (to print its id) owns the widest range of power and to print the width of this range after each such throw. If there are several possibilities, choose the magician with the smallest id.

Note: it is guaranteed that each magician throws at most one ball.

The first line contains the number of test cases T (1 ≤ T ≤ 5).

In the first line of every test case there is an integer n (1 ≤ n ≤ 10⁵) - the number of list entries.

In every following n lines there are four integer numbers id (0 ≤ id ≤ 10⁹), P_initial (1 ≤ P_initial ≤ 10⁹), x (0 ≤ x ≤ 10⁹), y (0 ≤ y ≤ 10⁹) - the id of the magician, the initial power of the thrown ball and the coordinates of his ball in the wall.

Note: It is guaranteed that it will be at most 1000 distinct values of x and at most 1000 distinct values of y.

For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1).

Then output lines “id width” - id of the magician owning the widest range and width - the maximum width of any owned range after each given throw.

2
2
1 1 1 1
0 1 0 1
2
1 2 1 1
0 1 0 1

Case #1:
1 0
0 0
Case #2:
1 1
1 1