MAH có sở thích ngắm sao. Hôm nay anh ấy thấy n ngôi sao trên bầu trời, ngôi sao thứ i có tọa độ (xi, yi) và độ sáng tối đa là c, và độ sáng ban đầu của các ngôi sao là si(0 <= si <= c).

Ở thời điểm ban đầu (t = 0), ngôi sao thứ có độ sáng si. Nếu ở thời điểm t một ngôi sao có độ sáng là x thì thời điểm (t + 1) ngôi sao này có độ sáng là x + 1 khi x + 1 <= c và có độ sáng 0 trong trường hợp còn lại.

MAH muốn nhìn bầu trời q lần. Trong lần thứ i anh ấy sẽ nhìn vào thời điểm ti và anh ấy sẽ nhìn một hình chữ nhật có các cạnh song song với trục tọa độ, góc trên bên trái là \((x_1i, y_1i)\) và góc dưới bên phải là \((x_2i, y_2i)\). Mỗi lần nhìn, anh ấy muốn biết tổng độ sáng của tất các các ngôi sao nằm trong hình chữ nhật (có thể nằm trên đường viền).

Input

Dòng đầu gồm 3 số nguyên n, q, c (1 ≤ n, q ≤ 10^5, 1 ≤ c ≤ 10) biểu diễn số ngôi sao, số lần nhìn, và độ sáng tối đa của các ngôi sao.

N dòng tiếp theo biểu diễn các ngôi sao. Dòng thứ i chứa 3 số nguyên xi, yi, si (1 ≤ xi, yi ≤ 100, 0 ≤ si ≤ c ≤ 10) biểu diễn tọa độ của ngôi sao thứ i và độ sáng ban đầu.

Q dòng tiếp theo mỗi dòng chữa 5 số nguyên \(t_i, x_1i, y_1i, x_2i, y_2i\) \((0 ≤ t_i ≤ 10^9, 1 ≤ x_1i < x_2i ≤ 100, 1 ≤ y_1i < y_2i ≤ 100)\) biểu diễn thời điểm nhìn và tọa độ của hình chữ nhật.

Output

Mỗi dòng in tổng độ sáng trong mỗi lần nhìn.

Example

Input

2 6 5
40 6 4
60 48 4
17 4 1 47 38
16 2 5 66 14
18 3 2 72 74
19 1 4 68 26
15 1 3 8 53
12 1 3 69 59

Output

3
2
8
5
0
8