typedef long long llong;

using namespace std;

typedef long long ll;

class Hash {
	class myHash {
		ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;
		ll x, y;
		ll getMod(ll a, ll b) const {
			if (a > b) {
				a -= b;
			}
			return a;
		}
	public:
		myHash() {}
		myHash(ll x, ll y) : x(x), y(y) {}
		bool operator == (myHash p) const {
			return x == p.x && y == p.y;
		}
		bool operator != (myHash p) const {
			return x != p.x || y != p.y;
		}
		myHash operator + (myHash p) const {
			return myHash(getMod(x + p.x, mod1), getMod(y + p.y, mod2));
		}
		myHash operator — (myHash p) const {
			return myHash(getMod(x — p.x + mod1, mod1), getMod(y — p.y + mod2, mod2));
		}
		myHash operator * (myHash p) const {
			return myHash((x * p.x) % mod1, (y * p.y) % mod2);
		}
	};
	int n;
	vector <myHash> h, deg;
	const myHash p = myHash(101, 103);
public:
	Hash(string &s) {
		n = s.size();
		h.assign(n + 1, myHash(0, 0));
		deg.assign(n + 1, myHash(1, 1));
		for (int i = 1; i < n + 1; i++) {
			deg[i] = deg[i &mdash; 1] * p;
			h[i] = h[i &mdash; 1] * p + myHash(s[i &mdash; 1] & mdash; 'a' + 1, s[i &mdash; 1] & mdash; 'a' + 1);
		}
	}
	myHash get_hash(int l, int r) const { // [l, r) &mdash; полуинтервал (нумерация с 0)
		return h[r] & mdash; h[l] * deg[r &mdash; l];
	}
	bool compare(int l1, int r1, int l2, int r2) const {
		return get_hash(l1, r1) == get_hash(l2, r2);
	}
};