Trong khi đang di chuyển, các con kiến đi thành đàn nối đuôi nhau. Ta xem rằng mỗi khi hai đàn kiến đi ngược chiều chạm nhau (mà chiều rộng không đủ lớn để hai bên tránh nhau), bọn chúng sẽ nhảy qua nhau.

Từ khi hai đàn gặp nhau, cứ mỗi giây, những con kiến sẽ nhảy qua (hoặc bị nhảy qua) con kiến đứng trước chúng, nói cách khác, chúng đổi vị trí cho nhau khi và chỉ khi chúng đi ngược hướng nhau.

Cho hai xâu \(S1\) và \(S2\) gồm các kí tự latin in hoa biểu diễn thứ tự các con kiến trong hai đàn. Hãy tìm thứ tự của chúng sau \(T\) giây kể từ khi hai đàn gặp nhau.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N1, N2\)
• Dòng thứ hai chứa xâu \(S1\)
• Dòng thứ ba chứa xâu \(S2\)
• Dòng cuối cùng chứa số nguyên \(T\)

Output

• In ra trên 1 dòng chứa thứ tự của các con kiến.

Constraints

• \(0 < N1, N2 \le 20\)
• \(0 \le T \le 50\)

Example

Input

3 3
ABC
XYZ
0

Output

CBAXYZ

Input

3 3
ABC
XYZ
2

Output

CXBYAZ

Input

3 4
FDB
ACEG
3

Output

ABCDEFG