Dino vừa hoàn thiện toà biệt thự thông minh của mình. Sơ đồ mặt bằng của toà nhà là một lưới ô vuông n x n, mỗi ô là một căn phòng. Các hàng của lưới được đánh số từ 1 tới n từ trên xuống và các cột của lưới được đánh số từ 1 tới n từ trái qua. Phòng nằm trên giao của hàng i và cột j được gọi là phòng (i, j) và có cao độ mặt sàn là a_ij.

Dino muốn mua một robot hút bụi tự động. Trên thị trường có nhiều loại robot, mỗi loại D được đặc trưng bởi khả năng vượt chướng ngại vật (chênh lệch độ cao) của nó. Cụ thể, robot loại D chỉ có khả năng di chuyển giữa hai phòng kề cạnh nếu chênh lệch tuyệt đối về cao độ mặt sàn giữa hai phòng đó đúng bằng D.

Hãy giúp Dino chọn một loại robot (tức là chọn một giá trị D) và một phòng bắt đầu để robot có thể đi vào và dọn dẹp được nhiều phòng nhất.

Input

• Dòng 1: Chứa số nguyên dương n (n <= 1000).
• n dòng tiếp theo: Dòng thứ i chứa n số nguyên không âm, số thứ j là aij (aij <= 10^6), là cao độ mặt sàn của phòng (i, j).

Các số trên một dòng của file input được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là số lượng phòng tối đa mà robot có thể dọn dẹp được theo phương án chọn robot và chọn phòng xuất phát của bạn (tính cả phòng xuất phát).

Sample test

Input:

5
0 3 6 3 0
3 7 0 7 3
0 0 9 0 6
3 7 0 7 9
0 3 6 3 6

Output

16

Giải thích: Nếu Dino chọn robot loại 3 (tức D = 3), robot có thể di chuyển giữa các phòng có cao độ 0, 3, 6, và 9. Với loại robot này, ta có thể đi được tất cả 16 phòng có cao độ thuộc tập {0, 3, 6, 9} (ví dụ, bắt đầu từ phòng (1,1) có cao độ 0). Bất kỳ lựa chọn D nào khác đều dẫn đến số lượng phòng dọn dẹp được ít hơn.

An có một bộ sưu tập gồm n con búp bê Nga (Matryoshka). Chúng được đặt trên bàn theo một thứ tự nhất định từ trái sang phải. Con búp bê ở vị trí thứ i có kích thước là a_i.

An muốn chọn ra một vài con búp bê từ hàng này để xếp lồng vào nhau. Nguyên tắc xếp búp bê của An như sau:

• Ban đầu, An có một "bộ" rỗng (chưa chọn con búp bê nào).
• An xét các con búp bê lần lượt theo thứ tự chúng xuất hiện, từ a1 đến an.
• Khi xét một con búp bê ai mới, An có các lựa chọn sau:
  1. Lồng ra ngoài: Nếu bộ đã chọn không rỗng và ai lớn hơn con búp bê *lớn nhất* (ngoài cùng) trong bộ, An có thể lấy ai và đặt nó lồng bên ngoài.
  2. Đặt vào trong: Nếu bộ đã chọn không rỗng và ai nhỏ hơn con búp bê *nhỏ nhất* (trong cùng) trong bộ, An có thể lấy ai và đặt nó vào bên trong cùng.
  3. Làm con đầu tiên: Nếu bộ đang rỗng, An có thể lấy ai làm con búp bê đầu tiên trong bộ.
  4. Bỏ qua: An có thể quyết định không lấy con búp bê a_i này.

Cuối cùng, An sẽ nhận được một bộ búp bê lồng nhau (tức là các con búp bê được chọn có kích thước tăng dần từ trong ra ngoài).

Yêu cầu: Cho trước dãy kích thước a1, a2, ..., a_n của các con búp bê. Hãy tìm cách chọn và xếp búp bê để được bộ búp bê lồng nhau gồm nhiều con nhất.

Input

• Dòng 1 chứa số nguyên dương n (n <= 10^5)
• Dòng 2 chứa n số nguyên dương a1, a2, ..., an (với mọi ai <= 10^9) cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số lượng búp bê tối đa trong bộ lồng nhau có thể tạo được.

Ví dụ

Input

5
4 4 5 3 1

Output

4

Giải thích: Phương án tối ưu là:

1. Xét búp bê kích thước 4 (đầu tiên): Lấy làm con đầu tiên.
   • Bộ hiện tại: (4)
2. Xét búp bê kích thước 4 (thứ hai): Bỏ qua (vì không lớn hơn 4, cũng không nhỏ hơn 4).
   • Bộ hiện tại: (4)
3. Xét búp bê kích thước 5: Lấy và lồng ra ngoài (vì 5 > 4).
   • Bộ hiện tại: (4, 5)
4. Xét búp bê kích thước 3: Lấy và đặt vào trong (vì 3 < 4).
   • Bộ hiện tại: (3, 4, 5)
5. Xét búp bê kích thước 1: Lấy và đặt vào trong (vì 1 < 3).
   • Bộ hiện tại: (1, 3, 4, 5)

Bộ cuối cùng gồm 4 búp bê.

40% số điểm ứng với các test có n <= 20 30% số điểm ứng với các test có 20 <= n <= 1000 30% số điểm ứng với các test có 1000 <= n <= 10^5

An là một nghệ nhân dệt thảm tài hoa, vừa hoàn thành một tấm thảm khổng lồ kích thước n x m. Tấm thảm được dệt từ các ô vuông, mỗi ô mang một ký tự Latinh in thường (tượng trưng cho một màu chỉ).

Bạn của An, Khánh, là một người cực kỳ thông minh và rất giỏi giải đố. An quyết định đưa ra một thử thách cho Khánh.

"Khánh xem này," An chỉ vào tấm thảm. "Tớ có một khái niệm gọi là 'Tấm thảm Hoàn mỹ'. Một tấm thảm (hay ma trận) được gọi là 'hoàn mỹ' nếu nó đáp ứng hai điều kiện:

1. Mọi hàng của nó đều là một xâu đối xứng (đọc từ trái sang phải giống như đọc từ phải sang trái).
2. Mọi cột của nó cũng đều là một xâu đối xứng."

Khánh gật gù: "Tớ hiểu rồi. Ví dụ như ma trận: aba bwb aba ... là một ma trận hoàn mỹ."

"Chính xác!" An mỉm cười. "Nhưng tấm thảm của tớ có thể chưa 'hoàn mỹ'. Nó có thể là một tấm thảm 'Gần Hoàn mỹ'."

An giải thích tiếp: "Một tấm thảm được gọi là 'gần hoàn mỹ' nếu tớ có thể sắp xếp lại các ký tự trên từng hàng (chỉ sắp xếp nội bộ trong hàng đó, các hàng là độc lập với nhau) để nó trở thành một 'Tấm thảm Hoàn mỹ'."

🎯 Yêu cầu

"Bây giờ, thử thách thực sự của cậu đây," An nói. "Tớ không chỉ quan tâm đến cả tấm thảm lớn. Tớ muốn biết có bao nhiêu 'mảnh thảm con' hình chữ nhật bên trong nó là 'gần hoàn mỹ'."

Cụ thể, An muốn Khánh đếm số lượng các bộ chỉ số (x1, y1, x2, y2) sao cho:

• 1 <= x1 <= x2 <= n
• 1 <= y1 <= y2 <= m
• Ma trận con được tạo bởi các ô (i, j) với x1 <= i <= x2 và y1 <= j <= y2 là một ma trận gần hoàn mỹ.

Bạn hãy giúp Khánh lập trình giải bài toán này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên n và m, cách nhau bởi dấu cách (kích thước của tấm thảm, 1 <= n, m <= 300).
• n dòng tiếp theo, mỗi dòng chứa một xâu m ký tự, mô tả tấm thảm của An. Dòng thứ i chứa xâu mô tả hàng thứ i, từ trái sang phải.

Output

• Một số nguyên duy nhất là tổng số lượng ma trận con "gần hoàn mỹ" đếm được.

Sample Test

Input

1 3
aba

Output

4

Input

2 3
aca
aac

Output

11

Input

3 5
accac
aaaba
cccaa

Output

43

Subtests

• 30% số test ứng với 30% số điểm của bài thỏa mãn n = 1.
• 30% số test khác ứng với 30% số điểm của bài thỏa mãn n, m <= 30.
• 20% số test khác ứng với 30% số điểm của bài thỏa mãn n, m <= 100.
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Một siêu máy tính thế hệ mới mang tên "Titan" vừa được đưa vào vận hành. Hệ thống này bao gồm n nút máy chủ (server) tính toán, được đánh số từ 1 đến n. Mỗi nút máy chủ i có một "Năng Lực Xử Lý" là a_i.

Các nút này được kết nối với nhau bằng n-1 liên kết cáp quang siêu tốc, tạo thành một cấu trúc mạng cây (đảm bảo không có chu trình và mọi nút đều được kết nối).

Để chuẩn bị cho việc vận hành chính thức, ban quản trị hệ thống muốn thực hiện một buổi "diễn tập sự cố" (stress test) để đo lường độ ổn định của mạng lưới.

Kịch bản diễn tập: Ban quản trị sẽ lần lượt mô phỏng trường hợp một số cáp quang bị đứt.

Khi các cáp quang bị đứt, hệ thống mạng sẽ bị chia cắt thành nhiều "phân vùng mạng" (components) độc lập, không thể liên lạc với nhau.

Công thức tính toán: Giá trị của một phân vùng mạng được định nghĩa là bình phương của tổng Năng Lực Xử Lý của tất cả các nút trong phân vùng đó.

Thiệt Hại Hệ Thống = Tổng giá trị của tất cả các phân vùng mạng được tạo ra.

Yêu cầu: Bạn hãy giúp ban quản trị tính "Tổng Thiệt Hại Tiềm Tàng" của toàn bộ hệ thống. Tức là, bạn cần tính "Thiệt Hại Hệ Thống" cho từng trường hợp đứt cáp quang có thể xảy ra (bao gồm cả trường hợp không đứt cáp nào), sau đó tính tổng của tất cả các giá trị thiệt hại này lại.

Vì con số này có thể rất lớn, hãy in ra kết quả cuối cùng theo modulo 998 244 353.

Input

• Dòng đầu tiên: Chứa một số nguyên n (1 <= n <= 10^5) – tổng số nút máy chủ.
• Dòng thứ hai: Chứa n số nguyên a1, a2, ..., an (1 <= ai <= 10^5) – Năng Lực Xử Lý của mỗi nút.
• n-1 dòng cuối cùng: Mỗi dòng chứa hai số nguyên ui, vi (1 <= ui, vi <= n) mô tả một liên kết cáp quang giữa nút ui và vi.

Output

• In ra một số nguyên duy nhất là "Tổng Thiệt Hại Tiềm Tàng" theo modulo 998 244 353.

Sample Test

Input

2
3 4
1 2

Output

74

Input

3
1 1 1
1 2
2 3

Output

22

Subtests

• 20% số test ứng với 20% số điểm của bài thỏa mãn n <= 20.
• 20% số test khác ứng với 20% số điểm của bài thỏa mãn n <= 1000 và ui = i, vi = i+1 với mọi 1 <= i < n.
• 20% số test khác ứng với 20% số điểm của bài thỏa mãn n <= 1000.
• 20% số test khác ứng với 20% số điểm của bài thỏa mãn ui = i, vi = i+1 với mọi 1 <= i < n.
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.