CF853C Boredom

Ilya is sitting in a waiting area of Metropolis airport and is bored of looking at time table that shows again and again that his plane is delayed. So he took out a sheet of paper and decided to solve some problems. First Ilya has drawn a grid of size $ n×n $ and marked $ n $ squares on it, such that no two marked squares share the same row or the same column. He calls a rectangle on a grid with sides parallel to grid sides beautiful if exactly two of its corner squares are marked. There are exactly $ n·(n-1)/2 $ beautiful rectangles. Ilya has chosen $ q $ query rectangles on a grid with sides parallel to grid sides (not necessarily beautiful ones), and for each of those rectangles he wants to find its beauty degree. Beauty degree of a rectangle is the number of beautiful rectangles that share at least one square with the given one. Now Ilya thinks that he might not have enough time to solve the problem till the departure of his flight. You are given the description of marked cells and the query rectangles, help Ilya find the beauty degree of each of the query rectangles.

N/A

N/A

The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1. In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:  There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture: