VORAIN - Chuyện Mưa

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Mưa từng con phố có nhớ bóng dáng em đi cuối thu, đông về hè sang vội vàng quá

Mưa từng đêm vắng, mưa ơi cứ rơi phố xa, anh đi tìm yêu đương chiều qua

Ai vội vàng đi ngang lòng người mang theo bao yêu đương thoáng qua như là cơn mưa rào

Chuyện mưa

Có bao giờ bạn tự hỏi, những giọt mưa kia rồi sẽ về đâu? Chúng ta hãy cùng nhau trả lời câu hỏi này nhé.

Hình dung thế giới như một mặt phẳng Oxy, tại mỗi thời điểm có 1 trong 3 loại sự kiện xảy ra:

  • Một đoạn thẳng nối điểm (x 1 , y 1 ) và (x 2 , y 2 ) xuất hiện trên mặt phẳng
  • Một đoạn thẳng được thêm vào trước đó biến mất
  • Một giọt mưa xuất hiện tại điểm (x, y) và rơi xuống. Giọt mưa rơi theo phương thẳng đứng từ điểm (x, y) về điểm (x, 0).

Nhiệm vụ của bạn là xác định xem, giọt mưa rơi xuống mặt đất, hay rơi vào một đoạn thẳng.

Input

Dòng đầu chứa số nguyên dương Q (Q ≤ 10 5 ), cho biết số sự kiện xảy ra.

Q dòng tiếp theo, mỗi dòng cho biết 1 sự kiện xảy ra. Mỗi dòng có 1 trong 3 dạng:

  • 1 x 1 y 1 x 2 y 2 : Một đoạn thẳng xuất hiện, nối điểm (x 1 , y 1 ) và (x 2 , y 2 ). (1 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10 6 , x 1 ≠ x 2 ). Không có 2 đoạn thẳng nào có điểm chung.
  • 2 i: Đoạn thẳng xuất hiện thứ i (tính cả những đoạn đã bị xóa) biến mất (1 ≤ i ≤ số đoạn thẳng đã xuất hiện). Nếu đoạn thẳng thứ i đã biến mất trước đó, sự kiện này không có bất kỳ ảnh hưởng gì.
  • 3 x y: Một giọt mưa xuất hiện ở tọa độ (x, y). (1 ≤ x, y ≤ 10 6 ). Chú ý rằng giọt mưa có thể nằm trên đoạn thẳng.

Output

Với mỗi sự kiện loại 3, in ra 0 nếu giọt mưa sẽ rơi xuống đất mà không chạm vào bất kỳ đoạn thẳng nào. Ngược lại, in ra thứ tự của đoạn thẳng đầu tiên mà giọt mưa chạm vào.

Giới hạn

  • Trong 30% test đầu tiên, Q ≤ 10 3 .
  • Trong 30% test tiếp theo, trong các sự kiện loại 1, 1 ≤ x 1 , y 1 , x 2 , y 2 < 10 6 . Trong các sự kiện loại 3, y = 10 6 .
  • Mọi giá trị x, y đều là số nguyên.
  • Thời gian chạy cho tất cả các test: 3 giây. Riêng thời gian chạy cho test đề bài là 0.5s.

Example

Input:
12
1 1 2 3 2
3 1 1
3 2 1
3 3 1
3 1 2
3 2 2
3 3 2
3 1 3
3 2 3
3 3 3
2 1
3 2 2

Output:
0
0
0
1
1
1
1
1
1
0

  • Người up: voj
  • Nguồn bài: VO 2015