Problem B
Path Crossings

Yraglac is the developer of a popular Android/iOS racing game that also happens to collect location data from its players all the time, even when the player is not using the app. He has now amassed a large database of the precise location $(x,y)$ of players over time $(t)$. We will refer to a triplet $(x,y,t)$ as a “ping”.

Now Yraglac wants to analyze this data to determine which players are likely to have met in person. He will probably sell this information and also use it to send targeted advertisements encouraging players to purchase a new co-op game mode add-on. Players are considered to have likely met if they have “crossed paths”, meaning that they were within $1$ meter of each other within $10$ seconds. Precisely, players A and B have crossed paths if there exists a ping $(x_ A,y_ A,t_ A)$ from player A and a ping $(x_ B,y_ B,t_ B)$ from player B such that the Euclidean distance from $(x_ A,y_ A)$ to $(x_ B,y_ B)$ is at most $1$ meter and $|t_ A - t_ B| \leq 10 \text { seconds}$.

Can you help Yraglac find all players who crossed paths?

Input

The first line contains two integers $P$ and $N$ ($2 \leq P \leq 100$, $1 \leq N \leq 2 \cdot 10^5$), the number of players and the total number of pings in Yraglac’s database. Next will follow $N$ lines with one ping per line. The $i$th line contains four integers of $p_ i$, $x_ i$, $y_ i$, and $t_ i$ ($1 \leq p_ i \leq P$, $-1\, 000 \leq x_ i, y_ i \leq 1\, 000$, $0 \leq t_ i \leq 10^9$). $p_ i$ is the player, $(x_ i, y_ i)$ is the location in millimeters (where $1\, 000$ millimeters = $1$ meter), and $t_ i$ is the time in seconds. Pings may be given in any order. For a given player, there will not be two pings with the same time. Some players may not have any pings.

It is guaranteed that there are at most $5$ pings in any $10$-second time window. That is, for any integer $t$, there will be at most $5$ pings from any player with a time between $t$ and $t+10$ inclusive.

Output

Output a line containing an integer $C$ which is the total number of distinct player pairs who cross paths at least once. Note that $C=0$ is possible. Then output $C$ lines, where the $i$th line contains two integers $a_ i$, $b_ i$ ($1 \leq a_ i, b_ i \leq P$, $a_ i < b_ i$), identifying a player pair who crossed paths. The player pairs must be output in ascending order of $a_ i$, and if two pairs have the same $a_ i$, then ascending order of $b_ i$.

3 4
1 0 0 0
3 -1000 -1000 6
3 5 5 17
2 5 5 6

1
1 2