Mỗi chương trình trí tuệ nhân tạo được gán một mã định danh là số nguyên dương N. Lõi năng lượng của chương trình đó chính là ước số nguyên tố lớn nhất của N. Hãy viết một module phần mềm giúp hệ thống tìm ra lõi năng lượng của một chương trình bất kỳ.

Input: Một dòng chứa số nguyên dương N (1 <= N <= 10^12).

Output: Ước số nguyên tố lớn nhất của N.

Ví dụ:

Input:

13195

Output:

29

(Giải thích: Các thừa số nguyên tố của 13195 là 5, 7, 13 và 29. Lớn nhất là 29).

Máy chủ phát ra một chuỗi tín hiệu gốc S. Các trạm thu nhận được Q chuỗi tín hiệu Ti. Một tín hiệu Ti được coi là hợp lệ nếu nó là một "xâu con" của S (tức là có thể tạo ra T_i bằng cách xóa đi một số ký tự trong S và giữ nguyên thứ tự các ký tự còn lại). Hãy kiểm tra tính hợp lệ của toàn bộ Q tín hiệu.

Input: Dòng 1: Xâu S chỉ gồm chữ cái in thường (Độ dài <= 10^5).

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

Q dòng tiếp theo: Mỗi dòng chứa một xâu Ti (Tổng độ dài các xâu Ti không vượt quá 10^6).

Output: In ra Q dòng, mỗi dòng in YES nếu hợp lệ, ngược lại in NO.

Ví dụ:

Input:

ahbgdc
2
abc
axc

Output:

YES
NO

Trung tâm dữ liệu có N luồng xử lý liên tiếp, luồng thứ i cần T_i miligiây để tính toán. Giám đốc kỹ thuật cần chia N luồng này thành đúng K nhóm liên tiếp nhau để giao cho K máy chủ xử lý song song. Thời gian hoàn thành của toàn bộ hệ thống bằng thời gian của máy chủ mất nhiều thời gian nhất. Hãy tìm cách chia sao cho thời gian hoàn thành của toàn hệ thống là nhỏ nhất có thể.

Input:

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

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

Output: Thời gian hoàn thành nhỏ nhất có thể đạt được.

Ví dụ:

Input:

5 3
2 4 1 3 5

Output:

6

(Giải thích: Chia thành [2, 4], [1, 3], [5]. Thời gian của 3 máy lần lượt là 6, 4, 5. Máy lâu nhất mất 6 miligiây).

Hai trạm thu phát vô tuyến ghi nhận được hai dãy tần số A (gồm N số) và B (gồm M số). Các chuyên gia cần tìm một dãy tần số phụ thỏa mãn 3 điều kiện: là dãy con của A, là dãy con của B, và là một dãy tăng ngặt. Hãy tìm độ dài của dãy con chung tăng ngặt dài nhất này.

Input:

Dòng 1: N, M (1 <= N, M <= 500).

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

Dòng 3: M số nguyên Bi (1 <= Bi <= 10^4).

Output: Độ dài lớn nhất tìm được.

Ví dụ:

Input:

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

Output:

3

(Giải thích: Dãy con chung tăng dài nhất là 1 2 5 hoặc 1 2 3).