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 (Pinitial). 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 Pfinal = Pinitial + |{i|X < xi and Y < yi}|, where (X;Y) describes the current ball coordinates, (xi;yi) 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 Pfinal. 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
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 ≤ 105) - the number of list entries.
In every following n lines there are four integer numbers id (0 ≤ id ≤ 109), Pinitial (1 ≤ Pinitial ≤ 109), x (0 ≤ x ≤ 109), y (0 ≤ y ≤ 109) - 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.
## Input
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 ≤ 105) - the number of list entries.In every following n lines there are four integer numbers id (0 ≤ id ≤ 109), Pinitial (1 ≤ Pinitial ≤ 109), x (0 ≤ x ≤ 109), y (0 ≤ y ≤ 109) - 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.
## Output
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.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $, and define the grid size $ N = 2n + 1 $.
Let $ G = (g_{i,j})_{i,j=1}^{N} $ be an $ N \times N $ grid, where each cell $ g_{i,j} \in \{ \text{'b'}, \text{'w'} \} $.
The center of the grid is at position $ (c, c) $ where $ c = n + 1 $.
**Constraints**
$ 1 \leq n \leq 100 $, $ T \leq 10 $
**Objective**
For each test case $ n $, construct grid $ G $ such that:
- Initially, only the center cell $ g_{c,c} = \text{'b'} $.
- In step $ k \geq 1 $, color black all cells at Chebyshev distance exactly $ k $ from the center, **but only if** they are not adjacent (by edge) to any previously colored black cell.
- The set of black cells at step $ k $ forms a minimal diamond (i.e., Chebyshev circle) of radius $ k $, and must not share an edge with any prior black cell — only possibly share a corner.
- All other cells remain white.
**Pattern Rule**
A cell $ (i,j) $ is black **if and only if** the Chebyshev distance from the center satisfies:
$$
\max(|i - c|, |j - c|) \equiv 0 \pmod{2}
$$
Equivalently, black cells are those where the Chebyshev distance from center is even.
**Output**
For each test case, output the $ N \times N $ grid with 'b' for black and 'w' for white.