#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct min_matrix{
int ysize;
int xsize;
vector<vector<int>> data;
min_matrix(){}
min_matrix(int x, int y, int init) : ysize(y), xsize(x), data(ysize){
for (auto &i : data)
i = vector<int>(xsize, init);
}
min_matrix operator*(const min_matrix& other) const{
min_matrix result(other.xsize, ysize, inf);
for (int from = 0; from < xsize; from++)
{
for (int to = 0; to < xsize; to++)
{
for (int mid = 0; mid < xsize; mid++)
{
result.data[to][from] = min(result.data[to][from], data[mid][from] + other.data[to][mid]);
}
}
}
return result;
}
};
template<class T>
struct sparse_table
{
vector<vector<T>> data;
function<T(const T&, const T&)> op;
sparse_table(){}
sparse_table(function<T(const T&, const T&)> op, int sz, T* arr) : op(op){
data.emplace_back(vector(arr, arr+sz));
int block_size = 2;
int j = 1;
while (block_size < sz){
data.emplace_back(sz);
for (int begin = 0; begin < sz; begin+=2*block_size)
{
int center = min(sz-1, begin+block_size-1);
data[j][center] = arr[center];
for (int i = center - 1; i >= begin; i--)
{
data[j][i] = op(arr[i], data[j][i+1]);
}
if (center != sz - 1)
data[j][center+1] = arr[center+1];
for (int i = center+2; i < min(center+block_size+1, sz); i++)
{
data[j][i] = op(data[j][i-1], arr[i]);
}
}
block_size *= 2;
j++;
}
}
min_matrix query(int l, int r){
if (l == r)
return data[0][l];
int layer = -1;
int t = l ^ r;
while (t){
layer++;
t >>= 1;
}
return op(data[layer][l], data[layer][r]);
}
};
void solve(){
int k, n, m, q;
cin >> k >> n >> m >> q;
vector<min_matrix> data_for_table(n/k, min_matrix(k, k, inf));
for (int i = 0; i < m; i++)
{
int a, b, cost;
cin >> a >> b >> cost;
data_for_table[a/k].data[b%k][a%k] = cost;
}
sparse_table<min_matrix> table([](const min_matrix& l, const min_matrix& r){return l*r;}, data_for_table.size(), data_for_table.data());
for (int i = 0; i < q; i++)
{
int a, b;
cin >> a >> b;
if (b/k <= a/k){
cout << "-1\n";
continue;
}
int result = table.query(a/k, b/k-1).data[b%k][a%k];
if (result == inf){
result = -1;
}
cout << result << '\n';
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int t = 1;
for (int i = 0; i < t; i++)
{
solve();
}
}
