Nhân dịp đầu năm mới, Đoàn Thanh niên tổ chức chương trình khai xuân cho học sinh chơi các trò chơi. Có tất cả ~n~ học sinh ~(1 \le n \le 10^9)~ đăng ký tham gia, các bạn học sinh này được xếp thành hàng ngang và đánh số từ ~1~ đến ~n~.

Có tất cả ~k~ ~(1 \le k \le 10^6)~ trò chơi, trò chơi thứ ~i~ gồm các bạn học sinh có số thứ tự từ ~l_i~ đến ~r_i~ được tham gia, sau khi tham gia xong trò chơi đó học sinh quay về vị trí cũ trong hàng.

Yêu cầu

Kết thúc chương trình, Ban Tổ chức muốn biết ~q~ ~(1 \le q \le 10^6)~ bạn học sinh có số thứ tự lần lượt là ~b_1, b_2, ..., b_q~ mỗi bạn đã được tham gia bao nhiêu trò chơi?

Dữ liệu đầu vào

Gồm ~k + 2~ dòng:

• Dòng đầu tiên chứa ba số nguyên dương ~n, k, q~.
• Dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.
• Dòng cuối cùng chứa ~q~ số nguyên dương ~b_1, b_2, ..., b_q~ ~(1 \le b_i \le n;\ 1 \le i \le q)~.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ ~(1 \le i \le q)~ chứa một số nguyên là số lượng trò chơi mà học sinh bị đã tham gia.

Ràng buộc dữ liệu

• Có 40% số test tương ứng với 40% số điểm của bài có ~1 \le n, k, q \le 10^3~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 10^6~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~10^6 < n \le 10^9~.

Ví dụ

Ví dụ 1

INPUT

10 2 3
3 9
8 9
6 8 2

OUTPUT

1
2
0