/* import random class LazySegTree: def __init__(self, op, e, mapping, composition, id_v, v): n = len(v) log = 0 while (1 << log) < n: log += 1 size = 1 << log d = [e] * (2 * size) lz = [id_v] * size for i in range(n): d[size + i] = v[i] self._op = op self._e = e self._mapping = mapping self._composition = composition self._id = id_v self._n = n self._log = log self._size = size self._d = d self._lz = lz for i in range(self._size - 1, 0, -1): self._update(i) def _update(self, k): self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) def _all_apply(self, k, f): self._d[k] = self._mapping(f, self._d[k]) if k < self._size: self._lz[k] = self._composition(f, self._lz[k]) def _push(self, k): if self._lz[k] != self._id: self._all_apply(2 * k, self._lz[k]) self._all_apply(2 * k + 1, self._lz[k]) self._lz[k] = self._id def set(self, p, x): p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p): p += self._size for i in range(self._log, 0, -1): self._push(p >> i) return self._d[p] def prod(self, l, r): if l == r: return self._e l += self._size r += self._size for i in range(self._log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) sml, smr = self._e, self._e while l < r: if l & 1: sml = self._op(sml, self._d[l]) l += 1 if r & 1: r -= 1 smr = self._op(self._d[r], smr) l >>= 1 r >>= 1 return self._op(sml, smr) def all_prod(self): return self._d[1] def apply(self, l, r, f): if l == r: return l += self._size r += self._size for i in range(self._log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) l2, r2 = l, r while l < r: if l & 1: self._all_apply(l, f) l += 1 if r & 1: r -= 1 self._all_apply(r, f) l >>= 1 r >>= 1 l, r = l2, r2 for i in range(1, self._log + 1): if ((l >> i) << i) != l: self._update(l >> i) if ((r >> i) << i) != r: self._update((r - 1) >> i) def apply_point(self, p, f): p += self._size for i in range(self._log, 0, -1): self._push(p >> i) self._d[p] = self._mapping(f, self._d[p]) for i in range(1, self._log + 1): self._update(p >> i) #右区間と左区間をマージ def op(x, y): x_k, x_len, x_l = x y_k, y_len, y_l = y xx_k = (x_k*powb[y_len])%mod new_k = (xx_k+y_k)%mod new_len = x_len+y_len new_l = [0]*26 for i in range(26): new_l[i] = ((x_l[i]*powb[y_len])%mod+y_l[i])%mod return (new_k, new_len, new_l) #値の単位元 #op(x, e) = op(e, x) = x を満たす必要がある。 def e(): return (0, 0, 0) #区間に区間変更値fを付与 def mapping(f, S): S_k, S_len, S_l = S sum_p, minus_p = 0, 0 new_sl = [0]*26 for i in range(1, 27): sum_p += S_l[i-1] if i+f >= 27: minus_p += S_l[i-1] new_sl[(i-1+f)%26] = S_l[i-1] new_k = (S_k+f*sum_p-26*minus_p)%mod return (new_k, S_len, new_sl) #元々溜まっていたgに新たに降ってきたfを合わせる def composition(f, g): return (f + g)%26 #何も操作しないときの状態(操作の単位元) #mapping(id, x) = x と composition(f, id) = f を満たす必要がある。 #例えば区間乗算なら、1を掛けても何も変わらないのでid=1 #区間代入なら、入力で与えられない極端な数字6*10**18など def id(): return 0 base = random.randint(30, 10**9+1) mod = 2**61-1 S = list(map(str, input())) T = list(map(str, input())) powb = [pow(base, i, mod) for i in range(max(len(S), len(T))+10)] s_l = [] for s in S: p = [0]*26 p[(ord(s) - ord('a'))] = 1 s_l.append([(ord(s) - ord('a') + 1), 1, p]) t_l = [] for t in T: p = [0]*26 p[(ord(t) - ord('a'))] = 1 t_l.append([(ord(t) - ord('a') + 1), 1, p]) seg_S = LazySegTree(op, (0, 0, [0]*26), mapping, composition, 0, s_l) seg_T = LazySegTree(op, (0, 0, [0]*26), mapping, composition, 0, t_l) Q = int(input()) ans = [] for _ in range(Q): q = list(map(int, input().split())) if q[0] == 1: seg_S.apply(q[1]-1, q[2], q[3]) elif q[0] == 2: seg_T.apply(q[1]-1, q[2], q[3]) else: p = q[1] s, t = seg_S.prod(p-1, p)[0], seg_T.prod(p-1, p)[0] if s > t: ans.append("Greater") elif s < t: ans.append("Lesser") else: left, right = p-1, min(len(S), len(T)) while left + 1 < right: mid = (left+right)//2 if seg_S.prod(p-1, mid+1)[0] == seg_T.prod(p-1, mid+1)[0]: left = mid else: right = mid if right == min(len(S), len(T)): if right == len(S) and right == len(T): ans.append("Equals") elif right == len(S) and right != len(T): ans.append("Lesser") else: ans.append("Greater") else: s, t = seg_S.prod(right, right+1)[0], seg_T.prod(right, right+1)[0] if s < t: ans.append("Lesser") else: ans.append("Greater") for i in ans: print(i) */ #include #include #include #include #include #include using namespace std; const long long MOD = (1ULL << 61) - 1; long long safe_mod(long long x) { long long res = x % MOD; if (res < 0) res += MOD; return res; } long long add(long long a, long long b) { long long res = a + b; if (res >= MOD) res -= MOD; return res; } long long mul(long long a, long long b) { unsigned __int128 res = (unsigned __int128)a * b; res = (res >> 61) + (res & MOD); if (res >= MOD) res -= MOD; return (long long)res; } vector powb; struct Node { long long k; long long length; long long l[26]; Node() { k = 0; length = 0; for (int i = 0; i < 26; i++) l[i] = 0; } }; Node op(const Node& x, const Node& y) { if (x.length == 0) return y; if (y.length == 0) return x; Node res; long long xx_k = mul(x.k, powb[y.length]); res.k = add(xx_k, y.k); res.length = x.length + y.length; for (int i = 0; i < 26; i++) { res.l[i] = add(mul(x.l[i], powb[y.length]), y.l[i]); } return res; } Node mapping(long long f, const Node& S) { if (S.length == 0) return S; long long sum_p = 0; long long minus_p = 0; Node res; res.length = S.length; for (int i = 1; i <= 26; i++) { sum_p = add(sum_p, S.l[i - 1]); if (i + f >= 27) { minus_p = add(minus_p, S.l[i - 1]); } res.l[((i - 1 + f) % 26 + 26) % 26] = S.l[i - 1]; } // オーバーフロー対策に __int128_t を使用 __int128_t val = S.k; val += (__int128_t)f * sum_p; val -= (__int128_t)26 * minus_p; long long rem = val % MOD; if (rem < 0) rem += MOD; res.k = rem; return res; } long long composition(long long f, long long g) { return (f + g) % 26; } struct LazySegTree { int _n, _log, _size; vector _d; vector _lz; LazySegTree(const vector& v) { _n = v.size(); _log = 0; while ((1 << _log) < _n) _log++; _size = 1 << _log; _d.assign(2 * _size, Node()); _lz.assign(_size, 0); for (int i = 0; i < _n; i++) { _d[_size + i] = v[i]; } for (int i = _size - 1; i >= 1; i--) { update(i); } } void update(int k) { _d[k] = op(_d[2 * k], _d[2 * k + 1]); } void all_apply(int k, long long f) { _d[k] = mapping(f, _d[k]); if (k < _size) { _lz[k] = composition(f, _lz[k]); } } void push(int k) { if (_lz[k] != 0) { all_apply(2 * k, _lz[k]); all_apply(2 * k + 1, _lz[k]); _lz[k] = 0; } } void apply(int l, int r, long long f) { if (l == r) return; l += _size; r += _size; for (int i = _log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; for (int i = 1; i <= _log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } Node prod(int l, int r) { if (l == r) return Node(); l += _size; r += _size; for (int i = _log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } Node sml, smr; while (l < r) { if (l & 1) sml = op(sml, _d[l++]); if (r & 1) smr = op(_d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); long long base = uniform_int_distribution(30, 1000000001)(rng); string S, T; if (!(cin >> S >> T)) return 0; int max_len = max(S.size(), T.size()) + 10; powb.assign(max_len, 0); powb[0] = 1; for (int i = 1; i < max_len; i++) { powb[i] = mul(powb[i - 1], base); } vector s_l(S.size()); for (int i = 0; i < (int)S.size(); i++) { s_l[i].k = S[i] - 'a' + 1; s_l[i].length = 1; s_l[i].l[S[i] - 'a'] = 1; } vector t_l(T.size()); for (int i = 0; i < (int)T.size(); i++) { t_l[i].k = T[i] - 'a' + 1; t_l[i].length = 1; t_l[i].l[T[i] - 'a'] = 1; } LazySegTree seg_S(s_l); LazySegTree seg_T(t_l); int Q; if (!(cin >> Q)) return 0; vector ans; for (int i = 0; i < Q; i++) { int type; cin >> type; if (type == 1) { int l, r; long long f; cin >> l >> r >> f; seg_S.apply(l - 1, r, f); } else if (type == 2) { int l, r; long long f; cin >> l >> r >> f; seg_T.apply(l - 1, r, f); } else if (type == 3) { int p; cin >> p; long long s = seg_S.prod(p - 1, p).k; long long t = seg_T.prod(p - 1, p).k; if (s > t) { ans.push_back("Greater"); } else if (s < t) { ans.push_back("Lesser"); } else { int left = p - 1; int right = min(S.size(), T.size()); while (left + 1 < right) { int mid = left + (right - left) / 2; if (seg_S.prod(p - 1, mid + 1).k == seg_T.prod(p - 1, mid + 1).k) { left = mid; } else { right = mid; } } if (right == (int)min(S.size(), T.size())) { if (right == (int)S.size() && right == (int)T.size()) { ans.push_back("Equals"); } else if (right == (int)S.size() && right != (int)T.size()) { ans.push_back("Lesser"); // タイポ修正済 } else { ans.push_back("Greater"); } } else { long long s_next = seg_S.prod(right, right + 1).k; long long t_next = seg_T.prod(right, right + 1).k; if (s_next < t_next) { ans.push_back("Lesser"); // タイポ修正済 } else { ans.push_back("Greater"); } } } } } for (const string& out : ans) { cout << out << "\n"; } return 0; }