Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, …, a_n~, tìm phần tử xuất hiện nhiều nhất trong dãy.

Input

• Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy).
• Dòng thứ hai chứa ~n~ số nguyên là các phần tử ~a_1, a_2, …, a_n~

Giới hạn:

• ~1≤n≤10^5,0≤a_i≤10^5~

Output

• In ra trên một dòng hai số nguyên là phần tử xuất hiện nhiều nhất và số lần xuất hiện của phần tử đó (nếu có nhiều phần tử khác nhau với số lần xuất hiện là như nhau và lớn nhất thì in ra phần tử đầu tiên xuất hiện trong dãy).

Sample

Input #1

5
2 1 1 2 3

Output #1

22

Input #2

5
3 1 3 1 2

Output #2

3 2

Problem source: Chuyên Sơn La Online Judge

Cho một dãy gồm ~n~ số nguyên, hãy đếm số cặp bằng nhau trong dãy

Input

• Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy).
• Dòng thứ hai chứa n số nguyên là các phần tử ~a_1,a_2,…,a_n~

Giới hạn:

• ~1≤n≤10^5,0≤a_i≤5.10^4~

Output

• In ra trên một dòng số nguyên không âm là số cặp bằng nhau liên tiếp trong dãy.

Sample

Input #1

4
3 1 2 3

Output #1

1

Input #2

5
4 1 1 2 2

Output #2

2

Input #3

6
5 3 1 2 1 1

Output #3

3

Problem source: Chuyên Sơn La Online Judge

Cho mảng ~A~ gồm ~n~ số nguyên không âm: ~a_1, a_2, …, a_n~, hãy đếm số lần xuất hiện của các phần tử khác nhau trong mảng.

Input

• Dòng đầu ghi số nguyên dương ~n~ là số phần tử của mảng;
• Dòng thứ hai ghi ~n~ số ~a_1, a_2, …, a_n~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

• ~1 ≤ n ≤ 10^6, |a_i|≤ 10^9~.

Output

• Dòng đầu ghi số nguyên dương ~m~ là số phần tử khác nhau trong mảng ~A~;
• ~m~ dòng tiếp theo, mỗi dòng ghi ~2~ số ~u_i, f_i~ trong đó ~u_i~ là giá trị có trong mảng ~A, f_i~ là số lần xuất hiện của ~u_i~ (các số ~u_i~ được sắp xếp theo thứ tự xuất hiện lần đầu trong mảng ~A~).

Sample

Input #1

6
5 3 2 3 2 2

Output #1

3
5 1
3 2
2 3

Hint

Xét #1, có ~3~ giá trị khác nhau là ~5~, ~3~, ~2~ (theo đúng thứ tự xuất hiện). Số ~2~ xuất hiện ~3~ lần, số ~3~ xuất hiện ~2~ lần và số ~5~ xuất hiện ~1~ lần.

Problem source: Chuyên Sơn La Online Judge

Viết chương trình đếm tần suất xuất hiện của tất cả các ký tự (không phân biệt hoa thường) có trong chuỗi ~s~ được nhập từ bàn phím. In ra kết quả theo thứ tự từ điển (Tần suất xuất hiện của các chữ số 0-9, sau đó là a-z).

Lưu ý:

• Chỉ đếm các ký tự thuộc bảng chữ cái tiếng anh (a-z, A-Z) và các chỗ số (0-9)
• Không in các ký tự có tần suất bằng 0.

Input

• Chuỗi ~s~ có độ dài không vượt quá 10000 ký tự

Giới hạn

• Chuỗi ~s~ có thể bao gồm các chữ cái (a-z, A-Z), chữ số (0-9), khoảng trắng và các ký tự đặc biệt

Output

• kết quả theo thứ tự từ điển (Tần suất xuất hiện của các chữ số 0-9, sau đó là a-z).Mỗi dòng gồm 1 ký tự (dạng viết thường) và số lần xuất hiện của ký tự đó trong ~s~, ngăn cách nhau bởi dấu cách

Sample

Input #1

Lap Trinh Khong Kho!

Output #1

a 1
g 1
h 3
i 1
k 2
l 1
n 2
o 2
p 1
r 1
t 1

Tí năm nay đã lên lớp 1 rồi, Tết đến Tí rất vui vì nhận được rất nhiều lời chúc.

Vì mới tập viết nên Tí đã ghi lại tất cả các lời chúc đó. Cũng vì rất trân trọng các lời chúc nên Tí đã ghi tất cả các lời chúc bằng chữ IN HOA, tuy nhiên do mới tập viết nên Tí ghi không có dấu. Giờ ngồi lật lại cuốn nhật ký ghi các lời chúc, Tí thấy mình đã ghi được ~n~ lời chúc.

Tí muốn biết có bao nhiêu lời chúc khác nhau (hai lời chúc được gọi là khác nhau nếu chúng có độ dài khác nhau hoặc tồn tại ít nhất một vị trí mà ký tự ở vị trí đó của hai lời chúc là khác nhau, hay nói cách khác, đó là hai xâu ký tự khác nhau). Bạn hãy lập chương trình giúp Tí đếm xem có bao nhiêu lời chúc khác nhau nhé.

Input

• Dòng đầu chứa số nguyên dương ~n~ là số lời chúc Tí ghi được;
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu ký tự là một lời chúc.

Giới hạn:

• ~1 ≤ n ≤ 10^4~; Các lời chúc có độ dài không quá ~30~ ký tự gồm các chữ cái latinh IN HOA ‘A’…’Z’ và dấu cách.

Output

• Một số nguyên dương duy nhất là số lời chúc khác nhau.

Sample

Input #1

4
CHUC MUNG NAM MOI
HAPPY NEW YEAR
CHUC MUNG TUOI MOI
CHUC MUNG NAM MOI

Output #1

3

Problem source: Chuyên Sơn La Online Judge

Cho hai xâu ký tự ~s~ và ~t~ có độ dài lần lượt là ~n~ và ~m\ (m ≤ n)~. Xâu ~t~ được gọi là xuất hiện (khớp) tại vị trí ~i~ của xâu ~s~ nếu ~t = s[i..(i + m – 1)]~ (hay ~s[i] = t[1], ..., s[i + m – 1] = t[m]~).

Bạn được cho hai xâu ký tự ~s~ và ~t~ chỉ gồm các chữ cái Latinh thường (‘a’, …, ’z’). hãy liệt kê tất cả các vị trí trên xâu ~s~ mà xâu ~t~ xuất hiện.

Input

• Dòng đầu chứa xâu ~s~;
• Dòng thứ hai chứa xâu ~t~.

Giới hạn:

• ~1 ≤ |s|, |t| ≤ 10^6; |t| ≤ |s|~.

Output

• Ghi trên một dòng các vị trí xuất hiện của xâu ~t~ trong xâu ~s~ (chỉ số của ký tự đầu tiên trong xâu là ~1~, các vị trí được liệt kê theo thứ tự tăng dần, hai số liên tiếp được ghi cách nhau một dấu cách).

Sample

Input #1

abababa
ba

Output #1

2 4 6

Problem source: Chuyên Sơn La Online Judge

Phú ông có rất nhiều ngọc quý, các hạt ngọc được chia làm ~26~ loại khác nhau được đại diện bởi ~26~ ký tự la-tin thường (từ a đến z ). Phú ông đem kết các hạt ngọc thành những vòng ngọc, mỗi vòng có ~N~ hạt ngọc.

Một hôm, Phú ông đem các vòng ngọc của mình ra để đổi lấy quạt mo của Bờm. Phú ông đưa cho Bờm một vòng ngọc làm mẫu được biểu diễn bởi một xâu ký tự ~S~ độ dài ~N~ và ~K~ chuỗi ngọc đánh số từ ~1~ đến ~K~, chuỗi ngọc thứ ~i~ Phú ông đã cắt ra từ ~1~ vòng ngọc ở một vị trí nào đó và được biểu diễn bởi xâu ký tự ~S_i~. Phú ông sẽ cho Bờm các chuỗi ngọc nếu Bờm tìm được đúng những chuỗi ngọc được cắt ra từ vòng ngọc giống với vòng ngọc mẫu ~S~.

Yêu cầu: Cho biết ~N,K~, chuỗi ký tự ~S~ và ~K~ chuỗi ký tự ~S_1,S_2,…,S_K~. Hãy giúp Bờm tìm xem trong các chuỗi ngọc ~S_1,S_2,…,S_K~, chuỗi nào được cắt ra từ vòng ngọc giống với mẫu ~S~.

Input

• Dòng đầu chứa hai số nguyên dương ~N,K~ được ghi cách nhau một dấu cách;
• Dòng thứ hai chứa chuỗi ký tự ~S~;
• ~K~ dòng tiếp theo, dòng thứ ~i~ chứa chuỗi ký tự ~S_i~.

Giới hạn:

• ~70\%~ số điểm của bài có ~1≤N≤500;1≤K≤10~;
• ~30\%~ số điểm còn lại có ~500<N≤10^5;1≤K≤10~.</li>

Output

• Ghi ra ~K~ dòng, dòng thứ ~i~ là YES nếu chuỗi ngọc thứ ~i~ được cắt ra từ vòng ngọc giống với mẫu ~S~, ngược lại ghi ra NO.

Sample

Input #1

5 4
abcde
abcde
bcdea
cbaed
cdeab

Output #1

YES
YES
NO
YES

Problem source: Chuyên Sơn La Online Judge

Cho số nguyên dương ~n~ và dãy ~n~ số nguyên dương ~a_1, a_2, …, a_n~. Ta gọi một số ~a_i~ là độc thân nếu ~a_i ≠ a_j, \forall j ≠ i~. Hãy đếm số lượng số độc thân trong dãy số trên.

Input

• Dòng đầu ghi số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~. Hai số liên tiếp được ghi cách nhau một dấu cách.

Giới hạn:

• ~80\%~ số điểm có ~n ≤ 10^3~ và ~1 ≤ a_i ≤ 10^6~;
• ~20\%~ số điểm có ~10^3 < n ≤ 10^6~ và ~1 ≤ a_i ≤ 10^6~.

Output

• Một dòng duy nhất ghi số nguyên là số lượng số độc thân tìm được.

Sample

Input #1

5
1 2 2 3 1

Output #1

1

Hint

Quan sát #1, có duy nhất một số độc thân là số ~3~.

Problem source: Chuyên Sơn La Online Judge