Một số ~M~ đươc gọi là liên kết với ~X~ nếu ~M~ ~XOR~ ~X~ ~>~ ~M~ ~AND~ ~X~. Cho trước một 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 đếm xem trong đoạn từ ~L~ đến ~R~ có bao nhiêu số liên kết với ~X~.

Input

Dòng đầu chứa số nguyên ~n \le 2.10^5~, dòng tiếp theo chứa ~n~ số nguyên là các phần tử của mảng gồm các số nguyên dương không vượt quá ~10^9~, dòng thứ ba chứa số nguyên ~q~ là số truy vấn.

Trong ~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.

Output

~Q~ dòng là kết quả cho từng truy vấn.

Sample input

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

Sample output

3
2

Subtasks

• Subtask 1: 50% số test có ~n~ và ~q \le 2000~.
• Subtask 2: 50% số test còn lại có ~n~ và ~q \le 200000.~