Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn (x1, y1, x2, y2, X) yêu cầu đếm số lần giá trị X xuất hiện trong HCN con (x1, y1) đến (x2, y2).

Gợi ý: Xây dựng mảng P-Sum với P[i][j] = số lần X xuất hiện từ (1,1) đến (i,j).

Ràng buộc: Ma trận A chỉ chứa các số từ 0 đến 9.

Input:

Dòng đầu M, N (1 <= M, N <= 100).

M dòng ma trận A.

Dòng tiếp theo chứa Q (1 <= Q <= 1000).

Q dòng truy vấn (x1, y1, x2, y2, X).

Output:

Q dòng, mỗi dòng là số lượng đếm được.

Ví dụ:

Input:

3 3
1 2 1
2 1 2
1 2 1
2
1 1 3 3 1
1 1 2 2 2

Output:

5
2

Cho dãy số A gồm N số nguyên. Với mỗi đoạn con liên tiếp A[i...j], ta tính tổng các phần tử của nó. Hãy tính tổng của tất cả các tổng đoạn con đó. (Lưu ý: Bài này có thể giải bằng toán học thuần túy hoặc quy hoạch động đơn giản).

Dữ liệu vào:

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

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

Dữ liệu ra:

Tổng của tất cả các đoạn con modulo 10^9 + 7.

Ví dụ:

Input:

3 
1 2 3

Output:

20

Cho 2 xâu S và T, tìm và in ra xâu con ngắn nhất của S chứa đầy đủ các ký tự trong T (lưu ý không cần đúng thứ tự trong T).

Ràng buộc: ~1 \leq len(T), len(S) \leq 10^6~

S, T chứa các ký tự in thường

In ra xâu con nhỏ nhất thỏa mãn, nếu không có xâu nào thỏa mãn in ra NOT FOUND

Input 01:

hoccohocnngnghehnc
henn

Output 01:

ngnghe

Input 02:

hoccohocnngnghehnc
henng

Output 02:

ngnghe

Input 03:

hoccohocnngnghehnc
htnng

Output 03:

NOT FOUND

Cho 2 mảng A[] và B[] có N và M phần từ đã được sắp xếp theo thứ tự tăng dần, nhiệm vụ của bạn là hãy đếm xem trong 2 mảng tồn tại bao nhiêu cặp i,j sao cho A[i] = B[j]

Định dạng đầu vào:

Dòng đầu tiên là N và M

Dòng 2 là N số trong màng A[]

Dòng 3 là M số trong mảng B[]

Ràng buộc:

1<=N,M<=10^7

1<=A[i], B[i]<= 10^9

Định dạng đầu ra: In ra đáp án của bài toán

Input 01:

5 5
1 2 3 4 5
3 4 5 6 7

Output 01:

3

Input 02:

6 6
1 2 2 3 4 5
2 2 3 4 5 6

Output 02:

7