409869: GYM103821 A Laser Tag

Laser tag is a team shooting game, where players attempt to shoot other individuals by tagging them with a laser emitting gun.

Ali and Resli decided to play a match, so each one of them gathered a team of $$$n$$$ players.

The Arena where the match will be held is a $$$N\times N$$$ $$$2d$$$ plane, the $$$i_{th}$$$ player of Resli's team will stand at coordinates $$$(i, 0)$$$, while the $$$i_{th}$$$ player of Ali's team will stand at coordinates $$$(i, N)$$$.

To make things challenging, the arena has $$$Q$$$ walls, each wall is parallel to the x-axis and is given by three integers $$$x_1, x_2, y$$$ which means that the wall extends between points $$$(x_1, y)$$$ and $$$(x_2, y)$$$.

To ensure his win, Resli modified his team's guns, such that when a laser beam hits some wall, the beam will stop and two new beams will be generated at the endpoints of the wall (at coordinates $$$(x_1,y)$$$ and $$$(x_2,y)$$$ ) and will continue forward in the same direction as the original laser beam, and if one of these new generated laser beams hits a wall, the previously mentioned process will happen again (see notes for clarification).

Can you help Resli to find out how many players of Ali's team will be tagged by at least one laser beam if each player of Resli's team shot one laser beam in a direction parallel to the y axis towards the opposite team player (the $$$i_{th}$$$ player of Resli's team will shoot one laser beam in the direction of the $$$i_{th}$$$ player of Ali's team).

The first line contains a single integer $$$T$$$ ($$$1\le{T}\le{10}^4$$$), the number of test cases.

The first line of each test case contains two integers $$$n$$$ ($$$2\le{n}\le{2}\times{10}^5$$$) and $$$q$$$ ($$$1\le{q}\le{n}$$$).

Each of the next $$$q$$$ lines of each test case contains three integers $$$x_1$$$,$$$x_2$$$,$$$y$$$ ($$$1\le{x_1}\le {x_2}\le{n}$$$), ($$$1\le {y}\le {n-1}$$$), which means there is a wall between coordinates $$$(x_1,y)$$$ and $$$(x_2,y)$$$.

The sum of $$$n$$$ over all test cases will not exceed $$$2\times {10}^5$$$.

$$$\textbf {It's guaranteed that no two walls will overlap or share a common point.}$$$

Output $$$T$$$ lines, the $$$i^{th}$$$ line contains the answer for the $$$i^{th}$$$ test case.

1
5 4
1 4 1
4 5 2
2 3 3
3 5 4

3

This picture demonstrates how the laser beam will move assuming that each team has $$$5$$$ persons and only the third person of Resli's team will shoot a laser, and there is a wall between $$$(1,1)$$$ and $$$(4,1)$$$. The laser will move towards the third person in Ali's team, and will stop after hitting the wall and two new lasers at the endpoints of the wall $$$(1,1)$$$, $$$(4,1)$$$ will be generated and will continue towards the first and fourth persons of Ali's team.