magicwand

Problem Description

Rar the Cat has found a greyscale picture H by W pixels wide. Each pixel is a value between 0 and 1023 (inclusive).

Rar the Cat wants to edit the photo but is too lazy. He wants you to code the 'Magic Wand' feature.

The 'Magic Wand' will start at pixel (X, Y) with a threshold T, that is the Xth pixel from the top and Yth pixel from the left. It will then propagate in 4 directions (up/down/left/right), selecting pixels whose value is not more than T different from the starting pixel (X, Y). A pixel will only be selected if it is adjacent to another selected pixel, in addition to the constraint of values.

At the end of the day, Rar the Cat wants to know which pixels are selected by printing a H by W grid of 0 and 1s. '0' will denote an unselected pixel while '1' will denote a selected pixel.

Limits

For all testcases, 0 < X ≤ H, 0 < Y ≤ W, 0 ≤ T ≤ 1023.

Subtask 1 (32%): H = 1, 1 ≤ W ≤ 500.

Subtask 2 (33%): 1 ≤ H, W ≤ 500, each pixel will be either 0 or 1.

Subtask 3 (35%): 1 ≤ H, W ≤ 500.

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain five integers, H, W, X, Y followed by T. X and Y are 1-indexed.

There will be H lines containing W integers each. Each integer will be between 0 and 1023, representing the value of the pixel.

Output

The output should contain H lines with W characters each. Each character should either be a '0' or '1', indicating whether the pixel is selected or not.

Sample Testcase 1

Input

3 3 2 2 1
1 3 4
2 0 1
3 1 2

Output

000
011
010

Explanation

The 'Magic Wand' operation starts at cell(2, 2), which corresponds to the centre pixel with value 0.

The 2 adjacent '1's are then selected as they are adjacent to the starting cell and their difference to the starting cell is not more than 1.

Sample Testcase 2

Input

7 9 3 7 2
3 4 4 6 3 9 4 8 2
2 3 4 9 5 2 1 2 0
0 3 4 6 9 2 3 8 1
2 3 5 7 8 3 2 8 1
0 9 3 8 5 6 8 2 0
0 5 6 4 6 5 4 2 3
1 2 3 4 5 6 7 8 9

Output

000010100
000011110
000001100
000001100
000000000
000000000
000000000

Explanation

The 'Magic Wand' operation starts at cell(3, 7), which corresponds to the pixel with value 3.

Hence, pixels between 1 and 5 that are adjacent to another selected cell, will be selected.

Sample Testcase 3

Input

7 9 3 7 3
3 4 4 6 3 9 4 8 2
2 3 4 9 5 2 1 2 0
0 3 4 6 9 2 3 8 1
2 3 5 7 8 3 2 8 1
0 9 3 8 5 6 8 2 0
0 5 6 4 6 5 4 2 3
1 2 3 4 5 6 7 8 9

Output

111110101
111011111
111101101
111001101
101011011
111111111
111111000

Explanation

The grid is the same as Sample Testcase 2.

The 'Magic Wand' operation starts at cell(3, 7), which corresponds to the pixel with value 3.


Submitting .cpp to 'magicwand'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 61
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 32
2 33
3 35
4 0