Cho một mảng ~a~ có độ dài ~n~; mọi phần tử hoặc nằm trong đoạn từ ~1~ đến ~m~ hoặc là ~-1~. Sử dụng mảng này, bạn A đã cho ra một bài toán đơn giản như sau: Tính tổng của

~\displaystyle \sum_{i<j}|a_i-a_j|~</p>

trong mọi cách điền một số từ ~1~ đến ~m~ vào các phần tử có giá trị ~-1~ trong mảng ~a~ mod ~10^9+7~.

Tuy nhiên do bạn A đã bị quá sung sướng nên bạn B đã chỉnh một vài chi tiết của bài toán. Bây giờ, bạn sẽ cần phải tính đáp án của mảng ~a~ trong ~q~ lần cập nhật, mỗi cập nhật có dạng ~l, r, v~ biểu thị cho việc cập nhật giá trị ~a_i~ thành ~v~ với ~l \le i \le r~.

Input

Dòng đầu tiên gồm ~3~ số nguyên dương ~n, m, q~ ~(1 \le n, m, q \le 350000)~.

Dòng thứ ~2~ gồm ~n~ số nguyên dương lần lượt là ~a_1, \dots, a_n~, các số tách nhau bởi một dấu cách (~1 \le a_i \le m~ hoặc ~a_i=-1~ với mọi ~i~ từ ~1~ đến ~n~).

~q~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~l, r, v~ ~(1 \le l \le r \le n, -1 \le v \le m, v \ne 0)~ biểu thị cho lần cập nhật thứ ~i~ của mảng. Lưu ý rằng các lần cập nhật mảng là vĩnh viễn.

Output

In ra ~q~ số dòng, dòng thứ ~i~ chứa một số nguyên ~x~ là đáp án của bài toán ~a~ mod ~10^9+7~ sau lần cập nhật thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

1
20
6

Sample Input 2

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

Sample Output 2

3
3
0
4
3