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

 x x x x x x x x x

### 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, ai1 < 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.104s 0.012s 13