B. Смесь
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Серж, шеф-повар знаменитого ресторана «Соль, Перец & Чеснок» пытается получить свою первую звезду Мишлен. Его уведомили, что сегодня вечером его ресторан посетит секретный эксперт.

Несмотря на то, что имя эксперта не разглашено, Серж знает его вкусовые предпочтения, а также, какое блюдо он закажет. Кроме прочего, он знает, что эксперту нравится исключительно точная пропорция соли, перца и чеснока в его блюде.

Серж хранит у себя несколько бутылок со смесями соли, перца и чесночного порошка на особой полке на кухне. Он знает точное количество каждого ингредиента в каждой бутылке в килограммах. Серж может использовать любое количество бутылок смесей (или ровно одну из них напрямую), чтобы получить смесь нужных пропорций для своего блюда.

К счастью, количество смеси, которой нужно добавить к блюду, настолько мало, что количества смеси в каждой бутылке всегда будет достаточно. Однако, числа, описывающие пропорции, могут быть весьма большими.

Серж хочет узнать, возможно ли получить любимую смесь эксперта из доступных бутылок, и если да — чему равняется наименьшее количество бутылок, нужных для этого.

Более того, множество бутылок на полке может меняться со временем, так как Серж получает новые бутылки и одалживает свои другим поварам. Поэтому он хотел бы узнать ответ на свой вопрос после каждого такого изменения.

Например, допустим, что любимая смесь эксперта является $$$1:1:1$$$ и на полке находятся три бутылки со смесями:

$$$$$$ \begin{array}{cccc} \hline \text{Mixture} & \text{Соль} & \text{Перец } & \text{Чесночный порошок} \\ \hline 1 & 10 & 20 & 30 \\ 2 & 300 & 200 & 100 \\ 3 & 12 & 15 & 27 \\ \hline \end{array} $$$$$$ Количество ингредиента в бутылке, кг

Чтобы получить нужную смесь, достаточно использовать одинаковое количество смесей из бутылок 1 и 2. Если бутылка 2 отсутствует, то больше нет возможности получить нужную смесь.

Напишите программу, которая поможет Сержу решить эту задачу!

Входные данные

Первая строка ввода содержит три неотрицательных целых числа $$$S_f$$$, $$$P_f$$$ и $$$G_f$$$ ($$$0 \leq S_f, P_f, G_f$$$; $$$0 < S_f+P_f+G_f \leq 10^6$$$), которые описывают количество соли, перца и чесночного порошка в любимой смеси эксперта. Для любого вещественного $$$\alpha>0$$$, $$$(\alpha{S_f}, \alpha{P_f}, \alpha{G_f})$$$ тоже является любимой смесью эксперта.

Во второй строке дано целое положительное число $$$N$$$ (количество изменений на полке, $$$N \leq 100\,000$$$). Изначально полка пуста.

Каждая из следующих $$$N$$$ строк описывает одно изменение на полке:

  • Если добавляется новая бутылка, строка содержит заглавную букву $$$A$$$, за которой следуют три неотрицательных целых числа $$$S_i$$$, $$$P_i$$$ и $$$G_i$$$ ($$$0 \leq S_i, P_i, G_i$$$; $$$0 < S_i+P_i+G_i \leq 10^6$$$) описывающих количество соли, перца и чесночного порошка в новой бутылке. Добавленные бутылки нумеруются последовательными целыми числами, начиная с $$$1$$$, то есть, $$$i$$$-я бутылка соответствует $$$i$$$-й добавленной бутылке во вводе.
  • Если конкретная бутылка убирается с полки, строка содержит заглавную букву $$$R$$$, за которой следует целое число, номер этой бутылки, $$$r_i$$$. Все значения $$$r_i$$$ среди убираний различны, и $$$r_i$$$ никогда не превышает общее количество в данный момент добавленных бутылок.
Выходные данные

Выведите $$$N$$$ строк. В $$$j$$$-й строке ($$$1 \leq j \leq N$$$) выведите число $$$x_j$$$, наименьшее количество бутылок, которое нужно использовать для приготовления любимой смеси эксперта с нужной пропорцией соли, перца и чесночного порошка, при условии, что на полке доступны только бутылки после первых $$$j$$$ изменений. Если же такую смесь нельзя приготовить, просто выведите $$$0$$$.

Система оценки

Подзадачи:

  1. (13 баллов) $$$N \leq 50$$$, $$$0 < S_i+P_i+G_i \leq 10^2$$$
  2. (17 баллов) $$$N \leq 500$$$, $$$0 < S_i+P_i+G_i \leq 10^3$$$
  3. (30 баллов) $$$N \leq 5000$$$, $$$0 < S_i+P_i+G_i \leq 10^4$$$
  4. (40 баллов) Без дополнительных ограничений.
Пример
Входные данные
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
Примечание

Обратите внимание, что в данном примере бутылки $$$1$$$ и $$$3$$$ содержат одинаковое количество соли, перца и чесночного порошка.