Thị trấn Điên (Crazy Town)

Trên mặt phẳng tọa độ có $n$ đường thẳng vô hạn, đường thẳng thứ $i$ được cho bởi phương trình $a_{i}x+b_{i}y+c_i=0$ (với $a_i$ và $b_i$ không đồng thời bằng $0$). Các đường thẳng này chia mặt phẳng thành nhiều miền liên thông (có thể có miền vô hạn). Mỗi miền như vậy được gọi là một khối.

Nhà của bạn nằm trong một khối nào đó, và trường đại học của bạn cũng nằm trong một khối. Trong một bước, bạn có thể di chuyển từ khối hiện tại sang một khối khác nếu hai khối có chung một đoạn biên giới có độ dài khác $0$. Nếu hai khối chỉ gặp nhau tại một điểm giao (không có đoạn biên chung dài hơn $0$) thì không được phép di chuyển trực tiếp giữa chúng.

Hãy xác định số bước ít nhất cần thực hiện để đi từ khối chứa nhà tới khối chứa trường đại học. Bảo đảm rằng cả nhà và trường đại học đều không nằm trên bất kỳ đường thẳng nào.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $x_1,y_1$ — tọa độ của nhà.
• Dòng thứ hai chứa hai số nguyên $x_2,y_2$ — tọa độ của trường đại học.
• Dòng thứ ba chứa một số nguyên $n$ — số đường thẳng.
• $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i,b_i,c_i$ — các hệ số của đường thẳng thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất là số bước ít nhất cần thực hiện.

Ràng buộc

• $-{10}^6\le x_1,y_1,x_2,y_2\le {10}^6$
• $1\le n\le 300$
• $-{10}^6\le a_i,b_i,c_i\le {10}^6$ và $|a_i|+|b_i|>0$
• Không có hai đường thẳng nào trùng nhau.
• Cả nhà và trường đại học đều không nằm trên đường thẳng nào.

Ví dụ