You are given a matrix arr of m x n size. Write a program to searches for a value k in arr. This arr has the following properties:

• Integers in each row are sorted from left to right.
• The first value of each row is greater than the last value of previous row.

If the value is found, then return 1 otherwise return 0.

Example 1

Input:
arr[][] = [
          [23, 25, 35, 37],
          [40, 41, 42, 43],
          [50, 60, 74, 80]
        ]
k = 41
Output: 1
Explanation: The value 41 is present in the array arr. So, 1 is returned.

Example 2

Input:
arr[][] = [
          [23, 25, 35, 37],
          [40, 41, 42, 43],
          [50, 60, 74, 80]
        ]
k = 100
Output: 0
Explanation: The value 100 is not present in the array arr. So, 0 is returned.