408208: GYM103055 B Restore Atlantis

There are $$$n$$$ ancient Greek maps describing the fabled islands Atlantis. The maps are labeled by $$$1,2,\dots,n$$$. The $$$i$$$-th map shows the rectangle area $$$R_i$$$ is a part of Atlantis. The sides of all rectangles are parallel to the axes. There may be multiple islands, and the rectangles may overlap.

Unfortunately, some maps are even unreliable so they will not be considered. You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i\leq t_i\leq n$$$). Please write a program to figure out the total area of Atlantis when all maps labeled by $$$k$$$ ($$$s_i\leq k\leq t_i$$$) are unreliable.

The input contains only a single case.

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 100\,000$$$), denoting the number of maps and the number of queries.

In the next $$$n$$$ lines, the $$$i$$$-th line contains four integers $$$xa_i$$$, $$$ya_i$$$, $$$xb_i$$$ and $$$yb_i$$$ ($$$0\le xa_i<xb_i\leq 2\,000$$$, $$$0\le ya_i<yb_i\leq 2\,000$$$), describing the $$$i$$$-th map $$$R_i$$$. $$$(xa_i,ya_i)$$$ is the southwest corner of $$$R_i$$$, and $$$(xb_i,yb_i)$$$ is the northeast corner of $$$R_i$$$.

In the next $$$q$$$ lines, the $$$i$$$-th line $$$(1 \le i \le q)$$$ contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i\leq t_i\leq n$$$), describing the $$$i$$$-th query.

For each query, print a single line containing an integer, denoting the total area using the information of all reliable maps in this query.

3 6
10 10 20 20
12 12 22 22
15 15 25 25
1 1
2 2
3 3
1 2
2 3
1 3

151
175
136
100
100
0