Trình Soạn Thảo Có Hoàn Tác

Một trình soạn thảo giữ chuỗi $S$, ban đầu rỗng. Hãy xử lý $q$ thao tác:

• $1$ $w$: nối chuỗi chữ thường $w$ vào cuối $S$.
• $2$ $k$: xóa $k$ ký tự cuối của $S$.
• $3$ $k$: in ký tự thứ $k$ của $S$, đánh số từ $1$.
• $4$: hoàn tác thao tác loại $1$ hoặc $2$ gần nhất chưa bị hoàn tác.

Thao tác loại $3$ không làm thay đổi chuỗi. Một thao tác loại $4$ chỉ hủy một thao tác sửa chuỗi và bản thân nó không được đưa vào lịch sử để hoàn tác lại.

Input

• Dòng đầu chứa số nguyên $q$.
• Mỗi trong $q$ dòng tiếp theo mô tả một thao tác theo một trong bốn dạng trên.

Output

• Với mỗi thao tác loại $3$, in ký tự được hỏi trên một dòng riêng.

Constraints

• $1\le q\le 10^5$.
• $w$ chỉ gồm các chữ cái thường $a$ đến $z$ và không rỗng.
• Tổng độ dài của mọi chuỗi $w$ không vượt quá $10^6$.
• Tổng các giá trị $k$ trong thao tác loại $2$ không vượt quá $2\cdot 10^6$.
• Mọi thao tác loại $2,3$ và $4$ đều hợp lệ tại thời điểm được thực hiện.

Scoring

• Subtask $1$ ($50\%$ số điểm): $q\le 2000$ và tổng độ dài các chuỗi được thêm không quá $2\cdot 10^4$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

9
1 abc
3 3
2 2
1 xy
3 2
4
1 z
4
3 1

c
x
a