#include "validate.h"
#include <regex>

using namespace std;

bool read_solution(istream &in, int s, vector<int> &result, feedback_function feedback) {
    string first;
    if (!(in >> first)) {
        feedback("Failed to read first token");
    }
    transform(first.begin(), first.end(), first.begin(), ::tolower);
    if (first == "impossible")
        return false;

    result.resize(s);
    stringstream firsts(first);
    for (int i = 0; i < s; ++i) {
        if (!((i ? in : firsts) >> result[i])) {
            feedback("First token not 'impossible' and token %d/%d not an integer", i+1, s);
        }
    }
    return true;
}

pair<int, vector<int>> check_solution(int n, int m, int d,
                                      const vector<int> &c, const vector<int> &r,
                                      feedback_function feedback) {
    int slots_filled = 0, new_sodas = 0, old_sodas = 0;
    vector<int> cold_remaining;
    for (int i = 0; i < c.size(); ++i) {
        if (r[i] < 0 || r[i] > d - c[i])
            feedback("Slot %d: can't put %d sodas here, must be in range [%d, %d]\n",
                     i+1, r[i], 0, d-c[i]);
        if (r[i]) {
            ++slots_filled;
            new_sodas += r[i];
        } else if (c[i]) {
            cold_remaining.push_back(c[i]);
            old_sodas += c[i];
        }
    }
    if (new_sodas != n) {
        feedback("Wrong number of sodas added to machine, was %d should be %d\n", new_sodas, n);
    }
    if (old_sodas < m) {
        feedback("Too few old sodas still available, only %d need at least %d\n", old_sodas, m);
    }
    // Additional sodas after the m'th one in a slot do not help
    for (int &x: cold_remaining)
        x = min(x, m);
    sort(cold_remaining.begin(), cold_remaining.end());
    return make_pair(slots_filled, cold_remaining);
}

int main(int argc, char **argv) {
    init_io(argc, argv);

    int n, m, s, d;
    judge_in >> n >> m >> s >> d;

    vector<int> c(s);
    for (int &x: c) judge_in >> x;

    vector<int> ans, out;
    bool judge_poss = read_solution(judge_ans, s, ans, judge_error);
    bool sol_poss = read_solution(cin, s, out, wrong_answer);

    if (sol_poss) {
        auto out_sol = check_solution(n, m, d, c, out, wrong_answer);
        if (!judge_poss)
            judge_error("Output found a solution but answer file says impossible");
        auto ans_sol = check_solution(n, m, d, c, ans, judge_error);
        if (ans_sol != out_sol) {
            wrong_answer("Suboptimal solution");
        }
    } else { // output file says "impossible"
        if (judge_poss)
            wrong_answer("Solution claims impossible but solution exists");
    }

    string trash;
    if (cin >> trash) {
        wrong_answer("Correct solution but trailing output");
    }

    accept();
}