Cho chuỗi ký tự ~s~ gồm các ký tự latin in hoa (A đến Z). Ta gọi một đoạn liên tiếp các ký tự của ~s~ có mặt đủ 26 ký tự latin in hoa là một chuỗi con đầy đủ. Hãy tìm một chuỗi con đầy đủ của s có độ dài ngắn nhất.

INPUT

• Một dòng duy nhất chứa chuỗi ~s~. Độ dài chuỗi ~s~ không quá ~10^5~.

OUTPUT

• Một số nguyên dương duy nhất là độ dài chuỗi con đầy đủ ngắn nhất. Nếu không có chuỗi con đầy đủ thì ghi ra -1.

VÍ DỤ

Input:

ABCDEFGHIJKLMNOPQRSTUVWXYZASCSWO

Output:

26

Cho hai xâu ký tự ~S~ và ~T~ chỉ gồm các chữ cái in hoa tiếng Anh (~A–Z~).

Hãy tìm xâu con liên tiếp ngắn nhất của ~S~ sao cho xâu con đó chứa tất cả các ký tự của ~T~, bao gồm cả số lần xuất hiện của từng ký tự.

Nếu có nhiều xâu con thỏa mãn, hãy in ra xâu có độ dài nhỏ nhất. Nếu không tồn tại, in ra xâu rỗng.

Dữ liệu vào

• Dòng 1: xâu ~S~ (~1≤∣𝑆∣≤10^5~)
• Dòng 2: xâu ~T~ (~1≤∣𝑇∣≤10^5~)

Dữ liệu ra

• In ra xâu con ngắn nhất của ~S~ thỏa mãn yêu cầu. Nếu không tồn tại, in ra xâu rỗng (không in gì)

Ví dụ

Input1:

ADOBECODEBANC
ABC

Output1:

BANC

Input2:

AAABBC
ABC

Output2:

ABBC

Mật khẩu là một xâu ký tự. Một mật khẩu được gọi là an toàn nếu thoả mãn các điều kiện sau:

• Có độ dài ít nhất bằng 8
• Chứa ít nhất một chữ cái in hoa ['A'..'Z']
• Chứa ít nhất một chữ cái in thường ['a'..'z']
• Chứa ít nhất một chữ số ['0'..'9']

Cho một xâu ký tự có độ dài không quá 1000 ký tự.

Yêu cầu: Hãy xác định có bao nhiêu đoạn con gồm các ký tự liên tiếp nhau trong xâu S có thể chọn làm mật khẩu an toàn.

Input:

Được cho bởi tệp MATKHAU.INP có cấu trúc như sau:

• Dòng 1: Ghi xâu ký tự S

Output

Ghi ra tệp MATKHAU.OUT theo cấu trúc:

• Dòng 1. Ghi số nguyên dương t là kết quả tìm được theo yêu cầu.

Example

Input

ABC123abc

Output

3

Input

ABC123

Output

0

Constrains:

• Có 50% số test ứng với độ dài xâu ~S \le 50~
• Có 30% số test ứng với độ dài xâu ~50 \le S \le 300~
• Có 20% số test ứng với độ dài xâu ~300 \le S \le 1000~

Việc bảo vệ máy tính của mình để hạn chế người khác xâm nhập vào là một vấn đề đặt ra cho mọi người sử dụng máy tính. Để tăng tính an toàn trong lưu trữ, bạn Bình đã quyết định giấu mật khẩu truy cập máy tính của mình vào 1 xâu 𝑡 với 1 quy ước sao cho khi cần bạn ấy có thể lấy lại mật khẩu từ 𝑡 như sau:

Mật khẩu là xâu ~𝑝~ (gồm các kí tự chữ thường trong bảng chữ cái tiếng Anh). Xâu ~𝑝~ là một chuỗi liên tiếp các kí tự trong ~𝑡~ xuất hiện đúng 1 lần và dịch chuyển (mã hóa) nó qua ~𝑚~ kí tự trong bảng mã ASCII, chẳng hạn trong bảng mã ASCII kí tự ~𝑎~ được dịch chuyển qua 3 kí tự là ~𝑑~. Bạn hãy giúp Bình viết chương trình tìm lại mật khẩu.

Ví dụ: xâu 𝑡='𝑎𝑎𝒗𝑤𝑤𝑛𝒚𝒔𝑐𝑐𝑤𝑐𝑛. Với ~𝑚 = 2~, mật khẩu ~𝑝~ là 'xau'

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~𝑚~ (~0 ≤ 𝑚 ≤ 25~), là số ký tự cần dịch chuyển.

• Dòng thứ hai chứa xâu 𝑡 có chiều dài ~𝑙~ (~1 ≤𝑙≤ 10^7~), gồm các ký tự trong bảng mã ASCII.

Kết quả:

• Xâu ~𝑝~ cần tìm. Nếu không tồn tại xâu ~𝑝~ thì ghi ~0~.

Cho xâu S độ dài n. Hãy tìm xâu con dài nhất của ~S~, sao cho mỗi ký tự tham gia vào xâu con không quá ~k~ lần (~1 ≤ n ≤ 100000~, ~1 ≤ k ≤ n~).

Yêu cầu: Chỉ ra độ dài của xâu con tìm được và vị trí của ký tự đầu tiên thuộc xâu con trong xâu ~S~ ban đầu. Nếu có nhiều cách chọn xâu con – chỉ ra cách chọn xâu con với vị trí bắt đầu là nhỏ nhất.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~

• Dòng thứ hai chứa xâu ~S~.

Kết quả:

• Một dòng chứa hai số nguyên: độ dài xâu con và vị trí ký tự đầu tiên của xâu con. Nếu có nhiều xâu con thì ghi vị trí của xâu con đầu tiên trong dãy.

Ví dụ:

Input

5 2
ababa

Output

4 1

Hai xâu A và B tương đương nhau khi và chỉ khi có thể sắp xếp lại xâu A thành xâu B. Cho hai xâu A và B, hãy tìm xem hai xâu đó có tương đương không.

Input:

• Dòng 1. Xâu ký tự a
• Dòng 2. Xâu ký tự b

Output:

• Ghi 'Yes' nếu 2 xâu a,b tương đương, ngược lại ghi 'No'.

Example:

Input:

abcdef
acebdf

Output:

Yes

Constraints:

• Độ dài xâu A,B bằng nhau, không quá 1000 và chỉ chứa chữ cái viết thường.

Cho xâu X, kiểm tra xem xâu X có chứa đủ các ký tự từ a đến z không.

Input:

• Dòng 1. Xâu ký tự s

Output:

• Dòng 1. ghi ký tự 'Y' nếu xâu S có đầy đủ các ký tự từ a đến z, ngược lại ghi 'N'.

Example:

Input:

abcdefghijklmnopqrstuvwxyz

Output:

Y

Constraints:

Độ dài xâu X không quá 1000 và chỉ chứa chữ cái viết thường.

Ta định nghĩa các kí tự in thường (~'a'…'z'~) và in hoa (~'A'…'Z'~) được sắp xếp theo đúng thứ tự cho trong bảng chữ cái gọi là sắp xếp tăng dần, còn sắp xếp theo chiều ngược lại được gọi là sắp xếp giảm dần.

Cho một xâu S chỉ gồm các ký tự in thường (~'a'…'z'~) và in hoa (~'A'…'Z'~).

Yêu cầu: Sắp xếp xâu ~S~ theo thứ tự: Các kí tự in hoa giảm dần rồi đến các kí tự in thường giảm dần.

Input

• Gồm một dòng duy nhất chứa xâu ~S~ (~|S| ≤ 10^5~).

Output

• Xâu S sau khi được sắp xếp theo yêu cầu đề bài.

Scoring

• Có 50% số điểm ứng với các test có ~|S| ≤ 10^3~.

• Có 50% số điểm ứng với các test có ~|S| ≤ 10^5~.

Example

Input

aBAbDAbaC

Output

DCBAAbbaa