Bạn có hai tài khoản email, lần lượt có mật khẩu là ~S_1~ và ~S_2~.

Ô để nhập mật khẩu ở email 1 có độ dài là ~L_1~, tương tự với ô của email 2 có độ dài là ~L_2~.

Để nhập mật khẩu, bạn được điền 26 kí tự latin và kí tự '<' (tức là xóa một kí tự). Giả sử bạn đang điền mật khẩu cho email 1 ở ô độ dài là ~L_1~, gọi ~T~ là giá trị xâu đang điền, ~|T|~ là độ dài của xâu ~T~:

• Nếu ~|T| = 0~: khi bạn điền '<' (tức là xóa), không có gì xảy ra. Ngược lại nếu ~|T| > 0~ thì bạn xóa đi kí tự cuối cùng.

• Nếu ~|T| = L_1~, thì nếu bạn điền thêm kí tự, xâu ~T~ sẽ không thay đổi (do đã tràn ra khỏi số kí tự có thể lưu), ngược lại thì xâu ~T~ sẽ nhận giá trị vừa điền vào cuối.

Vì sợ máy tính của mình bị cài keylog, bạn quyết định sẽ tạo ra một cách điền mang tính bảo mật như sau:

• Gọi ~S~ là xâu chứa thao tác cách điền của bạn. Nếu bạn thực hiện thao tác biểu diễn bởi ~S~ cho ô mật khẩu 1, thì kết quả thu được là ~S_1~. Ngược lại là ~S_2~.

• Bạn muốn độ dài xâu ~S~ là nhỏ nhất có thể.

Yêu cầu: Hãy tìm xâu ~S~ tương ứng.

Input

Dữ liệu vào từ file văn bản password.inp.

Dòng đầu tiên gồm xâu ~S_1~ và số nguyên ~L_1~ ~(1 \le |S_1| \le L_1 \le 1000)~ — lần lượt là mật khẩu và độ dài của ô để nhập mật khẩu của email 1.

Dòng thứ hai gồm xâu ~S_2~ và số nguyên ~L_2~ ~(1 \le |S_2| \le L_2 \le 1000)~ — lần lượt là mật khẩu và độ dài của ô để nhập mật khẩu của email 2.

Xâu ~S_1~ và ~S_2~ chỉ chứa các chữ cái tiếng Anh in thường.

Lưu ý: ~|S|~ là độ dài của xâu ~S~.

Output

Ghi ra file văn bản password.out.

Dòng đầu tiên gồm độ dài của xâu ~S~ tương ứng. Nếu không tồn tại xâu ~S~ thỏa mãn, in ra ký tự "!".

Dòng thứ hai gồm xâu ~S~ tương ứng, nếu tồn tại.

Lưu ý: Thí sinh sẽ được ~50\%~ số điểm của một test nếu in ra đúng độ dài xâu ~S~, ~100\%~ số điểm nếu in ra được xâu ~S~ thỏa mãn yêu cầu.

Scoring

Sample Input 1

ab 3
abc 4

Sample Output 1

5
abcq<

Sample Input 2

abb 3
abc 4

Sample Output 2

!

Notes

Ví dụ 1 :

Chuỗi ~S~ là cách điền thao tác nhỏ nhất để tạo ra ~S_1~. Khi thực hiện các thao tác :

• 'a' ~\to~ "a".

• 'b' ~\to~ "ab".

• 'c' ~\to~ "abc". (Đã đạt độ dài tối đa là ~L_1 = 3~).

• 'q' ~\to~ "abc". (Xâu kí tự không thay đổi vì đạt đến độ dài tối đa của ~L_1~).

• '<' ~\to~ Xóa ký tự 'c', xâu hiện tại trở thành là "ab".

Sau khi thực hiện, ta được ~S_1 = \texttt{"ab"}~.

Tương tự, để tạo ra ~S_2~. Khi thực hiện các thao tác:

• 'a' ~\to~ "a".

• 'b' ~\to~ "ab".

• 'c' ~\to~ "abc"

• 'q' ~\to~ "abcq" (đã đạt độ dài tối đa là ~L_2 = 4~).

• '<' ~\to~ Xóa ký tự 'q', xâu hiện tại là "abc".

Tương tự, ta được ~S_2 = \texttt{"abc"}.~