Problem Statement

Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' or '.' he will construct donuts from the cells.

To make the donuts:

1. Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
2. Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
3. For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.

Here is an example with three overlapping donuts.

..........
.00000000.
.0......0.
.0.000000.
.0.0...00.
.0.0...00.
.0.000000.
.0......0.
.00000000.
..........

The grid in this problem will be pseudo-randomly generated using the following method:

You are given four ints: H (the grid height), W (the grid width), seed and threshold. Let x₀=seed and for all i>=0 let x_i+1 = (x_i * 25173 + 13849) modulo 65536. Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, calculate the next x_i (starting with x₁ for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a '.', otherwise it will contain a '0'.

Return the number of distinct donuts in the figure. Two donuts are considered distinct if they either have different width or height, or if the top left hand corner is in a different location (i.e., overlapping donuts are counted).

Definition

Notes

Constraints

Examples