/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.6.0"
+/

import std.stdio, std.algorithm, std.range, std.conv, std.string;
import std.container, std.random;
import core.stdc.stdlib : exit;

// import dcomp.scanner;

immutable DEBUG = 0;

Scanner sc;
static this() {
    sc = new Scanner(stdin);
}

int h, w, n, md;
DataBase d;

struct S {
    int y, c;
}


int[] search(int l, int r, S[] v, int co) {
//    assert(co == d.query(l, v[0].y, r, v[$-1].y+1));
    if (v.length == 1) {
        return [co];
    }
    if (co == 0) {
        return repeat(0).take(v.length).array;
    }
    if (co == v.map!(s => min(s.c, r-l)).sum) {
        return v.map!(s => min(s.c, r-l)).array;
    }
    int md = v.length.to!int / 2;
    int u = d.query(l, v[0].y, r, v[md].y);
    assert(u <= co);
    return search(l, r, v[0..md], u) ~ search(l, r, v[md..$], co-u);
}

void solve() {
    S[][] st = new S[][](1000);
    int[] lv = new int[1000], rv = new int[1000];
    lv[1] = 0; rv[1] = w;
    iota(h).each!(y => st[1] ~= S(y, d.query(0, y, w, y+1)));
    foreach (ph, v; st[0..$]) {
        int l = lv[ph], r = rv[ph];
        int md = (l+r)/2;

        S[] v2;
        foreach (s; v) {
            if (s.c == 0) continue;
            if (s.c == r-l) {
                iota(l, r).each!(i => d.fix(i, s.y));
                continue;
            }
            v2 ~= s;
        }
        v = v2;
        if (v.length == 0) continue;
        assert(r-l > 1);

        lv[2*ph] = l;
        rv[2*ph] = md;
        lv[2*ph+1] = md;
        rv[2*ph+1] = r;

        v.sort!"a.y < b.y";
        auto li = search(l, md, v, d.query(l, 0, md, h));
        assert(v.length == li.length);
        foreach (i, s; v) {
            int nc = li[i];
//            assert(nc == d.query(l, s.y, md, s.y+1));
//            int nc = d.query(l, s.y, md, s.y+1);
            st[2*ph] ~= S(s.y, nc);
            st[2*ph+1] ~= S(s.y, s.c-nc);
        }
    }
/*    foreach (i; 0..h) {
        dfs(0, w, i, d.query(0, i, w, i+1));        
    }*/
}

int main() {
    if (!DEBUG) {
        sc.read(h, w, n, md);
        d = new Data();
    } else {
        h = 50;
        w = 50;
        n = 250;
        d = new DataRandom();
    }

    d.first();
    solve();
    d.answer();

    return 0;
}

class DataBase {
    void first() {
        g = new bool[][](h, w);
        sm = new int[][](h+1, w+1);        
    }
    int query(int ax, int ay, int bx, int by) { return 0; }
    void answer() {}
        
    bool[][] g;
    int[][] sm;
    final void calcSm() {
        foreach (i; 0..h) {
            foreach (j; 0..w) {
                sm[i+1][j+1] = sm[i+1][j] + sm[i][j+1] - sm[i][j];
                if (g[i][j]) sm[i+1][j+1]++;
            }
        }
    }
    final void fix(int x, int y) {
        assert(!g[y][x]);
        g[y][x] = true;
        calcSm();
    }
}

class DataRandom : DataBase {
    bool[][] ans;
    int[][] ansSm;
    int co;
    override void first() {
        super.first();
        ans = new bool[][](h, w);

        int[2][] buf;
        foreach (y; 0..h) {
            foreach (x; 0..w) {
                buf ~= [x, y];
            }
        }

        foreach (e; buf.randomSample(n)) {
            ans[e[1]][e[0]] = true;
        }
        ansSm = new int[][](h+1, w+1);
        foreach (y; 0..h) {
            foreach (x; 0..w) {
                ansSm[y+1][x+1] = ansSm[y+1][x] + ansSm[y][x+1] - ansSm[y][x];
                if (ans[y][x]) ansSm[y+1][x+1]++;
            }
        }
    }
    override int query(int ax, int ay, int bx, int by) {
        int p = queryBase(ax, ay, bx, by);
        int q;
        q += sm[by][bx];
        q -= sm[by][ax];
        q -= sm[ay][bx];
        q += sm[ay][ax];
        int q2 = 0;
        foreach (y; ay..by) {
            foreach (x; ax..bx) {
                if (g[y][x]) q2++;
            }
        }
        assert(q == q2);
        return p - q;
    }
    bool[int[4]] mp;
    int queryBase(int ax, int ay, int bx, int by) {
        int[4] key = [ax, ay, bx, by];
        if (key !in mp) {
            mp[key] = true;
            co++;
        }
        int q;
        q += ansSm[by][bx];
        q -= ansSm[by][ax];
        q -= ansSm[ay][bx];
        q += ansSm[ay][ax];
        return q;
    }
    override void answer() {
        bool ok = true;
        foreach (i; 0..h) {
            foreach (j; 0..w) {
                if (g[i][j] != ans[i][j]) {
                    ok = false;
                }
            }
        }
        if (ok) {
            writeln("AC! ", co);
        } else {
            writeln("WA...");
        }
    }    
}

class Data : DataBase {
    override int query(int ax, int ay, int bx, int by) {
        int p = queryBase(ax, ay, bx, by);
        int q;
        q += sm[by][bx];
        q -= sm[by][ax];
        q -= sm[ay][bx];
        q += sm[ay][ax];
        return p - q;
    }
    int[int[4]] mp;
    int queryBase(int ax, int ay, int bx, int by) {
        int[4] key = [ax, ay, bx, by];
        if (key in mp) return mp[key];
        writefln("? %d %d %d %d", ay, ax, by-1, bx-1);
        stdout.flush;
        int p;
        sc.read(p);
        return mp[key] = p;
    }
    override void answer() {
        long res = 0;
        long base = 1;
        foreach (i; 0..h) {
            foreach (j; 0..w) {
                if (g[i][j]) res = (res+base) % md;
                base = 2*base % md;
            }
        }
        writeln("! ", res);
        stdout.flush;
    }
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    char[512] lineBuf;
    char[] line;
    private bool succ() {
        import std.range.primitives : empty, front, popFront;
        import std.ascii : isWhite;
        while (true) {
            while (!line.empty && line.front.isWhite) {
                line.popFront;
            }
            if (!line.empty) break;
            if (f.eof) return false;
            line = lineBuf[];
            f.readln(line);
        }
        return true;
    }

    private bool readSingle(T)(ref T x) {
        import std.algorithm : findSplitBefore;
        import std.string : strip;
        import std.conv : parse;
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                //string or char[10] etc
                //todo optimize
                auto r = line.findSplitBefore(" ");
                x = r[0].strip.dup;
                line = r[1];
            } else {
                auto buf = line.split.map!(to!E).array;
                static if (isStaticArray!T) {
                    //static
                    assert(buf.length == T.length);
                }
                x = buf;
                line.length = 0;
            }
        } else {
            x = line.parse!T;
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}



unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    fout.writeln("1 2 3");
    fout.writeln("ab cde");
    fout.writeln("1.0 1.0 2.0");
    fout.close;
    Scanner sc = new Scanner(File(fileName, "r"));
    int a;
    int[2] b;
    char[2] c;
    string d;
    double e;
    double[] f;
    sc.read(a, b, c, d, e, f);
    assert(a == 1);
    assert(equal(b[], [2, 3]));
    assert(equal(c[], "ab"));
    assert(equal(d, "cde"));
    assert(e == 1.0);
    assert(equal(f, [1.0, 2.0]));
}

unittest {
    import std.path : buildPath;
    import std.file : tempDir;
    import std.algorithm : equal;
    import std.stdio : File, writeln;
    import std.datetime;
    string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
    auto fout = File(fileName, "w");
    foreach (i; 0..1_000_000) {
        fout.writeln(3*i, " ", 3*i+1, " ", 3*i+2);
    }
    fout.close;
    writeln("Scanner Speed Test(3*1,000,000 int)");
    StopWatch sw;
    sw.start;
    Scanner sc = new Scanner(File(fileName, "r"));
    foreach (i; 0..500_000) {
        int a, b, c;
        sc.read(a, b, c);
        assert(a == 3*i);
        assert(b == 3*i+1);
        assert(c == 3*i+2);
    }
    foreach (i; 500_000..700_000) {
        int[3] d;
        sc.read(d);
        int a = d[0], b = d[1], c = d[2];
        assert(a == 3*i);
        assert(b == 3*i+1);
        assert(c == 3*i+2);
    }
    foreach (i; 700_000..1_000_000) {
        int[] d;
        sc.read(d);
        assert(d.length == 3);
        int a = d[0], b = d[1], c = d[2];
        assert(a == 3*i);
        assert(b == 3*i+1);
        assert(c == 3*i+2);
    }
    writeln(sw.peek.msecs, "ms");
}


Measured memory_bytes: 976