#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 5e4 + 7 ;
const int inf = 1e9 ;
int k , n , m , q ;
struct node {
int len ;
int dp[ 5 ][ 5 ] ;
node ( ) {
len = 0 ;
for ( int i = 0 ; i < k ; ++ i ) {
for ( int j = 0 ; j < k ; ++ j ) {
dp[ i ][ j ] = inf ;
}
}
}
};
node mv[ MAXN ] ;
node unite ( node p1 , node p2 ) {
if ( p1.len == 0 ) { return p2 ; }
if ( p2.len == 0 ) { return p1 ; }
node ret = node ( ) ;
ret.len = p1.len + p2.len ;
for ( int i = 0 ; i < k ; ++ i ) {
for ( int j = 0 ; j < k ; ++ j ) {
for ( int t = 0 ; t < k ; ++ t ) {
ret.dp[ i ][ t ] = min ( ret.dp[ i ][ t ] , p1.dp[ i ][ j ] + p2.dp[ j ][ t ] ) ;
}
}
}
return ret ;
}
class Tree {
public :
node tr[ 4 * MAXN ] ;
void init ( int where , int IL , int IR ) {
if ( IL == IR ) {
tr[ where ] = mv[ IL ] ;
tr[ where ].len = 1 ;
return ;
}
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}
node query ( int where , int IL , int IR , int CURL , int CURR ) {
if ( IL > IR || CURL > CURR ) { return node ( ) ; }
if ( IR < CURL || CURR < IL ) { return node ( ) ; }
if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
int mid = ( IL + IR ) / 2 ;
return unite ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
}
};
Tree w ;
void solve ( ) {
cin >> k >> n >> m >> q ;
for ( int i = 0 ; i <= n ; ++ i ) {
mv[ i ] = node ( ) ;
}
for ( int i = 1 , x , y , c ; i <= m ; ++ i ) {
cin >> x >> y >> c ;
int wh = ( x / k ) ;
x %= k , y %= k ;
mv[ wh + 1 ].dp[ x ][ y ] = min ( mv[ wh + 1 ].dp[ x ][ y ] , c ) ;
}
int mx = ( n - 1 ) / k + 1 ;
w.init ( 1 , 1 , mx ) ;
while ( q -- ) {
int x , y ; cin >> x >> y ;
if ( ( x / k ) >= ( y / k ) ) {
cout << "-1\n" ;
continue ;
}
node aux = w.query ( 1 , 1 , mx , ( x / k ) + 1 , ( y / k ) ) ;
x %= k , y %= k ;
if ( aux.dp[ x ][ y ] == inf ) { cout << "-1\n" ; }
else { cout << aux.dp[ x ][ y ] << "\n" ; }
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
