Railguns

#include <bits/stdc++.h>
using namespace std;
//Mudar para submeter
const int MAXN = 1e3 + 10;
const int MAXSZ = 10;
const int INF = 0x3f3f3f3f;
array<array<set<int>, MAXN>, MAXN> Chegam;
array<set<int>, MAXN> lin, col;

void updateChegam(int start, int x, int y, set<int> &resp)
{
    int limLin = *lin[x].lower_bound(start);
    int limCol = *col[y].lower_bound(start);
    for (int i = start; i <= min(limLin,limCol) && resp.size() <= MAXSZ; i++) resp.insert(i);
}

void solve()
{
    int N, M;
    cin >> N >> M;
    int R;
    cin >> R;
    for (int i = 0; i < R; i++)
    {
        int T, dir, X;
        cin >> T >> dir >> X;
        if (dir == 1) lin[X].insert(T);
        else if (dir == 2) col[X].insert(T);
    }
    for (int i = 0; i <= N; i++) lin[i].insert(INF);
    for (int i = 0; i <= M; i++) col[i].insert(INF);

    updateChegam(0, 0, 0, Chegam[0][0]);

    // cerr << "||" << 0 << " " << 0 << '\n' << "|||";
    // for (auto x : Chegam[0][0]) cerr << x << " ";
    // cerr << '\n';

    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (i == 0 && j == 0) continue;
            auto &resp = Chegam[i][j];
            if (i != 0)
            {
                auto &cheg = Chegam[i-1][j];
                for (auto x : cheg) resp.insert(x+1);
            }
            if (j != 0)
            {
                auto &cheg = Chegam[i][j-1];
                for (auto x : cheg) resp.insert(x+1);
            }
            for (auto x : lin[i]) resp.erase(x);
            for (auto x : col[j]) resp.erase(x);
            if (!resp.empty()) updateChegam(*resp.rbegin(), i, j, resp);
            // cerr << "||" << i << " " << j << '\n' << "||";
            // for (auto x : resp) cerr << x << " ";
            // cerr << '\n';
        }
    }

    if (Chegam[N][M].empty()) {cout << "-1" << '\n'; return;}

    cout << *Chegam[N][M].begin() << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) solve();
}