Khảo cổ

Một nhóm khảo cổ họ tìm thấy những cổ vật mà trên đó có thông tin được mã hoá như sau:

Dòng đầu tiên là số $0$ hoặc số $1$;
Dòng thứ hai là một dãy các kí tự chữ cái la tình in thường (gọi là đoạn mã $V$).

Qua nghiên cứu một cổ vật, họ phát hiện ra rằng các thông tin được mã hoá theo mô tả trên sau khi giải mã sẽ thu được một đoạn mã thông tin gốc $S$. Quy luật biến đổi ngược lại từ đoạn mã gốc $S$ về đoạn mã $V$ theo các bước sau:

Bước 1: Đoạn mã gốc $S$ được nhân đôi thành đoạn mã $T$ (tức là $T = SS$, nối $S$ với chính nó);
Bước 2: Chọn một trong các kí tự của đoạn mã $T$, nhân đôi kí tự đó làm cho độ dài đoạn mã $T$ tăng thêm một kí tự, ta được một đoạn mã $U$;
Bước 3: Nếu dòng đầu tiên trên cổ vật là số $1$ thì đảo ngược đoạn mã $U$ được đoạn mã $V$, nếu dòng đầu tiên trên cổ vật là số $0$ thì đoạn mã $U$ chính là đoạn mã $V$.

Yêu cầu: Dựa vào thông tin mỗi cổ vật, bạn hãy lập trình giúp các nhà khảo cổ tìm kí tự được nhân đôi ở bước $2$ và đoạn mã thông tin gốc của cổ vật đó.

Input

Dữ liệu vào:

Dòng thứ nhất chứa số nguyên $K$ ($0 \le K \le 1$);
Dòng thứ hai chứa đoạn mã $V$ có độ dài không vượt quá $10^6$ kí tự.
Dữ liệu đảm bảo luôn có đáp án.

Ràng buộc:

Có $40\%$ số test ứng với $40\%$ số điểm của bài có độ dài của $V$ không quá $10^2$;
Có $30\%$ số test ứng với $30\%$ số điểm của bài có độ dài của $V$ không quá $10^5$;
Có $30\%$ số test còn lại ứng với $30\%$ số điểm của bài có độ dài của $V$ không quá $10^6$.

Output

In ra

Dòng thứ nhất ghi ra kí tự đã được nhân đôi;
Dòng thứ hai ghi ra đoạn mã gốc $S$.

Example 1

Input:

1
ebbaeba

Output:

b
abe

Example 2

Input:

0
ttpcdtpcd

Output:

t
tpcd

Note

Ở ví dụ thứ nhất, $K = 1$ nên đảo ngược $V$ được $U = $ abeabbe. Bỏ đi một kí tự $b$ trong cặp $bb$ ta được $T = $ abeabe $= SS$ với $S = $ abe, kí tự được nhân đôi là $b$.

Ở ví dụ thứ hai, $K = 0$ nên $U = V = $ ttpcdtpcd. Bỏ đi một kí tự $t$ ở đầu ta được $T = $ tpcdtpcd, $S = $ tpcd, kí tự được nhân đôi là $t$.

Điều hướng chính

Ngôn ngữ

Phím tắt