An đang vẽ các đoạn thẳng trên mặt phẳng toạ độ. An muốn kiểm tra xem có bất kỳ hai đoạn thẳng nào cắt nhau (kể cả tại đầu mút) hay không. Hãy giúp An viết chương trình kiểm tra nhanh.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 10^5\)).
• \(N\) dòng sau, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) (\(-10^6 \le x_i, y_i \le 10^6\)) mô tả một đoạn thẳng từ \((x_1,y_1)\) đến \((x_2,y_2)\).
• Không có hai đoạn nào trùng nhau hoàn toàn.

Định dạng đầu ra

• In ra \(1\) nếu tồn tại ít nhất một cặp đoạn thẳng giao nhau, ngược lại in ra \(0\).

Ví dụ

Input:

4
1 1 3 3
4 1 2 3
1 2 5 1
4 4 6 4

Output:

1

Giải thích: Đoạn thứ nhất \((1,1)-(3,3)\) và đoạn thứ hai \((4,1)-(2,3)\) giao nhau tại \((2.5, 2.5)\).

Ràng buộc

• Subtask 1 (20%): \(N \le 100\), toạ độ nguyên dương nhỏ.
• Subtask 2 (30%): \(N \le 10^3\).
• Subtask 3 (50%): \(N \le 10^5\).