Pizza Cutter

Interview

Time limit2sMemory limit512 MB

Summary

Count the pieces made by H rightward and V upward cuts whose endpoints are given, using Euler's formula and inversion counting of crossing pairs.

Level: Medium6 of 10
Topics: Math, Combinatorics, Sorting, Binary search
Solved: No attempts yet

Problem

Grandpa Giuseppe received a professional pizza cutter as a gift, the wheel kind, and to celebrate he baked a giant rectangular pizza for his grandchildren! He always divided his pizzas into pieces by cutting along continuous lines, not necessarily straight, of two kinds: some start on the left edge of the pizza, proceed monotonically to the right, and end on the right edge; others start on the bottom edge, proceed monotonically upward, and end on the top edge. But Grandpa Giuseppe always followed one property: two cuts of the same kind could never intersect. The left part of the figure shows an example with 4 cuts, two of each kind, dividing the pizza into 9 pieces.

Grandpa Giuseppe simply loves geometry, topology, combinatorics, and things like that. So he decided to show the children that he could obtain more pieces with the same number of cuts if intersections between cuts of the same kind were allowed. The right part of the figure shows, for example, that if the two cuts of the left-to-right kind may intersect, the pizza is divided into 10 pieces.

Grandpa Giuseppe discarded the property, but he will not make random cuts. Besides being of one of the two kinds, they obey the following restrictions:

Two cuts have at most one intersection point, and if they do, it is because the cuts cross at that point.
Three cuts do not intersect at the same point.
Two cuts do not intersect on the edge of the pizza.
A cut does not intersect a corner of the pizza.

Given the start and end points of each cut, your program must compute the number of pieces resulting from Grandpa Giuseppe's cuts.

Input

The first line of the input contains two integers X and Y, (1 ≤ X, Y ≤ 10^9), representing the coordinates (X, Y) of the top-right corner of the pizza. The bottom-left corner always has coordinates (0, 0). The second line contains two integers H and V, (1 ≤ H, V ≤ 10^5), indicating, respectively, the number of cuts that go from left to right, and the number of cuts that go from bottom to top. Each of the following H lines contains two integers Y1 and Y2 defining the ordinates where the vertical sides of the pizza meet a cut that goes from the left side, at ordinate Y1, to the right side, at ordinate Y2. Each of the following V lines contains two integers X1 and X2 defining the abscissas where the horizontal sides of the pizza meet a cut that goes from the bottom side, at abscissa X1, to the top side, at abscissa X2.

Output

Print one line containing an integer representing the number of resulting pieces.

Examples3

Example 1
Input
```
3 4
3 2
1 2
2 1
3 3
1 1
2 2
```
Expected output
```
13
```
Example 2
Input
```
5 5
3 3
2 1
3 2
1 3
3 4
4 3
2 2
```
Expected output
```
19
```

Example 3

Input

10000 10000
1 2
321 3455
10 2347
543 8765

Expected output