Cho một xâu kí tự ~s~ (có thể có dấu cách) thể hiện một câu. Các từ trong câu cách nhau một dấu cách và câu không có dấu chấm câu. Hãy viết hoa các kí tự đầu tiên của mỗi từ trong xâu ~s~.

Input

• Gồm một xâu kí tự ~s~ duy nhất (~1 \le |s| \le 1000~, ~s~ có thể bao gồm kí tự dấu cách).

Output

• In ra xâu ~s~ sau khi viết hoa các kí tự đầu tiên của mỗi từ.

Example

Den hoc o newton

Den Hoc O Newton

C++ is fun

C++ Is Fun

Cho hai xâu ~a,b~ và số nguyên ~x~. Hãy chèn xâu ~b~ vào vị trí ~x~ của xâu ~a~. (Xâu bắt đầu tại vị trí 0)

Input

• Gồm hai xâu kí tự ~a, b~ (~1 \le |a, b| \le 1000~, ~a, b~ không bao gồm kí tự dấu cách) và một số nguyên ~x~.

Output

• In ra xâu ~a~ sau khi chèn

Example

lsadfh ass 1

lasssadfh

newton notwen 5

newtonotwenn

Cho hai xâu ~a~ và ~b~. Hãy kiểm tra xâu ~b~ có nằm trong xâu ~a~ hay không. Nếu có in ra YES, ngược lại in ra NO.

Input

• Dòng đầu tiên chứa xâu ~a~.
• Dòng thứ hai chứa xâu ~b~.

Output

• In ra YES nếu xâu ~b~ nằm trong xâu ~a~, ngược lại in ra NO.

Example

lsadfh
sad

YES

lsngd
mnsd

NO

Cho xâu ~S~ chỉ gồm hai kí tự 'a' và 'b'. Xâu mới được tạo bởi việc ghép ~X~ lần xâu ~S~ liền kề với nhau.

Yêu cầu: Hãy đếm xem có bao nhiêu xâu con "ab" xuất hiện trong xâu được tạo thành.

Input

• Dòng thứ nhất chứa xâu ~S~ có độ dài ~N~ (~0 < N \le 30~).
• Dòng thứ hai chứa số nguyên dương ~X~ (~0 < X \le 10~).

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

ab
3

3

ba
4

3

Note

• Trong test 1, xâu ~S~=ababab
• Trong test 2, xâu ~S~=babababa

Xâu ~S~ được chuẩn hóa là thỏa mãn các điều kiện sau:

• Không chứa dấu cách ở vị trí đầu tiên và cuối cùng.
• Không chứa 2 dấu cách liên tiếp nhau.
• Các chữ cái đầu tiên của 1 câu phải viết hoa.
• Dấu chấm, dấu phẩy liền ngay sau kí tự, sau đó là dấu cách rồi đến kí tự.

Nhập vào một xâu ~S~, chuẩn hóa xâu $S$ đó.

Input

• Gồm một xâu kí tự ~S~ duy nhất (~1 \le |S| \le 1000~).

Output

• Dòng duy nhất in ra xâu ~S~ sau khi đã chuẩn hóa.

Example

XIN chao . hom NAY , troi THAT dep .

Xin chao. Hom nay, troi that dep.

ShIKANokO noKOnOko koshItanTAn.

Shikanoko nokonoko koshitantan.