Tại vương quốc BMA, có \(N\) viên đá pha lê được xếp thành hàng ngang, ban đầu năng lượng của tất cả các viên đá đều bằng \(0\).
Đại pháp sư Đức Cống sở hữu một cuốn bí kíp gồm \(Q\) câu thần chú, được đánh số từ \(1\) đến \(Q\). Câu thần chú thứ \(i\) có tác dụng: "Tăng năng lượng của các viên đá từ vị trí \(L_i\) đến \(R_i\) lên \(1\) đơn vị".
Để cường hóa các viên đá, đại pháp sư ra lệnh thực hiện \(M\) đợt niệm chú. Trong đợt thứ \(j\), các học trò sẽ phải thực hiện lần lượt tất cả các câu thần chú trong phạm vi từ số \(x_j\) đến số \(y_j\) (tức là thực hiện câu thần chú \(x_j\), sau đó đến \(x_j + 1, \dots,\) cho đến \(y_j\)).
Hãy tính năng lượng cuối cùng của \(N\) viên đá sau khi hoàn tất \(M\) đợt niệm chú.

Input

• Dòng 1: Ba số nguyên \(N, Q, M\) (\(1 \le N, Q, M \le 10^5\)).
• \(Q\) dòng tiếp theo: Dòng thứ \(i\) chứa hai số nguyên \(L_i, R_i\) (\(1 \le L_i \le R_i \le N\)) mô tả phạm vi tác động của câu thần chú thứ \(i\).
• \(M\) dòng tiếp theo: Dòng thứ \(j\) chứa hai số nguyên \(x_j, y_j\) (\(1 \le x_j \le y_j \le Q\)) mô tả đợt niệm chú thứ \(j\).

Output

• In ra \(N\) số nguyên trên một dòng, là năng lượng của các viên đá sau cùng.

Example

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

2 4 4 3 1

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q, M \le 1000\).
• Subtask \(2\) (\(70\%\) số điểm): \(N, Q, M \le 10^5\).