Trong quá trình nghiên cứu và phân tích dữ liệu gen, bạn phát hiện ra một loại đột biến đặc biệt xảy ra trên chuỗi DNA của một mẫu sinh vật. Chuỗi DNA ban đầu được biểu diễn bằng một xâu ~S~ gồm ~n~ kí tự in thường. Các vị trí được đánh số từ ~1~ tới ~n~.

Trong quá trình tiến hóa và sao chép tế bào, hệ thống ghi nhận có hai loại sự kiện liên tục xảy ra đối với chuỗi DNA này:

• Sự kiện 1 (Đột biến nhân đôi): Một đoạn gen từ vị trí ~l~ đến ~r~ xảy ra lỗi trong quá trình phiên mã, khiến mỗi nucleotide (kí tự) trong đoạn này bị nhân đôi. (Ví dụ: nếu chuỗi hiện tại là abac và xảy ra đột biến từ vị trí ~2~ đến ~3~, chuỗi mới sẽ bị kéo dài và trở thành abbaac).

• Sự kiện 2 (Truy vấn trích xuất): Để đánh giá đặc điểm di truyền tại thời điểm hiện tại, bạn cần trích xuất thông tin của chuỗi gen. Bạn muốn xác định xem nucleotide ở vị trí thứ ~i~ trong chuỗi gen lúc này đang là kí tự nào.

Với số lượng các sự kiện đột biến xảy ra liên tục, chuỗi gen có thể trở nên rất dài. Nhiệm vụ của bạn là viết một chương trình mô phỏng lại quá trình biến đổi này và trả lời chính xác các truy vấn trích xuất dữ liệu.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 3 \cdot 10^5)~ — độ dài của chuỗi DNA ban đầu ~s~ và tổng số sự kiện được ghi nhận.

• Dòng thứ hai chứa chuỗi ~s~ gồm ~n~ ký tự là các chữ cái tiếng Anh in thường — cấu trúc của chuỗi DNA ban đầu.

• ~q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo một trong hai định dạng:

  • ~1\ l\ r~ ~(1 \le l \le r \le 10^{18})~: Các nucleotide trong đoạn ~[l, r]~ của chuỗi hiện tại bị nhân đôi.

  • ~2\ i~ ~(1 \le i \le 10^{18})~: Yêu cầu xác định kí tự tại vị trí ~i~.

Tất cả giá trị ~l, r, i~ đều đảm bảo không vượt quá độ dài xâu ~S~ tại thời điểm sự kiện diễn ra.

Output

Với mỗi sự kiện truy vấn loại ~2~, in ra kí tự nucleotide tìm được trên một dòng riêng biệt.

Scoring

Sample Input 1

4 6
abac
2 2
2 3
1 2 3
2 3
2 4
2 6

Sample Output 1

b
a
b
a
c