Demen và những truy vấn lẻ
View as PDFDemen có ~N~ đoạn, đoạn thứ ~i \space (1 \leq i \leq n)~ bắt đầu ở ~L_{i}~ và kết thúc ở ~R_{i}~. Đoạn thẳng này đi qua mọi điểm ~x~ thỏa mãn ~L_{i} \leq x \leq R_{i}~.
Demen có ~Q~ câu hỏi, mỗi câu hỏi có dạng ~X_{1}, X_{2}, ..., X_{M}~. Bạn cần tính số đoạn trong ~N~ đoạn trên thỏa mãn: số điểm mà đoạn thẳng đó đi qua trong ~M~ điểm trên là lẻ.
Input
Dòng đầu tiên chứa số ~T \space (T \leq 100)~ là số test case cho bài này
Mỗi test có dạng như sau
Dòng đầu tiên của mỗi test chứa số ~N \space (N \leq 10^5)~ là số đoạn
~N~ dòng từ dòng ~2~ đến ~N + 1~, dòng thứ ~(i + 1)~ gồm 2 số ~L_{i}~ và ~R_{i}~ ~(1 \leq L_{i} \leq R_{i} \leq N)~ biểu diễn đoạn thứ ~i~
Dòng thứ ~N + 2~ chứa số ~Q \space (Q \leq 10^5)~ là số truy vấn
~Q~ dòng cuối cùng biểu diễn các truy vấn, bắt đầu bằng số ~M~, và sau đó là ~M~ điểm ~X_{1}, X_{2}, ..., X_{M} \space (1 \leq X_{i} \leq N)~ đôi một phân biệt. Dữ liệu đảm bảo tổng số điểm trong tất cả các truy vấn trong bộ test ~\leq N~
Dữ liệu đảm bảo tất cả các số trong input nguyên dương, và tổng ~N, Q~ trong tất cả các truy vấn ~\leq 2 * 10^5~
Output
Với mỗi truy vấn, in ra đáp án của truy vấn đó (theo đúng thứ tự), mỗi số trên một dòng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10~ | ~N, Q \leq 300~ |
| 2 | ~90~ | Không có điều kiện gì thêm |
Sample Input 1
2
5
4 5
3 5
2 4
1 3
5 5
2
4 1 2 3 4
1 4
5
4 5
3 5
2 4
2 3
5 5
2
2 2 5
3 1 2 5
Sample Output 1
3
3
5
5
Comments
This comment is hidden due to too much negative feedback. Show it anyway.