Cho một mảng \(a\) có độ dài \(n\). Mỗi phần tử là số nguyên trong đoạn từ \(1\) đến \(m\) hoặc là \(-1\).

Bạn cần tính tổng: \[ ∑_{i<j} |a_i - a_j| \]

trong mọi cách điền số từ \(1\) đến \(m\) vào các vị trí \(-1\) trong mảng \(a\), lấy kết quả modulo \(10^9 + 7\).

Tuy nhiên, sau mỗi lần cập nhật đoạn \(l\) đến \(r\) thành giá trị \(v\) (v có thể là \(-1\)), bạn cần tính lại đáp án theo mảng mới.

Input

• Dòng đầu gồm 3 số nguyên \(n\), \(m\), \(q\) (\(1 \le n, m, q \le 350000\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, ..., a_n\) (\(1 \le a_i \le m\) hoặc \(a_i = -1\)).
• \(q\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(l\), \(r\), \(v\) (\(1 \le l \le r \le n\), \(-1 \le v \le m\), \(v ≠ 0\)).

Output

• Gồm \(q\) dòng, mỗi dòng là kết quả sau lần cập nhật tương ứng, lấy mod \(10^9 + 7\).

Examples

Input

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

Output

1
20
6

Input

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

Output

3
3
0
4
3

Scoring

• Subtask 1 (5%): \(n, m, q \le 7\)
• Subtask 2 (15%): \(n, m, q \le 100\)
• Subtask 3 (15%): \(n, m, q \le 500\)
• Subtask 4 (25%): \(n, m, q \le 5000\)
• Subtask 5 (40%): \(n, m, q \le 350000\)