CF2020D Connect the Dots

One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist. To play the game, Alice draws a straight line and marks $ n $ points on it, indexed from $ 1 $ to $ n $ . Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $ m $ operations of the following type: - She picks three integers $ a_i $ , $ d_i $ ( $ 1 \le d_i \le 10 $ ), and $ k_i $ . - She selects points $ a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i $ and connects each pair of these points with arcs. After performing all $ m $ operations, she wants to know the number of connected components $ ^\dagger $ these points form. Please help her find this number. $ ^\dagger $ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le m \le 2 \cdot 10^5 $ ). The $ i $ -th of the following $ m $ lines contains three integers $ a_i $ , $ d_i $ , and $ k_i $ ( $ 1 \le a_i \le a_i + k_i\cdot d_i \le n $ , $ 1 \le d_i \le 10 $ , $ 0 \le k_i \le n $ ). It is guaranteed that both the sum of $ n $ and the sum of $ m $ over all test cases do not exceed $ 2 \cdot 10^5 $ .

For each test case, output the number of connected components.

In the first test case, there are $ n = 10 $ points. The first operation joins the points $ 1 $ , $ 3 $ , $ 5 $ , $ 7 $ , and $ 9 $ . The second operation joins the points $ 2 $ , $ 4 $ , $ 6 $ , $ 8 $ , and $ 10 $ . There are thus two connected components: $ \{1, 3, 5, 7, 9\} $ and $ \{2, 4, 6, 8, 10\} $ . In the second test case, there are $ n = 100 $ points. The only operation joins the points $ 19 $ , $ 21 $ , $ 23 $ , $ 25 $ , and $ 27 $ . Now all of them form a single connected component of size $ 5 $ . The other $ 95 $ points form single-point connected components. Thus, the answer is $ 1 + 95 = 96 $ . In the third test case, there are $ n = 100 $ points. After the operations, all odd points from $ 1 $ to $ 79 $ will be in one connected component of size $ 40 $ . The other $ 60 $ points form single-point connected components. Thus, the answer is $ 1 + 60 = 61 $ .