Competitive Contagion

Interview

Time limit1sMemory limit256 MB

Summary

Simulate a grid where each cell's virus spreads to four neighbors every second, with lower-numbered viruses spreading first and blocking others, then report the virus at one cell after S seconds.

Level: Medium5 of 10
Topics: BFS, Simulation, Graph, Sorting
Solved: No attempts yet

Problem

There is a test tube of size $N \times N$ . The test tube is divided into $1 \times 1$ cells, and a virus may exist in a particular cell. Every virus belongs to one of the virus types numbered 1 through $K$ .

Every virus in the test tube multiplies each second in the up, down, left, and right directions. Each second, viruses of lower-numbered types multiply before those of higher-numbered types. Also, during the multiplication process, if a virus already exists in a particular cell, no other virus can enter that cell.

Given the size of the test tube and the positions of the viruses, write a program that prints the type of the virus that exists at $(X, Y)$ after $S$ seconds. If no virus exists at that position after $S$ seconds, print 0. Here $X$ and $Y$ denote the row and column positions, respectively, and the top-left cell of the test tube is $(1, 1)$ .

For example, suppose there is a test tube of size $3 \times 3$ as follows. Distinct viruses 1, 2, and 3 are located at $(1, 1)$ , $(1, 3)$ , and $(3, 1)$ , respectively. Let us compute the type of the virus that exists at $(3, 2)$ after 2 seconds.

After 1 second, the state of the test tube is as follows.

After 2 seconds, the state of the test tube is as follows.

As a result, the type of the virus that exists at $(3, 2)$ after 2 seconds is virus 3. Therefore, printing 3 is the correct answer.

Input

The first line gives the natural numbers $N$ and $K$ , separated by a space. ( $1 \le N \le 200$ , $1 \le K \le 1{,}000$ ) From the second line, $N$ lines give the information of the test tube. Each row consists of $N$ elements, and the number of the virus existing at that position is given separated by spaces. If no virus exists at that position, 0 is given. Also, every virus number is given as a natural number no greater than $K$ . The $(N+2)$ -th line gives $S$ , $X$ , and $Y$ , separated by spaces. ( $0 \le S \le 10{,}000$ , $1 \le X, Y \le N$ )

Output

Print the type of the virus that exists at $(X, Y)$ after $S$ seconds. If no virus exists at that position after $S$ seconds, print 0.

Examples2

Example 1
Input
```
3 3
1 0 2
0 0 0
3 0 0
2 3 2
```
Expected output
```
3
```
Example 2
Input
```
3 3
1 0 2
0 0 0
3 0 0
1 2 2
```
Expected output
```
0
```