Chcemy przygotować mieszankę przypraw, w której sól, pieprz i czosnek są w proporcji $S : P : G$ . Mamy półkę z butelkami przypraw w różnych proporcjach i chcemy obsługiwać zmiany stanu półki (dodanie lub usunięcie butelki) oraz zapytania o minimalną liczbę butelek z półki, które potrzebne są, aby przygotować mieszankę $S : P : G$ .

Dwie przyprawy

Zastanówmy się najpierw, jak wyglądałoby rozwiązanie zadania, gdybyśmy mieli tylko dwie przyprawy (czyli $G = 0$ i w żadnej butelce nie ma czosnku). Jeśli sól i pieprz mają być w stosunku $S : P$ , to znaczy, że w objętości 1 będziemy chcieli mieć $x = S / (S + P)$ soli oraz $1 - x = P / (S + P)$ pieprzu. Zatem porządany stosunek możemy opisać jedną liczbą rzeczywistą $x$ .

Każda butelka zawiera mieszankę soli i pieprzu w pewnym stosunku. Zatem dla $i$ -tej butelki możemy ją opisać liczbą $x_{i}$ .

Zastanówmy się, jakie proporcje możemy uzyskać, mieszając zawartości dwóch butelek $x_{1}$ i $x_{2}$ (załóżmy, że $x_{1} \leq x_{2}$ ). Jeśli chcemy uzyskać objętość 1, to z pierwszej możemy wziąć $α$ (dla $0 \leq α \leq 1$ ), a z drugiej $1 - α$ . Wtedy proporcja wyniesie $x_{1} α + x_{2} (1 - α)$ . Zmieniając $α$ , możemy uzyskać wszystkie liczby z przedziału od $x_{1}$ do $x_{2}$ . Zatem uda nam się uzyskać $x$ , jeśli $x_{1} \leq x \leq x_{2}$ .

Geometrycznie można to przedstawić tak, że uzyskamy wszystkie liczby na osi liczbowej pomiędzy $x_{1}$ i $x_{2}$ .

Widać zatem, że nie będziemy potrzebowali więcej niż dwóch butelek. Bo jeśli mamy trzy butelki $x_{1} \leq x_{2} \leq x_{3}$ , to dowolną propocję uzyskamy też, biorąc skrajne wartości $x_{1}$ oraz $x_{3}$ . W ogólności wystarczy nam minimalna i maksymalna wartość $x_{i}$ .

Ostatecznie kryterium jest następujące: jeśli $x = x_{i}$ , to wystarczy nam użyć jednej butelki $i$ . Jeśli $min (x_{i}) \leq x \leq max (x_{i})$ , to wystarczą nam dwie butelki. W przeciwnym wypadku się nie da.

Tak więc cały algorytm jest następujący: trzymamy wartości $x_{i}$ w strukturze danych multiset. Dzięki temu w czasie logarytmicznym możemy wykonać wszystkie potrzebne operacje: dodanie wartości, usunięcie wartości, sprawdzenie czy wartość istnieje, znalezienie najmniejszej i największej wartości.

Zatem całe rozwiązanie będzie działać w złożoności czasowej $O (n \log n)$ .

Trzy przyprawy

W przypadku trzech przypraw, możemy stosunek $S : P : G$ wyrazić za pomocą pary liczb $(x, y)$ , bo w objętości 1 weźmiemy $x = S / (S + P + G)$ soli, $y = P / (S + P + G)$ pieprzu i $1 - x - y = G / (S + P + G)$ czosnku. Zatem $i$ -tą butelkę możemy reprezentować za pomocą $(x_{i}, y_{i})$ . Wygodnie jest myśleć o tym geometrycznie, jako o punkcie $B_{i} = (x_{i}, y_{i})$ na płaszczyźnie.

Dla dwóch butelek $B_{1} = (x_{1}, y_{1})$ i $B_{2} = (x_{2}, y_{2})$ uzyskamy tutaj wszystkie punkty postaci $B_{1} α + B_{2} (1 - α)$ dla $0 \leq α \leq 1$ , czyli punkty na odcinku łączącym $B_{1}$ i $B_{2}$ .

Tak więc, jeśli punkt $B = (x, y)$ jest równy któremuś $B_{i}$ , to wystarczy jedna butelka, a jeśli leży na odcinku pomiędzy jakimiś $B_{1}$ i $B_{2}$ , to wystarczą dwie butelki.

Jeśli mamy trzy punkty $B_{1}$ , $B_{2}$ i $B_{3}$ , które tworzą trójkąt, to możemy uzyskać z nich dowolny punkt, który leży wewnątrz lub na brzegu tego trójkąta. Punkty na brzegu leżą bowiem na odcinkach pomiędzy wierzchołkami trójkąta, a każdy punkt w trójkącie leży na odcinku pomiędzy pewnymi punktami na brzegu.

Okazuje się, że podobnie jak dla dwóch przypraw wystarczały dwie butelki, to w przypadku trzech przypraw zawsze wystarczą trzy butelki (o ile rozwiązanie istnieje). Wynika to z tego, że dla większej liczby punktów $B_{1}, \dots, B_{k}$ możemy uzyskać dowolny punkt, który leży w otoczce wypukłej $B_{1}, \dots, B_{k}$ . A z kolei dowolny punkt w otoczce wypukłej leży na pewnym trójkącie z triangulacji tej otoczki wypukłej, zatem wystarczy wziąć trzy punkty będące wierzchołkami tego trójkąta.

Implementacja

Rozwiązanie zaimplementujemy z użyciem liczb całkowitych, zatem punkty $B_{i} = (x_{i}, y_{i})$ będziemy trzymać w postaci ułamków zwykłych w strukturze point. Przez $B_{0}$ oznaczymy punkt odpowiadający stosunkowi $S : P : G$ .

Aby stwierdzić, czy odpowiedź jest równa $1$ , będziemy utrzymywali liczbę punktów $B_{i}$ , które są równe $B$ .

Aby stwierdzić, czy odpowiedź jest równa $2$ , będziemy utrzymywać liczbę odcinków $B_{i} B_{j}$ , które zawierają w swoim wnętrzu punkt $B$ . Będziemy w tym celu utrzymywać multizbiór wektorów $V_{i} = B_{i} - B$ (przy czym nie potrzebujemy ich dokładnej długości, więc będziemy trzymać tylko unikalnego reprezentanta wyznaczającego kierunek/zwrot w strukturze angle). Dodając wektor $V_{i}$ , patrzymy ile mamy w multizbiorze wektorów $- V_{i}$ i o tyle zwiększamy licznik odcinków.

W końcu, aby stwierdzić, czy odpowiedź jest równa $3$ , musimy sprawdzić, czy punkt $B$ leży w otoczce wypukłej wszystkich punktów. Posortujmy wektory $V_{i}$ wokół punktu $B$ i niech $α_{i}$ oznacza kąt pomiędzy wektorem $V_{i}$ a kolejnym wektorem $V_{i + 1}$ w tym posortowanieu.

Można pokazać, że jeśli $B$ nie leży w otoczce, to jest pewna prosta $p$ przechodząca przez $B$ , która nie przecina otoczki, zatem wszystkie wektory $V_{i}$ leżą po jednej stronie prostej $p$ . Z tego wynika, że istnieją dwa kolejne wektory $V_{i}$ i $V_{i + 1}$ , pomiędzy którymi kąt $α_{i}$ jest większy niż $180^{\circ}$ .

Będziemy zatem utrzymywać liczbę kątów $α_{i}$ większych niż $180^{\circ}$ . Tak więc na multisecie wektorów będziemy utrzymywać posortowanie wokół punktu $B$ , oraz podczas wkładania nowego wektora $V_{i}$ pomiędzy wektory $V_{j}$ oraz $V_{j + 1}$ , uaktualnimy liczbę kątów, odejmując kąt między $V_{j}$ i $V_{j + 1}$ oraz dodając kąty między $V_{j}$ i $V_{i}$ , a także między $V_{i}$ i $V_{j + 1}$ (przy czym musimy tu uważać na zdegenerowane przypadki, kiedy różnych wektorów na multisecie jest mniej niż $3$ ).

Złożoność czasowa algorytmu będzie wynosić $O (n \log n)$ :

const int N = 110000;
int sf,pf,gf,n,k;
int cnt_one,cnt_two,cnt_three;

struct point {
  ll x,y,mian;
  
  point() : x(), y(), mian(1) { }
  point(ll _x, ll _y, ll _mian) {
    x = _x;
    y = _y;
    mian = _mian;
    ll d = __gcd(__gcd(x, y), mian);
    if (d < 0) { d *= -1; }
    x /= d;
    y /= d;
    mian /= d;
    if (mian < 0) {
      x *= -1; y *= -1; mian *= -1;
    }
  }
};

bool operator==(const point& p, const point& q) {
  return p.x == q.x && p.y == q.y && p.mian == q.mian;
}


struct angle {
  ll x,y;

  angle(ll _x, ll _y) {
    x = _x;
    y = _y;
    ll d = __gcd(x, y);
    if (d < 0) { d *= -1; }
    x /= d;
    y /= d;
  }

  bool up() const {
    return y > 0 || y == 0 && x > 0;
  }
};

__int128_t det(const angle& p, const angle& q) {
  return __int128_t(p.x) * q.y - __int128_t(p.y) * q.x;
}

bool operator<(const angle& p, const angle& q) {
  if (p.up() != q.up()) {
    return p.up();
  } else {
    return det(p, q) > 0;
  }
}

bool operator==(const angle& p, const angle& q) {
  return !(p < q) && !(q < p);
}

bool bigger(const angle& p, const angle& q) {
  return det(p, q) < 0;
}

angle operator-(const angle& p) {
  return angle(-p.x, -p.y);
}

angle operator-(const point& p, const point& q) {
  ll x = p.x * q.mian - q.x * p.mian;
  ll y = p.y * q.mian - q.y * p.mian;
  return angle(x, y);
}


point pt[N],zero;
multiset<angle> zbior_katy;

int calc(multiset<angle>::iterator& it) {
  auto prev_it = prev(it == zbior_katy.begin() ? zbior_katy.end() : it);
  auto next_it = next(it) == zbior_katy.end() ? zbior_katy.begin() : next(it);
  return bigger(*prev_it, *it) + bigger(*it, *next_it) - bigger(*prev_it, *next_it);
}

bool three() {
  if (zbior_katy.empty()) return 0;
  if (zbior_katy.count(*zbior_katy.begin()) == zbior_katy.size()) return 0;
  return cnt_three == 0;
}

int main() {
  scanf("%d%d%d%d",&sf,&pf,&gf,&n);
  zero = point(sf, pf, sf+pf+gf);

  REP(i,n) {
    char typ; scanf(" %c",&typ);
    if (typ == 'A') {
      int s,p,f; scanf("%d%d%d",&s,&p,&f);
      pt[k] = point(s, p, s+p+f);

      if (pt[k] == zero) {
        cnt_one++;
      } else {
        angle kat = pt[k] - zero;

        auto it = zbior_katy.insert(kat);
        cnt_three += calc(it);

        cnt_two += zbior_katy.count(-kat);
      }

      k++;
    } else {
      int x; scanf("%d",&x); --x;

      if (pt[x] == zero) {
        cnt_one--;
      } else {
        angle kat = pt[x] - zero;

        auto it = zbior_katy.find(kat);
        cnt_three -= calc(it);
        zbior_katy.erase(it);

        cnt_two -= zbior_katy.count(-kat);
      }
    }

    int ans = 0;
    if (cnt_one > 0) {
      ans = 1;
    } else if (cnt_two > 0) {
      ans = 2;
    } else if (three()) {
      ans = 3;
    }

    printf("%d\n", ans);
  }
}