#include <bits/stdc++.h>

using namespace std;

mt19937 gen(time(0));

vector<vector<int32_t>> previous(4, vector<int32_t> (4, 0));

bool have_moves(vector<vector<int32_t>> &a) {
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t j = 0; j < 4; ++j) {
            if (a[i][j] == 0) {
                return true;
            }
        }
    }
    for (int32_t i = 0; i < 3; ++i) {
        for (int32_t j = 0; j < 3; ++j) {
            if (a[i][j] == a[i][j + 1] || a[i][j] == a[i + 1][j]) {
                return true;
            }
        }
    }
    return false;
}

void add(vector<vector<int32_t>> &a) {
    vector<pair<int32_t, int32_t>> zero;
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t j = 0; j < 4; ++j) {
            if (a[i][j] == 0) {
                zero.push_back(make_pair(i, j));
            }
        }
    }
    int32_t id = gen() % (zero.size());
    int32_t value = gen() % 6;
    if (value == 5) {
        value = 4;
    } else {
        value = 2;
    }
    a[zero[id].first][zero[id].second] = value;
    return;
}

bool zero_down(vector<vector<int32_t>> &a) {
    bool change = false;
    for (int32_t j = 0; j < 4; ++j) {
        vector<int32_t> id_not_zero;
        for (int32_t i = 0; i < 4; ++i) {
            if (a[i][j] != 0) {
                id_not_zero.push_back(a[i][j]);
            }
        }
        for (int32_t i = 3; i >= 0; --i) {
            if (id_not_zero.size() > 0) {
                if (a[i][j] != id_not_zero[id_not_zero.size() - 1]) {
                    change = true;
                }
                a[i][j] = id_not_zero[id_not_zero.size() - 1];
                id_not_zero.pop_back();
            } else {
                a[i][j] = 0;
            }
        }
    }
    return change;
}

bool zero_up(vector<vector<int32_t>> &a) {
    bool change = false;
    for (int32_t j = 0; j < 4; ++j) {
        vector<int32_t> id_not_zero;
        for (int32_t i = 0; i < 4; ++i) {
            if (a[i][j] != 0) {
                id_not_zero.push_back(a[i][j]);
            }
        }
        for (int32_t i = 0; i < 4; ++i) {
            if (id_not_zero.size() > 0) {
                if (a[i][j] != id_not_zero[id_not_zero.size() - 1]) {
                    change = true;
                }
                a[i][j] = id_not_zero[0];
                reverse(id_not_zero.begin(), id_not_zero.end());
                id_not_zero.pop_back();
                reverse(id_not_zero.begin(), id_not_zero.end());
            } else {
                a[i][j] = 0;
            }
        }
    }
    return change;
}

bool zero_right(vector<vector<int32_t>> &a) {
    bool change = false;
    for (int32_t i = 0; i < 4; ++i) {
        vector<int32_t> id_not_zero;
        for (int32_t j = 0; j < 4; ++j) {
            if (a[i][j] != 0) {
                id_not_zero.push_back(a[i][j]);
            }
        }
        for (int32_t j = 3; j >= 0; --j) {
            if (id_not_zero.size() > 0) {
                if (a[i][j] != id_not_zero[id_not_zero.size() - 1]) {
                    change = true;
                }
                a[i][j] = id_not_zero[id_not_zero.size() - 1];
                id_not_zero.pop_back();
            } else {
                a[i][j] = 0;
            }
        }
    }
    return change;
}

bool zero_left(vector<vector<int32_t>> &a) {
    bool change = false;
    for (int32_t i = 0; i < 4; ++i) {
        vector<int32_t> id_not_zero;
        for (int32_t j = 0; j < 4; ++j) {
            if (a[i][j] != 0) {
                id_not_zero.push_back(a[i][j]);
            }
        }
        for (int32_t j = 0; j < 4; ++j) {
            if (id_not_zero.size() > 0) {
                if (a[i][j] != id_not_zero[id_not_zero.size() - 1]) {
                    change = true;
                }
                a[i][j] = id_not_zero[0];
                reverse(id_not_zero.begin(), id_not_zero.end());
                id_not_zero.pop_back();
                reverse(id_not_zero.begin(), id_not_zero.end());
            } else {
                a[i][j] = 0;
            }
        }
    }
    return change;
}

bool sum_down(vector<vector<int32_t>> &a) {
    bool change = zero_down(a);
    for (int32_t j = 0; j < 4; ++j) {
        for (int32_t i = 3; i > 0; --i) {
            if (a[i][j] == a[i - 1][j]) {
                if (a[i][j] != 0) {
                    a[i][j] *= 2;
                    a[i - 1][j] = 0;
                    change = true;
                }
            }
        }
    }
    bool change1 = zero_down(a);
    return (change1 || change);
}

bool sum_up(vector<vector<int32_t>> &a) {
    bool change = zero_up(a);
    for (int32_t j = 0; j < 4; ++j) {
        for (int32_t i = 0; i < 3; ++i) {
            if (a[i][j] == a[i + 1][j]) {
                if (a[i][j] != 0) {
                    a[i][j] *= 2;
                    a[i + 1][j] = 0;
                    change = true;
                }
            }
        }
    }
    bool change1 = zero_up(a);
    return (change1 || change);
}

bool sum_right(vector<vector<int32_t>> &a) {
    bool change = zero_right(a);
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t j = 3; j > 0; --j) {
            if (a[i][j] == a[i][j - 1]) {
                if (a[i][j] != 0) {
                    a[i][j] *= 2;
                    a[i][j - 1] = 0;
                    change = true;
                }
            }
        }
    }
    bool change1 = zero_right(a);
    return (change1 || change);
}

bool sum_left(vector<vector<int32_t>> &a) {
    bool change = zero_left(a);
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t j = 0; j < 3; ++j) {
            if (a[i][j] == a[i][j + 1]) {
                if (a[i][j] != 0) {
                    a[i][j] *= 2;
                    a[i][j + 1] = 0;
                    change = true;
                }
            }
        }
    }
    bool change1 = zero_left(a);
    return (change1 || change);
}

void print(vector<vector<int32_t>> &a, bool cls) {
    if (cls) {
        system("cls");
    }
    for (int32_t k = 0; k < 4; ++k) {
        cout << "\n";
    }
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t k = 0; k < 7; ++k) {
            cout << ' ';
        }
        for (int32_t j = 0; j < 4; ++j) {
            cout << a[i][j];
            for (int32_t k = 0; k < 8 - to_string(a[i][j]).size(); ++k) {
                cout << ' ';
            }
        }
        cout << "\n" << "\n";
    }
}

bool win(vector<vector<int32_t>> &a) {
    for (int32_t i = 0; i < 4; ++i) {
        for (int32_t j = 0; j < 4; ++j) {
            if (a[i][j] >= 2048) {
                return true;
            }
        }
    }
    return false;
}

bool cls = true;
void game(vector<vector<int32_t>> &a) {
    print(a, cls);
    char c;
    cin >> c;
    bool change;
    vector<vector<int32_t>> prev = a;
    if (c == 'w') {
        change = sum_up(a);
    } else if (c == 'a') {
        change = sum_left(a);
    } else if (c == 's') {
        change = sum_down(a);
    } else if (c == 'd') {
        change = sum_right(a);
    }
    bool check = false;
    if (c == 'r') {
        a = previous;
        check = true;
    }
    if (!check) {
        if (!change) {
            cls = false;
            system("cls");
            cout << "Please, make another move\n";
            game(a);
        } else {
            previous = prev;
            cls = true;
        }
    }
    if (win(a)) {
        system("cls");
        cout << "You won\n";
        cls = false;
    }
    if (!check) {
        add(a);
    }
}

int main() {
    vector<vector<int32_t>> a(4, vector<int32_t> (4, 0));
    add(a);
    previous = a;
    while (have_moves(a)) {
        game(a);
    }
    cout << "Lose :-(\n";
    return 0;
}