Search in 2D Matrix

Problem statement

A records cabinet is arranged in a rectangular grid. Numbers increase within each shelf, and the first number on a shelf is larger than the last number on the shelf above. A lookup should exploit this organization instead of examining every drawer. Your task Determine whether target occurs in the matrix. Use O(log(rows * columns)) time. Important details Rows are individually sorted and the ranges of successive rows do not overlap. A target may lie between rows or outside the full range. Do not assume that its numerical value identifies a row or column directly. Worked example In rows [2, 5, 9] and [12, 18, 21], target 12 is the first drawer on the second shelf. It is present, so the result is true.

Input format

First line: rows columns target. Then rows lines, each containing columns integers.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= rows, columns <= 100; -10000 <= entries, target <= 10000; rows are nondecreasing and each new row starts above the previous row maximum.

Sample input

2 3 12
2 5 9
12 18 21

Sample output

true