This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0355"
#include <iostream>
#include "string/range_update_range_hash.hpp"
int main() {
int n;
std::string u;
std::cin >> n >> u;
auto rh = range_update_range_hash<>::from(u);
int q;
std::cin >> q;
while (q--) {
std::string t;
std::cin >> t;
if (t == "set") {
int x, y;
char z;
std::cin >> x >> y >> z;
rh.apply(--x, y, z);
}
if (t == "comp") {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
int sgn = rh.cmp(--a, b, --c, d);
std::cout << (sgn == -1 ? 's' : sgn == 0 ? 'e' : 't') << '\n';
}
}
}
#line 1 "test/aoj/0355.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/0355"
#include <iostream>
#line 2 "string/range_update_range_hash.hpp"
#include <algorithm>
#include <array>
#include <random>
#line 1 "atcoder/lazysegtree.hpp"
#line 5 "atcoder/lazysegtree.hpp"
#include <cassert>
#line 7 "atcoder/lazysegtree.hpp"
#include <vector>
#line 1 "atcoder/internal_bit.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#line 10 "atcoder/lazysegtree.hpp"
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
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);
}
S sml = e(), smr = e();
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);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
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);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#line 2 "math/modint2305843009213693951.hpp"
#include <cstdint>
struct modint2305843009213693951 {
using mint = modint2305843009213693951;
public:
static constexpr uint64_t mod = 2305843009213693951;
modint2305843009213693951() : _v(0) {
}
modint2305843009213693951(uint64_t v) : _v(fast_mod(v)) {
}
static constexpr uint64_t fast_mod(uint64_t v) {
uint64_t u = v >> 61;
uint64_t d = v & mod;
uint64_t x = u + d;
if (x > mod) x -= mod;
return x;
}
uint64_t val() const {
return _v;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= mod) _v -= mod;
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= mod) _v += mod;
return *this;
}
mint& operator*=(const mint& rhs) {
static constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
static constexpr uint64_t mask30 = (uint64_t(1) << 30) - 1;
uint64_t au = _v >> 31;
uint64_t ad = _v & mask31;
uint64_t bu = rhs._v >> 31;
uint64_t bd = rhs._v & mask31;
uint64_t m = ad * bu + au * bd;
uint64_t mu = m >> 30;
uint64_t md = m & mask30;
_v = fast_mod((au * bu << 1) + mu + (md << 31) + ad * bd);
return *this;
}
mint operator+() const {
return *this;
}
mint operator-() const {
return mint() - *this;
}
mint pow(uint64_t n) const {
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
uint64_t _v;
};
#line 2 "math/pow_sum_table.hpp"
template <typename mint>
struct pow_mod_sums {
pow_mod_sums() {
}
pow_mod_sums(mint base, int n) : base(base) {
ensure(n);
}
// sum(pow[0..i])
const mint& operator[](int i) const {
ensure(i);
return pow_sums[i];
}
void ensure(int n) const {
int sz = pow_sums.size();
if (sz > n) return;
pow_sums.resize(n + 1);
pows.resize(n + 1);
for (int i = sz; i <= n; i++) {
pows[i] = base * pows[i - 1];
pow_sums[i] = pow_sums[i - 1] + pows[i - 1];
}
}
private:
mutable std::vector<mint> pow_sums{0};
mutable std::vector<mint> pows{1};
mint base;
static constexpr int mod = mint::mod;
};
#line 3 "math/pow_table.hpp"
template <typename mint>
struct pow_mods {
pow_mods() {
}
pow_mods(mint base, int n) : base(base) {
ensure(n);
}
const mint& operator[](int i) const {
ensure(i);
return pows[i];
}
void ensure(int n) const {
int sz = pows.size();
if (sz > n) return;
pows.resize(n + 1);
for (int i = sz; i <= n; i++) pows[i] = base * pows[i - 1];
}
private:
mutable std::vector<mint> pows{1};
mint base;
static constexpr int mod = mint::mod;
};
#line 10 "string/range_update_range_hash.hpp"
template <int base_num = 1, typename mint = modint2305843009213693951>
struct range_update_range_hash {
public:
range_update_range_hash() {
}
range_update_range_hash(const std::vector<int>& a) : n(a.size()) {
std::vector<S> v(n);
for (int i = 0; i < n; i++) {
for (int base_id = 0; base_id < base_num; base_id++) {
v[i].hash[base_id] = a[i];
}
v[i].size = 1;
v[i].is_e = false;
}
segt = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>(v);
}
template <typename Iterable>
static range_update_range_hash from(const Iterable& s) {
std::vector<int> a;
for (auto&& e : s) a.push_back(int(e));
return range_update_range_hash(a);
}
template <typename T>
void set(int p, T x) {
segt.set(p, int(x));
}
std::array<mint, base_num> get(int p) {
return segt.get(p).hash;
}
std::array<mint, base_num> prod(int l, int r) {
return segt.prod(l, r).hash;
}
std::array<mint, base_num> all_prod() {
return segt.all_prod();
}
template <typename T>
void apply(int l, int r, T x) {
segt.apply(l, r, {int(x), false});
}
int lcp(int l1, int r1, int l2, int r2) {
int len = std::min(r1 - l1, r2 - l2);
int ok = 0, ng = len + 1;
while (ng - ok > 1) {
int mid = (ok + ng) / 2;
bool f = prod(l1, l1 + mid) == prod(l2, l2 + mid);
(f ? ok : ng) = mid;
}
return ok;
}
int cmp(int l1, int r1, int l2, int r2) {
int x = std::min({lcp(l1, r1, l2, r2), r1 - l1, r2 - l2});
if (l1 + x == r1 && l2 + x != r2) return -1;
if (l1 + x == r1 && l2 + x == r2) return 0;
if (l1 + x != r1 && l2 + x == r2) return 1;
return get(l1 + x)[0].val() < get(l2 + x)[0].val() ? -1 : 1;
}
private:
static inline std::array<mint, base_num> gen_bases() {
static std::mt19937_64 rng(std::random_device{}());
std::array<mint, base_num> bases;
for (int i = 0; i < base_num; i++) {
while (true) {
uint64_t k = std::uniform_int_distribution<uint64_t>(
1, mint::mod - 1)(rng);
if (std::gcd(k, mint::mod - 1) != 1) continue;
uint64_t b = mint(r).pow(k).val();
if (b <= A) continue;
bases[i] = b;
break;
}
}
return bases;
}
static inline std::array<pow_mod_sums<mint>, base_num> init_pow_sums(
const std::array<mint, base_num>& bases) {
std::array<pow_mod_sums<mint>, base_num> pow_sums;
for (int i = 0; i < base_num; i++) {
pow_sums[i] = pow_mod_sums<mint>(bases[i], 0);
}
return pow_sums;
}
static inline std::array<pow_mods<mint>, base_num> init_pows(
const std::array<mint, base_num>& bases) {
std::array<pow_mods<mint>, base_num> pows;
for (int i = 0; i < base_num; i++) {
pows[i] = pow_mods<mint>(bases[i], 0);
}
return pows;
}
static inline std::array<mint, base_num> bases = gen_bases();
static inline std::array<pow_mod_sums<mint>, base_num> pow_sums =
init_pow_sums(bases);
static inline std::array<pow_mods<mint>, base_num> pows = init_pows(bases);
int n;
static constexpr uint64_t r = 37;
static constexpr uint64_t A = 2147483647;
struct S {
std::array<mint, base_num> hash;
int size;
bool is_e;
};
static S op(S a, S b) {
if (a.is_e) return b;
if (b.is_e) return a;
for (int base_id = 0; base_id < base_num; base_id++) {
b.hash[base_id] += a.hash[base_id] * pows[base_id][b.size];
}
b.size += a.size;
return b;
}
static S e() {
return {std::array<mint, base_num>(), 0, true};
}
struct F {
int f;
bool is_id;
};
static S mapping(F f, S x) {
if (!f.is_id) {
for (int base_id = 0; base_id < base_num; base_id++) {
x.hash[base_id] = f.f * pow_sums[base_id][x.size];
}
}
return x;
}
static F composition(F f, F g) {
return (f.is_id ? g : f);
}
static F id() {
return {0, true};
}
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> segt;
};
#line 5 "test/aoj/0355.test.cpp"
int main() {
int n;
std::string u;
std::cin >> n >> u;
auto rh = range_update_range_hash<>::from(u);
int q;
std::cin >> q;
while (q--) {
std::string t;
std::cin >> t;
if (t == "set") {
int x, y;
char z;
std::cin >> x >> y >> z;
rh.apply(--x, y, z);
}
if (t == "comp") {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
int sgn = rh.cmp(--a, b, --c, d);
std::cout << (sgn == -1 ? 's' : sgn == 0 ? 'e' : 't') << '\n';
}
}
}