#include <iostream>
#include <vector>

/* Utility functions for writing output validators for the Kattis
 * problem format.
 *
 * The primary functions and variables available are the following.
 * In many cases, the only functions needed are "init_io",
 * "wrong_answer", and "accept".
 *
 * - init_io(argc, argv):
 *        initialization
 *
 * - judge_in, judge_ans, author_out:
 *        std::istream objects for judge input file, judge answer
 *        file, and submission output file.
 *
 * - accept():
 *        exit and give Accepted!
 *
 * - accept_with_score(double score):
 *        exit with Accepted and give a score (for scoring problems)
 *
 * - judge_message(std::string msg, ...):
 *        printf-style function for emitting a judge message (a
 *        message that gets displayed to a privileged user with access
 *        to secret data etc).
 *
 * - wrong_answer(std::string msg, ...):
 *        printf-style function for exitting and giving Wrong Answer,
 *        and emitting a judge message (which would typically explain
 *        the cause of the Wrong Answer)
 *
 * - judge_error(std::string msg, ...):
 *        printf-style function for exitting and giving Judge Error,
 *        and emitting a judge message (which would typically explain
 *        the cause of the Judge Error)
 *
 * - author_message(std::string msg, ...):
 *        printf-style function for emitting an author message (a
 *        message that gets displayed to the author of the
 *        submission).  (Use with caution, and be careful not to let
 *        it leak information!)
 *
 */
#pragma once

#include <sys/stat.h>
#include <cassert>
#include <cstdarg>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>

typedef void (*feedback_function)(const std::string &, ...);

const int EXITCODE_AC = 42;
const int EXITCODE_WA = 43;
const std::string FILENAME_AUTHOR_MESSAGE = "teammessage.txt";
const std::string FILENAME_JUDGE_MESSAGE = "judgemessage.txt";
const std::string FILENAME_JUDGE_ERROR = "judgeerror.txt";
const std::string FILENAME_SCORE = "score.txt";

#define USAGE "%s: judge_in judge_ans feedback_dir < author_out\n"

std::ifstream judge_in, judge_ans;
std::istream author_out(std::cin.rdbuf());

char *feedbackdir = NULL;

void vreport_feedback(const std::string &category,
                      const std::string &msg,
                      va_list pvar) {
    std::ostringstream fname;
    if (feedbackdir)
        fname << feedbackdir << '/';
    fname << category;
    FILE *f = fopen(fname.str().c_str(), "a");
    assert(f);
    vfprintf(f, msg.c_str(), pvar);
    fclose(f);
}

void report_feedback(const std::string &category, const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(category, msg, pvar);
}

void author_message(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_AUTHOR_MESSAGE, msg, pvar);
}

void judge_message(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_JUDGE_MESSAGE, msg, pvar);
}

void wrong_answer(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    std::cerr << msg << "\n";
    vreport_feedback(FILENAME_JUDGE_MESSAGE, msg, pvar);
    exit(EXITCODE_WA);
}

void judge_error(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_JUDGE_ERROR, msg, pvar);
    assert(0);
}

void accept() {
    exit(EXITCODE_AC);
}

void accept_with_score(double scorevalue) {
    report_feedback(FILENAME_SCORE, "%.9le", scorevalue);
    exit(EXITCODE_AC);
}


bool is_directory(const char *path) {
    struct stat entry;
    return stat(path, &entry) == 0 && S_ISDIR(entry.st_mode);
}

void init_io(int argc, char **argv) {
    if(argc < 4) {
        fprintf(stderr, USAGE, argv[0]);
        judge_error("Usage: %s judgein judgeans feedbackdir [opts] < userout", argv[0]);
    }

    // Set up feedbackdir first, as that allows us to produce feedback
    // files for errors in the other parameters.
    if (!is_directory(argv[3])) {
        judge_error("%s: %s is not a directory\n", argv[0], argv[3]);
    }
    feedbackdir = argv[3];

    judge_in.open(argv[1], std::ios_base::in);
    if (judge_in.fail()) {
        judge_error("%s: failed to open %s\n", argv[0], argv[1]);
    }

    judge_ans.open(argv[2], std::ios_base::in);
    if (judge_ans.fail()) {
        judge_error("%s: failed to open %s\n", argv[0], argv[2]);
    }

    author_out.rdbuf(std::cin.rdbuf());
}

using namespace std;
const int MAX_MOVES = 10000;

int read(int lo, int hi, string s) {
    int x;
    author_out >> x;
    if (x < lo || x > hi) {
        wrong_answer("value for " + s + " out of range");
    }
    return x;
}

void check_acceptable(vector<int> &perm, int idx, int m) {
    int c = idx%m;
    if (c > 0) {
        if (perm[idx-1] > perm[idx]) {
            wrong_answer("unacceptable permutation");
        }
    }
    if (c+1 < m) {
        if (perm[idx+1] < perm[idx]) {
            wrong_answer("unacceptable permutation");
        }
    }
}

bool check_case() {
    int r, c;
    judge_in >> r >> c;
    vector<int> start, end;
    for (int i = 0; i < r*c; i++) {
        int x;
        judge_in >> x;
        start.push_back(x);
    }
    for (int i = 0; i < r*c; i++) {
        int x;
        judge_in >> x;
        end.push_back(x);
    }
  

  int k = read(0,MAX_MOVES,"k");
  for (int i = 0; i < k; i++) {
    int r1 = read(1,r,"r1"), c1 = read(1,c,"c1"), r2 = read(1,r,"r2"), c2 = read(1,c,"c2");

    if (r1 == r2 && c1 == c2) {
      wrong_answer("(r1,c1) == (r2,c2)");
    }
    int id1 = (r1-1)*c + c1-1, id2 = (r2-1)*c + c2-1;
    int t = start[id1]; start[id1] = start[id2]; start[id2] = t;
    check_acceptable(start, id1, c);
    check_acceptable(start, id2, c);
  }
  for (int i = 0; i < r*c; i++) {
    if (start[i] != end[i]) {
      wrong_answer("incorrect permutation");
    }
  }
  return true;
}


int main(int argc, char **argv) {
    init_io(argc, argv);
    if(!check_case()) {
        wrong_answer("returned false");
    }

    /* Check for trailing output. */
    string trash;
    if (author_out >> trash) {
        wrong_answer("Trailing output");
    }

    accept();
}