**Introduction**

**Problem**

In this problem, we are given a 2D plane and we have to perform two types of queries:

- (x,y) - For this type of query, insert a point with coordinates (x,y) into the 2D plane.
- (x1, y1, x2, y2) - For this type of query, first consider a rectangle having coordinates - (x1,y1), (x1,y2), (x2,y1), (x2,y2). Now count the number of triangles that can be formed by joining the points inside this rectangle. Also include the triangles with 0 areas in your answer.

In other words, we have to implement two types of queries. One is to insert a point in the plane, and the other is to count the number of triangles that can be formed inside a given rectangle.

**Example - **

**Input:** queries = [ {2, 2}, {3, 5}, {4, 2}, {4, 5}, {5, 4}, {1, 1, 6, 6} ].

**Output: **10 20

**Explanation:**

- In the first 5 queries, we have inserted 5 points in our 2D plane.
- For the next query, we have to count the number of triangles formed by the points inside the rectangle (1,1),(1,6),(6,6),(6,1).

The plane will now look like this:

There are 5 points inside the given rectangle. To form a triangle, we can choose any 3 points and connect them. Therefore, the answer will be ^{5}C_{3} = 10.

**Approach**

First, let us assume that we know the number of points inside a rectangle at any instance. Let the number of points inside the given rectangle be ‘m’. Now, how can we count the number of triangles formed by these points?

The number of triangles formed by ‘m’ points is equal to ^{m}C_{3}. Note that we will get a count of the triangles having non-zero areas and zero areas. As we have to count both, this will work.

We just need to find the number of points inside the given rectangle to count the number of triangles. Let P(x, y) define the number of points in a rectangle starting from (1,1) to (x, y). Thus, the number of points inside the rectangle defined by (x1, y1) and (x2, y2) will be:

`P(x2, y2) - P(x1-1, y2) - P(x2, y1-1) + P(x1-1, y1-1)`

We now need a way to find P(x,y). If we have to insert all the points at first and then count the number of triangles, then we can just maintain a 2D table to store the number of points such that ‘table[x][y]’ will store the number of points inside the rectangle defined by (1,1) and (x,y).

For multiple queries, we can use a 2D __Binary Indexed Tree__ to insert a point and calculate P(x,y). The update function will add a new point in the table and the query function will return the number of points inside a rectangle, which will then be used to count the number of triangles inside that rectangle.

Also see, __Euclid GCD Algorithm__