Usually, producing methanphetamine 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 particules 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 particules are kinda dumb; they are only able to move in

horizontal and vertica 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 particules of that sample (2 ≤ N ≤ 100, 000).

After there are N lines to follow. Each of them 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, DIST AN CE, which corresponds to the value

of the farthest distance between particules in the that sample.

Example

Input:
5
112
341
257
411
333
Output:
12