{"raw_statement":[{"iden":"problem statement","content":"There are $N$ trees. On Day $0$, each tree bears no fruits.  \nOn the morning of Day $1$ and subsequent days, the $i$\\-th tree bears $i$ new fruits for each $i = 1, 2, \\ldots, N$.\nTakahashi will perform $Q$ harvesting. For each $i = 1, 2, \\ldots, Q$, the $i$\\-th harvesting takes place on the night of Day $D_i$, collecting all fruits remaining on the $L_i$\\-th through $R_i$\\-th trees at that point.\nFor each of the $Q$ harvesting, print the number of fruits Takahashi will collect, modulo $998244353$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^{18}$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq D_1 \\lt D_2 \\lt \\cdots \\lt D_Q \\leq 10^{18}$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$D_1$ $L_1$ $R_1$\n$D_2$ $L_2$ $R_2$\n$\\vdots$\n$D_Q$ $L_Q$ $R_Q$"},{"iden":"sample input 1","content":"5 3\n2 2 3\n3 3 4\n5 1 5"},{"iden":"sample output 1","content":"10\n15\n50\n\nFor each $i = 1, 2, 3, 4, 5$, let $A_i$ be the number of fruits remaining on the $i$\\-th tree. Now, we use the sequence $A = (A_1, A_2, A_3, A_4, A_5)$ to represent the numbers of fruits remaining in the trees.\n\n*   On Day $0$, we have $A = (0, 0, 0, 0, 0)$.\n*   On the morning of Day $1$, each tree bears new fruits, and we have $A = (1, 2, 3, 4, 5)$.\n*   On the morning of Day $2$, each tree bears new fruits, and we have $A = (2, 4, 6, 8, 10)$.\n*   On the night of Day $2$, Takahashi performs the $1$\\-st harvesting. $4 + 6 = 10$ fruits are collected, and we have $A = (2, 0, 0, 8, 10)$.\n*   On the morning of Day $3$, each tree bears new fruits, and we have $A = (3, 2, 3, 12, 15)$.\n*   On the night of Day $3$, Takahashi performs the $2$\\-nd harvesting. $3 + 12 = 15$ fruits are collected, and we have $A = (3, 2, 0, 0, 15)$.\n*   On the morning of Day $4$, each tree bears new fruits, and we have $A = (4, 4, 3, 4, 20)$.\n*   On the morning of Day $5$, each tree bears new fruits, and we have $A = (5, 6, 6, 8, 25)$.\n*   On the night of Day $5$, Takahashi performs the $3$\\-rd harvesting. $5 + 6 + 6 + 8 + 25 = 50$ fruits are collected, and we have $A = (0, 0, 0, 0, 0)$."},{"iden":"sample input 2","content":"711741968710511029 1\n82803157126515475 516874290286751784 588060532191410838"},{"iden":"sample output 2","content":"603657470\n\nBe sure to print the numbers modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}