Cho hai số nguyên a, b. Ta định nghĩa nếu a chia hết cho b thì b được gọi là ước của a.

Ví dụ: 3 là ước của 6 vì 6 chia hết cho 3.

Yêu cầu

Cho một dãy gồm n số nguyên ~a_1, a_2, \dots, a_n~ và một số nguyên x. Viết chương trình tính tổng các số là ước của số nguyên x ở trong dãy số đã cho.

Input:

• Dòng 1 ghi số nguyên dương ~n~ (~n \le 10^5~) và số nguyên ~x~ (~x < 10^9~)
• Dòng 2 ghi ~n~ số nguyên 32 bit cách nhau một dấu cách trống

Output:

Ghi ra một dòng là kết quả tìm được

Ví dụ:

sumuoc.inp

6 10
2 4 1 3 5 2

sumuoc.out

10

Cho dãy số gồm ~N~ phần tử nguyên ~a_1, a_2, \dots, a_N~ (~1 \le N \le 10^3~) và số nguyên ~X~. Hãy đếm cặp số liên tiếp có tổng bằng ~X~.

Input:

• Dòng 1 ghi số nguyên ~N~ và ~X~
• Dòng 2 ghi ~N~ số nguyên ~a_1, a_2, \dots, a_N~

Output:

Ghi ra một số duy nhất là số cặp liên tiếp có tổng bằng ~X~

Ví dụ:

tongx.inp

5 7
6 1 9 -2 9

tongx.out

3

Cho số nguyên dương ~N~ và dãy số ~A~ có ~N~ phần tử nguyên ~A_1, A_2, ..., A_N~ (~|A_i| \le 10^9, 1 \le N \le 10^5~). Độ lệch số của hai phần tử ~A_i, A_j~ (~1 \le i \le j \le N~) được xác định là ~|A_i - A_j|~. Hãy xác định số cách chọn cặp ~(i, j)~ sao cho độ lệch bằng ~K~.

Input:

• Dòng 1 ghi hai số nguyên ~N, K~ (~1 \le N \le 10^5, 0 \le K \le 10^9~)
• Dòng 2 ghi ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| \le 10^9~), mỗi số cách nhau một dấu cách

Output:

Ghi ra một số duy nhất là số cách chọn cặp thỏa mãn. Nếu không có cặp nào, ghi ra 0.

Ví dụ:

dolech.inp

5 10
2 -4 5 -5 -8

dolech.out

2

Cho một dãy số nguyên gồm N phần tử không âm ~a_1, a_2, \dots, a_N~. K được gọi là số tiêu chuẩn nếu trong dãy A có ít nhất K số không nhỏ hơn K.

Input:

• Dòng 1 ghi số nguyên ~N~ (~N \le 1000~)
• Dòng 2 ghi ~N~ số nguyên ~a_i~ (~a_i \le 10^6~)

Output:

Ghi ra số tiêu chuẩn lớn nhất trong mảng A. Nếu không có số nào thì in ra 0.

Ví dụ:

sotc.inp

5
3 4 7 6 7

sotc.out

4

Cho một dãy số nguyên gồm N phần tử không âm ~A_1, A_2, \dots, A_N~. K được gọi là số tiêu chuẩn nếu trong dãy A có ít nhất K số không nhỏ hơn K.

Input:

• Dòng 1 ghi số nguyên ~N~ (~N \le 10^5~)
• Dòng 2 ghi ~N~ số nguyên ~A_i~ (~A_i \le 10^6~)

Output:

Ghi ra số tiêu chuẩn lớn nhất trong mảng A. Nếu không có số nào thì in ra 0.

Ví dụ:

sotc2.inp

5
3 4 7 6 7

sotc2.out

4

Bài: Thống kê độ tuổi

Mô tả

An đang thực hiện thu thập độ tuổi của tất cả người dân trong một làng nọ. Sau khi thu thập xong, An muốn biết trong ngôi làng này, hiện tại có bao nhiêu độ tuổi khác nhau.

Yêu cầu

Viết chương trình nhập vào một mảng gồm n số nguyên, được đánh số từ 1 đến n là số tuổi hiện tại của n người dân. Hãy đếm xem có bao nhiêu độ tuổi khác nhau của người dân ở trong làng đó.

Input

• Dòng 1: số nguyên n (0 < n < 10⁶)
• Dòng 2: n số nguyên a₁, a₂, ..., aₙ là độ tuổi của mỗi người dân trong làng (0 ≤ aᵢ ≤ 120)

Output

• Một số nguyên là số lượng các độ tuổi khác nhau của người dân.

Ví dụ

Giải thích: có 3 độ tuổi khác nhau là: 1, 23, 56.

Ràng buộc

• 50% số test có n ≤ 10⁴
• 50% số test còn lại có n ≤ 10⁶

Có một hòn đảo rất đẹp, thu hút nhiều khách du lịch đến thăm. Trên đảo có ~n~ người thuộc nhiều bộ tộc sinh sống. Dân cư trên đảo rất thân thiện. Mỗi người thuộc một bộ tộc nào đó. Trong đoàn du lịch có một nhà nhân chủng học. Tranh thủ dịp may được ghé thăm đảo, ông không bỏ phí thời gian tiến hành khảo sát. Ông gặp từng người một trên đảo với một câu hỏi duy nhất: Trên đảo, bộ tộc của bạn có bao nhiêu người?. Từ kết quả khảo sát, ông đã xác định được số bộ tộc khác nhau tồn tại trên đảo.

Ví dụ: với ~n = 10~ và các câu trả lời là ~5,1,2,5,5,2,5,5,2,2~ ta có thể suy ra là trên đảo có ~4~ bộ tộc khác nhau.

Yêu cầu

• Cho ~n~ câu hỏi và các câu trả lời. Hãy xác định số bộ tộc trên đảo. Dữ liệu đảm bảo bài toán có nghiệm.

Input

• Dòng 1 chứa số nguyên ~n~ (~1 ≤ n ≤ 100000~)
• Mỗi dòng trong ~n~ dòng sau chứa một số nguyên, câu trả lời nhận được.

Output

• Một số nguyên là số bộ tộc trên đảo.

Sample Input

10
5 1 2 5 5 2 5 5 2 2

Sample Output

4

Đề bài

Vova thích sô cô la. Cậu ấy đã mua một thanh sô cô la lớn gồm N miếng sô cô la nhỏ. Mỗi miếng sô cô la có một độ ngon nhất định, cụ thể miếng thứ i có độ ngon là ~A[i]~ ~(1 ≤ i ≤ N)~.

Mỗi lần, Vova có thể ăn miếng đầu trái hoặc miếng đầu phải trên thanh sô cô la. Vova luôn để phần cho em gái miếng sô cô la cuối cùng của thanh sô cô la sau khi cậu ta đã ăn ~N-1~ miếng. Vova có tính tham ăn nên cậu ấy muốn ăn được nhiều miếng ngon nhất có thể.

Biết tình trạng độ ngon của N miếng sô cô la, hãy xác định độ ngon của miếng sô cô la cuối cùng mà em gái Vova có thể nhận được.

Đầu vào:

Dòng đầu tiên của đầu vào chứa một số nguyên ~T~ biểu thị số bộ dữ liệu cần kiểm tra. Trong đó, mỗi bộ dữ liệu gồm:

• Dòng đầu chứa một số nguyên ~N~ ~(N <= 1000)~ cho biết độ dài thanh sô cô la (số miếng trên thanh kẹo).
• Dòng thứ hai chứa N số nguyên được phân cách bằng dấu cách biểu thị độ ngon tương ứng của mỗi miếng sô cô la nhỏ theo thứ tự từ đầu trái sang đầu phải thanh sô cô la.

Đầu ra:

Ứng với mỗi bộ dữ liệu đầu vào,in ra một dòng chứa đáp án tương ứng.

Ví dụ:

CHOCOLATE.INP:

3
5
5 3 1 6 9
6
2 6 4 8 1 6
4
2 2 2 2

CHOCOLATE.OUT:

1
1
2

Đề bài

Viết chương trình nhập vào một ma trận có ~m~ hàng và ~n~ cột. In ra giá trị lớn nhất của từng hàng.

Input

• Dòng đầu tiên ghi hai số nguyên không âm ~m, n~ (~m, n \leq 200~).
• ~m~ dòng sau, mỗi dòng ghi ~n~ số nguyên cách nhau một dấu cách biểu diễn ma trận.

Output

In ra kết quả bài toán.

Ví dụ

Sample Input

3 2
3 6
2 1
7 0

Sample Output

6
2
7

Giới hạn

• Thời gian: 1s
• Bộ nhớ: 256MB
• ~m, n \leq 200~

Đề bài

Viết chương trình nhập vào một ma trận có ~m~ hàng và ~n~ cột. In ra giá trị lớn nhất của từng cột.

Input

• Dòng đầu tiên ghi hai số nguyên không âm ~m, n~ (~m, n \le 200~).
• ~m~ dòng sau, mỗi dòng ghi ~n~ số nguyên cách nhau một dấu cách biểu diễn ma trận.

Output

In ra kết quả bài toán.

Ví dụ

Sample Input

3 2
3 6
2 1
7 0

Sample Output

7
6

Đề bài

Ở siêu thị BigC có trò chơi đập ếch. Màn hình trò chơi là một bảng lưới ô vuông hình chữ nhật được chia thành ~M~ hàng và ~N~ cột. Trong mỗi ô của bảng có một chú ếch, trên lưng có in một số nguyên dương là số hiệu của chú ếch đó có giá trị ~\leq 10^5~.

Khi người chơi cầm búa đập vào chú ếch ở một ô nào đó trong bảng thì tất cả các chú ếch có cùng số hiệu sẽ biến mất (kể cả chú ếch bị đập) và người chơi sẽ nhận được số điểm bằng tổng số ếch đã bị biến mất.

Yêu cầu

Cho biết tổng số điểm lớn nhất mà người chơi có thể nhận được sau ~K~ lần đập.

Input

Dòng đầu tiên ghi 3 số nguyên dương ~M, N~ và ~K~. (~N, M \leq 1000~; ~1 \leq K \leq N \times M~).

~M~ dòng tiếp theo, dòng thứ ~i~ ghi ~N~ số tương ứng là số hiệu của các chú ếch ở hàng ~i~.

Output.

In ra kết quả bài toán.

Ví dụ

Sample Input

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

Sample ouput

15

Giải thích

Lần 1 đập ếch có số hiệu là 1 , đạt 7 điểm. Lần 2 đập ếch có số hiệu là 4 , đạt 8 điểm.