Một số \(m\) đươc gọi là số huyền bí cơ số \(x\) nếu \((m\ \hat{}\ x)\ > \ (m\ \&\ x)\). Trong đó \(\hat{}\) là phép XOR bit, \(\&\) là phép AND bit trong C++.

Bạn được cho 1 mảng \(n\) số nguyên và \(q\) truy vấn. Mỗi truy vấn được cho bởi bộ 3 số \(l\), \(r\) và \(x\). Yêu cầu tìm trong đoạn từ \(l\) đến \(r\) xem có bao nhiêu số huyền bí cơ số \(X\).

Dữ liệu vào:

+ Dòng đầu chứa số nguyên \(n\).

+ Dòng tiếp theo chứa \(n\) số nguyên là các phần tử của mảng.

+ Dòng thứ ba chứa số nguyên \(q\) là số truy vấn.

+ \(q\) dòng cuối cùng, mỗi dòng chứa 3 số nguyên \(l\), \(r\) và \(x\) biểu thị truy vấn.

Dữ liệu ra:

+ \(q\) dòng là kết quả cho từng truy vấn theo đúng thứ tự vào của các truy vấn trong Input

Ví dụ:

Ghi chú:

+ Subtask 1: 50% số test có \(n\) và \(q \leq 2000\).

+ Subtask 2: 50% số test còn lại có \(n\) và \(q \leq 200000.\)