Серж, шеф-повар знаменитого ресторана «Соль, Перец & Чеснок» пытается получить свою первую звезду Мишлен. Его уведомили, что сегодня вечером его ресторан посетит секретный эксперт.
Несмотря на то, что имя эксперта не разглашено, Серж знает его вкусовые предпочтения, а также, какое блюдо он закажет. Кроме прочего, он знает, что эксперту нравится исключительно точная пропорция соли, перца и чеснока в его блюде.
Серж хранит у себя несколько бутылок со смесями соли, перца и чесночного порошка на особой полке на кухне. Он знает точное количество каждого ингредиента в каждой бутылке в килограммах. Серж может использовать любое количество бутылок смесей (или ровно одну из них напрямую), чтобы получить смесь нужных пропорций для своего блюда.
К счастью, количество смеси, которой нужно добавить к блюду, настолько мало, что количества смеси в каждой бутылке всегда будет достаточно. Однако, числа, описывающие пропорции, могут быть весьма большими.
Серж хочет узнать, возможно ли получить любимую смесь эксперта из доступных бутылок, и если да — чему равняется наименьшее количество бутылок, нужных для этого.
Более того, множество бутылок на полке может меняться со временем, так как Серж получает новые бутылки и одалживает свои другим поварам. Поэтому он хотел бы узнать ответ на свой вопрос после каждого такого изменения.
Например, допустим, что любимая смесь эксперта является \(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 отсутствует, то больше нет возможности получить нужную смесь.
Напишите программу, которая поможет Сержу решить эту задачу!
Выходные данные
Выведите \(N\) строк. В \(j\)-й строке (\(1 \leq j \leq N\)) выведите число \(x_j\), наименьшее количество бутылок, которое нужно использовать для приготовления любимой смеси эксперта с нужной пропорцией соли, перца и чесночного порошка, при условии, что на полке доступны только бутылки после первых \(j\) изменений. Если же такую смесь нельзя приготовить, просто выведите \(0\).