혼합물

Serge는 유명한 레스토랑 "Salt, Pepper & Garlic"의 셰프이다. 그는 미슐랭 별을 처음으로 받으려고 한다. 오늘 저녁 비밀 평론가가 식당을 방문할 예정이라는 정보를 받았다.

평론가의 이름은 공개되지 않았지만, Serge는 평론가가 주문할 요리와 그의 취향을 안다. 평론가는 요리에 들어가는 소금, 후추, 마늘 가루의 비율이 매우 정확하기를 요구한다.

Serge는 특별한 선반에 소금, 후추, 마늘 가루를 섞은 혼합물 병들을 보관한다. 각 병에는 세 재료의 양이 kg 단위로 정확히 적혀 있다. Serge는 병의 혼합물을 여러 개 섞거나 병 하나를 그대로 사용해서 요리에 필요한 비율의 혼합물을 만들 수 있다.

요리에 넣는 혼합물의 절대량은 매우 적으므로, 병에 든 재료는 항상 충분하다고 가정해도 된다. 다만 비율을 나타내는 수는 매우 클 수 있다.

Serge는 선반의 병으로 평론가가 좋아하는 혼합물을 만들 수 있는지, 만들 수 있다면 필요한 병의 최소 개수가 몇 개인지 알고 싶어 한다. 선반은 Serge가 새 병을 받거나 다른 요리사에게 병을 빌려주면서 시간에 따라 바뀐다. 따라서 병이 바뀔 때마다 이 질문에 답해야 한다.

표 1: 선반에 있는 병

평론가가 좋아하는 혼합물의 비율은 1 : 1 : 1이고, 선반에는 병이 세 개 있다 (표 1). 병 1과 병 2를 같은 양으로 사용하면 원하는 혼합물을 얻을 수 있다. 병 2를 치우면 원하는 혼합물을 더 이상 만들 수 없다.

첫 줄에 평론가가 좋아하는 혼합물의 소금, 후추, 마늘 가루 양을 나타내는 음이 아닌 정수 $S_f$, $P_f$, $G_f$ ($0 \le S_f, P_f, G_f$, $0 < S_f + P_f + G_f \le 10^6$)가 주어진다. 임의의 실수 $\alpha > 0$에 대해 $(\alpha S_f, \alpha P_f, \alpha G_f)$도 좋아하는 혼합물이다.

둘째 줄에는 선반의 변경 횟수를 나타내는 양의 정수 $N$ ($N \le 100000$)이 주어진다. 처음에 선반은 비어 있다고 가정한다. 이어지는 $N$개의 줄에 선반의 변경이 하나씩 주어진다.

• 새 병을 추가하는 경우, 문자 A에 이어서 음이 아닌 정수 $S_i$, $P_i$, $G_i$ ($0 \le S_i, P_i, G_i$, $0 < S_i + P_i + G_i \le 10^6$)가 주어진다. 병은 1부터 차례로 번호가 붙으며, $i$번째로 추가된 병의 번호는 $i$이다.
• 병을 제거하는 경우, 문자 R에 이어서 병의 번호 $r_i$가 주어진다. 제거하는 번호는 모두 서로 다르며, $r_i$는 지금까지 추가된 병의 수를 넘지 않는다.

$N$개의 줄을 출력한다. $j$번째 줄에는 처음 $j$번의 변경 후 선반의 병으로 평론가가 좋아하는 비율의 혼합물을 만드는 데 필요한 병의 최소 개수를 출력한다. 만들 수 없으면 0을 출력한다.

병 1과 병 3은 소금, 후추, 마늘 가루의 비율이 같다.