Nhà giả kim có N lọ dung dịch với nồng độ phép thuật là A_i. Để dung hợp chúng thành một siêu tinh thể, yêu cầu bắt buộc là Ước chung lớn nhất (ƯCLN) của nồng độ tất cả N lọ phải lớn hơn 1. Hệ thống máy đo tự động cần bạn viết một thủ tục tính ƯCLN của toàn bộ N phần tử trong mảng để kiểm tra độ khả thi.

Input:

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

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

Output: Số nguyên duy nhất là ƯCLN của mảng.

Ví dụ:

Input:

4
24 36 48 60

Output:

12

Ổ khóa kỹ thuật số gồm một mảng N số nguyên. Mỗi lần xoay bánh răng sang phải 1 nấc, toàn bộ mảng sẽ dịch chuyển sang phải 1 vị trí, phần tử cuối cùng sẽ bị đẩy ngược lên vị trí đầu tiên. Ổ khóa sẽ thực hiện xoay phải đúng K lần. Sau đó, nó sẽ đưa ra Q câu hỏi, mỗi câu hỏi cho một chỉ số X, yêu cầu bạn cho biết giá trị của phần tử tại vị trí X lúc này là bao nhiêu.

Input:

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

Dòng 2: N số nguyên A0, A1, ..., A{N-1} (|Ai| <= 10^9).

Q dòng tiếp theo: Mỗi dòng một số nguyên X (0 <= X < N).

Output: In ra Q dòng, mỗi dòng là giá trị tại vị trí X tương ứng.

Ví dụ:

Input:

5 2 3
1 2 3 4 5
0
2
4

Output:

4
1
3

(Giải thích: Xoay 1 lần: 5 1 2 3 4. Xoay 2 lần: 4 5 1 2 3).

Đài thiên văn chụp lại một vùng không gian dưới dạng lưới N dòng, M cột. Các ô trống đánh dấu '.', các ngôi sao đánh dấu '*'. Hai ngôi sao được coi là thuộc cùng một chòm sao nếu chúng nằm kề nhau (chung cạnh trên, dưới, trái hoặc phải). Bức ảnh chứa bao nhiêu chòm sao hoàn chỉnh?

Input:

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

N dòng tiếp theo: Mỗi dòng gồm M ký tự '.' hoặc '*'.

Output: Số lượng chòm sao.

Ví dụ:

Input:

4 5
...
**..
....
...

Output:

1

Trình biên dịch đang kiểm tra cú pháp của một hàm chứa rất nhiều các khối lệnh lồng nhau, được biểu diễn bằng một dãy ngoặc tròn. Mức độ lồng nhau (chiều sâu) của một dãy ngoặc hợp lệ được định nghĩa là số lượng cặp ngoặc bao bọc nhau nhiều nhất. Ví dụ dãy "()(())" có chiều sâu lớn nhất là 2. Dãy "((()))" có chiều sâu là 3. Cho một xâu ngoặc hợp lệ, hãy tìm chiều sâu lớn nhất của nó.

Input: Một xâu S chỉ gồm '(' và ')' (Độ dài <= 10^5, đảm bảo xâu luôn hợp lệ).

Output: Chiều sâu lớn nhất của xâu ngoặc.

Ví dụ:

Input:

( () ( () () ) )

Output:

3