Processing math: 100%
Bulk range update - MarisaOJ: Marisa Online Judge

Bulk range update

Time limit: 1000 ms
Memory limit: 256 MB

Given an array A consists of n zero. You are also given q queries, each of the form Qi=(l,r) which means to increment Al,Al+1,…,Ar by 1.

There are also m more queries, each of the form (x,y) which means to perform Qx,Qx+1,…,Qy.

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≤n,q,m≤105.
  • 1≤l,r,x,y≤n.

Example

Input:

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

Output:

4 7 5