{"problem":{"name":"Ex - Range Harvest Query","description":{"content":"There are $N$ trees. On Day $0$, each tree bears no fruits.   On the morning of Day $1$ and subsequent days, the $i$\\-th tree bears $i$ new fruits for each $i = 1, 2, \\ldots, N$. Takahashi will perfor","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc255_h"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc255_h","tags":[],"sample_group":[["5 3\n2 2 3\n3 3 4\n5 1 5","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)$."],["711741968710511029 1\n82803157126515475 516874290286751784 588060532191410838","603657470\n\nBe sure to print the numbers modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}