Usually, producing methamphetamine is somewhat laborous and boring. There are some TV series who assume that there is a new way to produce it, being way cheaper than actually is. Nonsense. The fact is there is a new drug around, called Krokodil. This drug is a variation of morphine, which gives 8 to 10 times more hallucination than “meth”, costing up to 10 times less than it.

Your friend Derp works in a “meth lab” and, while he was doing some tests, looking at the microscope, he found an interesting property: if he isolates the most far away pair of atoms in it, he will produce a substance as powerful (perhaps even more) as Krokodil is. This happens because one of the electron moves from one atom to the other.

But, most of the times, there are hundreds, maybe thousands of particles in each sample, each of them using several layers, making kinda hard to find out which is the longest distance. There’s an unusual fact about this distance calculus:

Each electron from these particles are kinda dumb; they are only able to move in horizontal and vertical axis. Also, since there are nanometrical layers, and distance is also considered for calculation between layers (which is the same), and a electron, in the layer L, with position (x, y), can only move to layers L + 1 and L − 1, if any of those exist, in the same relative position as in layer L.

Input

Each input contains several test cases. The first line of every test case contains a number N, which is the number of particles of that sample (2 ≤ N ≤ 100,000).

Then there are N lines, each of which contains 3 integers, li, xi, yi, which are the actual layer, the position corresponding corresponding to the X-axis, and the position corresponding to Y-axis (1 ≤ li, xi, yi ≤ 1,000,000,000).

Output

For each output you print one integer, DISTANCE, which corresponds to the value of the farthest distance between particles in the that sample.

Example

Input:
5
1 1 2
3 4 1
2 5 7
4 1 1
3 3 3
0

Output:
12