Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Cho dù là học sinh cuối cấp và đang ở rất gần kỳ thi THPT Quốc gia, nhưng Thùy Trang có cho mình cách riêng để giải trí: sau khi làm bài tập mỗi tối, cô lên tầng thượng nhà mình để ngắm sao.

Hãy giả định bầu trời là một hệ tọa độ phẳng Oxy, và luôn cố định trên bầu trời là n ngôi sao, ngôi sao thứ i luôn nằm ở tọa độ (x[i], y[i]), và ở một mốc-thời-điểm-0 cố định do Trang quy ước, ngôi sao đó sẽ có độ sáng s[i].

Độ sáng của mỗi ngôi sao là không cố định, nhưng sẽ không âm và không bao giờ vượt quá một giá trị c nhất định. Tức là, với mọi i thỏa mãn 1 <= i <= n, 0 <= s[i] <= c.

Cụ thể hơn:

• Ở mốc-thời-điểm-0, ngôi sao thứ i chắc chắn sẽ có độ sáng s[i].

• Ở một thời điểm bất kỳ, ngôi sao thứ i sẽ có độ sáng cố định là t. Ở thời điểm kế tiếp, độ sáng sẽ chuyển thành (t+1) nếu giá trị này không vượt quá c, nếu không độ sáng sẽ về 0.

Còn q ngày nữa là đến kỳ thi THPT Quốc gia, và Trang dự định mỗi ngày sẽ lên sân thượng ngắm sao một lần.

Với lần ngắm sao thứ i, Trang sẽ chỉ ngắm sao trong một vùng trên bầu trời: vùng này có dạng một hình chữ nhật với các cạnh song song với các trục tọa độ, điểm dưới trái có tọa độ (x1[i], y1[i]) điểm trên phải có tọa độ (x2[i], y2[i]).

Trang muốn với mỗi lần ngắm sao, cô đều có thể chứng kiến khoảnh khắc mảng trời trong đôi mắt cô bừng sáng nhất. Và cô tự hỏi, với mỗi lần như thế, tổng độ sáng tối đa của những ngôi sao trong vùng trời cô quan sát sẽ là bao nhiêu. Ở đây, một ngôi sao thuộc một vùng trời nếu nó nằm trên các cạnh giới hạn hoặc nằm bên trong vùng đó.

Các bạn hãy giúp Trang nhé! <3

Input

Dòng đầu tiên chứa 3 số nguyên n, q, c (1 ≤ n, q ≤ 131072, 1 ≤ c ≤ 16) – số ngôi sao trên trời, số ngày Trang ngắm sao và mức độ sáng tối đa của các ngôi sao.

n dòng tiếp theo chứa thông tin về các ngôi sao: dòng thứ i trong n dòng gồm 3 số nguyên x[i], y[i], s[i] (1 ≤ x[i], y[i] ≤ 128, 0 ≤ s[i] ≤ c ≤ 16) — tọa độ và độ sáng tại mốc-thời-điểm-0 của ngôi sao thứ i.

q dòng tiếp theo mô tả q lần ngắm sao của Trang: dòng thứ i trong q dòng gồm 4 số nguyên x1[i], y1[i], x2[i], y2[i] (1 ≤ x1[i] < x2[i] ≤ 128, 1 ≤ y1[i] < y2[i] ≤ 128) – tọa độ các điểm giới hạn vùng trời.

Output

Với mỗi lần ngắm sao, in ra trên 1 dòng 1 số nguyên duy nhất là giá trị lớn nhất của tổng độ sáng của các ngôi sao trên vùng trời được xét.

Example

Input:
2 3 3
1 1 1
3 2 0
1 1 2 2
2 1 4 5
1 1 5 5
Output:
3
3
5

Input:
3 4 5
1 1 2
2 3 0
3 3 1
1 1 100 100
2 2 4 4
2 1 4 7
50 50 51 51
Output:
12
9
9
0

Giải thích test 1:
• Vào ngày đầu tiên, Trang chỉ có thể nhìn thấy ngôi sao đầu tiên. Hiển nhiên độ sáng tối đa của vùng trời sẽ bằng với độ sáng tối đa của ngôi sao đó, và bằng 3.
• Vào ngày thứ hai, Trang chỉ có thể nhìn thấy ngôi sao thứ hai. Hiển nhiên độ sáng tối đa của vùng trời sẽ bằng với độ sáng tối đa của ngôi sao đó, và bằng 3.
• Vào ngày thứ ba, Trang có thể thấy cả 2 ngôi sao. Vùng trời Trang quan sát sẽ sáng nhất vào một số thời điểm, chẳng hạn như thời điểm 6 – khi đó ngôi sao thứ nhất có độ sáng là 3, và ngôi sao thứ hai có độ sáng là 2 – như vậy kết quả cuối cùng sẽ là 5.