Gương Phản Chiếu

Cho $N$ gương phẳng đặt tại các vị trí nguyên trên mặt phẳng tọa độ. Mỗi gương nằm ở vị trí $(x_i,y_i)$ và có hướng là "/" hoặc "\" (nghiêng 45 độ). Một tia sáng xuất phát từ điểm $(0,0)$ theo hướng sang phải (hướng Đông). Khi gặp gương, tia sáng phản chiếu theo quy tắc:

• Gương "/": Tia từ Đông → Bắc, từ Tây → Nam, từ Bắc → Đông, từ Nam → Tây
• Gương "\": Tia từ Đông → Nam, từ Tây → Bắc, từ Bắc → Tây, từ Nam → Đông

Mục tiêu là tia sáng cần đến điểm $(a,b)$. Biết rằng chính xác một gương có thể đang đặt sai hướng (hoặc tất cả đều đúng). Hãy tìm chỉ số của gương cần đổi hướng (từ "/" thành "\" hoặc ngược lại) để tia sáng đến được $(a,b)$.

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $a$, $b$
• Dòng $2$ đến $N+1$: Mỗi dòng gồm $x_i$, $y_i$ và ký tự "/" hoặc "\" mô tả gương thứ $i$

Dữ liệu ra

• In ra chỉ số (1-indexed) của gương cần đổi hướng
• In ra $0$ nếu tia sáng đã đến đích mà không cần thay đổi gương nào
• In ra $-1$ nếu không thể đạt được dù thay đổi bất kỳ một gương nào

Ràng buộc

• $1\le N\le 200$
• $-{10}^6\le x_i,y_i,a,b\le {10}^6$
• Không có gương nào tại $(0,0)$ hoặc $(a,b)$

Ví dụ

Ghi chú

Tia sáng đi theo đường thẳng giữa các gương. Nếu tia sáng ra khỏi giới hạn tọa độ hoặc đi vào vòng lặp vô hạn mà không đến đích thì coi là thất bại.