#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int inf = 1e10 + 1e5;
int K;
struct spm
{
vector<vector<int>> M;
spm(int dim, int initVal, int diagVal)
{
M = vector<vector<int>> (dim, vector<int> (dim, initVal));
for(int i = 0; i < dim; i ++)
M[i][i] = diagVal;
}
inline int dim()
{
return M.size();
}
};
spm operator + (spm L, spm R)
{
int dim = L.dim();
spm ans(dim, 0, 0);
for(int i = 0; i < dim; i ++)
{
for(int j = 0; j < dim; j ++)
{
int cur = L.M[i][0] + R.M[0][j];
for(int k = 1; k < dim; k ++)
{
int newVal = L.M[i][k] + R.M[k][j];
cur = cur < newVal ? cur : newVal;
}
ans.M[i][j] = cur;
}
}
return ans;
}
struct bst
{
vector<spm> a;
int N;
int offs;
bst(vector<spm> initArray)
{
int n = initArray.size();
N = 2;
while (N < 2 * n + 4)
N *= 2;
offs = N / 2 + 1;
a = vector<spm> (N, spm(K, inf, inf));
for(int i = 0; i < n; i ++)
a[i + offs] = initArray[i];
for(int i = offs - 2; i > 0; i --)
a[i] = a[2 * i] + a[2 * i + 1];
}
spm sum(int i, int j)
{
int L = i + offs - 1;
int R = j + offs + 1;
spm Lans(K, inf, (int)0);
spm Rans(K, inf, (int)0);
while (true)
{
bool Lright = L % 2 == 0;
bool Rleft = R % 2 == 1;
L /= 2;
R /= 2;
if (L == R)
break;
if (Lright)
Lans = Lans + a[2 * L + 1];
if (Rleft)
Rans = a[2 * R] + Rans;
}
return Lans + Rans;
}
};
signed main()
{
int N, M, O;
cin >> K >> N >> M >> O;
vector<spm> initArray(N / K, spm(K, inf, inf));
for (int i = 0; i < M; i ++)
{
int a, b, t;
cin >> a >> b >> t;
initArray[a / K].M[a % K][b % K] = t;
}
bst T(initArray);
for (int i = 0; i < O; i ++)
{
int a, b;
cin >> a >> b;
if(a / K >= b / K)
cout << "-1\n";
else
{
spm ans = T.sum(a / K, b / K - 1);
cout << (ans.M[a % K][b % K] < inf ? ans.M[a % K][b % K] : -1) << '\n';
}
}
}
