#pragma once
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

struct Strategy {
  public:
    // Note that x and y use 0-based indexing for this method, but 1-based indexing in the
    // interaction and generators.
    virtual ll get(int x, int y) = 0;

    virtual ll answer() = 0;
};

struct FixedStrategy : Strategy {
    vector<vector<ll>> grid;

  public:
    FixedStrategy(vector<vector<ll>> grid) : grid(grid){};

    ll get(int x, int y) override { return grid[y][x]; }

    ll answer() override {
        ll ans = 0;
        for(const auto& row : grid) ans = max(ans, *max_element(row.cbegin(), row.cend()));
        return ans;
    }
};

struct SpiralStrategy : Strategy {
    int n;
    bool inwards;

  public:
    SpiralStrategy(int n, bool inwards) : n(n), inwards(inwards) {
        if(n % 2 != 0) {
            cerr << "n should be even!" << endl;
            exit(1);
        }
    };

    ll get(int x, int y) override {
        ll dx = x - n / 2;
        ll dy = y - n / 2;

        ll r, val;
        if(n - x - 1 >= y) { // top-left
            r   = max(abs(dx), abs(dy + 1));
            val = 4 * r * r;
            val += x - y;
        } else { // bottom-right
            r   = max(abs(dx + 1), abs(dy + 1));
            val = 4 * r * r;
            val += y - x - 4 * r + 2;
        }

        return inwards ? (n * n + 1 - val) : val;
    }

    ll answer() override {
        return inwards ? get(n / 2, n / 2 - 1) : max(get(0, 0), get(n - 1, n - 1));
    }
};

struct DoubleSpiralStrategy : Strategy {
    int n;

  public:
    DoubleSpiralStrategy(int n) : n(n){};

    ll get(int x, int y) override {
        ll dx = 2 * x - n + 1;
        ll dy = 2 * y - n + 1;

        ll r, d;
        bool invert;
        if((x <= y and y <= n - x - 1) or (n - x - 1 <= y and y <= x)) {
            r      = abs(dx) + 1;
            invert = bool(r & 2) != (dx >= 0);
            d      = -abs(y - x);
        } else {
            r      = abs(dy) - 1;
            invert = bool(r & 2) != (dy >= 0);
            d      = +abs(y - x);
        }

        return n * n / 2 + 1 + (d + r * r / 2) * (invert ? -1 : 1);
    }

    ll answer() override { return max(get(0, 0), get(n - 1, n - 1)); }
};

struct HillStrategy : Strategy {
    int n, cx, cy;

  public:
    HillStrategy(int n, int x, int y) : n(n), cx(x), cy(y){};

    ll get(int x, int y) override {
        ll dx = x - cx;
        ll dy = y - cy;
        ll r  = abs(dx) + abs(dy);

        // `add` has unique for every cell in a "radius" (i.e. a diamond-shaped "ring" around the
        // top of the hill)
        ll add = abs(dx);
        if(dx < 0) add += 2 * n - 1;
        if(dy > 0) add += n;

        return (2 * n - r) * n * 4 + add;
    }

    ll answer() override { return get(cx, cy); }
};

struct ZigZagStrategy : Strategy {
    int n, cx, cy;

  public:
    ZigZagStrategy(int n, int x, int y) : n(n), cx(x), cy(y){};

    ll get(int x, int y) override {
        ll dx = x - cx;
        ll dy = y - cy;
        if(x == cx) {
            return 2 * n * n - 2 * abs(dy) + (dy > 0 ? 1 : 0);
        }
        return 2 * n * n - 2 * n * abs(dx) - 2 * ((dx + (dx < 0 ? 1 : 0)) % 2 ? y : n - y - 1) +
               (dx > 0 ? 1 : 0);
    }

    ll answer() override { return get(cx, cy); }
};

struct SparseZigZagStrategy : Strategy {
  private:
    int n, startx, starty, gap;
    bool transpose, mirror;

    int finishx, finishy, hillMaxVal;

    HillStrategy hillStrategy;

  public:
    SparseZigZagStrategy(int n, int startx, int starty, int gap, int mask)
        : n(n), startx(startx), starty(starty), gap(gap), transpose((mask & 1) > 0),
          mirror((mask & 2) > 0), hillStrategy(HillStrategy(n, startx, starty)) {

        hillMaxVal = hillStrategy.answer() + 1;

        finishy = n - gap - 1;
        finishx = cleanGet(gap, finishy) > cleanGet(n - gap - 1, finishy) ? gap : n - gap - 1;

        // Order of mirror/transpose is reversed w.r.t. the `get` method.
        // Here, we transform output coordinates, while `get` transforms input coordinates.
        if(mirror) finishx = n - 1 - finishx;
        if(transpose) swap(finishx, finishy);
    }

    ll get(int x, int y) override {
        if(transpose) swap(x, y);
        if(mirror) x = n - 1 - x;
        return cleanGet(x, y);
    }

    // Returns the value without mirroring and transposing. Used to calculate finishx in
    // constructor.
    ll cleanGet(int x, int y) {
        if(isOnSparseLine(x, y))
            return hillMaxVal + y * n + (((y - starty) % (2 * gap) < gap) ? x : n - x);
        else
            return hillStrategy.get(x, y);
    }

    bool isOnSparseLine(int x, int y) {
        if(y < starty) return false;
        if(y >= n - gap) return false;
        if(y == starty)
            return startx < n / 2 ? x >= startx && x < n - gap : x <= startx && x >= gap;
        if((y - starty) % gap == 0) return gap <= x && x < n - gap;
        if((y - starty + (startx < n / 2 ? 0 : gap)) % (2 * gap) < gap) return x == n - gap - 1;
        return x == gap;
    }

    ll answer() override { return get(finishx, finishy); }
};

struct SparseDiagonalZigZagStrategy : Strategy {
  private:
    int n, startx, starty, gap;
    bool transpose, mirror;

    int starti, finishx, finishy, hillMaxVal;

    HillStrategy hillStrategy;

  public:
    SparseDiagonalZigZagStrategy(int n, int startx, int starty, int gap, int mask)
        : n(n), startx(startx), starty(starty), gap(gap), transpose((mask & 1) > 0),
          mirror((mask & 2) > 0), hillStrategy(HillStrategy(n, startx, starty)) {

        hillMaxVal = hillStrategy.answer() + 1;

        starti  = n - startx + starty + 1; // Index of the diagonal line
        finishx = gap;
        finishy = n - gap;
        if(!isOnSparseLine(finishx, finishy)) {
            if(isOnSparseLine(finishx + 1, finishy)) {
                if(isOnSparseLine(finishx, finishy - 1)) {
                    if(getZigZag(finishx + 1, finishy) > getZigZag(finishx, finishy - 1))
                        finishx++;
                    else
                        finishy--;
                } else
                    finishx++;
            } else
                finishy--;
        }

        // Order of mirror/transpose is reversed w.r.t. the `get` method.
        // Here, we transform output coordinates, while `get` transforms input coordinates.
        if(mirror) finishx = n - 1 - finishx;
        if(transpose) swap(finishx, finishy);
    }

    ll get(int x, int y) override {
        if(transpose) swap(x, y);
        if(mirror) x = n - 1 - x;

        if(isOnSparseLine(x, y))
            return hillMaxVal + getZigZag(x, y);
        else
            return hillStrategy.get(x, y);
    }

    ll getZigZag(int x, int y) {
        int i     = (n - x + y + 1 - starti) / gap; // Index of the diagonal line
        int partI = (n - x + y + 1 - starti) % gap;
        if(partI < 2) return 2 * i * (n + gap) + (i & 1 ? 2 * (n - x) + 1 - partI : 2 * x + partI);
        return 2 * (i + 1) * (n + gap) + partI;
    }

    bool isOnSparseLine(int x, int y) {
        if(x < gap || x > n - gap || y < gap || y > n - gap) return false;
        int i = n - x + y + 1 - starti; // Index of the diagonal line
        if(i < 0) return false;
        if(i < gap && (x < startx || y < starty)) return false;

        // Cut off "sharp edges" that cause extra local maxima
        if(i % (2 * gap) == gap && x == gap) return false;
        if(i % (2 * gap) == gap + 1 && x == n - gap) return false;
        if(i % (2 * gap) == 1 && y == gap) return false;
        if(i % (2 * gap) == 0 && y == n - gap) return false;

        // Diagonal lines, two pixels thick
        if(i % gap < 2) return true;
        // Transitions between diagonal lines, depending on parity
        if((i / gap) & 1) return x == gap || y == gap;
        return x == n - gap || y == n - gap;
    }

    ll answer() override { return get(finishx, finishy); }
};

struct SparseSpiralStrategy : Strategy {
  private:
    int n, cx, cy, gap;
    bool transpose, mirror, inwards;

    int maxr, finishx, finishy, hillMaxVal;

    HillStrategy hillStrategy;

  public:
    SparseSpiralStrategy(int n, int centerx, int centery, int gap, int mask, bool inwards)
        : n(n), cx(centerx), cy(centery), gap(gap), transpose((mask & 1) > 0),
          mirror((mask & 2) > 0), hillStrategy(HillStrategy(n, centerx, centery)),
          inwards(inwards) {

        maxr    = min(min(cx - gap / 2, n - gap / 2 - cx), min(cy - gap / 2, n - gap / 2 - cy));
        finishx = cx + maxr;
        finishy = cy - maxr / gap * gap;

        hillStrategy = inwards ? HillStrategy(n, finishx, finishy) : HillStrategy(n, centerx, centery);
        hillMaxVal = hillStrategy.answer() + 1;

        // Order of mirror/transpose is reversed w.r.t. the `get` method.
        // Here, we transform output coordinates, while `get` transforms input coordinates.
        if(mirror) finishx = n - 1 - finishx;
        if(transpose) swap(finishx, finishy);
    }

    ll get(int x, int y) override {
        auto fx = finishx;
        auto fy = finishy;
        if(transpose) swap(x, y), swap(fx, fy);
        if(mirror) x = n - 1 - x, fx = n - 1 - fx;

        if(isOnSparseLine(x, y))
            if(inwards) {
                return hillMaxVal + getSpiral(fx, fy) - getSpiral(x, y);
            } else {
                return hillMaxVal + getSpiral(x, y);
            }
        else
            return hillStrategy.get(x, y);
    }

    ll getSpiral(int x, int y) {
        int dx       = x - cx;
        int dy       = y - cy;
        int r        = max(abs(dx), abs(dy));
        int roundedR = r / gap * gap;
        int add      = 4 * roundedR * (roundedR - gap) / gap;
        if(r % gap != 0 || (dx == r && dy == -r)) return add + 8 * roundedR + r % gap;
        if(dx == r) return add + r + dy;
        if(dy == r) return add + 3 * r - dx;
        if(dx == -r) return add + 5 * r - dy;
        if(dy == -r) return add + 7 * r + dx;
        assert(false);
    }

    bool isOnSparseLine(int x, int y) {
        int dx = abs(x - cx);
        int dy = abs(y - cy);
        int r  = max(dx, dy);
        if(r > maxr) return false;
        if(dy % gap == 0 && cx - dy <= x && x <= cx + dy + (y <= cy) * gap) return true;
        if(dx % gap == 0 && cy - dx + (x > cx) * gap <= y && y <= cy + dx) return true;
        return false;
    }

    ll answer() override {
        if(inwards) {
            auto x = cx;
            auto y = cy;
            if(mirror) x = n - 1 - x;
            if(transpose) swap(x, y);
            return get(x, y);
        } else {
            return get(finishx, finishy);
        }
    }
};