Binh đoàn La Mã có N binh sĩ xếp thành một hàng ngang, ban đầu áo giáp của mỗi người đều có độ bền là 0. Tướng quân ban ra Q sắc lệnh cường hóa. Sắc lệnh thứ i yêu cầu các thợ rèn tăng cường thêm V độ bền cho áo giáp của tất cả binh sĩ đứng từ vị trí L đến vị trí R. Sau khi thực hiện xong toàn bộ Q sắc lệnh, hãy báo cáo độ bền áo giáp của từng binh sĩ trong hàng.

Input:

Dòng 1: Hai số nguyên N, Q (1 <= N, Q <= 10^5).

Q dòng tiếp theo: Mỗi dòng 3 số nguyên L, R, V (1 <= L <= R <= N, 1 <= V <= 10^4).

Output: In ra N số nguyên trên một dòng, cách nhau bởi khoảng trắng, là độ bền áo giáp của binh sĩ từ 1 đến N.

Ví dụ:

Input:

5 3
1 3 2
2 4 1
5 5 5

Output:

2 3 3 1 5

Thư viện trung tâm cần sắp xếp lại N tệp tài liệu được đánh mã số nguyên dương. Tiêu chí sắp xếp không dựa vào giá trị của mã số, mà dựa vào "trọng lượng" của tài liệu (được tính bằng tổng các chữ số của mã số đó). Tài liệu nào có trọng lượng nhỏ hơn sẽ xếp trước. Nếu hai tài liệu có cùng trọng lượng, tài liệu nào có mã số nhỏ hơn sẽ xếp trước. Hãy in ra danh sách mã số sau khi đã sắp xếp.

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai là mã số tài liệu (1 <= Ai <= 10^9).

Output: In ra mảng sau khi sắp xếp.

Ví dụ:

Input:

4
12 3 21 11

Output:

11 3 12 21

Dọc theo một tuyến quốc lộ có N vị trí đất trống tọa độ X_i có thể dùng để xây trạm phát sóng. Công ty viễn thông chỉ được cấp phép xây dựng đúng K trạm. Để tránh hiện tượng nhiễu sóng từ trường lẫn nhau, khoảng cách giữa hai trạm bất kỳ phải càng xa càng tốt. Hãy sắp xếp vị trí xây K trạm sao cho "khoảng cách ngắn nhất giữa hai trạm bất kỳ" đạt giá trị lớn nhất có thể.

Input:

Dòng 1: Hai số nguyên N, K (2 <= K <= N <= 10^5).

Dòng 2: N số nguyên Xi (0 <= Xi <= 10^9).

Output: Khoảng cách ngắn nhất cực đại có thể đạt được.

Ví dụ:

Input:

5 3
1 2 8 4 9

Output:

3

(Giải thích: Chọn xây tại vị trí 1, 4, 8. Các khoảng cách là 3 và 4. Khoảng cách ngắn nhất là 3).

Trên một bàn cờ vua kích thước N x N, quân Mã di chuyển theo quy tắc hình chữ L (đi 2 ô dọc 1 ô ngang, hoặc 2 ô ngang 1 ô dọc). Quân mã đang đứng ở ô (R1, C1) và cần giải cứu quân Vua đang bị nhốt tại ô (R2, C2). Có một số ô trên bàn cờ bị đặt bẫy và quân Mã không thể nhảy vào đó. Hãy tìm số bước nhảy ít nhất để quân Mã đến được đích.

Input:

Dòng 1: Số nguyên N (1 <= N <= 1000).

Dòng 2: Tọa độ R1, C1, R2, C2 (1 <= R, C <= N).

N dòng tiếp theo: Mỗi dòng N ký tự, '.' là ô trống, '#' là ô bị bẫy.

Output: Số bước nhảy ít nhất. Nếu không thể đến đích, in -1.

Ví dụ:

Input:

5
1 1 5 5
.....
...#.
.....
.#...
.....

Output:

4

Trong một cuộc thi lập trình đồng đội, có N nam và N nữ. Sức mạnh code của nam thứ i là Ai, của nữ thứ i là Bi. Cần ghép mỗi bạn nam với một bạn nữ thành 1 đội. Độ chênh lệch của đội được tính bằng Ai * Bi. Ban tổ chức muốn tổng độ chênh lệch của tất cả N đội là nhỏ nhất có thể để giải đấu cân bằng.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên mảng A (1 <= A_i <= 10^5).

Dòng 3: N số nguyên mảng B (1 <= B_i <= 10^5).

Kết quả ra: Tổng độ chênh lệch nhỏ nhất.

Ví dụ:

Input:

3
3 1 1
6 5 4

Output:

23

(Ghép: 34 + 15 + 16)