Bob và truy vấn mảng

Trong một buổi đánh giá dự án bất động sản, FullHouse Dev được đối tác đưa ra một bài toán thú vị về xử lý dữ liệu. Họ cần phải xây dựng một hệ thống quản lý thông tin với các thao tác phức tạp trên một mảng số.

Bài toán

FullHouse Dev có một mảng \(A\) gồm \(N\) số nguyên. Ban đầu, tất cả các phần tử trong mảng đều bằng 0. Họ cần thực hiện \(Q\) thao tác trên mảng này.

Có ba loại thao tác có thể thực hiện:

1. Thao tác 1 \(X\): Cập nhật giá trị của \(A[X]\) thành \(2 * A[X] + 1\)
2. Thao tác 2 \(X\): Cập nhật giá trị của \(A[X]\) thành \(⌊A[X]/2⌋\), trong đó \(⌊x⌋\) là hàm làm tròn xuống
3. Thao tác 3 \(X\) \(Y\): Lấy tất cả các \(A[i]\) với \(X ≤ i ≤ Y\) và chuyển đổi chúng thành chuỗi nhị phân tương ứng. Sau đó nối tất cả các chuỗi nhị phân này và đếm tổng số ký tự '1' trong chuỗi kết quả.

Lưu ý: Đảm bảo có ít nhất 1 truy vấn loại 3 trong mỗi bộ test. Tất cả các phần tử mảng sẽ nằm trong giới hạn số nguyên 64 bit.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) cách nhau bởi dấu cách
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một trong ba loại thao tác như đã mô tả ở trên

OUTPUT FORMAT:

• Với mỗi truy vấn loại 3, in ra số lượng ký tự '1' trong chuỗi kết quả

Ràng buộc:

• \(1 ≤ N ≤ 10^5\)
• \(1 ≤ Q ≤ 10^5\)
• \(1 ≤ X, Y ≤ N\)

Ví dụ

INPUT

5 5
1 1
1 2
1 3
3 1 3
3 2 4

OUTPUT

3
2

Giải thích

Ban đầu, \(A=[0,0,0,0,0]\)

Sau truy vấn 1: \(A=[1,0,0,0,0]\)

Sau truy vấn 2: \(A=[1,1,0,0,0]\)

Sau truy vấn 3: \(A=[1,1,1,0,0]\)

Với truy vấn 4, số lượng số '1' trong biểu diễn nhị phân của \(A[1]=A[2]=A[3]=1\). Vì vậy, kết quả là 3.

Với truy vấn 5, kết quả là 2.