Truy vấn MOD Phạm vi

Trong một ngày nắng nóng, FullHouse Dev đang ngồi trong phòng máy lạnh và nghiên cứu về các thuật toán xử lý chuỗi nhị phân. Họ nhận được một thử thách thú vị về việc tính toán giá trị của các đoạn con trong một chuỗi nhị phân.

Bài toán

FullHouse Dev được cung cấp một chuỗi nhị phân \(s\) và cần xử lý \(q\) truy vấn. Mỗi truy vấn thuộc một trong hai loại:

• Lật bit tại một vị trí (0 thành 1 hoặc ngược lại)
• Tính giá trị thập phân của một đoạn con theo modulo \(m\)

INPUT FORMAT

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) - độ dài chuỗi và số lượng truy vấn
• Dòng thứ hai chứa chuỗi \(s\) chỉ gồm các ký tự 0 và 1
• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • Loại 1: số 1 và vị trí cần lật bit
  • Loại 2: số 2, hai vị trí \(l\), \(r\) và số \(m\) để tính modulo

OUTPUT FORMAT

• Với mỗi truy vấn loại 2, in ra một số nguyên - giá trị thập phân của đoạn con theo modulo \(m\)

Ràng buộc

• \(1 \leq n, q \leq 10^5\)
• \(1 \leq m \leq 10^9\)

Ví dụ

INPUT

5 3
10101
2 1 5
1 2
2 1 3

OUTPUT

21
7

Giải thích

• Truy vấn 1: Đoạn "10101" có giá trị thập phân là 21
• Truy vấn 2: Lật bit tại vị trí 2, chuỗi trở thành "11101"
• Truy vấn 3: Đoạn "111" (từ vị trí 1 đến 3) có giá trị thập phân là 7