Sau một cuộc thí nghiệm, MH khám phá ra $n$ loài sinh vật mới. Sinh vật thứ $i$ có độ nguy hiểm $a_i$ và chi phí cách ly là $b_i$, với mỗi $i<j$ thì $a_i\le a_j$ và $b_i\ge b_j$. Cô ấy cần cách ly $n$ sinh vật này, tuy nhiên, vì vấn đề kinh phí, MH sẽ phải cách ly những sinh vật này thành từng nhóm liên tiếp nhau từ trái sang phải. Chi phí để cách ly một nhóm sinh vật với $i$ là sinh vật đầu nhóm, $j$ là sinh vật cuối nhóm là $a_i\ast b_j+b_i^2\ast a_j^2$. Vì trước giờ chỉ học mỗi sinh nên MH không biết phải chia nhóm như nào để tốn ít chi phí nhất, các bạn hãy giúp cô ấy nhé!</p>

INPUT

• Dòng đầu tiên gồm $1$ số nguyên dương $n(n\le {10}^6)$ .
• Dòng thứ hai gồm $n$ số nguyên dương $a_i(a_i\le {10}^6)$ .
• Dòng thứ ba gồm $n$ số nguyên dương $b_i(b_i\le {10}^3)$.

OUTPUT

• Một số nguyên dương duy nhất là chi phí tối thiểu.

Sample Input

7
2 5 5 8 13 15 19
20 17 15 7 4 4 4

Sample Output

17960

Subtask

• Subtask 1: $b_i=1$ (7p)
• Subtask 2: $n\le {10}^3$ (28p)
• Subtask 3: $n\le {10}^6$ (35p)

Giải thích

• 1 cách chia nhóm để có chi phí là 17960, chia làm 4 nhóm :
• Nhóm 1 bao gồm 1 với chi phí là 1640
• Nhóm 2 bao gồm 2-> 3 với chi phí là 7300
• Nhóm 3 bao gồm 4 với chi phí là 3192
• Nhóm 4 bao gồm 5->7 với chi phí là 5828
• 1640+7300+3192+5828=17960

Sau chuyến thị sát quanh vương quốc, MH phát hiện rằng hệ thống thu thuế của vương quốc đang không hoạt động hiệu quả và làm thất thoát lượng lớn thuế của vương quốc. Vì vậy, cô quyết định thiết lập lại hệ thống thu thuế, mở đầu bằng việc thống kê. Vương quốc Poinciana là một vùng đất hình chữ nhật kéo dài từ $(0,0)$ đến $(W,H)$ trên mặt phẳng tọa độ. Bên trong vương quốc bao gồm $n$ lãnh địa quý tộc và $m$ thành phố. Lãnh địa quý tộc thứ i là một mảnh đất hình chữ nhật kéo dài từ $(X_i,Y_i)$ đến $(A_i,B_i)(X_i<A_i,Y_i<B_i)$. 2 cạnh bất kì của các lãnh địa không có điểm chung với nhau và cũng không có điểm chung với biên giới vương quốc. Thành phố thứ $j$ nằm ở vị trí $(C_j,R_j)$ và có số thuế hàng nằm là $t_j$. Để tiện cho việc quản lý thì mỗi thành phố sẽ nộp thuế trực tiếp cho quý tộc của vùng lãnh địa nhỏ nhất mà nó nằm trong hoặc hoàng gia nếu không nằm trong vùng lãnh địa quý tộc. Biết không có thành phố nào nằm trên biên giới vương quốc cũng như biên giới lãnh địa, hãy giúp MH tính xem với hoàng gia và từng quý tộc thì số thuế hàng nay thu trực tiếp từ các thành phố là bao nhiêu nhé!

INPUT

• Dòng đầu tiên gồm 4 số nguyên dương $W,H,n,m$ $(W,H\le {10}^9,n,m\le {10}^5)$
• $n$ dòng tiếp theo, dòng thứ $i$ gồm 4 số $X_i,Y_i,A_i,B_i(0<X_i,A_i<W,0<Y_i,B_i<H)$ tọa độ góc trái dưới và phải trên của từng lãnh địa.
• $m$ dòng còn lại, dòng thứ $j$ gồm 3 số $C_j,R_j,t_j$ tọa độ của thành phố thứ $j$ và số thuế hàng năm.

OUTPUT

• Gồm $n+1$ số in trên 1 dòng, số thứ $i$ là lượng thuế hàng năm quý tộc thứ $i$ thu và số thứ $n+1$ là lượng thuế hàng năm hoàng gia thu.

Sample Input

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

Sample Output

16 17 4 20

Subtask

• Subtask 1: $n,m\le {10}^3$ ($20p$).
• Subtask 2: $W,H\le {10}^3$ ($30p$).
• Subtask 3: không ràng buộc ($20p$).

Poinciana là một vương quốc rất đẹp được đặt tên theo loài hoa Phượng vỹ. Vương quốc này gồm có $n$ thành phố được chia thành $m$ loại. Các thành phố được đánh số từ $1$ đến $n$ với thành phố $1$ là thủ đô và $t_i(t_i\le m)$ là loại của thành phố thứ $i$. Hệ thống đường cao tốc của vương quốc này đảm bảo kết nối giữa thủ đô với các thành phố còn lại bằng $n-1$ tuyến đường một chiều hướng ra khỏi thủ đô. Sau nhiều năm rời khỏi vương quốc du học, công chúa MH của vương quốc đã trở lại và quyết định thực hiện một chuyến thị sát dọc các tuyến đường cao tốc. Hiện tại, có $q$ kế hoạch cho chuyến thị sát này, với kế hoạch thứ $k$ là một lộ trình xuất phát từ một thành phố loại $a_k$ và kết thúc ở thành phố loại $b_k$ và vì một số lý do, sẽ không đi qua thành phố loại $c_k$ nào. Với mỗi kế hoạch, hãy giúp MH biết có bao nhiêu lộ trình phù hợp để tham quan bằng các tuyến cao tốc nhé!

INPUT

• Dòng đầu tiên gồm 3 số nguyên dương $n,m,q$ số thành phố, số loại thành phố và số kế hoạch.
• $n$ dòng tiếp theo, dòng thứ $i$ miêu tả thông tin về thành phố thứ $i$.
• Dòng thứ nhất chứa 1 số $t_1$ là loại thành phố của thủ đô.
• Dòng thứ $i$ trong $n-1$ dòng còn lại gồm hai số $p_i,t_i$ thành phố có đường cao tốc dẫn đến $i$ và loại thành phố của $i$.
• Trong $q$ dòng còn lại, dòng thứ k gồm ba số $a_k,b_k,c_k(a_k,b_k,c_k\le m,a_k\ne b_k\ne c_k)$ mô tả kế hoạch tham quan thứ $k$.

OUTPUT

• Gồm $q$ dòng với dòng thứ $k$ là số lộ trình phù hợp cho kế hoạch tham quan thứ $k$, hai lộ trình từ $u_1$ đến $v_1$ và từ $u_2$ đến $v_2$ được gọi là khác nhau khi $u_1\ne u_2$ hoặc $v_1\ne v_2$

Sample Input

12 3 5
1
1 1
1 2
3 3
4 1
4 2
6 3
6 1
8 1
2 3
10 1
11 3
1 3 2
1 2 3
2 1 3
3 1 2
2 3 1

Sample Output

5
1
2
2
3

Subtask

• Subtask 1: $n\le {10}^3,m\le 100,q=1$ (20p)
• Subtask 2: $n\le {10}^5,m\le {10}^4,q\le 100$ (20p)
• Subtask 3: $n\le {10}^5,m\le {10}^4,q\le {10}^4$ và $b_k=b_{k-1}$ với mọi $k>1$ (20p)
• BONUS:
• Subtask thử thách: $n\le {10}^5,m\le {10}^4,q\le {10}^4$ và số thành phố thuộc mỗi loại thành phố $\le 100$(prize for first AC )
• Subtask: $n\le {10}^5,m\le {10}^4,q\le {10}^4$.