Cho một xâu nhị phân (bắt đầu từ chỉ số \(0\)). Bạn hãy thực hiện các thao tác dạng \(l\:r\): lật tất cả các bit trong vị trí từ \(l\) tới \(r\) trên xâu, cuối cùng in ra xâu nhị phân đó.

Ghi chú: Lật bit là phép biến đổi bit \(0\) thành bit \(1\), bit \(1\) thành bit \(0\).

Đầu vào

Dòng đầu tiên chứa một xâu nhị phân, độ dài \(L\) không quá \(10^6\).

Dòng tiếp theo chứa một số nguyên \(q\) \((1 \le q \le 10^6)\), số thao tác trên xâu.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) \((0 \le l \le r \le L - 1)\).

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Đầu ra

Một xâu nhị phân duy nhất.

Subtask

\(30\%\) số test có \(L*q \le 10^6\).

Ví dụ

Đầu vào:

10010100
3
0 2
1 3
6 7

Đầu ra:

00000111

Giải thích:

Sau thao tác đầu tiên ta được xâu: \(01110100\).

Sau thao tác thứ hai ta được xâu: \(00000100\).

Sau thao tác cuối cùng ta được xâu: \(00000111\) \(\to\) xuất ra \(00000111\).