ACM 2007 - Enormous spiral

Problem E. Enormous spiral ≡

problems
visible spaces
basic formulae
wide text
editor

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 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 N K S 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⁹, a_i − 1 < a_i + 1, 1 ≤ N ≤ 10⁶,  − 10⁹ ≤ x_i, y_i ≤ 10⁹, 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`