In the vast Plains of Laurasia, there lives a foolish horse named Doddo, who is about to take part in an obstacle race.
The race track consists of $$$N$$$ lanes, numbered from $$$1$$$ to $$$N$$$, arranged side by side.
Each lane contains $$$M+2$$$ positions, labeled from $$$0$$$ to $$$M+1$$$. Positions $$$1$$$ through $$$M$$$ form the actual track. Position $$$0$$$ is the starting point, and position $$$M+1$$$ is the finishing point of each lane; these two positions are not considered part of the track.
There are $$$K$$$ obstacles. Each obstacle is described by a triple $$$(i, l, r)$$$, meaning that in lane $$$i$$$, every position $$$x$$$ such that $$$l \le x \le r$$$ is blocked by this obstacle.
It is guaranteed that the starting and finishing points in every lane are never blocked, and that no two obstacles in the same lane overlap.
Doddo starts at the starting point (position $$$0$$$) in a chosen lane. Each second of the race, the following steps occur in order:
- If Doddo is already at the finishing point (position $$$M+1$$$) in any lane, the race ends immediately.
- Suppose Doddo is currently at position $$$x$$$ in lane $$$i$$$. He checks whether position $$$x+1$$$ in lane $$$i$$$ is blocked.
- If position $$$x+1$$$ is not blocked, Doddo stays in the same lane.
- Otherwise, Doddo attempts to switch to an adjacent lane ($$$i-1$$$ or $$$i+1$$$), if such a lane exists and position $$$x$$$ in that lane is not blocked. Note that only position $$$x$$$ is checked for availability; even if position $$$x+1$$$ in the new lane is blocked, Doddo can still switch to that lane.
In this situation, Doddo behaves in the following way:
- If no adjacent lane is available, Doddo stays in the same lane.
- If exactly one adjacent lane is available, Doddo switches to that lane.
- If both adjacent lanes are available, Doddo becomes confused and chooses one of them uniformly at random.
- After that, if any obstacle does not block position $$$x+1$$$ in Doddo's current lane, Doddo moves to position $$$x+1$$$ in that lane; otherwise, Doddo crashes into the obstacle, and the race ends immediately.
If Doddo reaches the finishing point in any lane before the race ends, he wins the race. Otherwise, if he crashes at any point, he loses.
For each $$$i$$$ $$$(1 \le i \le N)$$$, determine the probability that Doddo wins the race if he starts at the starting point in lane $$$i$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The first line of each test case contains three space-separated integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$1 \le M \le 10^9$$$, $$$0 \le K \le 2 \cdot 10^5$$$) — the number of lanes, the length of each lane, and the number of obstacles.
Each of the next $$$K$$$ lines contains three space-separated integers $$$i$$$, $$$l$$$, and $$$r$$$ ($$$1 \le i \le N$$$, $$$1 \le l \le r \le M$$$) — describing an obstacle on lane $$$i$$$ blocking the segment $$$[l, r]$$$.
It is guaranteed that for each lane, no two obstacles overlap with each other.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$, and the sum of $$$K$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, output $$$N$$$ space-separated integers in a single line. The $$$i$$$-th of those integers should represent the probability that Doddo wins the race if he starts in lane $$$i$$$, modulo $$$998244353$$$.
Output all probabilities modulo $$$998244353$$$. Formally, if a probability can be expressed as an irreducible fraction $$$\displaystyle\frac{x}{y}$$$, you have to output $$$p = xy^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is an integer such that $$$yy^{-1} \bmod 998244353 = 1$$$.
16 5 42 2 23 2 24 4 45 4 4
1 499122177 748683265 499122177 499122177 1
The following diagram illustrates the race track for the first test case:
The probability of winning the race from each lane is $$$\displaystyle 1, \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{2}, \tfrac{1}{2}, 1$$$, respectively.
