Problem E. Enormous spiral ≡

Author:A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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 ai 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.

xxx
xxx
xxx

Input file format

Input file contains numbers N K S followed by N integers ai, and then by K coordinates xi yi.

Output file format

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

Constraints

2 ≤ ai ≤ 109, ai − 1 < ai + 1, 1 ≤ N ≤ 106,  − 109 ≤ xi, yi ≤ 109, 1 ≤ K ≤ 10000, 1 ≤ S ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
1 1 10
100
0 0
 
10
2 
2 1 10
100 1000
1 -1
 
0
3 
4 3 3
4 3 6 4
-1 0
0 0
1 0
 
5 6 7
0.106s 0.014s 13