Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- //<(")
- #define ll long long
- using namespace std;
- const ll base = 31;
- const ll siz = 1e6 + 10;
- const ll mod = 1e9 + 7;
- const ll MAXX = 1e18;
- ll n, m;
- string a, b;
- ll hashVal[siz][2];
- ll Pow[siz];
- void setup() {
- for (ll i = 1; i < siz; i++) {
- Pow[i] = (Pow[i - 1] * base) % mod;
- }
- a = ' ' + a;
- b = ' ' + b;
- for (ll i = 1; i <= n; i++) {
- hashVal[i][0] = (hashVal[i - 1][0] * base + a[i] - 'a' + 1) % mod;
- }
- for (ll i = 1; i <= m; i++) {
- hashVal[i][1] = (hashVal[i - 1][1] * base + b[i] - 'a' + 1) % mod;
- }
- }
- ll getHash(ll a, ll b, bool pos) {
- return (hashVal[b][pos] - hashVal[a - 1][pos] * Pow[b - a + 1] + mod * mod) % mod;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- //freopen("INP.txt", "r", stdin);
- //freopen("OUT.txt", "w", stdout);
- cin >> n >> m;
- cin >> a >> b;
- setup();
- ll q;
- cin >> q;
- while (q--) {
- ll l, r, u, v;
- cin >> l >> r >> u >> v;
- ll x = getHash(l, r, 0), y = getHash(u, v, 1);
- if (x == y) {
- cout << '=';
- continue;
- }
- if ((r - l) > (v - u)) {
- ll le = u, ri = v;
- ll pos = 0;
- while (le <= ri) {
- ll mid = (le + ri) / 2;
- if (getHash(l, l + mid - 1, 0) == getHash(u, u + mid - 1, 1)) {
- le = mid + 1;
- }
- else {
- pos = mid;
- ri = mid - 1;
- }
- }
- if (a[pos] == b[pos]) {
- cout << '>';
- }
- else {
- if (a[pos] < b[pos]) {
- cout << '<';
- }
- else {
- cout << '>';
- }
- }
- }
- else {
- ll le = l, ri = r;
- ll pos = 0;
- while (le <= ri) {
- ll mid = (le + ri) / 2;
- //cerr << mid << '\n';
- //cerr << getHash(l, l + mid - 1, 0) << ' ' << getHash(u, u + mid - 1, 1) << '\n';
- if (getHash(l, l + mid - 1, 0) == getHash(u, u + mid - 1, 1)) {
- le = mid + 1;
- }
- else {
- pos = mid;
- ri = mid - 1;
- }
- }
- if (a[pos] == b[pos]) {
- cout << '<';
- }
- else {
- if (a[pos] < b[pos]) {
- cout << '<';
- }
- else {
- cout << '>';
- }
- }
- cerr << pos << '\n';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement