Hôm nay lại có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko tham ăn có ~q~ lựa chọn dạng ~l_i, r_i~, đi ăn tất cả cửa hàng ở vị trí ~l_i~ đến vị trí ~r_i~.

Nhưng hôm nay do quá đói, cô đã đi ăn ~m~ lần, sử dụng tất cả các lựa chọn từ ~x_i~ đến ~y_i~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input:

• Dòng đầu gồm 3 số tự nhiên ~n, q, m~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le l_i, r_i \le n~ là lựa chọn thứ ~i~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le x_i, y_i \le q~ là lượt đi ăn thứ ~j~.

Output:

• ~n~ số nguyên không âm là số lần cô ghé thăm các gian hàng.

Sample Test:

• Input:

3 3 3
1 2
2 3
1 3
2 3
1 2
1 3

• Output

4 7 5

Giới hạn:

• 40% số điểm: ~n, q, m \le 100~.
• 30% số điểm: ~n, q, m \le 5000~.
• 30% số điểm: ~n, q, m \le 10^5~