题目描述

给你一个满足下述两条属性的 m x n 整数矩阵:

(1)每行中的整数从左到右按非严格递增顺序排列。

(2)每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,输出1 ;否则,输出0。

mat.jpg



输入格式

第1行输入矩阵的行数m、列数n、待查找值target

第2~m+1行输入每一行的n个整数值。


输出格式

如果 target 在矩阵中,输出1 ;否则,返回 0 。


样例输入

3 4 3
1 3 5 7
10 11 16 20
23 30 34 60

样例输出

1

提示

无