#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 50010
using namespace std;
int n, m, k, q;
//map<pair<pii, pii>, int> dp;
int w[MAXN][6], ress[MAXN];
/*int resi(int a, int b, int x, int y)
{
if (dp[{{a, b}, {x, y}}]) return dp[{{a, b}, {x, y}}];
if ((a+1)==b) return 1000000010;
int mid=a+(b-a)/2;
int ress=1000000010;
for (int i=0; i<k; i++)
{
ress=min(ress, resi(a, mid, x, i)+resi(mid, b, i, y));
}
dp[{{a, b}, {x, y}}]=ress;
return ress;
}*/
int main(){
cin>>k>>n>>m>>q;
for (int i=0; i<n; i++) for (int j=0; j<k; j++) w[i][j]=1000000010;
for (int i=0; i<m; i++)
{
int u, v, t; cin>>u>>v>>t;
w[u][v%k]=t;
}
while (q--)
{
int x, y; cin>>x>>y;
for (int i=x; i<=y; i++) ress[i]=1000000010;
ress[x]=0;
for (int i=x; i<(y/k)*k; i++)
{
for (int j=0; j<k; j++)
{
ress[((i/k)+1)*k+j]=min(ress[((i/k)+1)*k+j], ress[i]+w[i][j]);
//cout<<i<<" do "<<((i/k)+1)*k+j<<" kosta "<<ress[((i/k)+1)*k+j]<<endl;
}
}
if (ress[y]>=1000000010) cout<<-1<<"\n";
else cout<<ress[y]<<"\n";
}
}
