A higher resolution is required to access the IDE

- 94

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

You like to solve Minesweeper levels ? You will love generating them !**How to generate a level**

* A level is a

`width`x

`height`cells grid. Its origin is the top left corner. It contains

`n`mines.

* The level is generated only when the player selects the first cell. The 3x3 cells square centered on this cell is always set free of mines.

* To generate a mine, X and Y grid coordinates (X first and then Y) are randomly generated until an available position is found. To generate X (resp. Y), use the random value modulo

`width`(resp.

`height`).

**Controlling randomness**

The random number generator used to generate the level is a pseudo random number generator (PRNG) initialized with a

`seed`provided in the inputs. The PRNG works as follows:

The nth generated value is:

R(n) = (214013 * R(n-1) + 2531011) / 65536

with R(0) =

`seed`

R(1) is the first value to use.

With a seed of 31, the expected five first values produced by the PRNG are 139, 492, 1645, 5410, 17705.

You must use a single instance of PRNG for the whole generation. All calculations must be in 32-bit unsigned numbers. Beware that some languages (Python for instance) implicitly generate big integers without overflowing.

Input

**A single line:**

`width`the level width,

`height`the level height,

`n`the number of mines for the level,

`x`,

`y`the coordinates of the first selected cell,

`seed`the seed for the random number generator

Output

`height`

**lines:**for each line, a row of cells starting from the top row. Each cell is represented by a single ASCII code without space between chars.

**Cell format**

*

*

* otherwise

Constraints

5 ≤

5 ≤

5 ≤

`width`≤ 305 ≤

`height`≤ 165 ≤

`n`≤ 99Example

Input

6 6 7 3 3 31

Output

1#2##1 222221 #1..11 331.1# ##1.11 221...

A higher resolution is required to access the IDE