#include <bits/stdc++.h>
using namespace std;
#define forw(i,a,b) for(ll i=a;i<=b;i++)
#define forb(i,a,b) for(ll i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
#define getnum(i) (1<<(i))
#define minimize(a,b) ()
typedef long long int ll;
const ll maxN=1e6+5;
const ll mod=1e9+7;
const ll oo=1e18;
ll k,n,m,q,d[maxN][17][6],tmp[6],ans[6];
void solve()
{
cin>>k>>n>>m>>q;
// init
// d[u][i][v] : position i ; go through 2^i blocks ; destination k*(u/k+2^i) + v
forw(u,0,n-1)
forw(i,0,16)
forw(v,0,k-1)
d[u][i][v]=oo;
// read
forw(i,1,m)
{
int u,v,val;cin>>u>>v>>val;
d[u][0][v%k]=val;
}
// sparse
forb(u,n-1,0)
{
forw(i,1,16)
forw(pos,0,k-1)
forw(v,0,k-1)
d[u][i][v]=min(d[u][i][v],d[u][i-1][pos]+d[pos+k*(u/k+getnum(i-1))][i-1][v]);
}
// query
while (q--)
{
int l,r; cin>>l>>r;
int blocks=r/k - l/k; blocks--;
forw(i,0,k-1) ans[i]=d[l][0][i];
int cnt=l/k+1;
forw(i,0,16)
if (blocks & getnum(i))
{
forw(u,0,k-1) tmp[u]=oo;
forw(u,0,k-1)
forw(v,0,k-1)
tmp[v]=min(tmp[v],ans[u]+d[u+cnt*k][i][v]);
forw(u,0,k-1) ans[u]=tmp[u];
cnt+=getnum(i);
}
if (ans[r%k]==oo) cout<<-1<<"\n";
else cout<<ans[r%k]<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("bruh.inp","r",stdin);
//freopen("bruh.out","w",stdout);
solve();
return 0;
}
