783. Matrix Search

0

Medium

Given a matrix with n rows and m columns, where each row and column is sorted in ascending order, and a target number x, determine if x is present in the matrix.

Input Format

The first line consists of two space-separated integers N and M, representing the number of elements in a row and column, respectively. The second line of each test case consists of N*M space-separated integers representing the elements in the matrix in row-major order. The third line of each test case contains a single integer x, which is the element to be searched.

Output Format

Print 1 if the element is present in the matrix; otherwise, print 0.

Example

Input

3 3
3 30 38
44 52 54
57 60 69
62

Output

0

Constraints

1 <= N,M <= 30
0 <= A[i] <= 100

Loading...

View Submissions

Console