Given an array $A$ consists of $n$ zero. You are also given $q$ queries, each of the form $Q_i = (l, r)$ which means to increment $A_l, A_{l + 1}, ..., A_r$ by 1.
There are also $m$ more queries, each of the form $(x, y)$ which means to perform $Q_x, Q_{x + 1}, ..., Q_y$.
### Input
- The first line contains 3 integers $n, q, m$.
- Next $q$ lines, each line contains 2 integers $l, r$.
- Next $m$ lines, each line contains 2 integers $x, y$.
### Output
- Print array $A$ after all queries.
### Constraints
- $1 \le n, q, m\le 10^5$.
- $1 \le l, r, x, y\le n$.
### Example
Input:
```
3 3 3
1 2
2 3
1 3
2 3
1 2
1 3
```
Output:
```
4 7 5
```
