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 OR (ký hiệu ~\vee~), phép AND (ký hiệu ~\wedge~), phép XOR (ký hiệu ~\oplus~).

Cho một mảng gồm ~n~ phần tử ~a_1, a_2, ..., 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 \le u < v \le n~ và ~x_i \oplus (a_u \wedge a_v) = 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 \le u < v \le n~ và ~x_i \oplus (a_u \wedge a_v) = y_i~.

• ~2 \ x_i \ y_i~: Tìm số cặp vị trí ~(u, v)~ sao cho ~1 \le u < v \le n~ và ~x_i \oplus (a_u \vee a_v) = 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.

Input

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, ..., 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.

Output

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.

Scoring

Sample Input 1

7 2
1 2 3 5 4 7 6
1 5 7
2 2 7

Sample Output 1

4
3

Notes

Với truy vấn thứ 1: Có 4 cặp thoả mãn là (theo vị trí): ~(2, 3), (2, 6), (2, 7), (3, 7)~.