Serge, bếp trưởng của nhà hàng nổi tiếng “Salt, Pepper & Garlic”, đang cố gắng giành ngôi sao Michelin đầu tiên. Anh được báo rằng một chuyên gia ẩn danh dự định đến nhà hàng vào tối nay.

Dù danh tính của chuyên gia chưa được tiết lộ, Serge tin chắc mình biết vị khách sẽ gọi món nào trong thực đơn và có sở thích về hương vị ra sao. Cụ thể, chuyên gia yêu cầu tỉ lệ muối, tiêu và bột tỏi trong món ăn phải cực kỳ chính xác.

Trên một chiếc kệ riêng trong bếp, Serge có các chai chứa hỗn hợp muối, tiêu và bột tỏi. Với mỗi chai, anh biết chính xác khối lượng từng thành phần tính bằng kilôgam. Serge có thể kết hợp hỗn hợp từ một số chai bất kỳ, hoặc dùng trực tiếp hỗn hợp từ một chai, để thu được tỉ lệ cần thiết cho một món ăn.

May mắn thay, lượng hỗn hợp cần thêm vào món ăn rất nhỏ, nên có thể coi lượng hỗn hợp trong các chai luôn đủ dùng. Tuy nhiên, các giá trị số mô tả tỉ lệ có thể khá lớn.

Serge muốn biết liệu có thể tạo ra hỗn hợp yêu thích của chuyên gia từ các chai hiện có hay không; nếu có, anh muốn biết số chai ít nhất cần sử dụng. Các chai trên kệ có thể thay đổi theo thời gian khi Serge nhận thêm chai mới hoặc cho đầu bếp khác mượn chai của mình. Anh muốn trả lời câu hỏi sau mỗi thay đổi như vậy.

Ví dụ, giả sử tỉ lệ yêu thích của chuyên gia là \(1:1:1\), và trên kệ có ba chai sau. Các khối lượng trong bảng được tính bằng kilôgam.

Bảng 1: Các chai trên kệ.

Chỉ cần lấy cùng một khối lượng hỗn hợp từ mỗi chai \(1\) và \(2\) rồi trộn lại là thu được tỉ lệ mong muốn. Nếu bỏ chai \(2\) khỏi kệ thì không còn cách tạo ra hỗn hợp đó.

Hãy viết chương trình giúp Serge giải quyết bài toán này.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên không âm \(S_f,P_f,G_f\), mô tả khối lượng muối, tiêu và bột tỏi trong hỗn hợp yêu thích của chuyên gia. Với mọi số thực \(\alpha>0\), hỗn hợp \((\alpha S_f,\alpha P_f,\alpha G_f)\) cũng là hỗn hợp yêu thích của chuyên gia.

Dòng thứ hai chứa số nguyên dương \(N\), là số thay đổi trên kệ. Ban đầu, kệ không có chai nào.

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một thay đổi:

• Nếu thêm một chai mới, dòng có dạng A Si Pi Gi, với chữ cái in hoa A và ba số nguyên không âm \(S_i,P_i,G_i\) mô tả khối lượng muối, tiêu và bột tỏi trong chai được thêm. Các chai được đánh số liên tiếp, duy nhất, bắt đầu từ \(1\): chai số \(i\) là chai được thêm vào lần thứ \(i\), tính riêng các thao tác thêm trong dữ liệu vào.
• Nếu bỏ một chai khỏi kệ, dòng có dạng R ri, với chữ cái in hoa R và số nguyên \(r_i\) là số hiệu chai bị bỏ. Các giá trị \(r_i\) trong những thao tác bỏ chai đôi một khác nhau và không vượt quá tổng số chai đã được thêm tính đến thời điểm đó.

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(j\) (\(1\le j\le N\)) chứa số \(x_j\), là số chai ít nhất cần dùng để pha được hỗn hợp có tỉ lệ muối, tiêu và bột tỏi yêu thích của chuyên gia từ các chai còn trên kệ sau \(j\) thay đổi đầu tiên. Nếu không thể pha được, in 0.

Ràng buộc

• \(S_f,P_f,G_f\ge0\) và \(0<S_f+P_f+G_f\le10^6\).
• \(1\le N\le100\,000\).
• Với mỗi chai được thêm, \(S_i,P_i,G_i\ge0\) và \(0<S_i+P_i+G_i\le10^6\).
• Mọi giá trị số trong đầu vào đều là số nguyên.
• Mỗi thao tác bỏ chai chỉ định một chai đã được thêm và chưa bị bỏ khỏi kệ.
• Giới hạn thời gian: \(2{,}0\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

1. \(13\) điểm: \(N\le50\) và \(0<S_i+P_i+G_i\le10^2\) với mọi chai được thêm.
2. \(17\) điểm: \(N\le500\) và \(0<S_i+P_i+G_i\le10^3\) với mọi chai được thêm.
3. \(30\) điểm: \(N\le5000\) và \(0<S_i+P_i+G_i\le10^4\) với mọi chai được thêm.
4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

1 2 3
6
A 5 6 7
A 3 10 17
R 1
A 15 18 21
A 5 10 15
R 3

0
2
0
2
1
1