Trước đây, Farmer John từng cân nhắc một số ý tưởng sáng tạo cho những môn thể thao mới dành cho bò, trong đó có môn vượt chướng ngại vật dành cho bò, nơi các đàn bò đua quanh một đường chạy và nhảy qua các rào cản. Những nỗ lực trước đây của ông nhằm thu hút sự quan tâm tới môn thể thao này đã cho kết quả không đồng nhất, nên ông hy vọng xây dựng một đường đua vượt chướng ngại vật dành cho bò còn lớn hơn trên trang trại để quảng bá thêm cho môn thể thao này.

Đường đua mới của Farmer John được lên kế hoạch cẩn thận quanh \(N\) rào cản, được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 10^5\)), mỗi rào cản được mô tả là một đoạn thẳng trên bản đồ 2D của đường đua. Các đoạn thẳng này không được giao nhau dưới bất kỳ hình thức nào, kể cả tại các đầu mút.

Thật không may, Farmer John đã không chú ý khi vẽ bản đồ đường đua và nhận ra rằng có các đoạn thẳng giao nhau. Tuy nhiên, ông cũng nhận thấy rằng chỉ cần bỏ đi đúng một đoạn thẳng, bản đồ sẽ trở lại trạng thái dự định là không có đoạn thẳng nào giao nhau (kể cả tại đầu mút).

Hãy xác định một đoạn thẳng mà Farmer John có thể xóa khỏi kế hoạch để khôi phục tính chất không có đoạn thẳng nào giao nhau. Nếu có thể xóa nhiều đoạn thẳng theo cách này, hãy in ra chỉ số của đoạn xuất hiện sớm nhất trong dữ liệu vào.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng còn lại mô tả một đoạn thẳng bằng bốn số nguyên \(x_1\) \(y_1\) \(x_2\) \(y_2\), tất cả đều là số nguyên không âm không vượt quá \(10^9\). Đoạn thẳng có hai đầu mút là \((x_1, y_1)\) và \((x_2, y_2)\). Tất cả các đầu mút đều phân biệt với nhau.

Dữ liệu ra

In ra chỉ số nhỏ nhất trong dữ liệu vào của một đoạn thẳng sao cho việc xóa đoạn đó khiến các đoạn thẳng còn lại không giao nhau.

Ví dụ

4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3

2

Lưu ý: Bạn nên cẩn thận với tràn số nguyên trong bài này do độ lớn của các số được dùng làm tọa độ đầu mút đoạn thẳng.

Nguồn

USACO 2019 US Open Contest, Silver — Cow Steeplechase II

Tác giả: Brian Dean.