#include <iostream>
#include <vector>
using namespace std;
const int N=5e4;
vector<pair<int,int>> ma[N];
vector<int> MinDist[N];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int k,n,m,q;
cin>>k>>n>>m>>q;
// q<=1e4
for(int i=0;i<n;i++)
{
MinDist[i].push_back(0);
for(int j=i+1;j<n;j++)
MinDist[i].push_back(1e9);
}
for(int j=0;j<m;j++)
{
int a,b,t;
cin>>a>>b>>t;
ma[a].push_back({b,t});
}
for(int i=n-2;i>=0;i--)
{
for(int j=i+1;j<=n;j++)
{
for(auto [l,w]:ma[i])
{
MinDist[i][j-i]=min(MinDist[i][j-i],MinDist[l][j-l]+w);
}
}
}
while(q--)
{
int x,y;
cin>>x>>y;
if(x<=y)
{
if(MinDist[x][y-x]==1e9)
cout<<-1<<'\n';
else
cout<<MinDist[x][y-x]<<'\n';
}
else
{
cout<<-1<<'\n';
}
}
return 0;
}
