Cây cầu trên dải ngân hà

Trong một dải ngân hà xa xôi, có hai chuỗi các hành tinh được đánh số. Chuỗi hành tinh đầu tiên gồm \(n\) hành tinh có giá trị năng lượng \(a_1, a_2, \ldots, a_n\). Chuỗi hành tinh thứ hai gồm \(m\) hành tinh có giá trị năng lượng \(b_1, b_2, \ldots, b_m\).

Một hành tinh được coi là "đẹp" nếu nó có thể được kết nối bằng một cây cầu ánh sáng với một hành tinh khác. Cụ thể, một hành tinh có giá trị năng lượng \(x\) được gọi là "đẹp" nếu tồn tại hai hành tinh \(i, j\) thuộc chuỗi thứ hai (\(1 \le i \le j \le m\)) sao cho giá trị năng lượng của chúng khi kết hợp bằng phép toán bitwise OR (\(b_i | b_{i+1} | \ldots | b_j\)) bằng với \(x\).

Nhà thám hiểm vũ trụ Alex đang thực hiện một nhiệm vụ đặc biệt. Anh ấy có \(Q\) câu hỏi, mỗi câu hỏi yêu cầu đếm số cặp hành tinh \((i, j)\) trong chuỗi thứ nhất (\(L \le i \le j \le H\)) sao cho giá trị phép toán bitwise AND (\(a_i \& a_{i+1} \& \ldots \& a_j\)) bằng với giá trị năng lượng của một hành tinh "đẹp" bất kỳ.

Yêu cầu: Với mỗi câu hỏi, hãy giúp Alex tìm câu trả lời.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, m, Q\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\).
• Dòng thứ ba chứa \(m\) số nguyên không âm \(b_1, b_2, \ldots, b_m\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, H\) mô tả một truy vấn.

Output

• Ghi ra \(Q\) dòng, mỗi dòng là kết quả cho một truy vấn tương ứng.

Example

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

3
3
5

Scoring

• Trong tất cả các test: \(n, m, Q, a_i, b_i \le 2 \cdot 10^5\).
• Subtask 1 (16% số điểm): \(n \le 1000\) và \(a_i \le 1000\) và \(m \le 10\).
• Subtask 2 (20% số điểm): \(Q = 1\) và \(m \le 100\).
• Subtask 3 (24% số điểm): \(Q = 1\).
• Subtask 4 (40% số điểm): Ràng buộc chuẩn.