Là sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:

Cho ~n~ đoạn số nguyên trên trục số, đoạn thứ ~k~ (~1 \le k \le n~) có đầu mút bên trái là ~L_k~, đầu mút bên phải là ~R_k~ và có trọng số là ~w_k~. Với ~a, b~ là hai số nguyên, trọng số của cặp số ~(a, b)~ được tính bằng tổng trọng số của tất cả các đoạn ~t~ mà ~a \le L_t \le R_t \le b~ với ~1 \le t \le n~. Cần tìm cặp số nguyên ~(a, b)~ có trọng số là lớn nhất.

Yêu cầu: Cho ~n~ đoạn số, gọi ~S~ là trọng số của cặp số nguyên ~(a, b)~ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị ~S~.

Dữ liệu

Vào từ file văn bản SSEQ.INP:

• Dòng đầu chứa số nguyên dương ~n~;
• Dòng thứ ~k~ (~1 \le k \le n)~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~L_k, R_k, w_k~ mô tả đoạn thứ ~k~ (~1 \le L_k \le R_k \le 10^6~; ~|w_k| \le 10^6~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bảng SSEQ.OUT một số nguyên ~S~ là trọng số lớn nhất xác định được.

• Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: ~n \le 200~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm thỏa mãn: ~n \le 2000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~R_1 - L_1 = R_2 - L_2 = \ldots = R_n - L_n~ và ~n \le 10^5~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm thỏa mãn: ~n \le 10^5~.

Ví dụ

Input

4
1 2 -5
3 5 6
3 4 -1
4 6 3

Output

8

Giải thích

Trọng số lớn nhất là ~8~ bằng cách chọn cặp số ~(3, 6)~. Trọng số của cặp số ~(3, 6)~ bằng tổng trọng số của ba đoạn: ~[3, 5]~, ~[3, 4]~ và ~[4, 6]~.

Nam đã xây dựng được một phần mềm vẽ hình với giao diện chính là một bảng vẽ kích thước ~W \times H~. Bảng vẽ được đặt trên hệ trục chiếm một vùng là một hình chữ nhật có tọa độ trái dưới là ~(0, 0)~ và tọa độ phải trên là ~(W, H)~. Nam đã vẽ ~n~ đa giác lồi trên bảng vẽ để thử nghiệm phần mềm, đa giác nào cũng có đúng ~m~ đỉnh.

Đa giác thứ ~i~ (~1 \le i \le n~) được mô tả bằng dãy tọa độ của ~m~ đỉnh liệt kê theo chiều kim đồng hồ tương ứng là ~(x_{i, 1}, y_{i, 1}), (x_{i, 2}, y_{i, 2}), \ldots, (x_{i, m}, y_{i, m})~. Hai cạnh bất kì của hai đa giác không có điểm chung và cũng không chạm vào biên của bảng vẽ. Có ~Q~ phương án thử nghiệm, phương án thứ ~t~ (~1 \le t \le Q~) sẽ thực hiện bấm tô màu vào điểm ~(x_t, y_t)~ không nằm trên bất kì cạnh cào của đa giác cũng như biên của bảng vẽ, khi đó toàn bộ vùng chứa điểm ~(x_t, y_t)~ được giới hạn bởi các cạnh của đa giác và biên của bảng vẽ sẽ được tô, phần mềm sẽ trả về diện tích vùng được tô.

Yêu cầu: Cho ~n~ đa giác lồi cùng có ~m~ đỉnh và ~Q~ phương án tô màu, với mỗi phương án hãy xác định diện tích vùng được tô màu để kiểm tra phần mềm.

Dữ liệu

Vào từ file văn bản PAINT.INP:

• Dòng đầu chứa năm số nguyên ~W, H, n, m, Q~ (~W, H \le 10^8; 3 \le m \le 5~);
• Dòng thứ ~i~ (~1 \le i \le n~) trong ~n~ dòng tiếp theo chứa ~2m~ số nguyên dương ~x_{i, 1}, y_{i, 1}, x_{i, 2}, y_{i, 2}, \ldots, x_{i, m}, y_{i, m}~ lần lượt là tọa độ ~m~ đỉnh được liệt kê theo chiều kim đồng hồ của đa giác thứ ~i~ (~0 < x_{i, 1}, x_{i, 2}, \ldots, x_{i, m} < W~; ~0 < y_{i, 1}, y_{i, 2}, \ldots, y_{i, m} < H~);
• Dòng thứ ~t~ (~1 \le t \le Q~) trong ~Q~ dòng tiếp theo chứa hai số nguyên dương ~x_t, y_t~ mô tả phương án thứ ~t~ (~0 < x_t < W~; ~0 < y_t < H~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản PAINT.OUT gồm ~Q~ dòng, mỗi dòng chứa một số thực (lấy đúng một chữ số sau dấu chấm thập phân) là diện tích vùng được tô tương ứng phương án trong dữ liệu vào.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn: ~n, Q \le 20~ và các đa giác là các hình chữ nhật có cạnh song song với một trong hai trục tọa độ;
• ~35\%~ số test khác ứng với ~35\%~ số điểm của bài thỏa mãn: ~n, Q \le 2000~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~n, Q \le 10^5~ và các đa giác là các hình chữ nhật có cạnh song song với một trong hai trục tọa độ;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn: ~n, Q \le 10^5~.

Ví dụ

Input

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

Output

3.0
18.5
48.0

Minh họa

Để xây dựng thêm chức năng biến đổi ảnh cho phần mềm vẽ, Nam cần xây dựng ma trận ~A~ có tính chất sau:

• Ma trận có ~m~ hàng và ~n~ cột, các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Phần tử nằm ở hàng ~i~ (~1 \le i \le m~) và cột ~j~ (~1 \le j \le n~) kí hiệu là ~A_{i,j}~, giá trị mỗi phần tử của ma trận đều là các số nguyên dương;
• Hai phần tử cùng hàng nhưng có chỉ số cột là nguyên tố cùng nhau thì giá trị phải khác nhau. Cụ thể: với ~1 \le j_1, j_2 \le n~ và ước số chung lớn nhất của ~(j_1, j_2)~ bằng ~1~ thì ~A_{i,j_1}~ khác ~A_{i,j_2}~ với mọi ~i~ (~1 \le i \le m~);
• Hai phần tử cùng cột nhưng có chỉ số hàng là nguyên tố cùng nhau thì giá trị phải khác nhau. Cụ thể: với ~1 \le i_1, i_2 \le m~ và ước số chung lớn nhất của ~(i_1, i_2)~ bằng ~1~ thì ~A_{i_1,j}~ khác ~A_{i_2,j}~ với mọi ~j~ (~1 \le j \le n~);
• Thứ tự từ điển của ma trận là nhỏ nhất có thể.

Ma trận ~A~ được gọi là có thứ tự từ điển nhỏ hơn ma trận ~B~ (hai ma trận cùng có ~m~ hàng và ~n~ cột) nếu lần lượt so sánh từng phần tử theo từng hàng từ trên xuống dưới, trên mỗi hàng theo thứ tự từ trái sang phải để tìm phần tử khác nhau đầu tiên thì tại vị trí đó giá trị phần tử của ma trận ~A~ nhỏ hơn giá trị phần tử của ma trận ~B~.

Yêu cầu: Cho ~m~ và ~n~, gọi ~S~ là tổng các phần tử của ma trận, hãy tính ~S \bmod (10^9 + 7)~, trong đó ~\bmod~ là phép toán chia lấy dư.

Dữ liệu

Vào từ file văn bản MATRIX.INP gồm một dòng duy nhất chứa hai số nguyên dương ~m~, ~n~ cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản MATRIX.OUT một số nguyên duy nhất là ~S \bmod (10^9 + 7)~.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~m \times n \le 10^4~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~m = 1, n \le 10^9~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m, n\le 10^6~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài thỏa mãn: ~m, n\le 10^9~.

Ví dụ 1

Input

1 3

Output

6

Giải thích

Ma trận thỏa mãn cần tìm là:

$$\begin{array}{ccc} 1& 2& 3 \end{array}$$

Ví dụ 2

Input

3 3

Output

21

Giải thích

Ma trận thỏa mãn cần tìm là:

$$\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 4 \\ 3 & 4 & 1 \end{array}$$