Meteor

A well-known internet company runs a web photo service that lets users control a high-performance telescope and photograph events in the sky. A record-breaking meteor shower is coming, and the company is holding a contest: whoever captures a single photo containing the most meteors wins. The trajectory of every meteor is published in advance, so the winning move is to compute the exact moment when the telescope frame holds the largest number of meteors.

There are $n$ meteors, each in uniform linear motion. Meteor $m_i$ is at position $p_i + t \cdot v_i$ at time $t$, where $t$ is a non-negative real number, $p_i = (x_i, y_i)$ is its starting point, and $v_i = (a_i, b_i)$ is its non-zero velocity vector. For example, if $p_i = (1, 3)$ and $v_i = (-2, 5)$, then at $t = 0.5$ the meteor is at $(1, 3) + 0.5 \cdot (-2, 5) = (0, 5.5)$.

The telescope frame is an axis-aligned rectangle whose lower-left corner is $(0, 0)$ and whose upper-right corner is $(w, h)$. A meteor counts as being in the frame only when it is strictly in the interior, never on the boundary. In Figure 1, for instance, some starting points never enter the interior at all and so can never be photographed. Compute a time at which the number of meteors inside the frame is as large as possible, and output that maximum count.

Figure 1

The input is read from standard input and contains $T$ test cases. The first line holds the integer $T$. Each test case is:

• One line with two integers $w$ and $h$ ($1 \le w, h \le 100000$), the width and height of the telescope frame, separated by a single space.
• One line with the integer $n$ ($1 \le n \le 100000$), the number of meteors.
• $n$ lines, each with four integers $x_i$, $y_i$, $a_i$, and $b_i$ separated by single spaces, where $(x_i, y_i)$ is the starting point $p_i$ and $(a_i, b_i)$ is the non-zero velocity vector $v_i$. Here $-200000 \le x_i, y_i \le 200000$ and $-10 \le a_i, b_i \le 10$, and at least one of $a_i$ and $b_i$ is nonzero. All starting points $p_i$ are distinct.

Write to standard output. For each test case, print on its own line the maximum number of meteors that can be inside the telescope frame at a single moment.