See Problem N for PDF statements.

You are now in a -dimensional universe, which could be seen as an hyperrectangle. To be specific, let's divide the universe into hypercubes sized to describe different regions. The position of each region can be denoted by a -dimensional integer coordinate where . Each region owns a and the initial value is . However, due to the space war and the abuse of dimensionality weapons, the of some regions in the universe has decayed to less than .

Your spaceship is an hyperrectangle which can also be viewed as parts of hypercubes sized . The position of each part can also be denoted by a -dimensional integer coordinate where . Each part of your spaceship also owns a which is initially . Thanks to advanced technology, some parts of your spaceship are reformed and their become less than , which can make them enter the regions with lower .

We define the spaceship to be in a valid position if the following conditions are met:

• Each part of the spaceship is located exactly in one region.
• Each part of the spaceship cannot have a strictly higher than the of the region.

Please calculate the number of different valid positions for your spaceship. Please note that you can't rotate the spaceship.

The first line contains an integer  ().

The second line contains  integers  (), indicating the size of the universe.

The third line is an integer  (), indicating the number of regions whose  has decayed.

Each of the following  lines contains  integers  and  (, ), indicating that the  of region  has decayed to . It is guaranteed that the  regions are pairwise different.

The next line contains  integers  (), indicating the size of the spaceship.

The next line contains an integer  (), indicating the number of parts of the spaceship are reformed.

Each of the following  lines contains  integers  and  (, ), indicating that the  of part  becomes . It is guaranteed that the  parts are pairwise different.

Output one integer indicating the number of different valid positions for your spaceship.

2
4 4
7
0 0 1
1 0 1
1 2 1
2 0 1
2 1 1
2 3 1
3 3 1
2 2
1
1 1 1

1

For the first sample, the universe is two-dimensional. The  of the universe and spaceship are as follows.

3
4 4 4
4
0 1 0 1
1 2 2 2
3 2 3 2
3 3 0 1
2 2 2
1
1 0 0 2

15