492. Maze Search

0

Medium

Om is trapped in a maze and needs to find a way out. He has been 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 (maze) and a target value, you need to determine whether 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 should contain three integers: n, m, and the target value, representing the number of rows, number of columns, and the target value respectively. The following n lines should each contain m space-separated integers, representing the maze array.

Output Format

Print 0 if the target value is not present in the maze. Print 1 if the target value 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 (n) in the maze is equal to the length of the maze array. The number of columns (m) in the maze is equal to the length of each row in the maze array. The values of n and m must be between 1 and 300 (inclusive). The values in the maze array (matrix) must be between -10^9 and 10^9 (inclusive). The integers in each row of the maze array are sorted in ascending order. The integers in each column of the maze array are sorted in ascending order. The target value must be between -10^9 and 10^9 (inclusive).