#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#define hyathu main
#define popcorn __builtin_popcount
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int mmb = 5e4 + 69;
const ld pi = atan(1) * 4;
int n, q, m, k, a, b;
ll d[mmb][15][5];
void readData(){
cin >> k >> n >> m >> q;
fill(d[0][0], d[n + 1][0], 4e18);
int x, y;
ll w;
for(int i = 1; i <= m; ++i){
cin >> x >> y >> w;;
y %= k;
d[x][0][y] = min(d[x][0][y], w);
}
}
void solve(){
for(int j = 1; j <= 14; ++j){
for(int i = 0; i < n; ++i){
if(i / k + (1 << j) > n / k) break;
int ly = i / k + (1 << (j - 1));
for(int nx = 0; nx < k; ++nx){
for(int bt = 0; bt < k; ++bt)
d[i][j][nx] = min(d[i][j][nx], d[i][j - 1][bt] + d[ly * k + bt][j - 1][nx]);
}
}
}
while(q--){
cin >> a >> b;
int la = a / k;
int lb = b / k;
int step = 14;
ll mn[5], nx[5];
fill(mn, mn + k, 4e18);
fill(nx, nx + k, 4e18);
mn[a % k] = 0;
while(step >= 0){
if(la + (1 << step) <= lb){
int nl = la + (1 << step);
for(int i = 0; i < k; ++i){
for(int j = 0; j < k; ++j)
nx[j] = min(nx[j], mn[i] + d[la * k + i][step][j]);
}
copy(nx, nx + k, mn);
la = nl;
fill(nx, nx + k, 4e18);
}
--step;
}
cout << (mn[b % k] == 4e18 ? -1 : mn[b % k]) << "\n";
}
}
#define filename "test"
int hyathu(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifdef dangheo
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#else
//freopen(filename".INP", "r", stdin);
//freopen(filename".OUT", "w", stdout);
#endif
readData();
solve();
return 0;
}
