Mọi thông tin đều được mã hoá dưới dạng một chuỗi số nhị phân. Để nâng cao độ tin cậy khi truyền tin, mỗi bít được biểu diễn lặp lại 3 lần. Ví dụ, các bít tin '011' được biểu diễn thành '000111111' để thực hiện truyền. Do nhiễu của môi trường nên khi về đến đích, các bít tin có thể bị sai lệch. Vì vậy, khi nhận được thông tin cứ mỗi đoạn 3 bít được giải mã thành một bít. Bít này có giá trị 0 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 0, bít này có giá trị 1 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 1. Ví dụ, nếu các bít tin nhận được là '000110010011', sau khi đã giải mã ta thu được '0101'. Cho chuỗi nhị phân biểu diễn thông tin nhận được, hãy giải mã chuỗi nhị phân đó.

Dữ liệu vào

• Dòng đầu tiên ghi chuỗi nhị phân cần giải mã, là một dãy các số 0, 1 ghi liền nhau,độ dài không quá ~10^6~ kí tự.

Dữ liệu ra

• Dòng đầu tiên ghi chuỗi nhị phân đã được giải mã, là một dãy các số 0, 1 ghi liền nhau.

Ví dụ

Input

001111010110111000

Output

010110

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~.

Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu 'aaabccc' sẽ nén thành '3ab3c'.

Yêu cầu: Hãy lập trình để nén một xâu ký tự thường theo cách trên.

Input:

• Một xâu các ký tự là chữ cái thường có tối đa ký tự ~10^5~.

Output:

• Một xâu ký tự sau khi nén.

Example:

Input:

hhhooocssiinh

Output:

3h3oc2s2inh

Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu 'aaabccc' sẽ nén thành '3ab3c'.

sẽ nén thành

Yêu cầu: Cho một xâu ký tự S đã được nén theo cách trên. Hãy lập trình để giải nén xâu ký tự S.

Input:

• Một xâu các ký tự là chữ cái thường có tối đa ký tự ~10^5~.

Output:

• Một xâu ký tự sau khi giải nén.

Example:

Input:

3h3oc2s2inh

Output:

hhhooocssiinh

Julius Caesar bảo vệ các thông tin quan trọng bằng mã hóa mật mã. Mật mã của Caesar được thực hiện bằng cách dịch chuyển các ký tự chữ cái sang phải 𝑘 lần. Nếu như ký tự đó vượt quá ký tự cuối cùng của bảng chữ cái thì nó được chuyển lên đầu. Ví dụ với 𝑘 = 3, các chữ cái 𝑤, 𝑥, 𝑦, 𝑧 được dịch chuyển thành 𝑧, 𝑎, 𝑏, c.

Yêu cầu: Cho xâu 𝑠 và số nguyên dương 𝑘, hãy mã hóa xâu 𝑠 bằng cách dùng mật mã của Caesar. Lưu ý: mật mã của Caesar chỉ mã hóa các ký tự chữ cái.

Input:

• Dòng 1: Ghi xâu 𝑠 ~1 \le length(s) \le 1000~
• Dòng 2: Ghi số nguyên dương ~𝑘~ (~0 \le 𝑘 \le 10000~)

(Dữ liệu đầu vào luôn đảm bảo bài toán có nghiệm)

Output:

• Ghi ra xâu 𝑠 sau khi đã mã hóa

Example:

Input:

middle-Outz
2

Output:

okffng-Qwvb

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

Một nhóm trò chuyện (chat) trong một mạng xã hội đưa ra quy định các thành viên mới tham gia nhóm phải gõ dòng tin nhắn "hello" lên nhóm. Tuy nhiên nhiều thành viên đã cổ tình gõ lặp, gõ thừa, hoặc gỡ thiếu đi một số ký tự. Ví dụ, có thành viên gõ "hellohello", có thành viên gõ "helalo", hoặc có thành viên gõ "helo".

Yêu cầu: Hãy xác định các tin nhắn hợp lệ hay không? Một tin nhắn được xem là hợp lệ nếu xóa đi một số ký tự thì tin nhắn sẽ trở thành "hello". Chú ý rằng có thể không cần xóa ký tự nào mà bản thân tin nhắn là "hello" thì hiển nhiên là hợp lệ.

Input

• Gồm nhiều dòng, mỗi dòng chứa một xâu không vượt quá 256 ký tự là tin nhắn của một thành viên trong nhóm. Các xâu ký tự có thể gồm các chữ cái, chữ số, ký tự đặc biệt, dấu cách trống hoặc không chứa ký tự nào.

Output

• Gồm các dòng tương ứng, trong đó ghi "YES" nếu tin nhắn hợp lệ và ghi "NO" nếu tin nhắn không hợp lệ.

Example

Input

hello
Ah, hello!
hallloa

Output

YES
YES
NO

Cho một chuỗi ~S~ (tối đa 100 kí tự) chỉ gồm các chữ cái in thường, chuỗi ~X~ được gọi là ước của chuỗi ~S~ nếu chuỗi ~X~ có độ dài ngắn nhất và khi ghép một số lần ~X~ ta được chuỗi ~S~.

Yêu cầu: Hãy tìm chuỗi ~X~ là ước của chuỗi ~S~.

Input

• Một dòng duy nhất chứa chuỗi ~S~.

Output

• Một dòng duy nhất chứa chuỗi ~X~ là ước của chuỗi ~S~.

Examples

Input

abababab

Output

ab

Input

ababc

Output

ababc

Note

Ở ví dụ 1, ta ghép 4 lần chuỗi ab được chuỗi ~S~.

Ở ví dụ 2, ta ghép 1 lần chuỗi ababc được chuỗi ~S~.