408208: GYM103055 B Restore Atlantis
Description
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.
InputThe 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.
OutputFor each query, print a single line containing an integer, denoting the total area using the information of all reliable maps in this query.
ExampleInput3 6 10 10 20 20 12 12 22 22 15 15 25 25 1 1 2 2 3 3 1 2 2 3 1 3Output
151 175 136 100 100 0