Những con bò của Farmer John đã gây quá nhiều rắc rối quanh trang trại, vì vậy FJ muốn giám sát chúng kỹ hơn. Bằng cách lắp đặt \(N\) hàng rào phản chiếu (\(1 \le N \le 200\)) tại nhiều vị trí trong trang trại, ông hy vọng có thể nhìn từ ngôi nhà ở vị trí \((0,0)\) đến chuồng ở vị trí \((a,b)\).

Trên bản đồ hai chiều của trang trại FJ, hàng rào \(i\) là một đoạn thẳng ngắn có tâm tại vị trí nguyên \((x_i, y_i)\) và nghiêng \(45\) độ (theo hình dạng / hoặc \). Chẳng hạn, một hàng rào có hướng / tại vị trí \((3,5)\) có thể được mô tả là đoạn thẳng từ \((2.9,4.9)\) đến \((3.1,5.1)\). Mỗi hàng rào (và cả vị trí của chuồng) nằm ở một vị trí riêng biệt có tọa độ nguyên trong khoảng từ \(-1\,000\,000\) đến \(1\,000\,000\). Không có hàng rào nào nằm tại \((0,0)\) hoặc \((a,b)\).

FJ dự định ngồi tại nhà ở vị trí \((0,0)\) và nhìn thẳng sang phải (theo hướng \(+x\)). Với ánh nhìn phản xạ qua một số hàng rào phản chiếu trong trang trại, ông hy vọng có thể nhìn thấy điểm \((a,b)\). Không may, FJ cho rằng ông đã đặt sai hướng của một hàng rào (chẳng hạn, \ thay vì /). Hãy in chỉ số của hàng rào đầu tiên trong danh sách của FJ sao cho khi đảo hướng của nó (giữa / và \), FJ có thể nhìn thấy điểm \((a,b)\).

Nếu FJ đã có thể nhìn thấy điểm \((a,b)\) mà không cần đảo hướng hàng rào nào, hãy in \(0\). Nếu ông vẫn không thể nhìn thấy \((a,b)\) ngay cả sau khi đảo hướng nhiều nhất một hàng rào, hãy in \(-1\).

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(a\) và \(b\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) mô tả hàng rào \(i\) và có dạng x_i y_i / hoặc x_i y_i \, trong đó \((x_i, y_i)\) là vị trí tâm của hàng rào, còn \ hoặc / cho biết hướng của nó.

Dữ liệu ra

In ra chỉ số của hàng rào đầu tiên mà việc đảo hướng hàng rào đó cho phép FJ nhìn thấy điểm \((a,b)\). Nếu FJ đã có thể nhìn thấy điểm \((a,b)\), hãy in \(0\); nếu không có cách nào để ông nhìn thấy \((a,b)\) ngay cả sau khi đảo hướng nhiều nhất một hàng rào, hãy in \(-1\).

Ví dụ

5 6 2
3 0 /
0 2 /
1 2 /
3 2 \
1 3 \

4

3 .\.....
2 //.\..B
1 .......
0 H../...
  0123456

3 .\.....
2 //./--B
1 ...|...
0 H--/...
  0123456

Nguồn

USACO 2013 January Contest, Bronze — Problem 1: Mirrors

Tác giả đề: Brian Dean và Travis Hance, 2013.