Trong một hệ thống Object Tracking, mỗi đối tượng trong ảnh được biểu diễn bởi một bounding box là một hình chữ nhật có các cạnh song song với trục tọa độ.

Trong bài toán này, hệ tọa độ được quy ước theo hệ tọa độ ảnh: trục Ox hướng từ trái sang phải và trục Oy hướng từ trên xuống dưới.

Mỗi bounding box được biểu diễn bởi bốn tọa độ (a1, b1, a2, b2), trong đó:

• (a1, b1) là góc trên bên trái của bounding box.
• (a2, b2) là góc dưới bên phải của bounding box.

Do đó, luôn có a1 < a2 và b1 < b2.

Ở một khung hình trước, hệ thống đã xác định được bounding box của một đối tượng cần theo dõi. Ở khung hình hiện tại, hệ thống phát hiện được n bounding box có thể là đối tượng đó.

Để xác định bounding box nào tương ứng với đối tượng đang theo dõi, hệ thống sử dụng chỉ số Intersection over Union (IoU) giữa hai bounding box.

Với hai bounding box A và B, IoU được định nghĩa là:

$$ IoU(A,B)=\frac{S_{intersection}}{S_A+S_B-S_{intersection}} $$

Trong đó:

• S_A là diện tích của bounding box A.
• S_B là diện tích của bounding box B.
• S_intersection là diện tích phần giao nhau của hai bounding box.

Một bounding box được xem là phù hợp nếu:

$$ IoU(A,B) \ge T $$

Trong các bounding box phù hợp, hệ thống sẽ chọn bounding box có IoU lớn nhất.

Nếu có nhiều bounding box có cùng IoU lớn nhất, chọn bounding box có chỉ số nhỏ hơn.

Nếu không có bounding box nào đạt ngưỡng T, đối tượng được xem là không được phát hiện trong khung hình hiện tại.

Input

Dữ liệu vào gồm:

• Dòng đầu tiên chứa ba số nguyên n, T_num và T_den, trong đó ngưỡng IoU được biểu diễn bởi phân số:

$$ T=\frac{T_{num}}{T_{den}} $$

• Dòng thứ hai chứa bốn số nguyên x1, y1, x2, y2, là tọa độ hai đỉnh đối diện của bounding box cần theo dõi.
• n dòng tiếp theo, mỗi dòng chứa bốn số nguyên a1, b1, a2, b2, mô tả một bounding box được phát hiện trong khung hình hiện tại.

Output

In ra một số nguyên:

• Chỉ số của bounding box được lựa chọn, đánh số từ 1 đến n.
• In -1 nếu không có bounding box nào có IoU >= T.

Ràng buộc

• 1 ≤ n ≤ 2 * 10^5
• -20000 ≤ c ≤ 20000 với c là mọi tọa độ xuất hiện trong input.
• 1 ≤ T_num ≤ T_den ≤ 10^6

• T_num / T_den ≤ 1

• Với bounding box cần theo dõi:

$$ x_1 < x_2,\qquad y_1 < y_2. $$

• Với mỗi bounding box được phát hiện:

$$ a_1 < a_2,\qquad b_1 < b_2. $$

• Đảm bảo kết quả của các phép tính số học cần thiết nằm trong phạm vi của kiểu số nguyên 64-bit có dấu.

Ví dụ

Input

3 3 10
0 0 100 100
10 10 90 90
50 50 150 150
200 200 300 300

Output

1

Giải thích

Bounding box cần theo dõi là:

(0, 0) -------- (100, 0)
 |                 |
 |                 |
(0,100) -------- (100,100)

Xét từng bounding box:

• Bounding box 1: (10,10,90,90)

  Diện tích giao nhau là:

$$ 80\times80=6400 $$

Diện tích hợp là:

$$ 10000 $$

Do đó:

$$ IoU_1=\frac{6400}{10000}=0.64 $$

• Bounding box 2: (50,50,150,150)

  Diện tích giao nhau là:

$$ 50\times50=2500 $$

Diện tích hợp là:

$$ 10000+10000-2500=17500 $$

Do đó:

$$ IoU_2=\frac{2500}{17500}\approx0.143 $$

• Bounding box 3: (200,200,300,300)

  Hai bounding box không giao nhau nên:

$$ IoU_3=0 $$

Ngưỡng:

$$ T=\frac{3}{10}=0.3 $$

Chỉ bounding box 1 có IoU >= 0.3, vì vậy đáp án là 1.