You are given a sparse matrix of dimensions N x M. There K cells in the matrix {(x1, y1), (x2, y2) ... (xK, yK)} with non-zero values {v1, v2 ... vK}. All the other cells except these K cells contain value = 0. You are asked Q queries of the form sx sy fx fy, you need to print the sum of submatrix bounded by (sx, sy) and (fx, fy).

Input

First line contains two space separated integers N, M. (1 <= N, M <= 10^9)

Second line contains the integer K (1 <= K <= 10^5)

Next K lines contain three space separated integers xi, yi, vi. (1 <= xi <= N, 1 <= yi <= M, 1 <= vi <= 10^9).

Next line contains Q. (1 <= Q <= 10^5)

Next Q lines contain four space separated integers sx, sy, fx, fy. (1 <= sx <= fx <= N, 1 <= sy <= fy <= M).

Output

For each query, print a single integer representing the sum of submatrix.

Example

Input:
10 10 
2
1 1 5
2 2 15
1
1 1 3 3

Output:
20