A. Traffic Jam
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a long road of length $$$10^{9}$$$.

There are $$$N$$$ pedestrians crossing the road and $$$M$$$ cars driving on the road. You know, that the $$$i$$$-th pedestrian is going to cross the road from time $$$s_i$$$ to time $$$e_i$$$ at position $$$p_i$$$. You also know that the $$$j$$$-th car will drive from position $$$l_j$$$ to position $$$r_j$$$, starting at time $$$t_j$$$. To prevent car accidents, the following rule is set to regulate cars.

  • If a pedestrian is crossing the road at the same position with some cars, then the cars should stop and wait until the pedestrian finishes his/her crossing.

All the cars proceed $$$1$$$ unit of length per unit of time unless it is stopped by the regulation.

To better illustrate the idea, the action of the car is defined as below.

  • Let the current time be $$$t$$$ and the current position of the car be $$$x$$$.
  • If there exists some $$$i$$$ such that $$$s_i \leq t \leq e_i$$$ and $$$p_i = x$$$, then the car is stopped.
  • If there doesn't exist such $$$i$$$, then the car is driving.
  • Increase $$$t$$$ and $$$x$$$ based on the status of the car.
  • If $$$x = r_j$$$, then the car arrives at it's destination and disappears.

Given all the above information, you now wonder how many unordered pairs of cars would meet each other (formally speaking, there exists some time when the cars share the same position).

Below are some notes to avoid ambiguity, they are helpful but not necessary.

  • A pedestrain's crossing time is inclusive, meaning that cars should stop even at time $$$s_i$$$ and time $$$e_i$$$.
  • Two cars are counted as meeted each other even at the starting/ending position.
  • If a car is stopped by pedestrian $$$i$$$, then the car arrives at position $$$p_i + 1$$$ at time $$$e_i + 2$$$.
Input

The first line of the input consists of two integers $$$N, M$$$, representing the number of pedestrians and cars.

Each of the following $$$N$$$ lines consists of three integers $$$s_i, e_i, p_i$$$, representing the starting time, ending time, and the position of the pedestrian's crossing.

Each of the following $$$M$$$ lines consists of three integers $$$l_j, r_j, t_j$$$, representing the starting position, ending position, and the starting time of the car.

It is guaranteed that all position given ($$$p_i, l_j, r_j$$$) are distinct.

  • $$$1 \leq N, M \leq 10^{5}$$$
  • $$$1 \leq s_i, e_i, p_i, l_j, r_j, t_j \leq 10^{9}$$$
  • $$$s_i \leq e_i$$$
  • $$$l_j \lt r_j$$$
  • All $$$p_i, l_j, r_j$$$ are distinct
Output

Output a single line with the number of unordered pairs of cars which would meet each other.

Examples
Input
1 2
1 10 5
3 7 1
4 8 1
Output
1
Input
1 3
1 10 5
2 7 2
4 8 1
1 3 1
Output
2
Note

In sample input 1, car 1 and car 2 meets at position 5, time 3.

In sample input 2, car 1 and car 3 meets at position 2, time 2; car 1 and car 2 meets at position 5, time 5.