Bài tập

Trong một giải đấu có \(n\) kỵ sĩ, kỵ sĩ thứ \(i\) có sức mạnh \(p_i\) và đang giữ \(c_i\) đồng vàng. Khi hai kỵ sĩ giao đấu, kỵ sĩ thắng khi và chỉ khi sức mạnh của anh ta lớn hơn hẳn sức mạnh của đối thủ (nếu bằng nhau thì không ai thắng được ai). Người thắng lấy toàn bộ số vàng mà đối thủ đang giữ ban đầu (số vàng cướp được không được tính lại cho các trận sau của đối thủ; mỗi trận chỉ tính \(c\) ban đầu của đối phương).

Theo luật của nhà vua, mỗi kỵ sĩ chỉ được giao đấu với tối đa \(k\) kỵ sĩ khác, và mỗi kỵ sĩ có thể tự chọn đấu với ai. Với từng kỵ sĩ, hãy tính số vàng nhiều nhất mà anh ta có thể sở hữu (gồm vàng ban đầu của mình và vàng thu được) khi mỗi kỵ sĩ được xét độc lập với nhau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\).
• Dòng thứ ba chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\).

Output

In ra một dòng gồm \(n\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là lượng vàng lớn nhất mà kỵ sĩ thứ \(i\) có thể có.

Constraints

• \(1 \le n \le 10^5\), \(0 \le k \le \min(n-1, 50)\)
• \(1 \le p_i \le 10^9\)
• \(0 \le c_i \le 10^9\)

Sample Input 1

5 2
10 3 7 8 12
4 9 1 6 20

Sample Output 1

19 9 10 16 35

Explanation

• Kỵ sĩ 2 (sức mạnh \(3\)) không thắng được ai nên giữ \(9\).
• Kỵ sĩ 3 (sức mạnh \(7\)) chỉ thắng được kỵ sĩ 2: \(1 + 9 = 10\).
• Kỵ sĩ 4 (sức mạnh \(8\)) thắng được kỵ sĩ 2 và 3, lấy cả hai: \(6 + 9 + 1 = 16\).
• Kỵ sĩ 1 (sức mạnh \(10\)) thắng được kỵ sĩ 2, 3, 4 nhưng chỉ được đấu \(2\) trận nên chọn kỵ sĩ 2 và 4: \(4 + 9 + 6 = 19\).
• Kỵ sĩ 5 (sức mạnh \(12\)) thắng cả bốn người, chọn hai người giàu nhất (kỵ sĩ 2 và 4): \(20 + 9 + 6 = 35\).

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Một dãy con tăng là dãy các phần tử giữ lại từ \(A\) theo đúng thứ tự ban đầu (không cần liền kề) sao cho giá trị tăng ngặt. Dãy con tăng có số phần tử nhiều nhất gọi là dãy con tăng dài nhất.

Hãy đếm số dãy con tăng dài nhất của \(A\). Hai dãy con là khác nhau nếu tập chỉ số được chọn khác nhau. In kết quả sau khi lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).

Output

In ra một số nguyên là số dãy con tăng dài nhất, chia dư cho \(1000000007\).

Constraints

• \(1 \le N \le 10^5\)
• \(|A_i| \le 10^9\)

Sample Input 1

6
7 7 7 9 9 9

Sample Output 1

9

Sample Input 2

7
-3 5 -3 2 8 2 7

Sample Output 2

8

Explanation

• Ví dụ 1: độ dài lớn nhất là \(2\); chọn một số \(7\) (3 cách) và một số \(9\) (3 cách) nên có \(3 \cdot 3 = 9\) dãy.
• Ví dụ 2: độ dài lớn nhất là \(3\). Có \(2\) dãy dạng \((-3, 5, x)\) với \(x \in \{8, 7\}\), và \(6\) dãy dạng \((-3, 2, x)\) khi tính theo vị trí (hai vị trí cho số \(-3\), hai vị trí cho số \(2\), với điều kiện \(x\) đứng sau), tổng cộng \(8\) dãy.

Neko rất sợ số \(0\). Neko có dãy \(n\) số nguyên khác \(0\): \(a_1, a_2, \dots, a_n\) (có thể âm hoặc dương). Neko muốn dãy không có bất kỳ đoạn con liên tiếp nào (gồm ít nhất một phần tử) có tổng bằng \(0\).

Neko được phép chèn thêm các số nguyên bất kỳ (giá trị tùy chọn, có thể là \(0\) hoặc số rất lớn) vào các vị trí bất kỳ của dãy (đầu dãy, cuối dãy hoặc giữa hai phần tử). Hãy tìm số lượng số cần chèn ít nhất để dãy thu được không còn đoạn con liên tiếp nào có tổng bằng \(0\).

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên là số lượng số cần chèn ít nhất.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le |a_i| \le 10^3\)
• Tổng của tất cả các phần tử của dãy có giá trị tuyệt đối không quá \(2 \times 10^6\).

Sample Input 1

8
2 -1 -1 3 -3 4 -4 5

Sample Output 1

3

Sample Input 2

1
-1000

Sample Output 2

0

Explanation

Ví dụ 1: các đoạn có tổng \(0\) là \((2, -1, -1)\), \((3, -3)\) và \((4, -4)\); cần chèn một số vào mỗi chỗ để phá các đoạn này, tối thiểu \(3\) số (ví dụ chèn một số rất lớn vào ngay trước \(-1\) thứ hai, trước \(-3\) và trước \(-4\)).

Danh sách họ tên các bạn trong lớp (tối đa \(45\) bạn) được gõ nhưng còn dư khoảng trắng: có dấu cách thừa ở đầu dòng, cuối dòng và giữa các từ. Hãy chuẩn hóa từng họ tên: bỏ mọi dấu cách ở đầu và cuối dòng, và giữa hai từ liên tiếp chỉ giữ đúng một dấu cách. Không thay đổi chữ hoa/thường hay thứ tự các từ.

Input

Đọc từ đầu vào chuẩn (stdin) cho đến hết dữ liệu: mỗi dòng là họ tên của một bạn (mỗi dòng chứa ít nhất một từ, chỉ gồm chữ cái và dấu cách).

Output

In ra đầu ra chuẩn (stdout), mỗi dòng là một họ tên đã chuẩn hóa, theo đúng thứ tự ban đầu.

Constraints

• Tối đa \(45\) dòng, mỗi dòng dài không quá \(100\) ký tự.

Sample Input

An   Binh    Chi
   Pham      Van  Quan
Do Thi   Mai   
  Vu Minh Anh

Sample Output

An Binh Chi
Pham Van Quan
Do Thi Mai
Vu Minh Anh