Duchess#720
The Duchess is preparing for the royal croquet game and is sewing a special corset for the occasion. This corset has lacing holes, with a total of N+M holes arranged in rows: one row contains holes, and the other has holes.
The lacing is quite intricate—special ties connect holes from the first row to holes in the second row, resulting in numerous intersections between the rows. The Duchess is desperate—she must know how many of these intersections there are! After all, she does not want to offend the Queen with her ignorance.
It is hard to call the Duchess a sympathetic character—just look at the portrait of the "Ugly Duchess" by the th-century artist Quinten Massys. Most likely, she is based on Margarete Maultasch, Duchess of Carinthia and Tyrol (th century), who served as the model for the early illustrations of the Duchess in "Alice's Adventures in Wonderland." Still, the Duchess needs help.
Let us assume that the points in the first row have coordinates (0,1), (0,2), \ldots, (0,N), and the points in the second row have coordinates (1,1), (1,2), \ldots, (1,M). Some pairs of points with different abscissas are connected by segments. Determine how many distinct pairs of these segments intersect.
The first line contains the numbers , , and , where is the number of segments connecting the points (1 \leq N, M \leq 300, 1 \leq K \leq NM). The next lines each contain two numbers and , which means a segment connects the points with coordinates and . All the segments in the input are distinct.
Print the number of pairs of segments that intersect. If segments only touch at endpoints, this does not count as an intersection.
Example 1