struct hsh	{
	ll base, p1, p2;

	ll val1, val2;
	deque<ll> vals;

	ll inv1, inv2;

	ll modExp(ll power, ll prime) {
		if (power == 0) {
			return 1;
		} else {
			ll cur = modExp(power / 2, prime); cur = cur * cur; cur = cur % prime;
			if (power % 2 == 1) cur = cur * base;
			cur = cur % prime;
			return cur;
		}
	}

	hsh() {
	}

	hsh(ll b, ll x, ll y) {
		base = b;
		p1 = x;
		p2 = y;
		val1 = 0;
		val2 = 0;

		inv2 = modExp(p2-2, p2);
		inv1 = modExp(p1-2, p1);
	}

	hsh(ll b) {
		p1 = 1000000007;
		p2 = 1000000009;
		base = b;
		val1 = 0;
		val2 = 0;

		inv2 = modExp(p2-2, p2);
		inv1 = modExp(p1-2, p1);
	}

	hsh(ll b, string S) {
		p1 = 1000000007;
		p2 = 1000000009;
		base = b;
		val1 = 0;
		val2 = 0;

		inv2 = modExp(p2-2, p2);
		inv1 = modExp(p1-2, p1);
		F0R(i, sz(S)) {
			push_back(S[i] - 'a');
		}
	}

	void push_back(ll v) {
		val1 *= base;
		val1 %= p1;
		val1 += v;
		val1 %= p1;
		val2 *= base;
		val2 %= p2;
		val2 += v;
		val2 %= p2;

		vals.push_back(v);
	}

	void pop_back() {
		ll cur = vals.back();
		vals.pop_back();

		val1 += p1 - cur; val1 %= p1;
		val1 = val1 * inv1; val1 %= p1;

		val2 += p2 - cur; val2 %= p2;
		val2 = val2 * inv2; val2 %= p2;
	}

	void push_front(ll v) {
		val1 += v * modExp(sz(vals), p1);
		val1 %= p1;

		val2 += v * modExp(sz(vals), p2);
		val2 %= p2;

		vals.push_front(v);
	}

	void pop_front() {
		ll v = vals.front();
		vals.pop_front();
		ll sub1 = (v * modExp(sz(vals), p1)) % p1;
		val1 += p1 - sub1; val1 %= p1;

		ll sub2 = (v * modExp(sz(vals), p2)) % p2;
		val2 += p2 - sub2; val2 %= p2;

	}

	bool operator==(const hsh &v) const {
		return (val1 == v.val1 && val2 == v.val2 && sz(vals) == sz(v.vals));
	}

	bool operator<(const hsh &v) const {
		if (val1 == v.val1 && val2 == v.val2) {
			return sz(vals) < sz(v.vals);
		} else if (val1 == v.val1) {
			return val2 < v.val2;
		}
		return val1 < v.val1;
	}

};