Cơ cấu xoay của ổ khóa yêu cầu dịch chuyển vòng tròn một mảng N số nguyên. Mỗi lần xoay, toàn bộ các phần tử dịch sang phải 1 vị trí, phần tử cuối cùng vòng lên đứng đầu tiên. Bạn được yêu cầu thực hiện xoay mảng này đúng K lần. Khối lượng tính toán là rất lớn nên hãy dùng thuật toán toán học để in ra trạng thái mảng sau K lần xoay mà không dùng vòng lặp mô phỏng.

Input:

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

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

Output: In ra mảng sau khi xoay.

Ví dụ:

Input:

5 2
1 2 3 4 5

Output:

4 5 1 2 3

Khác với bài toán dãy con chung thông thường (các ký tự có thể ngắt quãng), hai máy chủ A và B cần tìm ra một "xâu con liên tiếp" giống hệt nhau, có độ dài lớn nhất xuất hiện trong cả 2 chuỗi mật khẩu của họ. Hãy tìm độ dài của xâu con liên tiếp chung dài nhất này.

Input:

Dòng 1: Xâu A (độ dài <= 2000).

Dòng 2: Xâu B (độ dài <= 2000).

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

Ví dụ:

Input:

abcdef
zabcyf

Output:

3

(Giải thích: Xâu con liên tiếp chung dài nhất là "abc").

Trong một mảng A gồm N số, một cặp chỉ số (i, j) được gọi là một "nghịch thế" (inversion) nếu i < j nhưng Ai > Aj. Số lượng nghịch thế là một chỉ số quan trọng để đánh giá mức độ "hỗn loạn" của mảng. Dữ liệu mảng rất lớn (N = 10^5), bạn hãy thiết kế cấu trúc dữ liệu hoặc thuật toán đếm (như Merge Sort hoặc Binary Indexed Tree) để tìm ra tổng số nghịch thế trong thời gian O(N log N).

Input:

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

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

Output: Tổng số lượng nghịch thế.

Ví dụ:

Input:

5
2 4 1 3 5

Output:

3

(Giải thích: Các cặp nghịch thế là (2, 1), (4, 1), (4, 3)).

Cho số nguyên N. Tính tổng LCM(i, N) với i chạy từ 1 đến N.

Dữ liệu vào:

Dòng 1: T (1 <= T <= 100).

T dòng: N (1 <= N <= 10^6).

Dữ liệu ra:

Kết quả.

Ví dụ:

Input:

1 
2

Output:

4

Giải thích: lcm(1,2) + lcm(2,2) = 2 + 2 = 4.