{"raw_statement":[{"iden":"problem statement","content":"Find the number, modulo $998244353$, of integer sequences $A = (A_1, \\dots, A_N)$ of length $N$ that satisfy all of the following conditions:\n\n*   $0 \\leq A_i \\leq M$ for all $i$ such that $1 \\leq i \\leq N$.\n*   The maximum value of $A_{L_j}, \\dots, A_{R_j}$ is $X_j$ for all $j$ such that $1 \\leq j \\leq Q$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\lt 998244353$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq L_i \\leq R_i \\leq N \\, (1 \\leq i \\leq Q)$\n*   $1 \\leq X_i \\leq M \\, (1 \\leq i \\leq Q)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$L_1$ $R_1$ $X_1$\n$\\vdots$\n$L_Q$ $R_Q$ $X_Q$"},{"iden":"sample input 1","content":"3 3 2\n1 2 2\n2 3 3"},{"iden":"sample output 1","content":"5\n\n$A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3)$ satisfy the conditions."},{"iden":"sample input 2","content":"1 1 1\n1 1 1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"6 40000000 3\n1 4 30000000\n2 6 20000000\n3 5 10000000"},{"iden":"sample output 3","content":"135282163"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}