Trong vương quốc JOI có ~N~ thành phố, được đánh số từ ~1~ đến ~N~. Có ~N - 1~ con đường trong vương quốc JOI, được đánh số từ ~1~ đến ~N - 1~. Con đường thứ ~i~ (~1 \le i \le N - 1~) nối thành phố ~A_i~ và thành phố ~B_i~ theo cả hai hướng. Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách đi qua một số con đường.

Trên một số con đường trong vương quốc JOI có các trạm kiểm tra. Có ~M~ trạm kiểm tra, được đánh số từ ~1~ đến ~M~. Trạm kiểm tra thứ ~j~ (~1 \le j \le M~) nằm trên con đường ~P_j~. Để đi qua trạm kiểm tra đó, bạn cần trả một đồng vàng hoặc ~C_j~ đồng bạc.

Có ~Q~ công dân trong vương quốc JOI, được đánh số từ ~1~ đến ~Q~. Công dân thứ ~k~ (~1 \le k \le Q~) có ~X_k~ đồng vàng và ~Y_k~ đồng bạc, và muốn đi từ thành phố ~S_k~ đến thành phố ~T_k~. Vì đồng vàng có giá trị, tất cả công dân đều muốn giữ nhiều đồng vàng nhất có thể.

Hãy viết một chương trình, cho thông tin về các thành phố, con đường, các trạm kiểm tra và các công dân trong vương quốc JOI, với mỗi ~k~ (~1 \le k \le Q~), xác định xem công dân thứ ~k~ có thể đi từ thành phố ~S_k~ đến thành phố ~T_k~ không, và nếu có thể, tính toán số đồng vàng tối đa mà công dân thứ ~k~ có thể giữ.

Input

Dòng đầu tiên chứa ba số nguyên ~N~, ~M~, ~Q~ lần lượt là số thành phố, số trạm kiểm tra và số công dân trong vương quốc JOI (~2 \le N \le 100000~, ~1 \le M, Q \le 100000~).

~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i~ và ~B_i~ mô tả một con đường hai chiều (~1 \le A_i, B_i \le N~).

~M~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~P_j~ và ~C_j~ mô tả một trạm kiểm tra (~1 \le P_j \le N - 1~, ~1 \le C_j \le 10^9~).

~Q~ dòng cuối cùng, dòng thứ ~k~ chứa bốn số nguyên ~S_k~, ~T_k~, ~X_k~, ~Y_k~ mô tả mộ công dân (~1 \le S_k, T_k \le N~, ~S_k \neq T_k~, ~0 \le X_k \le 10^9~, ~0 \le Y_k \le 10^{18}~).

Output

In ra ~Q~ dòng. Trên dòng thứ ~k~ (~1 \le k \le Q~), nếu công dân thứ ~k~ có thể đi từ thành phố ~S_k~ tới thành phố ~T_k~, in ra số lượng đồng vàng nhiều nhất công dân thứ ~k~ có thể giữ. Ngược lại, in ra ~-1~ trên dòng thứ ~k~.

Scoring

Sample Input 1

5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1

Sample Output 1

1
2
-1

Sample Input 2

10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3

Sample Output 2

3
6
6
7
7
3
1
2
2

Sample Input 3

8 7 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
7 1 5 55
3 1 6 8
8 2 5 45
4 6 4 45
6 1 3 33
2 1 0 19
3 7 2 31
7 1 2 31
7 2 4 58
8 3 5 63

Sample Output 3

7
5
5
5
4
2
0
2
1
4
5

Sample Input 4

8 7 11
1 8
1 4
3 1
3 6
6 7
2 1
5 2
5 5
5 8
4 7
6 6
4 1
6 4
1 7
4 7 2 18
2 4 5 1
4 2 1 32
1 5 7 21
2 5 0 50
8 4 4 33
1 7 6 16
4 8 7 18
1 2 8 13
5 4 10 42
7 1 6 40

Sample Output 4

1
3
1
7
0
4
5
7
8
10
6

Notes

Trong ví dụ thứ nhất:

Công dân ~1~ có thể đi từ thành phố ~3~ đến thành phố ~4~ như sau:

1. Công dân ~1~ đi từ thành phố ~3~ đến thành phố ~1~ qua con đường ~2~. Có trạm kiểm tra ~1~ và ~2~ trên con đường ~2~. Công dân ~1~ trả ~1~ đồng vàng cho trạm kiểm tra ~1~ và ~4~ đồng bạc cho trạm kiểm tra ~2~. Sau đó, công dân ~1~ còn lại ~1~ đồng vàng và ~7~ đồng bạc.

2. Công dân ~1~ đi từ thành phố ~1~ đến thành phố ~2~ qua con đường ~1~. Vì không có trạm kiểm tra nào trên đường nên công dân ~1~ còn lại ~1~ đồng vàng và ~7~ đồng bạc.

3. Công dân ~1~ đi từ thành phố ~2~ tới thành phố ~4~ qua con đường ~3~. Có trạm kiểm tra ~3~ trên con đường ~3~. Công dân ~1~ trả ~5~ đồng bạc cho trạm kiểm tra ~3~. Sau đó, công dân ~1~ còn lại ~1~ đồng vàng và ~2~ đồng bạc.

Sau khi di chuyển, công dân ~1~ còn lại ~1~ đồng vàng. Vì không có cách để công dân ~1~ có thể di chuyển và giữ lại nhiều hơn ~1~ đồng vàng, in ra ~1~ ở dòng đầu tiên.

Công dân ~2~ có thể đi từ thành phố ~5~ đến thành phố ~3~ như sau:

1. Công dân ~2~ đi từ thành phố ~5~ đến thành phố ~2~ qua con đường ~4~. Có trạm kiểm tra ~4~ trên con đường ~4~. Công dân ~2~ trả ~1~ đồng vàng cho trạm kiểm tra ~4~. Sau đó, công dân ~2~ còn lại ~3~ đồng vàng và ~5~ đồng bạc.

2. Công dân ~2~ đi từ thành phố ~2~ đén thành phố ~1~ qua con đường ~1~. Vì không có trạm kiểm tra nào trên đường nên công dân ~2~ còn lại ~3~ đồng vàng và ~5~ đồng bạc.

3. Công dân ~2~ đi từ thành phố ~1~ đến thành phố ~3~ qua con đường ~2~. Có trạm kiểm tra ~1~ và ~2~ trên con đường ~2~. Công dân ~2~ trả ~1~ đồng vàng cho trạm kiểm tra ~1~ và ~4~ đồng bạc cho trạm kiểm tra ~2~. Sau đó, công dân ~2~ còn lại ~2~ đồng vàng và ~1~ đồng bạc.

Sau khi di chuyển, công dân ~2~ còn lại ~2~ đồng vàng. Vì không có cách để công dân ~2~ có thể di chuyển và giữ lại nhiều hơn ~2~ đồng vàng, in ra ~2~ ở dòng thứ hai.

Không có cách nào để công dân ~3~ có thể đi từ thành phố ~2~ đến thành phố ~3~ với lượng tiền đang có, in ra ~-1~ ở dòng thứ ba.