Cho hai xâu kí tự ~a~, ~b~ và ~10^{18}~ xâu ~f_1, f_2, \dots, f_{10^{18}}~. Ban đầu ta có ~f_1 = a~, ~f_2 = b~, ~f_i = f_{i-2} + f_{i-1}~ với mọi ~3 \le i \le 10^{18}~ (phép '+' là phép nối xâu, ví dụ "abc" ~+~ "defg" ~=~ "abcdefg"). Gọi thao tác sau đây là thao tác ~X~:

• Gán ~f_1 = a~, ~f_2 = b~. Với mọi ~i~ từ ~3~ đến ~10^{18}~, ta gán ~f_i = f_{i-2} + f_{i-1}~.

Đặt ~|S|~ là độ dài xâu ~S~, ~S_i~ là kí tự thứ ~i~ của xâu ~S~ ~(1 \le i \le |S|)~. Bạn cần phải xử lí ~q~ truy vấn, mỗi truy vấn thuộc ~1~ trong ~4~ loại sau đây:

• Loại ~1~: Cho ~2~ số nguyên dương ~i, x~. Cho biết kí tự ~f_{i_x}~.

• Loại ~2~: Cho ~3~ số nguyên dương ~i, l, r~ và một kí tự ~\theta~. Cho biết trong các kí tự ~f_{i_l}, f_{i_{l+1}}, \dots, f_{i_r}~ có bao nhiêu kí tự là ~\theta~?

• Loại ~3~: Cho ~2~ số nguyên dương ~l, r~ và một kí tự ~\theta~. Gán các kí tự ~a_l, a_{l+1}, \dots, a_r~ bằng ~\theta~.

• Loại ~4~: Cho ~2~ số nguyên dương ~l, r~ và một kí tự ~\theta~. Gán các kí tự ~b_l, b_{l+1}, \dots, b_r~ bằng ~\theta~.

Sau mỗi truy vấn loại ~3~ hoặc ~4~, ta thực hiện lại thao tác ~X~ ở trên. Hãy giải bài toán này.

Input

Gồm ~q + 3~ dòng, trong đó:

• Dòng đầu tiên gồm xâu kí tự ~a~ ~(1 \le |a| \le 10^6)~. Các kí tự của ~a~ chỉ nằm trong tập các chữ cái Latin in thường.

• Dòng thứ ~2~ gồm xâu kí tự ~b~ ~(1 \le |b| \le 10^6)~. Các kí tự của ~b~ chỉ nằm trong tập các chữ cái Latin in thường.

• Dòng thứ ~3~ gồm duy nhất số nguyên dương ~q~ ~(1 \le q \le 10^5)~.

• ~q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn. Trong đó:

  • Truy vấn loại ~1~ có dạng 1 i x ~(1 \le i \le 10^{18},\ 1 \le x \le \min(|f_i|, 10^{18}))~.

  • Truy vấn loại ~2~ có dạng 2 i l r θ ~(1 \le i \le 10^{18},\ 1 \le l \le r \le \min(|f_i|, 10^{18}))~, ~\theta~ là kí tự nằm trong tập các chữ cái Latin in thường.

  • Truy vấn loại ~3~ có dạng 3 l r θ ~(1 \le l \le r \le |a|)~, ~\theta~ là kí tự nằm trong tập các chữ cái Latin in thường.

  • Truy vấn loại ~4~ có dạng 4 l r θ ~(1 \le l \le r \le |b|)~, ~\theta~ là kí tự nằm trong tập các chữ cái Latin in thường.

Output

Với mỗi truy vấn loại ~1~ và ~2~, in ra trên một dòng là kết quả của truy vấn tương ứng.

Scoring

Sample Input 1

abc
cb
6
1 5 11
2 4 2 7 b
3 1 2 d
4 2 2 c
1 5 9
2 6 7 18 c

Sample Output 1

c
3
d
8

Notes

Giải thích test ví dụ:

• Ở truy vấn đầu tiên, ta có ~f_5 =~ "abccbcbabccb". Kí tự thứ ~11~ của ~f_5~ là 'c'.

• Ở truy vấn thứ ~2~, ta có ~f_4 =~ "cbabccb". Trong đoạn "babccb" có ~3~ kí tự là 'b'.

• Ở truy vấn thứ ~3~, ta biến đổi xâu ~a =~ "ddc".

• Ở truy vấn thứ ~4~, ta biến đổi xâu ~b =~ "cc".

• Ở truy vấn thứ ~5~, ta có ~f_5 =~ "ddcccccddccc". Kí tự thứ ~9~ của ~f_5~ là 'd'.

• Ở truy vấn cuối cùng, ta có ~f_6 =~ "ccddcccddcccccddccc". Trong đoạn "cddcccccddcc" có ~8~ kí tự là 'c'.