885. Search in a Maze

0

Medium

Om is trapped in a maze and needs to find a way out. He is given a target value and needs to determine if the target is present in the maze. You are Om's best friend and must help him escape. Given a 2-D array representing the maze and an integer target, determine if the target is present in the maze. The maze has the following properties: the integers in each row are sorted in ascending order from left to right, and the integers in each column are sorted in ascending order from top to bottom.

Input Format

The first line of the input contains three integers: n, m, and target, representing the number of rows, number of columns, and the target value, respectively. The following n lines contain m space-separated integers representing the values in the maze.

Output Format

Print 0 if the target is not present in the maze. Print 1 if the target is present in the maze.

Example

Input

5 5 5 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30

Output

1

Constraints

The number of rows in the maze is equal to n. The number of columns in the maze is equal to m. The values of n and m are between 1 and 300, inclusive. The values in the maze are between -10^9 and 10^9, inclusive. The integers in each row of the maze are sorted in ascending order. The integers in each column of the maze are sorted in ascending order. The target value is between -10^9 and 10^9, inclusive.