Hệ thống giải mã yêu cầu bạn điền các số nguyên từ 1 đến N*N vào một ma trận vuông kích thước N x N theo hình xoắn ốc. Bắt đầu từ ô ở góc trên cùng bên trái (1, 1), điền các số tăng dần theo chiều sang phải, rồi đi xuống, sang trái, lên trên, và tiếp tục xoắn vào trong cho tới khi điền kín ma trận. Hãy in ma trận đó ra màn hình.

Input: Số nguyên N (1 <= N <= 100).

Output: Ma trận N x N sau khi điền.

Ví dụ:

Input:

3

Output:

1 2 3
8 9 4
7 6 5

Nhà máy có K cỗ máy sản xuất độc lập. Cỗ máy thứ i cần đúng T_i giây để sản xuất ra 1 sản phẩm. Bạn cần hoàn thành một đơn hàng gồm M sản phẩm. Các cỗ máy có thể hoạt động song song cùng lúc với nhau. Hãy tính thời gian ít nhất cần thiết để nhà máy sản xuất đủ M sản phẩm.

Input:

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

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

Output: Thời gian ngắn nhất tính bằng giây.

Ví dụ:

Input:

3 7
3 2 5

Output:

8

(Giải thích: Trong 8 giây, máy 1 làm được 2 cái, máy 2 làm được 4 cái, máy 3 làm được 1 cái. Tổng là 7 cái).

Mật mã mở cửa được giấu trong mảng A gồm N số nguyên dương. Cửa sẽ chỉ mở nếu bạn nhập đúng số lượng cặp chỉ số (i, j) sao cho 1 <= i < j <= N và phép toán XOR (loại trừ theo bit) của Ai và Aj có giá trị đúng bằng một số X cho trước. Hãy lập trình đếm số cặp thỏa mãn.

Input:

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

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

Output: Số lượng cặp thỏa mãn.

Ví dụ:

Input:

5 2
1 3 2 4 6

Output:

1

(Giải thích: Cặp duy nhất là 1 và 3 vì 1 XOR 3 = 2).

Khác với bài toán xâu con chung dài nhất (không cần liên tiếp), các nhà sinh học đang cần tìm đoạn gen chung liên tiếp dài nhất xuất hiện trong cả hai chuỗi gen A và B. Hãy tìm và in ra độ dài của đoạn gen chung liên tiếp cực đại đó.

Input:

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

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

Output: Độ dài chuỗi con liên tiếp chung dài nhất.

Ví dụ:

Input:

abcdxyz
cdeabcdx

Output:

5

(Giải thích: Đoạn chung liên tiếp dài nhất là abcdx).