Afraid of the Dark

Interview

Time limit1sMemory limit512 MB

Summary
Given an R x C grid of brightness values and Q rectangle corner queries, compute each rectangle's mean using integer division.
Level

Medium4 of 10

Topics
Prefix sum, Matrix
Solved
No attempts yet

Problem

Ho-geun is timid and hates the dark. We want to show him a photo, but he refuses to look at it at all unless its brightness is at least the average. Let us find a part of the photo that Ho-geun can see, even if only partially.

The figure above shows a 5×6 photo to show to Ho-geun, and each pixel represents its brightness. To determine whether Ho-geun can see even a part of the photo, we must find the average brightness of the rectangle whose corners are the two points (r1, c1) and (r2, c2). For example, in the figure above, this refers to the rectangle with corners (2, 2) and (4, 5).

Given an R×C photo to show to Ho-geun, find the average brightness of a part of the photo.

Input

The first line gives the integers R, C (1 ≤ R, C ≤ 1,000), the size of the photo, and the integer Q (1 ≤ Q ≤ 10,000), the number of parts of the photo whose average brightness we want to find.

The next R lines give the R×C photo. Each pixel of the photo has an integer K (1 ≤ K ≤ 1,000) representing its brightness.

Each of the next Q lines gives the integers r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C) representing the two corners of a part of the photo.

Output

For each of the Q lines, output the average brightness of the rectangle whose corners are the two points (r1, c1) and (r2, c2) in the given photo. The average is taken as the quotient of integer division.

Examples2

  1. Example 1

    Input
    5 6 1
4 1 3 4 9 5
1 2 8 7 5 5
8 1 2 5 3 2
1 5 3 4 2 5
5 2 1 2 3 5
2 2 4 5
    Expected output
    3

  2. Example 2

    Input
    4 3 5
25 93 64
10 29 85
80 63 71
99 58 86
2 2 2 3
3 2 3 3
1 2 2 2
1 2 4 3
2 3 2 3
    Expected output
    57
67
61
68
85