#include <bits/stdc++.h>
typedef long long ll;
typedef std::tuple<ll, ll, ll> hash_t;

using namespace std;

ll power(ll a,ll b,ll m){
  if(a==0) return 0;
  if(b==0) return 1;
  if(b==1) return a;
  if(b%2) return (power((a*a)%m,b/2,m)*a)%m;
  return power((a*a)%m,b/2,m);
}

class RollingHash {
    hash_t p = {151, 503, 47};
    hash_t hashes = {0, 0, 0};
    hash_t pows = {1, 1, 1};
    hash_t mods = {916192396117594829LL, 182964847282097359LL, 288894744815098423LL};

  public:
    void add(ll x) {
        get<0>(pows) = (get<0>(pows) * get<0>(p)) % get<0>(mods);
        get<0>(hashes) = (get<0>(hashes) + (x + 1) * get<0>(pows)) % get<0>(mods);
        get<1>(pows) = (get<1>(pows) * get<1>(p)) % get<1>(mods);
        get<1>(hashes) = get<1>(hashes) + (x + 1) * get<1>(pows) % get<1>(mods);
        get<2>(pows) = (get<2>(pows) * get<2>(p)) % get<2>(mods);
        get<2>(hashes) = get<2>(hashes) + (x + 1) * get<2>(pows) % get<2>(mods);
    }
    void remove(ll x) {
        ll inverseP0 = power(get<0>(p), get<0>(mods)-2, get<0>(mods)),
            inverseP1 = power(get<1>(p), get<1>(mods)-2, get<1>(mods)),
            inverseP2 = power(get<2>(p), get<2>(mods)-2, get<2>(mods));

        get<0>(hashes) = (get<0>(hashes) - (x + 1) * get<0>(p) + get<0>(mods)) % get<0>(mods);
        get<0>(hashes) *= inverseP0;
        get<0>(hashes) %= get<0>(mods);
        get<0>(pows) = (get<0>(pows) * inverseP0) % get<0>(mods);

        get<1>(hashes) = (get<1>(hashes) - (x + 1) * get<1>(p) + get<1>(mods)) % get<1>(mods);
        get<1>(hashes) *= inverseP1;
        get<1>(hashes) %= get<1>(mods);
        get<1>(pows) = (get<1>(pows) * inverseP1) % get<1>(mods);

        get<2>(hashes) = (get<2>(hashes) - (x + 1) * get<2>(p) + get<2>(mods)) % get<2>(mods);
        get<2>(hashes) *= inverseP2;
        get<2>(hashes) %= get<2>(mods);
        get<2>(pows) = (get<2>(pows) * inverseP2) % get<2>(mods);
    }
    auto getHash() { return hashes; }
    auto getPows() { return pows; }
};