D. Electi Lamps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$N$$$ lamps located along a street at positions $$$X_i$$$, each with a power level $$$P_i$$$. The $$$i$$$-th lamp lights up an area within the range $$$[X_i - P_i, X_i + P_i]$$$ when turned on. Initially, some lamps are turned on, and some are turned off. The initial state of the $$$i$$$-th lamp is denoted by $$$T_i$$$: if $$$T_i = 1$$$, the lamp is on; if $$$T_i = 0$$$, the lamp is off. The positions of the lamps are sorted in increasing order, i.e., $$$X_i \lt X_{i + 1}$$$ for all $$$1 \leq i \lt N$$$.

For each lamp $$$i \ (1 \leq i \lt N)$$$, you need to determine a value $$$F(i)$$$, which is the minimum total distance you must walk to achieve the following:

  • All lamps before position $$$X_i$$$ are considered destroyed and do not exist.
  • If the $$$i$$$-th lamp was initially off, it is turned on.
  • You start at position $$$X_i$$$ and want to walk to position $$$X_N$$$. Along the way, you must turn off every lamp except for the one at position $$$X_N$$$.

If you cannot reach position $$$X_N$$$ while ensuring all lamps except lamp $$$N$$$ are turned off, then $$$F(i) = 0$$$.

The task is to compute the sum of $$$F(i)$$$ for all $$$i \ (1 \leq i \lt N)$$$, modulo $$$998244353$$$.

Note: You can only walk in areas illuminated by the lamps.

Input

The first line contains one integer $$$T$$$ ($$$1 \leq T \leq 10^3$$$), the number of test cases.

Then, for each test case:

  • The first line contains one integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$).
  • Then, $$$N$$$ lines follow. In the $$$i$$$-th of these lines, there are three space-separated integers $$$X_i$$$, $$$P_i$$$, and $$$T_i$$$ $$$(1 \leq X_i \leq 10^{12}, 1 \leq P_i \leq 10^{12}, T_i \in \{0, 1\})$$$.
  • It is guaranteed that $$$X_i \lt X_{i+1}$$$ for all $$$1 \leq i \lt N$$$.

The total sum of $$$N$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test, print one line consisting of one integer, the answer.

Example
Input
2
3
3 1 0
5 2 0
6 2 1
3
1 8 1
4 7 1
6 1 0
Output
8
0
Note

In the first example:

Figure 1. Initial state of Lamps.

Now let's look at what happens when you start at the first lamp.

Figure 2. The starting lamp is turned on.Figure 3. Move to lamp $$$2$$$ and turn it on.
Figure 4. Go back to lamp $$$1$$$ and turn it off.Figure 5. Go to lamp $$$3$$$ and turn off lamp $$$2$$$.