Bài tập

Có \(n\) người xếp thành một hàng dọc, người thứ \(i\) có chiều cao \(h_i\). Với mỗi người trong hàng, hãy tìm vị trí của người gần nhất về phía bên trái có chiều cao lớn hơn người đó.

Input

• Dòng đầu tiên chứa số nguyên \(n\): số lượng người trong hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\): chiều cao của từng người.
• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq h_i \leq 10^9\)

Output

In ra \(n\) số nguyên, số thứ \(i\) là vị trí của người gần nhất bên trái có chiều cao lớn hơn người thứ \(i\). Nếu không có người nào như vậy, in ra \(0\).

Example

8
2 5 1 4 8 3 2 5

0 0 2 2 0 5 6 5 

Thành oai hùng ngày nào nay đã trở thành bảo vệ của rừng BaNgocLand(có dạng hình chữ nhật kích thước \(m \times n\)). Để đền đáp công lao to lớn của Thành, Chúa đất cho phép anh chọn một vùng đất hình chữ nhật có kích thước \(k \times k\), có các cạnh song song với các bìa rừng, khai thác tài nguyên tại vùng đất này để lây kinh phí dựng nhà, lấy vợ.

Chúa đất chỉ cho phép anh khai thác cây trong đúng vùng đất mà anh ấy chọn. Biết giá trị của mỗi cây trong khu rừng AnLuuLand tại vị trí dòng \(i\) cột \(j\) là \(a_{i, j}\) nguyên. Bạn hãy giúp Thành chọn một vùng đất có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất. Thành có thể không chọn nếu muốn.

Input

Dòng 1: Gồm \(3\) số nguyên dương \(m, n, k\) \((m, n, k \leq 700)\).

\(m\) dòng sau, mỗi dòng gồm \(n\) số nguyên là giá trị của mỗi cây trong khu rừng. Giá trị của mỗi cây là một số nguyên có trị tuyệt đối không quá \(10^9\).

Output

Một số duy nhất là giá trị cao nhất mà Thành có thể nhận được.

Example

4 5 2
1 1 2 0 0
1 2 1 0 1
4 3 5 1 1
1 5 5 0 0

18

Một công ty vận hành theo mô hình phân cấp rõ ràng: mỗi nhân viên (ngoại trừ Giám đốc điều hành) đều có một cấp trên trực tiếp, tạo thành một cấu trúc cây gốc với CEO là người số 1.

Mỗi nhân viên được gán một chỉ số ảnh hưởng cá nhân -- đại diện cho năng lực, trách nhiệm, hoặc độ tín nhiệm của người đó. Khi đánh giá tác động trong hệ thống báo cáo, công ty muốn phân tích xem trong tất cả các tuyến báo cáo ngược từ một nhân viên đến các cấp trên của họ, ảnh hưởng "yếu nhất" (thấp nhất) trên mỗi tuyến là bao nhiêu.

Cụ thể, với mỗi nhân viên $x$, bạn cần:

• Xét tất cả các cấp trên trực tiếp hoặc gián tiếp \(y\) của họ;
• Với mỗi cặp \((x, y)\) sao cho \(y\) là cấp trên của \(x\), hãy tính giá trị nhỏ nhất của các chỉ số ảnh hưởng trên đường đi từ \(x\) đến \(y\);
• Sau đó, cộng tất cả các giá trị nhỏ nhất này lại để có kết quả cuối cùng cho \(x\).

Input

• Dòng đầu tiên là số nguyên \(n\) -- tổng số nhân viên trong công ty \((n \leq 10^5)\).
• Dòng tiếp theo gồm \(n - 1\) số nguyên, mỗi số ở vị trí \(i\) cho biết người quản lý trực tiếp của nhân viên số \(i+1\).
• Dòng tiếp theo gồm \(n\) số nguyên, số thứ \(i\) là \(a_{i}\) - chỉ số ảnh hưởng của nhân viên số \(i\) \((0 \leq a_{i} \leq 10^9)\)

Output

• In ra \(n\) số nguyên. Số thứ \(i\) là tổng của các giá trị ảnh hưởng thấp nhất trên tất cả các tuyến báo cáo từ nhân viên \(i\) đến các cấp trên của họ (bao gồm cả bản thân họ).

Example

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

3 4 6 3 8 11 15 

Scoring

• Subtask 1 (30% số điểm): \(n \leq 100\).
• Subtask 2 (20% số điểm): \(n \leq 1000\).
• Subtask 3 (20% số điểm): Mỗi nhân viên chỉ có tối đa \(1\) cấp trên và \(1\) cấp dưới (cây có dạng đường thẳng).
• Subtask 4 (30% số điểm): \(n \leq 10^5\).

Một dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm \(5\) số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm \(n\) số nguyên \(a_{1}, a_{2},..., a_{n}\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

Dòng đầu chứa hai số nguyên dương \(n, k (k < n)\)

Dòng thứ hai chứa n số nguyên \(a_{1}, a_{2},..., a_{n}\) \((|a_{i}| ≤ 10^6)\)

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

5 2
28 9 5 1 69

100

Scoring

\(60\%\) số test có \(n \leq 20\).

\(40\%\) số test còn lại có \(n \leq 10^5\).