Quá trình sáp nhập hai tập đoàn công nghệ yêu cầu ghép nối hai cơ sở dữ liệu. Cơ sở dữ liệu A có N hồ sơ, cơ sở dữ liệu B có M hồ sơ. Điểm đặc biệt là mã định danh của các hồ sơ trong cả hai cơ sở dữ liệu này đều đã được sắp xếp tăng dần từ trước. Hãy viết thuật toán hợp nhất hai mảng này thành một mảng duy nhất cũng được sắp xếp tăng dần, yêu cầu thời gian chạy cực nhanh O(N+M).

Input:

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

Dòng 2: N số nguyên mảng A.

Dòng 3: M số nguyên mảng B.

Output: N + M số nguyên của mảng sau khi hợp nhất.

Ví dụ:

Input:

3 4
1 4 7
2 3 5 9

Output:

1 2 3 4 5 7 9

Trên chiến trường phẳng, hai cỗ máy tạo lá chắn lực lượng đang phát ra hai vùng bảo vệ hình chữ nhật có các cạnh song song với trục tọa độ. Mỗi hình chữ nhật được xác định bởi tọa độ của góc dưới cùng bên trái (x1, y1) và góc trên cùng bên phải (x2, y2). Những chiến binh đứng ở khu vực giao nhau của hai lá chắn sẽ được bảo vệ tuyệt đối. Hãy tính diện tích của khu vực giao nhau này.

Input:

Dòng 1: Tọa độ x1, y1, x2, y2 của lá chắn thứ nhất.

Dòng 2: Tọa độ x3, y3, x4, y4 của lá chắn thứ hai.

(Tất cả các tọa độ là số nguyên có giá trị tuyệt đối không vượt quá 10^4. Đảm bảo x1 < x2 và y1 < y2).

Output: Diện tích phần giao nhau. Nếu không giao nhau, in 0.

Ví dụ:

Input:

0 0 3 3
1 1 4 4

Output:

4

Hệ điều hành cần biên dịch một dự án phần mềm gồm N module (đánh số từ 1 đến N). Có M quy tắc phụ thuộc, mỗi quy tắc ở dạng cặp (U, V) mang ý nghĩa "Module U phải được biên dịch xong thì mới được phép biên dịch Module V". Hãy in ra một thứ tự biên dịch hợp lệ cho N module này. Nếu có nhiều thứ tự hợp lệ, in ra thứ tự mà các module có mã số nhỏ hơn được ưu tiên biên dịch trước. Dữ liệu đảm bảo luôn có ít nhất 1 cách biên dịch (không có vòng lặp phụ thuộc).

Input:

Dòng 1: N, M (1 <= N, M <= 10^5).

M dòng tiếp theo: Mỗi dòng chứa hai số U, V.

Output: In ra N số nguyên là thứ tự biên dịch.

Ví dụ:

Input:

4 3
2 1
3 1
4 2

Output:

3 4 2 1

Một lò phản ứng hóa học ghi nhận N chỉ số năng lượng liên tiếp Ai (có thể âm hoặc dương). Độ bùng nổ của phản ứng được tính bằng tổng của một dải các chỉ số liên tiếp. Để đẩy giới hạn lò phản ứng lên mức tối đa, nhà khoa học được cấp quyền can thiệp đặc biệt: Bạn được phép chọn tối đa 1 chỉ số Ai bất kỳ và nhân giá trị của nó với -1 (biến âm thành dương hoặc ngược lại), hoặc không can thiệp gì cả. Hãy tìm độ bùng nổ (tổng dải con liên tiếp) lớn nhất có thể đạt được.

Input:

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

Dòng 2: N số nguyên Ai (|Ai| <= 10^4).

Output: Tổng dải con lớn nhất sau khi áp dụng tối đa 1 lần can thiệp.

Ví dụ:

Input:

5
3 -5 2 4 -1

Output:

14

(Giải thích: Dải con chọn là [3, -5, 2, 4]. Can thiệp nhân -1 vào số -5. Dải trở thành [3, 5, 2, 4], tổng = 14).