I. Intersection of Hyperrectangles
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ $$$d$$$-dimensional hyperrectangles with sides parallel to the axes numbered from $$$1$$$ to $$$n$$$. Each of these hyperrectangles is defined by the region of all points with real coordinates $$$(x_1,x_2,\dots,x_d)$$$ such that $$$l_i \leq x_i \leq r_i$$$ (for $$$1 \leq i \leq d$$$). For each hyperrectangle, $$$2 \cdot d$$$ integers $$$l_1, r_1, l_2, r_2, \dots, l_d, r_d$$$ are given.

You can do the following operation on the hyperrectangles:

  • Select one hyperrectangle and move it a unit along an axis. More formally, select one hyperrectangle and a $$$i$$$ ($$$1 \leq i \leq d$$$) and set $$$l_i$$$ to $$$l_i+1$$$ and $$$r_i$$$ to $$$r_i+1$$$, or set $$$l_i$$$ to $$$l_i-1$$$ and $$$r_i$$$ to $$$r_i-1$$$.

Answer $$$q$$$ queries. In each query, you are given two integers $$$L$$$ and $$$R$$$. You have to find the minimum number of operations so the intersection of the hyperrectangles numbered from $$$L$$$ to $$$R$$$ is non-empty. In other words, there must exist a point that is contained inside all such hyperrectangles. A point in the boundary of the hyperrectangle is said to be inside the hyperrectangle.

Input

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 10^4$$$ and $$$1 \leq d \leq 50$$$) $$$-$$$ the number of hyperrectangles and the number of dimensions.

The following $$$n$$$ lines contain the description of the hyperrectangles. Each line contains $$$2 \cdot d$$$ integers $$$l_1, r_1, l_2, r_2, \dots, l_d, r_d$$$ ($$$-10^9 \leq l_i \lt r_i \leq 10^9$$$ for $$$1 \leq i \leq d$$$) $$$-$$$ the description of the hyperrectangles.

The following line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^4$$$) $$$-$$$ the number of queries.

The following $$$q$$$ lines contain the description of the queries. Each line contains $$$2$$$ integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq n$$$) $$$-$$$ the range of each query.

Output

Print $$$q$$$ lines with the answers to the queries.

Examples
Input
3 2
2 4 2 4
0 2 0 2
-2 0 -2 0
3
1 2
2 3
1 3
Output
0
0
4
Input
2 3
1 2 1 2 1 2
0 3 0 3 0 3
1
1 2
Output
0
Input
4 2
0 4 2 5
5 6 1 4
2 3 3 4
1 2 0 1
3
1 3
3 4
1 4
Output
2
2
5
Note

The diagram below shows the minimum number of operations needed in the third query of the first sample:

The operations are as follows:

  1. Move the third hyperrectangle one unit in the positive direction of the first axis.
  2. Move the third hyperrectangle one unit in the positive direction of the second axis.
  3. Move the first hyperrectangle one unit in the negative direction of the second axis.
  4. Move the first hyperrectangle one unit in the negative direction of the first axis.

After these $$$4$$$ operations, all the hyperrectangles intersect at point $$$(1,1)$$$.

Note that the first axis is the $$$x$$$-axis and the second axis is the $$$y$$$-axis in the diagram above.