Người ta đo độ giống nhau của hai xâu X, Y có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số i thỏa mãn Xi = Yi. Ví dụ: X = avbc; Y= avvr có độ giống nhau bằng 2. Cho một xâu S có độ dài n và một xâu T có độ dài m (m <n), độ giống nhau giữa xâu S và xâu T là tổng số độ giống nhau giữa xâu T và mọi xâu con gồm các kí tự liên tiếp của S có độ dài m.</p>

Yêu cầu: Cho hai xâu S và T. Tính độ giống nhau giữa xâu S và xâu T.

Đầu vào:

• Dòng đầu ghi xâu T.

• Dòng thứ 2 ghi xâu S.

• Các kí tự trong hai xâu thuộc a đên z và có độ dài không quá 2.10^6 kí tự.

Đầu ra:

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu S và xâu T.

Ràng buộc:

• Có 25% số test ứng với O < n ≤ 10^3

• Có 25% số test ứng với 102 < n ≤ 10^4

• Có 50% số test ứng với 101 < n ≤ 2.10^6

Input:

abaab 
aababacab

Output:

12

Cho n điểm trên mặt phẳng Descartes, điểm Ai có tọạ độ (xi, yi). Hãy tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong n điểm đã cho.

Khoảng cách Manhattan giữa hai điểm A(xA, yA) và B(xB, yB) có giá trị là |xA - xB| + |yA- YB|

Input:

• Dòng đầu tiên chứa số nguyên dương n - số lượng điểm (2 ≤ n ≤ 10^5).

• n dòng tiếp theo, một dòng chứa hai số nguyên xi và yi mô tả toạ độ của điểm Ai (|xi|, |yi| ≤ 10^9).

Output: In ra khoảng cách Manhattan lớn nhất tìm được.

Input:

5
1 2
2 3
4 4
0 -1
-1 4

Output:

9

Ma trận xoáy ốc nguyên tố cấp N là ma trận vuông có N*N phần tử. Các số được điền vào ma trận theo chiều kim đồng hồ đều là các số thuộc dãy fibonacci từ nhỏ đến lớn

INPUT:

3

OUTPUT:

0 1 1
13 21 2
8 5 3

Cho một lưới ô vuông kích thước N x M chứa các số nguyên không âm. Bạn cần tìm đường đi từ ô (1, 1) đến ô (N, M) sao cho tổng các số trên đường đi là nhỏ nhất. Tại mỗi bước, bạn chỉ có thể đi xuống dưới hoặc đi sang phải.

Dữ liệu vào:

Dòng 1: Hai số nguyên N, M (1 <= N, M <= 1000).

N dòng tiếp theo, mỗi dòng chứa M số nguyên A[i][j] (0 <= A[i][j] <= 1000).

Dữ liệu ra:

Tổng chi phí nhỏ nhất.

Ví dụ:

Input:

3 3 
1 3 1 
1 5 1 
4 2 1

Output:

7