Toll Upsol

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int INF = 0x3f3f3f3f;
array<array<int, 6>, MAXN> Dist;
array<bool, MAXN> Marc;
array<vector<pair<int, int>>, MAXN> grafo;
int K, N, M, O;

void bfs(int nivel, int nivelFim)
{
    Marc.fill(0);
    queue<int> q;
    for (int k = 0, v = nivel*K; k < K; k++, v++)
    {
        Dist[v][k] = 0;
        q.push(v);
        Marc[v] = 1;
    }

    while (!q.empty())
    {
        int cur = q.front(); q.pop();
        // if (cur/K > nivelFim) break;
        for (auto [viz, p] : grafo[cur])
        {
            for (int k = 0; k < K; k++)
            {
                Dist[viz][k] = min(Dist[viz][k], Dist[cur][k] + p);
            }
            if (!Marc[viz]) {q.push(viz); Marc[viz] = 1;}
        }
    }
}

bool cmp(tuple<int, int, int> a, tuple<int, int, int> b)
{
    if (((get<0>(a))/K) == ((get<0>(b))/K)) return get<1>(a) > get<1>(b);
    return get<0>(a) < get<0>(b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> K >> N >> M >> O;
    for (int i = 1; i <= M; i++)
    {
        int X, Y, P;
        cin >> X >> Y >> P;
        grafo[X].emplace_back(Y, P);
    }
    Dist.fill({INF, INF, INF, INF, INF, INF});

    vector<tuple<int, int, int> > queries;
    for (int i = 0; i < O; i++)
    {
        int X, Y;
        cin >> X >> Y;
        queries.emplace_back(X, Y, i);
    }
    sort(queries.begin(), queries.end(), cmp);

    vector<int> resp(O); int lastNivel = -1;
    for (auto [X, Y, id] : queries)
    {
        // cerr << '\r' << X << " " << Y << " " << id;
        if (X/K >= Y/K) {resp[id] = -1; continue;}
        if (lastNivel < (X/K)) {bfs((X/K)+1, N/K); lastNivel = (X/K)+1;}
        if (lastNivel == (X/K)+1)
        {
            resp[id] = INF;
            for (auto [viz, p] : grafo[X]) resp[id] = min(resp[id], Dist[Y][viz%K] + p);
            if (resp[id] >= INF) resp[id] = -1;
        }
        else if (lastNivel == (X/K)) resp[id] = (Dist[Y][X%K] >= INF ? -1 : Dist[Y][X%K]);
    }

    for (auto x : resp) cout << x << '\n';
}