Consider an infinite plane divided into square cells with the side of 1.
The spiral starts at cell (0, 0) and consists of N straight segments.
First segment runs from the starting cell in the direction of x axis,
each following segment takes a 90° turn to the right.
Segment number i contains exactly a_{i} cells.

Segments do not overlap except at joint cells,
which are treated as belonging to both adjacent segments.

A square window on the plane consists of S × S cells
and is defined by coordinates of top left cell (x, y)
(y axis is directed upwards).

Your program will be given coordinates of K square windows,
and must determine, for each window, the number of cells inside it
belonging to the spiral.

For example, a spiral below is defined by input of sample test 3.
Cells marked with 'x' are inside the first window from the same test.

x

x

x

x

x

x

x

x

x

Input file format

Input file contains numbers NKS followed by N integers a_{i},
and then by K coordinates x_{i}y_{i}.

Output file format

Output file must contain K numbers — cell counts for each window.

Constraints

2 ≤ a_{i} ≤ 10^{9}, a_{i−1} < a_{i+1}, 1 ≤ N ≤ 10^{6},
−10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}, 1 ≤ K ≤ 10000, 1 ≤ S ≤ 100