Note: All numbers for tests in this problem are 6 decimals of precision.

Rory is on a savanna expedition, deep in the outback of South Africa. He is here for one purpose: to hunt for rhinoceroses for their prized horns. Since this is highly illegal, he'd better make it worth his while by hunting for the most valuable horn.

Rory has spotted several rhinos, but he can only take one shot.

Each rhino's horn is shaped like an isosceles triangle: two of its sides are the same length, and the third side (the base) is strictly shorter than the other two. The point where the two long sides meet is the tip of the horn.

A horn's value is simply how far its tip sticks out from its base, or the straight-line distance from the tip straight down to the base, measured at a right angle to it. The farther the tip sticks out, the more valuable the horn.

Help Rory find which rhino has the most valuable horn.

Input

The first line consists of a single integer ~n~ ~(1 \leq n \leq 10^{5})~, the number of rhinos Rory can choose from.

The next ~n~ lines consists of ~6~ floating-point values, ~x_1~ ~y_1~ ~x_2~ ~y_2~ ~x_3~ ~y_3~, the coordinates of the points of the triangle that makes up the rhino's horn. All coordinate values are bound by ~(-10^{4} \leq x_i, y_i \leq 10^{4})~.

Output

Output a single integer: the 1-indexed position of the rhino Rory should hunt, corresponding to the order the rhinos were listed in the input.

It is guaranteed that only one horn will be the longest.

Example

Input 1

2
5.0 4.0 5.0 10.0 12.0 7.0
5.0 4.0 3.0 8.0 12.0 10.0

Output 1

2

Input 2

3
4.0 0.0 10.0 10.0 0.0 4.0
10.0 9.0 6.0 -1.0 2.0 9.0
10.0 12.0 10.0 14.0 8.0 13.0

Output 2

1