Nội dung chính trong tiết Tin học đội tuyển ngày hôm nay của Hoàng là các phép toán xử lý bit. Trong xử lý bit có các phép toán như phép \(OR\) (ký hiệu | ), phép \(AND\) (ký hiệu & ), phép \(XOR\) (ký hiệu ^ ). Để ôn tập, thầy đã giao cho Hoàng bài tập như sau:

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên \(A_1,A_2,…,A_N\). Có \(Q\) truy vấn, truy vấn thứ \(i\) thuộc một trong \(7\) loại như sau:

• \(1\) \(v_i\): Đếm các phần tử \(j\) \((1 \leq j \leq N)\) thoả mãn \(v_i\) | \(A_j\) \(=\) \(v_i\);
• \(2\) \(v_i\): Đếm các phần tử \(j\) \((1 \leq j \leq N)\) thoả mãn \(v_i\) & \(A_j\) \(=\) \(v_i\);
• \(3\) \(v_i\) \(t_i\): Đếm các phần tử \(j\) \((1 \leq j \leq N)\) thoả mãn \(v_i\) ^ \(A_j\) \(=\) \(t_i\);
• \(4\) \(v_i\) \(t_i\): Đếm các cặp phần tử \((j, k)\) \((1 \leq j < k \leq N)\) thoả mãn \(v_i\) ^ (\(A_j\) | \(A_k\)) \(=\) \(t_i\);
• \(5\) \(v_i\) \(t_i\): Đếm các cặp phần tử \((j, k)\) \((1 \leq j < k \leq N)\) thoả mãn \(v_i\) ^ (\(A_j\) & \(A_k\)) \(=\) \(t_i\);
• \(6\) \(v_i\): Đếm các cặp phần tử \((j, k)\) \((1 \leq j \leq N)\) thoả mãn \(v_i\) | (\(A_j\) ^ \(A_k\)) \(=\) \(v_i\);
• \(7\) \(v_i\): Đếm các cặp phần tử \((j, k)\) \((1 \leq j \leq N)\) thoả mãn \(v_i\) & (\(A_j\) ^ \(A_k\)) \(=\) \(v_i\).

Thầy giáo yêu cầu Hoàng trả lời hết \(Q\) truy vấn trên.

Yêu cầu: Vì Hoàng chỉ mới làm quen với các phép toán bit, chưa được thực hành nhiều nên hãy giúp Hoàng giải quyết bài toán trên.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N\), \(Q\);
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,…,A_N\);
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa một trong \(7\) loại truy vấn trên.
• Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Gồm Q dòng, dòng thứ \(i\) ghi ra một số nguyên duy nhất là kết quả của truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N,Q \leq 10^3\); \(0 \leq A_i,v_i,t_i < 2^{10}\).
• Subtask \(2\) (\(20\%\) số điểm): \(N,Q \leq 10^5\); \(0 \leq A_i,v_i,t_i < 2^{10}\).
• Subtask \(3\) (\(20\%\) số điểm): \(N,Q \leq 10^5\); \(0 \leq A_i,v_i,t_i < 2^{16}\); các truy vấn chỉ thuộc loại \(1,2,3\).
• Subtask \(4\) (\(20\%\) số điểm): \(N,Q \leq 10^6\); \(0 \leq A_i,v_i,t_i < 2^{20}\); các truy vấn chỉ thuộc loại \(1,2,3\).
• Subtask \(5\) (\(20\%\) số điểm): \(N,Q \leq 10^6\); \(0 \leq A_i,v_i,t_i < 2^{20}\); các truy vấn chỉ thuộc loại \(4,5,6,7\).

Example

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

3
4
1
3
4
9
6