Để cài đặt tọa độ cho cổng dịch chuyển không gian, máy tính lượng tử cần thực hiện phép tính lũy thừa siêu lớn. Tọa độ chính là kết quả của phép tính A mũ B. Do hệ thống hiển thị bị giới hạn, bạn chỉ cần báo cáo phần dư của kết quả này khi chia cho M. Vì A và B cực kỳ lớn, vòng lặp thông thường sẽ mất hàng trăm năm để chạy xong. Hãy dùng thuật toán tối ưu để đưa ra đáp án trong chưa tới 1 giây.

Input: Một dòng chứa ba số nguyên dương A, B, M (1 <= A, B, M <= 10^18).

Output: Kết quả của A^B modulo M.

Ví dụ:

Input:

2 10 1000

Output:

24

Tại Học Công Nghệ, hệ thống cửa an ninh được bảo vệ bởi một "Bánh răng Mật mã". Bánh răng này chứa N con số nguyên phân biệt, ban đầu được sắp xếp tăng dần. Tuy nhiên, để tăng tính bảo mật, bánh răng đã được xoay đi một số vòng ngẫu nhiên, khiến cho dãy số bị đứt gãy tại một vị trí nào đó (Ví dụ: 4 5 6 1 2 3).

Hàng ngày, có Q lượt học sinh quét thẻ để vào lớp. Mỗi thẻ mang một mã số X. Hệ thống cần nhanh chóng xác định xem mã số X có nằm trên bánh răng hay không, và nếu có thì nằm ở vị trí thứ mấy (chỉ số tính từ 0). Do số lượng học sinh quét thẻ vào giờ cao điểm cực kỳ lớn, hệ thống cần phản hồi ngay lập tức. Nếu thuật toán của bạn chạy quá 1 giây, hệ thống cửa sẽ bị sập nguồn.

DỮ LIỆU VÀO:

Dòng 1: Gồm 2 số nguyên dương N và Q (1 <= N, Q <= 10^5) lần lượt là số lượng phần tử trên bánh răng và số lượt học sinh quét thẻ.

Dòng 2: Gồm N số nguyên phân biệt A[i] (-10^9 <= A[i] <= 10^9), thể hiện các con số trên bánh răng mật mã.

Q dòng tiếp theo: Mỗi dòng chứa 1 số nguyên X (-10^9 <= X <= 10^9) là mã số thẻ của một học sinh.

DỮ LIỆU RA:

In ra Q dòng, mỗi dòng là một số nguyên duy nhất: Vị trí của X trên bánh răng, hoặc in ra -1 nếu mã thẻ không tồn tại.

GIỚI HẠN THỜI GIAN: 1.0 giây.

VÍ DỤ:

Input:

5 3
4 5 1 2 3
1
3
10

Output:

2
4
-1

Cho N phân số, mỗi phân số có dạng 1/X. Thay vì tính toán trực tiếp với số thập phân, em hãy chuyển đổi mỗi phân số 1/X thành giá trị nghịch đảo của X theo mô đun 10^9+7, sau đó tính tổng của N giá trị nghịch đảo đó và lại lấy dư cho 10^9+7 một lần nữa.

Dữ liệu vào: Dòng đầu là số N. Dòng thứ hai chứa N số nguyên dương X1, X2, ..., Xn.

Kết quả ra: Tổng các phân số nghịch đảo theo mô đun 10^9+7.

Ràng buộc: 1 <= N <= 10^5; 1 <= Xi <= 10^6.

Ví dụ:

Input:

2
2 3

Output:

833333340

Cho một mảng gồm N chữ số (từ 0 đến 9). Bạn hãy ghép một số hoặc tất cả các chữ số này lại với nhau để tạo thành một số nguyên dương lớn nhất có thể và số đó phải chia hết cho 15. Mỗi chữ số trong mảng chỉ được sử dụng tối đa bằng số lần xuất hiện của nó. Nếu không thể tạo ra số nào chia hết cho 15, hãy in ra -1.

Input:

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

Dòng 2: N chữ số di (0 <= di <= 9).

Output: Số nguyên lớn nhất chia hết cho 15.

Ví dụ:

Input:

5
8 1 0 4 3

Output:

8430

Một xâu được gọi là đối xứng nếu đọc từ trái qua phải hay từ phải qua trái đều giống hệt nhau. Cho một xâu ký tự S chỉ gồm các chữ cái in thường, bạn hãy tìm xâu con liên tiếp đối xứng có độ dài lớn nhất nằm trong S. Nếu có nhiều xâu con đối xứng đạt cùng độ dài lớn nhất, hãy in ra xâu xuất hiện đầu tiên.

Input: Một dòng chứa xâu S (Độ dài <= 5000).

Output: Xâu con đối xứng dài nhất.

Ví dụ:

Input:

babad

Output:

bab

Có N viên ngọc được xâu thành một vòng cổ hình tròn (viên thứ 1 kề với viên thứ 2, ..., viên thứ N kề với viên thứ 1). Viên ngọc thứ i có giá trị là V_i. Bạn được phép lấy ra một số viên ngọc để bán, nhưng do hệ thống báo động, bạn tuyệt đối không được lấy 2 viên ngọc nằm kề nhau trên vòng cổ. Hãy tìm cách chọn ngọc sao cho tổng giá trị thu được là lớn nhất.

Input:

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

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

Output: Tổng giá trị lớn nhất.

Ví dụ:

Input:

4
1 2 3 1

Output:

4

(Giải thích: Chọn viên thứ 2 và thứ 4, tổng = 2 + 1 = 3. Hoặc viên 1 và 3, tổng = 1 + 3 = 4).

Một nông trường chè tại Thái Nguyên có N luống chè, luống thứ i cho sản lượng A_i kg. Để thử nghiệm một loại phân bón mới, kỹ sư nông nghiệp cần chọn một dải gồm ít nhất K luống chè liên tiếp nhau sao cho "sản lượng trung bình" của dải này là lớn nhất có thể. Hãy tìm mức sản lượng trung bình cực đại đó.

Input:

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

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

Output: Sản lượng trung bình lớn nhất (in ra phần nguyên làm tròn xuống của kết quả).

Ví dụ:

Input:

4 2
8 1 9 10

Output:

9

(Giải thích: Chọn đoạn [9, 10] có độ dài 2 >= K, trung bình là 9.5. Làm tròn xuống là 9).