Cho một dãy nhị phân gồm N bit, chúng ta có 3 loại thao tác trên dãy:

• 0 p : Bật/tắt bit \(p\) trên dãy.
• 1 u v : Đếm số lượng bit 0 trong đoạn từ \(u\) đến \(v\) tính cả 2 đầu.
• 2 k : Tìm vị trí bit 0 thứ \(k\) tính từ đầu dãy.

Input

• Dòng đầu chứa số nguyên \(n\) là độ dài dãy nhị phân.
• Dòng 2 chứa một xâu nhị phân độ dài \(n\).
• Dòng 3 chứa số nguyên \(m\) là số truy vấn.
• \(m\) dòng tiếp theo, mỗi dòng chứa một trong 3 định dạng của các truy vấn.

Output

• Gồm nhiều dòng trả lời truy vấn 2 và 3,
• Với truy vấn 3 nếu không tồn tại bit 0 thứ \(k\) thì in ra 0.

Giới hạn

• \(n,m,k\leq 50000\)

Ví dụ

Sample Input

5
10010
4
1 1 4
0 3
1 1 4
2 3

Sample Output

2
1
0