Night is approaching and its dangers lurk. As is well known, the most illustrious gentlemen turn into true rogues when the clock strikes twelve. Tired of seeing your neighbors steal from each other on the street with total impunity, you decide to install streetlights along your street so that it is always illuminated, and at least they feel some shame when committing their misdeeds. However, you do not want to waste electricity unnecessarily, so you decide to create a program that, knowing where your neighbors are at a given moment and what radius each streetlight illuminates, calculates the minimum number of streetlights to turn on so that everyone is illuminated, or informs you if it is not possible to do so. A neighbor is considered illuminated if they are within a closed interval centered on a streetlight and with the radius of that streetlight.
The input will consist of several cases. The first line will contain an integer $$$t$$$, the number of cases to solve.
For each case:
- The first line will contain two integers $$$n, m$$$, the number of neighbors and the number of streetlights.
- The following line contains $$$n$$$ integers $$$x_i$$$ with the positions of your neighbors.
- The last $$$m$$$ lines contain a pair of integers $$$y_i, r_i$$$, the position and the radius of each streetlight.
For each case, write on a line the minimum number of streetlights that need to be turned on to illuminate all the neighbors or "imposible" if it cannot be resolved.
$$$0 \leq x_i, y_i, r_i \leq 10^9, 1 \leq t \leq 100$$$
- 30 points $$$1 \leq n \leq 100, 1 \leq m \leq 10$$$
- 30 points $$$1 \leq n \leq 1000, 1 \leq m \leq 100$$$
- 40 points $$$1 \leq n, m \leq 10^5$$$
3 1 2 5 3 2 7 2 5 5 7 10 3 4 4 3 3 7 1 8 2 3 2 2 4 1 1 0 3 2
1 2 imposible
