#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "k"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1e5 + 9;
struct Station{
int pos_edge;
int fee_silver;
Station(int pos_edge = 0, int fee_silver = 0):
pos_edge(pos_edge), fee_silver(fee_silver){}
};
struct Query{
int start, destination, silver, gold;
Query(int start = 0, int destination = 0, int silver = 0, int gold = 0):
start(start), destination(destination), silver(silver), gold(gold){}
};
int n, m, q;
vector<int> g[MAXN]; ii edge[MAXN];
vector<pair<int, Query>> SetQuery;
vector<Station> SetStation;
map<int, vector<int>> mp;
namespace sub1{
int par[MAXN], depth[MAXN];
void dfs(int u,int p){
for(auto e: g[u]){
int v = edge[e].fi + edge[e].se - u;
if (v == p) continue;
par[v] = e;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int getpath(int u,int v,int gold,int silver){
vector<int> path;
int sum = 0;
while(u != v){
// cerr << u << ' ' << v << endl;
if (depth[u] < depth[v]) swap(u, v);
int edge_to_p = par[u];
if (mp[edge_to_p].size() != 0){
for(auto v: mp[edge_to_p]){
path.pb(v);
sum += v;
}
}
u = edge[edge_to_p].fi + edge[edge_to_p].se - u;
}
sum = 0;
for(auto x: path){
sum += x;
}
sort(path.begin(), path.end());
int cnt = 0;
while(sum > silver and path.size() > 0){
cnt++;
sum -= path.back();
path.pop_back();
}
return max(gold - cnt, -1LL);
}
void solve(){
dfs(1, -1);
// for(int i = 1; i <= n; i++){
// cout << depth[i] << ' ' << par[i] << endl;
// }
for(int i = 0; i < q; i++){
int u = SetQuery[i].se.start;
int v = SetQuery[i].se.destination;
int golden = SetQuery[i].se.gold;
int silver = SetQuery[i].se.silver;
cout << getpath(u, v, golden, silver) << endl;
}
}
}
struct segtree{
vector<int> st, lazy;
int sz;
void init(int _sz){
sz = _sz;
st.resize(sz * 4 + 9);
}
void reset(){
fill(st.begin(), st.end(), 0);
}
void update(int node,int l,int r,int pos,int x){
if (l == r){
st[node] += x;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(node << 1, l, mid, pos, x);
else update(node << 1 | 1, mid + 1, r, pos, x);
st[node] = st[node << 1] + st[node << 1 | 1];
}
void update(int u,int x){
update(1, 0, sz - 1, u, x);
}
int getsum(int u,int v){
return getsum(1, 0, sz - 1, u, v);
}
int getsum(int node,int l,int r,int u,int v){
if (l >= u and r <= v){
return st[node];
}
if (l > v or r < u) return 0;
int mid = (l + r) >> 1;
return getsum(node << 1, l, mid, u, v)
+ getsum(node << 1 | 1, mid + 1, r, u, v);
}
};
namespace sub4{
int sz[MAXN], depth[MAXN], par[MAXN];
void precalc(int u,int p){
sz[u] = 1;
for(auto e: g[u]){
int v = edge[e].fi + edge[e].se - u;
if (v == p) continue;
depth[v] = depth[u] + 1;
par[v] = u;
precalc(v, u);
sz[u] += sz[v];
}
}
vector<int> etour;
int HeadChain[MAXN], IdChain[MAXN], in[MAXN], out[MAXN], PosOnChain[MAXN], NumChain;
void buildHLD(int u,int p,int curchain){
PosOnChain[u] = etour.size();
IdChain[u] = curchain;
if (etour.size() > 0 and IdChain[etour.back()] != curchain){
HeadChain[curchain] = u;
}
else if (etour.size() == 0) HeadChain[curchain] = u;
in[u] = etour.size();
etour.pb(u);
int bigchild = -1;
for(auto e: g[u]){
int v = edge[e].fi + edge[e].se - u;
if (v == p) continue;
if (bigchild == -1 or sz[bigchild] < sz[v]){
bigchild = v;
}
}
if (bigchild != -1) buildHLD(bigchild, u, curchain);
for(auto e: g[u]){
int v = edge[e].fi + edge[e].se - u;
if (v == p or v== bigchild) continue;
buildHLD(v, u, ++NumChain);
}
}
vector<int> listvalue;
unordered_map<int, int> TransferValue;
int lo[MAXN], hi[MAXN], MinimumWeightQuery[MAXN], NumNode[MAXN], Sum[MAXN], NumStationOn[MAXN], answer[MAXN];
vector<int> checkQuery[MAXN];
segtree st_numw, st_sumw;
ii getsum(int u,int v){
ii res = {0, 0}; //res.fi: sum
//res.se: num
while(IdChain[u] != IdChain[v]){
if (depth[HeadChain[IdChain[u]]] < depth[HeadChain[IdChain[v]]]){
swap(u, v);
}
// cout << "LEO: " << u << ' ' < PosOnChain[HeadChain[IdChain[u]]] << ' ' << IdChain;
res.fi += st_sumw.getsum(PosOnChain[HeadChain[IdChain[u]]], PosOnChain[u]);
res.se += st_numw.getsum(PosOnChain[HeadChain[IdChain[u]]], PosOnChain[u]);
u = par[HeadChain[IdChain[u]]];
}
if (depth[u] > depth[v]) swap(u, v);
res.fi += st_sumw.getsum(PosOnChain[u] + 1, PosOnChain[v]);
res.se += st_numw.getsum(PosOnChain[u] + 1, PosOnChain[v]);
return res;
}
void parallel_binary_search(int n){
for(int i = 0; i < q; i++){
lo[i] = 0, hi[i] = listvalue.size() - 1;
}
// for(int i = 0; i < n; i++){
// cout << listvalue[i] << ' ';
// }
// cout << endl;
sort(SetStation.begin(), SetStation.end(), [&](const Station &a, const Station &b){
return a.fee_silver < b.fee_silver;
});
st_sumw.init(n);
st_numw.init(n);
while(true){
st_numw.reset();
st_sumw.reset();
bool check = false;
for(int i = 0; i < listvalue.size(); i++){
checkQuery[i].clear();
}
for(int i = 0; i < q; i++){
if (lo[i] > hi[i]) {
continue;
}
int mid = (lo[i] + hi[i]) >> 1;
checkQuery[mid].pb(i);
check = true;
// cout << lo[i] << ' ' << hi[i] << endl;
}
// cout << endl;
if (!check) break;
int ptr = -1;
for(int i = 0; i < listvalue.size(); i++){
while(ptr + 1 < m and SetStation[ptr + 1].fee_silver < listvalue[i]){
ptr++;
int IdEdge = SetStation[ptr].pos_edge;
int u = edge[IdEdge].fi;
int v = edge[IdEdge].se;
int fee = SetStation[ptr].fee_silver;
if (depth[u] < depth[v]) swap(u, v);
// cout << i << ' ' << "STATION: " << u << ' ' << fee << endl;
st_sumw.update(in[u], fee);
st_numw.update(in[u], 1);
}
// ii p = getsum(3, 4);
// cout << p.fi << ' ' << p.se << endl;
for(auto idQuery: checkQuery[i]){
int u = SetQuery[idQuery].se.start;
int v = SetQuery[idQuery].se.destination;
int silver = SetQuery[idQuery].se.silver;
ii sumpath = getsum(u, v);
if (sumpath.fi <= silver){
lo[idQuery] = i + 1;
MinimumWeightQuery[idQuery] = i;
Sum[idQuery] = sumpath.fi;
NumNode[idQuery] = sumpath.se;
}
else{
hi[idQuery] = i - 1;
}
}
}
}
}
vector<int> Categorizing[MAXN], Event[MAXN];
int getval(int x){
return lower_bound(listvalue.begin(), listvalue.end(), x) - listvalue.begin();
}
void getans(){
// for(int i = 0; i < q; i++){
// cout << MinimumWeightQuery[i] << ' ' << Sum[i] << ' ' << NumNode[i] << endl;
// }
for(int i = 0; i < q; i++){
Categorizing[MinimumWeightQuery[i]].pb(i);
}
for(int i = 0; i < m; i++){
Event[SetStation[i].fee_silver].pb(i);
}
st_numw.reset();
for(int i = 0; i < m; i++){
int idedge = SetStation[i].pos_edge;
int u = edge[idedge].fi;
int v = edge[idedge].se;
if (depth[u] < depth[v]) swap(u, v);
st_numw.update(in[u], 1);
}
for(int i = 0; i < q; i++){
int u = SetQuery[i].se.start;
int v = SetQuery[i].se.destination;
NumStationOn[i] = getsum(u, v).se;
}
st_numw.reset();
for(int i = 0; i < listvalue.size(); i++){
for(auto idstation: Event[i]){
int idedge = SetStation[idstation].pos_edge;
int u = edge[idedge].fi;
int v = edge[idedge].se;
if (depth[u] < depth[v]) swap(u, v);
st_numw.update(in[u], 1);
}
for(auto x: Categorizing[i]){
if (i == listvalue.size() - 1) answer[x] = SetQuery[x].second.gold;
else{
int already_built = Sum[x];
int u = SetQuery[x].se.destination;
int v = SetQuery[x].se.start;
int left = SetQuery[x].second.silver - already_built;
int usedgold = NumStationOn[x] - NumNode[x];
usedgold -= left / listvalue[i];
answer[x] = max(SetQuery[x].se.gold - usedgold, -1LL);
}
}
for(auto idstation: Event[i]){
int idedge = SetStation[idstation].pos_edge;
int u = edge[idedge].fi;
int v = edge[idedge].se;
if (depth[u] < depth[v]) swap(u, v);
st_numw.update(in[u], -1);
}
}
for(int i = 0; i < q; i++){
cout << answer[i] << endl;
}
}
void solve(){
for(auto station: SetStation){
listvalue.pb(station.fee_silver);
}
listvalue.pb(INF + 1);
sort(listvalue.begin(), listvalue.end());
listvalue.erase(unique(listvalue.begin(), listvalue.end()), listvalue.end());
for(int i = 0; i < listvalue.size(); i++){
TransferValue[listvalue[i]] = i;
}
precalc(1, -1);
buildHLD(1, -1, ++NumChain);
// for(int i = 1; i <= n; i++){
// cout << in[i] << ' ' << par[i] << ' ' << depth[i] << ' ' << i << endl;
// }
// for(auto x: etour){
// cout << x << ' ';
// }
// cout << endl;
// for(int i = 1; i <= NumChain; i++){
// cout << HeadChain[i] << ' ';
// }
// cout << endl;
parallel_binary_search(n);
getans();
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
edge[i] = {u, v};
g[u].pb(i);
g[v].pb(i);
}
for(int i = 0; i < m; i++){
int node, fee = 0;
cin >> node >> fee;
SetStation.pb(Station(node, fee));
mp[node].pb(fee);
}
for(int i = 0 ; i < q; i++){
int u, v, silver, gold;
cin >> u >> v >> gold >> silver;
SetQuery.pb({i, Query(u, v, silver, gold)});
}
sub4::solve();
}
