#include <bits/stdc++.h>
using namespace std ;
const int inf = 2e9 ;
const int MAX = 5e4 + 10 ;
int arr[MAX][5] ;
int k , n , m , q ;
int dist[MAX][17][5][5] , ans[5] , tmp[5] ;
void preprocess()
{
for(int j = 1 ; j < 17 ; ++j)
{
for(int i = 0 ; i <= n/k ; ++i)
{
for(int k1 = 0 ; k1 < k ; ++k1)
{
for(int k2 = 0 ; k2 < k ; ++k2)
{
int jump = (1 << j) ;
if((i + jump) * k + k2 >= n)
continue ;
dist[i][j][k1][k2] = inf ;
int prv_jump = (1 << (j-1)) ;
for(int k3 = 0 ; k3 < k ; ++k3)
{
if(dist[i][j-1][k1][k3] && dist[i+prv_jump][j-1][k3][k2])
dist[i][j][k1][k2] = min(dist[i][j][k1][k2] , dist[i][j-1][k1][k3] + dist[i + prv_jump][j-1][k3][k2]) ;
}
if(dist[i][j][k1][k2] == inf)
dist[i][j][k1][k2] = 0 ;
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>k>>n>>m>>q ;
for(int i = 0 ; i < m ; ++i)
{
int x , y , z ;
cin>>x>>y>>z ;
dist[x/k][0][x%k][y%k] = z ;
}
preprocess() ;
while(q--)
{
memset(ans , -1 , sizeof(ans)) ;
int x , y ;
cin>>x>>y ;
int a = x/k , b = y/k ;
ans[x%k] = 0 ;
for(int j = 16 ; j >= 0 ; --j)
{
if((a + (1 << j)) > b)
continue ;
for(int k1 = 0 ; k1 < k ; ++k1)
tmp[k1] = ans[k1] ;
for(int k2 = 0 ; k2 < k ; ++k2)
{
ans[k2] = -1 ;
for(int k1 = 0 ; k1 < k ; ++k1)
{
if(dist[a][j][k1][k2] && tmp[k1] != -1)
{
if(ans[k2] == -1)
ans[k2] = dist[a][j][k1][k2] + tmp[k1] ;
else
ans[k2] = min(ans[k2] , dist[a][j][k1][k2] + tmp[k1]) ;
}
}
}
a += (1 << j) ;
}
cout<<ans[y%k]<<"\n" ;
}
return 0 ;
}
