The quadtree of a photo

divide and conquer recursion tree images precomputation

A quadtree compresses a picture like this: if all the pixels in a square are almost the same, the brightest differs from the darkest by at most a threshold t, the square is stored as one leaf, one colour. Otherwise it is divided into four equal squares, and each is treated the same way. A square of one pixel is always a leaf. Many map and image formats work like this: a smooth sky leaves large leaves, branches and stones small ones.

An editor wants to choose a threshold and looks at how many leaves there will be for different t. For each threshold in the list, count the leaves of the quadtree.

Tests three to six are four photographs by the site's author in greyscale: “Water and mountains”, 512 × 512 pixels, and three more of 256 × 256.

Input

The first line holds the side of the picture s, a power of two, 1 ≤ s ≤ 512, and the number of thresholds q (1 ≤ q ≤ 256). Then s lines of s numbers from 0 to 255, the brightness of the pixels row by row. The last line holds q thresholds t (0 ≤ t ≤ 255).

Output

For each threshold in input order, the number of leaves of the quadtree, on a separate line.

Examples

Example 1

Input

4 4
10 12 200 200
11 10 200 201
90 90 30 60
90 90 40 50
0 2 30 190

Output

Example 2

Input

1 2
5
0 255

Output

1
1

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 11 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

For one threshold the problem is a direct recursive descent: compute the range of a square, and if it is greater than t, descend into the four quarters. What does such a descent cost if the range of each square is computed by looking at all its pixels? Write the equation for T(n), where n is the number of pixels.

2Hint 2

The minimum and maximum of a square are the minimum and maximum of its four quarters. Going from the bottom up, gluing costs four comparisons, not a look at the whole square. How does the equation change?

3Hint 3

There are up to 256 thresholds, and building the tree anew for each is expensive. A node's range does not depend on the threshold. For which t is a node a leaf?

4The idea

Build the quadtree down to single pixels once, from the bottom up, and for each node know its range r = max − min. A node is a leaf if its range is at most t while its parent's range is greater than t (the root has no parent). So a node adds one leaf to all thresholds in the half-open interval [r(node), r(parent)). There are as many such intervals as nodes, and all of them are added up with a difference array over the 256 possible thresholds.

5Walkthrough

Levels from the bottom up. At the bottom level the minimum and maximum of a 1 × 1 square are the pixel itself. A square of side 2k is glued from four squares of side k: its minimum is the minimum of four minimums, its maximum the maximum of four maximums. While gluing we know at once the range of the parent and the ranges of the children.

A node's contribution. A child with range r inside a parent with range R is a leaf exactly when r ≤ t < R: for smaller t it has to be divided, for larger ones the parent or someone above is already a leaf. That is diff[r] += 1, diff[R] -= 1. The root is a leaf for all t ≥ r(root). The prefix sums of diff give the answer for all 256 thresholds at once.

Why this is right. The range does not grow when passing to a part of a square, so if a node is a leaf, all its ancestors are divided and its descendants are not considered; a leaf is exactly a node whose range is at most t while its parent's is greater.

5+Solution

6Complexity

A quadtree has n + n/4 + n/16 + … < 4n/3 nodes, where n = s², and each is glued in constant time: T(n) = 4T(n/4) + O(1), the third case of the master theorem, Θ(n). The answers are O(256 + q). A top-down descent that looks at the pixels is T(n) = 4T(n/4) + Θ(n), the second case, Θ(n log n) per threshold, and on 262,144 pixels of noise with 43 thresholds it does not finish in time. An intermediate option, building the ranges once and descending the ready tree for each threshold, costs O(q · n) in the worst case: in Go it passes, in Python it is borderline.

7Common mistakes

Recomputing the range from scratch. Looking at all the pixels of a square in each node and for each threshold is correct but slow (the seventh test).
“A leaf if all four children are leaves.” Four smooth quarters of different colours do not make a smooth square: the range must be computed from the minimum and maximum, not from whether the children are leaves.
A strict inequality. A leaf means a range at most the threshold; at t = 0 a single-coloured square becomes a leaf.
A forgotten root. If the whole picture is smooth (the eighth test), the answer is one leaf for any threshold.

Algorithms behind it

PAR Technique Divide and conquer Cut, solve the parts the same way, glue; what it costs follows from the levels of the recursion tree and the master theorem. T(n) = a·T(n/b) + f(n) 2 problems