Знайти число за модулем 998244353 цілих послідовностей \(A = (A_1, \dots, A_N)\) довжини \(N\), які задовольняють усі наступні умови:

• \(0 \leq A_i \leq M\) для всіх \(i\) таких, що \(1 \leq i \leq N\).

• Максимальне значення \(A_{L_j}, \dots, A_{R_j}\) є \(X_j\) для всіх \(j\) таких, що \(1 \leq j \leq Q\).

Обмеження

• \(1 \leq N \leq 2 \times 10^5\)
• \(1 \leq M \lt 998244353\)
• \(1 \leq Q \leq 2 \times 10^5\)
• \(1 \leq L_i \leq R_i \leq N\), (\(1 \leq i \leq Q\))
• \(1 \leq X_i \leq M\), (\(1 \leq i \leq Q\))
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,M,Q\)

Наступні  \(Q\) рядків містять цілі числа \(L_i,R_i,X_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

A=(0,2,3),(1,2,3),(2,0,3),(2,1,3),(2,2,3) задовольняють умови

Приклад вхідних даних

3 3 2
1 2 2
2 3 3

Приклад вихідних даних

5

Приклад вхідних даних

1 1 1
1 1 1

Приклад вихідних даних

1

Приклад вхідних даних

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

Приклад вихідних даних

135282163