#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 50007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
ll k, n, m, q, dp[M][6][20][6];
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> k >> n >> m >> q;
for(int i = 0; i <= n / k; ++i) for(int j = 0; j <= k; ++j) for(int bit = 0; bit < 20; ++bit) for(int j2 = 0; j2 <= k; ++j2) dp[i][j][bit][j2] = inf;
for(int i = 1; i <= m; ++i){
int a, b, c;
cin >> a >> b >> c;
dp[a / k][a % k][0][b % k] = c;
}
for(int j = 1; j < 20; ++j)
for(int i = 0; i + (1 << j) <= n / k + 1; ++i)
for(int from = 0; from < k; ++from)
for(int to = 0; to < k; ++to)
for(int mid = 0; mid < k; ++mid)
dp[i][from][j][to] = min(dp[i][from][j][to], dp[i][from][j - 1][mid] + dp[i + (1 << (j - 1))][mid][j - 1][to]);
while(q--){
int a, b;
cin >> a >> b;
vector <ll> ans;
for(int i = 0; i < k; ++i) ans.pb(inf);
int cur = a / k;
ans[a % k] = 0;
for(int j = 20; j >= 0; --j){
if(cur + (1 << j) > b / k) continue;
vector <ll> nxt;
for(int i = 0; i < k; ++i) nxt.pb(inf);
for(int from = 0; from < k; ++from) for(int to = 0; to < k; ++to) nxt[to] = min(nxt[to], ans[from] + dp[cur][from][j][to]);
cur += (1 << j);
ans = nxt;
}
if(ans[b % k] >= inf) cout << -1 << endl;
else cout << ans[b % k] << endl;
}
return 0;
}
