G. Binary Automaton
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
This is where the fun begins
— Anakin Skywalker

Mark found an old automaton with two buttons in his attic, which he used to play with as a child. The toy is quite rusty, but it still performs its function. When the first button is pressed, a single $$$0$$$ appears on the screen, and when the other button is pressed, either due to age or malfunction, the automaton outputs $$$k$$$ ones at once.

Mark became curious about how many different strings of lengths from $$$\ell$$$ to $$$r$$$ can be obtained if the automaton outputs $$$k$$$ ones when the second button is pressed. However, since the automaton is old and Mark's curiosity is great, you will have to answer $$$q$$$ queries instead of the automaton.

Since the answer to any of Mark's queries can be very large, compute it modulo $$$998244353$$$.

Input

In the first line, you are given $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the maximum length of the string and the number of queries.

In the next $$$q$$$ lines, three integers $$$\ell_i, \ r_i, \ k_i$$$ are given ($$$1 \le \ell_i \le r_i \le n, 1 \le k \le n$$$) — the range of lengths and the number of ones that the automaton prints.

Output

For each query, output the number of strings that the automaton can print modulo $$$998244353$$$.

Scoring
№Add. ConstraintsPointsReq. GroupsComment
$$$n$$$$$$q$$$$$$k$$$
$$$0$$$—————Tests from the statement
$$$1$$$$$$n \le 15$$$$$$q \le 15$$$—$$$7$$$$$$0$$$—
$$$2$$$$$$n \le 15$$$——$$$9$$$$$$0 - 1$$$—
$$$3$$$$$$n \le 5000$$$$$$q \le 5000$$$—$$$11$$$$$$0 -1$$$—
$$$4$$$$$$n \le 5000$$$——$$$8$$$$$$0-3$$$—
$$$5$$$——$$$k \le 20$$$$$$9$$$$$$0-2$$$—
$$$6$$$———$$$12$$$—$$$\ell_i = r_i = n$$$
$$$7$$$——$$$20 \cdot k \ge n$$$$$$13$$$——
$$$8$$$$$$n \le 50000$$$$$$q \le 50000$$$—$$$21$$$$$$0, 1, 3$$$—
$$$9$$$———$$$10$$$$$$0-8$$$—
Example
Input
8 6
1 1 1
4 8 2
1 8 3
1 8 1
4 6 2
4 6 4
Output
2
81
39
510
26
9