Greg có một mảng \(a = a_1, a_2, \dots, a_n\) gồm \(n\) số nguyên và \(m\) thao tác. Mỗi thao tác được mô tả bởi ba số nguyên \(l_i, r_i, d_i\) (\(1 \le l_i \le r_i \le n\)). Áp dụng thao tác thứ \(i\) lên mảng nghĩa là tăng tất cả các phần tử của mảng có chỉ số từ \(l_i\) đến \(r_i\) thêm một lượng \(d_i\).

Greg viết ra \(k\) truy vấn. Mỗi truy vấn được mô tả bởi hai số nguyên \(x_i, y_i\) (\(1 \le x_i \le y_i \le m\)). Truy vấn thứ \(i\) có nghĩa là áp dụng tất cả các thao tác có chỉ số từ \(x_i\) đến \(y_i\) vào mảng.

Nhiệm vụ của bạn là xác định trạng thái cuối cùng của mảng \(a\) sau khi thực hiện lần lượt tất cả các truy vấn.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) (\(1 \le n, m, k \le 10^5\)) — số phần tử của mảng, số thao tác và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^5\)) — mảng ban đầu.
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(l_i, r_i, d_i\) (\(1 \le l_i \le r_i \le n, 0 \le d_i \le 10^5\)) — mô tả thao tác thứ \(i\).
• \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\) (\(1 \le x_i \le y_i \le m\)) — mô tả truy vấn thứ \(i\).

Output

• In ra \(n\) số nguyên \(a_1, a_2, \dots, a_n\) trên một dòng, các số cách nhau bởi dấu cách — mảng thu được sau khi thực hiện tất cả các truy vấn.

Constraints

• \(1 \le n, m, k \le 10^5\)
• \(0 \le a_i \le 10^5\)
• \(1 \le l_i \le r_i \le n\)
• \(0 \le d_i \le 10^5\)
• \(1 \le x_i \le y_i \le m\)

Example

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

9 18 17

1 1 1
1
1 1 1
1 1

2

4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3

5 18 31 20