Trên hệ trục tọa độ ~OXY~, có ~n~ con robot, con robot thứ ~i~ ở tọa độ ~(x_i,y_i)~.

Giả sử một con robot đang ở vị trí ~(x,y)~, sau một giây, nó có thể đi tới ~4~ vị trí ~(x-1,y)~, ~(x,y-1)~, ~(x+1,y)~, ~(x,y+1)~.

Hãy tìm thời điểm ngắn nhất sao cho cả ~n~ con robot đều có thể cùng đứng ở một điểm nào đó trên hệ trục tọa độ.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ miêu tả số robot ~(1 \le n \le 3\times 10^5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của robot thứ ~i~ ~(|x_i|,|y_i| \le 10^{18})~.

Output

• In ra thời điểm nhanh nhất để các robot cùng đứng tại một điểm.

Sample Input 1

3
0 0
0 3
3 3

Sample Output 1

3

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Trên hệ trục tọa độ ~OXY~, cho hai tập điểm nguyên ~A~ và ~B~ lần lượt gồm ~n~ và ~m~ điểm.

Tập điểm ~A~ gồm ~a_1,a_2,...,a_n~ và tập điểm ~B~ gồm ~b_1,b_2,...,b_m~.

Gọi ~f(i,j,k)~ là số điểm ~b_x~ nằm trong tam giác được tạo bởi ba đểm ~(a_i,a_j,a_k)~.

Tính ~\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^n f(i,j,k)~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~ ~(1 \le n,m \le 300)~;
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.
• ~m~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.

Dữ liệu đảm bảo tọa độ ~x~ của mọi điểm là phân biệt và không có bộ ba điểm nào thẳng hàng.

Output

• In ra kết quả của bài toán.

Sample Input 1

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

Sample Output 1

2

Subtask

• Có ~80\%~ số điểm có ~n,m \le 50~.
• Có ~20\%~ số điểm không có ràng buộc gì thêm.

Bảo Bay Bổng được mời về làm việc cho cơ quan hàng không vũ trụ NASAR. Cơ quan này đang thực hiện một dự án khám phá hành tinh XYZ, nơi được cho là xuất hiện sự sống. Vì hành tinh XYZ rất lớn nên cơ quan này mới đi thám hiểm được một phần diện tích hình chữ nhật có kích thước ~m \times n~, với các hàng được đánh số từ ~1~ tới ~m~ và các cột được đánh số từ ~1~ tới ~n~.

Những khu vực ngoài hình chữ nhật này được coi là nguy hiểm và không được phép làm việc tại đó. Trong khu vực ~m \times n~ này, người ta đã chọn ra một số vị trí có toạ độ nguyên để xây dựng ~S~ trạm phát sóng và ~T~ trạm thu sóng phục vụ cho công việc nghiên cứu (ở cùng một toạ độ có thể đặt đồng thời nhiều trạm phát sóng và thu sóng). Vào thời điểm ~0~, các trạm phát sóng sẽ đồng loạt phát ra các nguồn sóng. Nếu ở thời điểm ~t~, sóng đang ở toạ độ ~(i, j)~ thì ở thời điểm ~t + 1~, sóng sẽ lan sang ~4~ ô kề cạnh với nó, cụ thể là ~(i - 1, j)~,~(i, j - 1)~,~(i + 1, j)~,~(i, j + 1)~. Thời điểm để một trạm thu sóng nhận được sóng là thời điểm nhỏ nhất sao cho có sóng từ một trạm phát sóng nào đó lan ra tới toạ độ trạm thu sóng này.

Hiện giờ, thời gian để tất cả các trạm thu sóng đều nhận được sóng là lâu hơn so với kế hoạch của NASAR cho nên họ muốn nhờ Bảo Bay Bổng công việc như sau: Hãy tìm cách đặt thêm một trạm phát sóng nữa sao cho thời gian để toàn bộ ~T~ thiết bị thu sóng đều nhận được sóng là nhỏ nhất có thể. Đồng thời, hãy đếm xem có bao nhiêu vị trí có thể đặt trạm phát sóng mới để đạt được thời gian đó.

Bảo Bay Bổng đã giải quyết hai vấn đề trên nhưng chưa chắc chắn về kết quả của mình. Bảo Bay Bổng muốn nhờ bạn tính toán lại để đối chiếu kết quả. Hãy giúp Bảo Bay Bổng hoàn thành công việc của NASAR giao cho.

Input: Nhập từ file "THUPHATSONG.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~m, n~ ~(1 \le m, n \le 10^5)~.
• Dòng thứ hai chứa hai số nguyên không âm ~S, T~ ~(0 \le S \le 10^5, 1 \le T \le 10^5)~.
• ~S~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm phát sóng ~(1 \le x \le m, 1 \le y \le n)~.
• ~T~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm thu sóng ~(1 \le x \le m, 1 \le y \le n)~.

Output: Xuất ra file "THUPHATSONG.OUT"

In ra hai số nguyên cách nhau bởi một dấu cách:

• Số thứ nhất là thời gian nhỏ nhất để tất cả ~T~ trạm thu sóng nhận được sóng sau khi xây thêm trạm phát sóng thứ ~S + 1~.

• Số thứ hai là số lượng vị trí có thể đặt trạm phát sóng thứ ~S + 1~. Các vị trí này phải là các toạ độ nguyên nằm trong phạm vi hinh chữ nhật an toàn ~m \times n~ và giúp cho thời gian để toàn bộ ~T~ trạm thu sóng nhận được sóng là nhỏ nhất có thể.

Ví Dụ

Sample Input 1

2 3
2 4
1 1
1 3
2 1
2 3
2 2
1 2

Sample Output 1

1 4

Sample Input 2

2 3
0 1
1 1

Sample Output 2

0 1

Sample Input 3

2 3
1 1
1 2
1 2

Sample Output 3

0 6

Giải thích

• Hình ảnh minh hoạ cho ví dụ đầu tiên:

  • Các trạm thu sóng kí hiệu lần lượt là ~T_1, T_2, T_3, T_4~.

  • Trạm phát sóng thứ nhất kí hiệu là ~S_1~, phát ra sóng màu xanh lá cây.

  • Trạm phát sóng thứ hai kí hiệu là ~S_2~, phát ra sóng màu xanh da trời.

  • Trạm phát sóng được đặt thêm vào kí hiệu là ~S_3~, phát ra sóng màu vàng.

  • Dưới đây là hình ảnh của các trạm sóng khi chưa đặt thêm trạm phát sóng mới:

    

  • Khi chưa đặt thêm trạm phát sóng mới, các trạm thu sóng ~T_1, T_2, T_4~ nhận được sóng tại thời điểm ~1~. Trong khi đó, trạm ~T_3~ nhận được sóng tại thời điểm ~2~. Do đó, thời gian nhỏ nhất để tất cả các trạm đều nhận được sóng là thời điểm ~2~.

  • Dưới đây là hình ảnh của các cách đặt trạm sóng ~S_3~ để thời gian tất cả các trạm thu sóng nhận được sóng là nhỏ nhất có thể:

  

  • Bây giờ, tất cả các trạm thu sóng đều nhận được sóng tại thời điểm ~1~.

• Ở ví dụ thứ hai, việc đặt trạm phát sóng tại ~(1, 1)~ sẽ giúp cho trạm thu sóng nhận sóng ngay tại thời điểm ~0~.

• Ở ví dụ cuối cùng, bất kể đặt trạm phát sóng mới tại đâu, trạm thu sóng đều bắt được sóng ngay tại thời điểm ~0~ do đã có sẵn một trạm phát sóng đặt trùng toạ độ tại đó.

Giới hạn

• Subtask 1 (10%): ~m, n, S, T \le 50~
• Subtask 2 (20%): ~S = 0; m, n, T \le 500~
• Subtask 3 (30%): ~S = 0~
• Subtask 4 (20%): ~m, n, S, T \le 5000~
• Subtask 5 (20%): Không có ràng buộc gì thêm