Horns and Hooves

Interview

Time limit2sMemory limit1024 MB

Summary

Given horn types and hoof types, each with a cost and a count, count the pairs where the horn costs more, costs the same, or costs less than the hoof.

Level: Medium4 of 10
Topics: Sorting, Prefix sum
Solved: No attempts yet

Problem

The attempted assault on Koreyko, a secret millionaire, was a disastrous failure. The foster brothers Panikovskiy and Balaganov have barricaded themselves in their office. They are playing a strange game. One of them has a room full of horns, and the other has a room full of hooves. They are taking all possible pairs (horn, hoof), and whoever has the more expensive object in the pair wins. They want to know one thing: who will win more often. Their psychological integrity has been somewhat compromised, and it might be beyond their powers at the moment to solve this problem by their own efforts. Please help them, and they will thank you... with horns and hooves.

Input

The first line of the input contains two integers $n$ and $m$ , where $n$ is the number of horn types and $m$ is the number of hoof types ( $1 \le n, m \le 10^5$ ).

The following $n$ lines describe the horn types, one type per line. Each type is defined by two positive integers. The first integer is the cost of one horn of that type, and the second integer is the supply of horns of that type (the number of individual units).

The following $m$ lines describe the hoof types in the same format.

The cost of any horn or hoof does not exceed $10^9$ . The number of horns or hooves of each type does not exceed $10^4$ .

Output

The output must contain three numbers: the number of pairs where the price of the horn is greater than the price of the hoof, the number of pairs where the prices are equal, and the number of pairs where the price of the horn is less than the price of the hoof, in that order.

Examples1

Example 1
Input
```
3 2
1 2
2 3
4 1
2 3
3 1
```
Expected output
```
4 9 11
```