Bảo cùng với Bình hiện đang huấn luyện cho đội tuyển thi học sinh giỏi Tin học. Hôm nay, để không khí lớp đội tuyển trở nên sôi động hơn, Bình đề nghị Bảo ra một bài toán mang tính giải trí cao như sau:

Bài này liên quan đến một số phép toán xử lý bit. Trong xử lý bit có một số phép toán như phép 𝑂𝑅 (ký hiệu \(\vee\)), phép 𝐴𝑁𝐷 (ký hiệu \(\land\)), phép 𝑋𝑂𝑅 (ký hiệu\(\ \bigoplus\)).

Cho một mảng gồm \(n\) phần tử \(a_{1},a_{2},\ldots,\ a_{n}\). Có \(q\) truy vấn, truy vấn thứ \(i\) có dạng như sau:

• \(x_{i}\ y_{i}\): Tìm số cặp vị trí \((u,\ v)\) sao cho \(1 \leq u < v \leq n\) và \(x_{i}\bigoplus_{}^{}{\ \left( a_{u} \land a_{v} \right) = y_{i}}.\)

Bảo thấy ý này của Bình rất thú vị nên đã đồng ý luôn. Nhưng sau vài phút suy nghĩ, Bảo đã đề nghị Bình đổi sang \(2\) loại truy vấn để bài toán trở nên phức tạp hơn như sau:

• \(1\ x_{i}\ y_{i}\): Tìm số cặp vị trí \((u,\ v)\) sao cho \(1 \leq u < v \leq n\) và \(x_{i}\bigoplus_{}^{}{\ \left( a_{u} \land a_{v} \right) = y_{i}}.\)

• \(2\ x_{i}\ y_{i}\): Tìm số cặp vị trí \((u,\ v)\) sao cho \(1 \leq u < v \leq n\) và \(x_{i}\bigoplus_{}^{}{\ \left( a_{u} \vee a_{v} \right) = y_{i}}.\)

Bình đã đồng ý với ý kiến rất hay của Bảo, và cả hai đều đã chốt bài này. Bảo và Bình cần các bạn trong đội tuyển cùng thảo luận và trả lời hết tất cả \(q\) truy vấn trên, và tổng cộng có \(2\) loại truy vấn.

Yêu cầu: Vì các bạn trong đội tuyển ít tiếp xúc với các bài toán liên quan đến xử lý bit nên bạn hãy giúp các bạn trong đội tuyển trả lời hết \(q\) truy vấn trên.

Dữ liệu vào: gồm \(q + 2\) dòng:

• Dòng đầu tiên chứa hai số nguyên dương \(n,\ q\).

• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1},a_{2},\ldots,\ a_{n}\).

• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa một trong \(2\) loại truy vấn trên.

Kết quả: Gồm \(q\ \)dòng, mỗi dòng ghi ra một số nguyên duy nhất là kết quả cho mỗi truy vấn.

Ví dụ:

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài thoả mãn điều kiện:\(\ n,\ q \leq {3.10}^{3};\ a_{i} < 2^{12}\) với \(1 \leq i \leq n\); \(x_{i},\ y_{i} < 2^{12}\) với \(1 \leq i \leq q\);

• 30% số test khác ứng với 30% số điểm của bài thoả mãn điều kiện: \(n \leq 10^{6},q \leq {3.10}^{5};\ a_{i} < 2^{15}\) với \(1 \leq i \leq n\); \(0 \leq x_{i},\ y_{i} < 2^{15}\) với \(1 \leq i \leq q\);

50% số test còn lại ứng với 50% số điểm của bài thoả mãn điều kiện: \(n \leq 10^{6},q \leq {3.10}^{5};\ a_{i} < 2^{19}\) với \(1 \leq i \leq n\); \(0 \leq x_{i},\ y_{i} < 2^{19}\) với \(1 \leq i \leq q\).