An array has \(M\) numbered range-add operations. Each of \(K\) queries selects an inclusive interval of operation numbers; every selected operation is applied once for that query. Compute the final array.

Input

The first line contains \(N,M,K\). The second line contains \(N\) integers. The next \(M\) lines contain operations \(L,R,D\) using one-based array indices. The next \(K\) lines contain operation intervals \(x,y\), also one-based.

The input satisfies:

• \(1 \le N, M, K \le 10^5\)
• \(0 \le A_i, D \le 10^5\)
• \(1 \le L \le R \le N\)
• \(1 \le x \le y \le M\)

Output

Print the final array with elements separated by single spaces.

Example

Input

1 1 1
1
1 1 1
1 1

Output

2