Nông dân John cần bạn giúp quyết định vị trí xây một hàng rào có dạng đường thẳng nhằm hạn chế sự di chuyển của đàn bò. Ông đã cân nhắc một số vị trí có thể đặt hàng rào và cần bạn xác định những vị trí nào sử dụng được. Một hàng rào được coi là sử dụng được nếu tất cả các con bò đều nằm về cùng một phía của hàng rào. Hàng rào không sử dụng được nếu có một con bò nằm trực tiếp trên đó. Nông dân John sẽ đưa ra một số truy vấn về các vị trí có thể đặt hàng rào; một truy vấn phải được trả lời YES nếu nó tương ứng với một vị trí hàng rào sử dụng được, và NO nếu không.

Ngoài ra, đôi khi Nông dân John có thể đưa thêm bò mới vào đàn. Khi một con bò mới gia nhập đàn, trong tất cả các truy vấn hàng rào kể từ thời điểm đó, hàng rào chỉ được coi là sử dụng được nếu con bò mới nằm cùng phía với toàn bộ đàn bò còn lại.

Dữ liệu vào

Tệp fencing.in:

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)) và \(Q\) (\(1 \leq Q \leq 100\,000\)), cách nhau bởi một dấu cách. Đây lần lượt là số bò ban đầu trong đàn và số truy vấn.

\(N\) dòng tiếp theo mô tả trạng thái ban đầu của đàn bò. Mỗi dòng chứa hai số nguyên \(x\) và \(y\), cách nhau bởi dấu cách, biểu thị vị trí của một con bò.

\(Q\) dòng còn lại chứa các truy vấn, mỗi truy vấn hoặc thêm một con bò mới vào đàn, hoặc kiểm tra xem một hàng rào có sử dụng được hay không. Dòng có dạng 1 x y cho biết một con bò mới được thêm vào đàn tại vị trí \((x, y)\). Dòng có dạng 2 A B C cho biết Nông dân John muốn kiểm tra hàng rào được mô tả bởi đường thẳng \(Ax + By = C\).

Mọi vị trí bò đều phân biệt trên toàn bộ bộ dữ liệu và thỏa mãn \(-10^9 \leq x, y \leq 10^9\). Ngoài ra, các truy vấn hàng rào thỏa mãn \(-10^9 \leq A, B \leq 10^9\) và \(-10^{18} \leq C \leq 10^{18}\). Không truy vấn hàng rào nào có \(A = B = 0\).

Dữ liệu ra

Tệp fencing.out:

Với mỗi truy vấn hàng rào, in YES nếu hàng rào sử dụng được. Nếu không, in NO.

Ví dụ

3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1

YES
NO
NO

Cảnh báo: Lượng dữ liệu vào/ra của bài này khá lớn. Người dùng C++ có thể cân nhắc sử dụng scanf hoặc dòng lệnh ios_base::sync_with_stdio(false) để đọc dữ liệu nhanh hơn. Người dùng Java nên tránh sử dụng java.util.Scanner. Không xả bộ đệm đầu ra (chẳng hạn bằng std::endl) sau mỗi truy vấn.

Nguồn

USACO 2015 February Contest, Gold — Fencing the Herd

Tác giả bài: Richard Peng, 2015.