Segments intersection - 2

n segments are given on the 2-D plane. Are they intersect? (the set of segments intersect if there exist two of them that have at least one common point)

Input

Each line contains the integer coordinates of segment endpoints (x_1, y_1) - (x_2, y_2). It is known that n ≤ 6*10^5 and -2000 ≤ x_1, y_1, x_2, y_2 ≤ 2000.

Output

Print "intersect" if segments intersect or "NOT intersect" otherwise.

Examples