#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<long long>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;
const int MODE = 1e9+7;
struct Matrix {
ll n;
vii a;
Matrix(ll n) : n(n), a(n, vi(n, INT32_MAX)) {}
Matrix operator*(const Matrix &b) const {
Matrix c(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[i][k] != INT32_MAX && b.a[k][j] != INT32_MAX)
c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]) % MODE;
}
}
}
return c;
}
};
void solve(int tc) {
ll k, n, m, q;
cin >> k >> n >> m >> q;
vector<vector<Matrix>> X(18, vector<Matrix>(n, Matrix(k)));
for (int i = 0; i < m; i++)
{
ll u, v, w; cin >> u >> v >> w;
X[0][u/k].a[u%k][v%k] = w;
}
for (int j = 1; j < 18; j++)
{
for (int i = 0; i < n; i++)
{
if ((i+(1<<(j-1))) >= n) continue;
X[j][i] = X[j-1][i] * X[j-1][i+(1<<(j-1))];
}
}
while (q--)
{
ll l, r; cin >> l >> r;
ll lvl1 = l / k, lvl2 = r / k;
if (l == r) cout << "0\n";
else if (lvl1>=lvl2) cout << "-1\n";
else {
Matrix res(k);
res.a[l%k][l%k] = 1;
ll p = lvl2-lvl1;
ll at = l/k;
for (int i = 0; i < p; i++)
{
if (p & (1<<i)) {
res = res * X[i][at];
at += 1<<i;
}
}
ll sol = res.a[l%k][r%k];
if (sol == INT32_MAX) cout << "-1\n";
else cout << sol - 1 << '\n';
}
}
}
signed main()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int size = 1;
// freopen("lazy.in", "r", stdin);
// freopen("lazy.out", "w", stdout);
// cin >> size;
for (int i = 1; i <= size; i++) solve(i);
return 0;
}
