import random as r
import bisect as b

def search_binary_diagonal(matrix, K):
    """
    Поиск числа K в матрице N x M
    """
    if not matrix or not matrix[0]:
        return False, 0
    
    N = len(matrix)
    M = len(matrix[0])
    steps = 0
    
    left, right = 0, min(N, M) - 1
    diag_indx = -1
    
    while left <= right:
        steps += 1
        mid = (left + right) // 2
        
        if matrix[mid][mid] == K:
            return True, steps
        elif matrix[mid][mid] < K:
            diag_indx = mid
            left = mid + 1
        else:
            right = mid - 1
    
    if diag_indx >= 0 and diag_indx < N:
        steps += 1
        row = matrix[diag_indx]
        pos = b.bisect_left(row, K)
        if pos < M and row[pos] == K:
            return True, steps
    
    if diag_indx >= 0 and diag_indx < M:
        steps += 1
        col_values = [matrix[i][diag_indx] for i in range(N)]
        pos = b.bisect_left(col_values, K)
        if pos < N and col_values[pos] == K:
            return True, steps
    
    if diag_indx + 1 < N:
        steps += 1
        row = matrix[diag_indx + 1]
        pos = b.bisect_left(row, K)
        if pos < M and row[pos] == K:
            return True, steps
    
    if diag_indx + 1 < M:
        steps += 1
        col_values = [matrix[i][diag_indx + 1] for i in range(N)]
        pos = b.bisect_left(col_values, K)
        if pos < N and col_values[pos] == K:
            return True, steps
    
    return False, steps


def generate_matrix(N, M):
    """
    Генерирует матрицу N x M со случайными числами
    """
    matrix = [[0] * M for g in range(N)]
    current = 1
    
    for i in range(N):
        for j in range(M):
            if i == 0 and j == 0:
                matrix[i][j] = current
                current += r.randint(1, 8)
            else:
                matrix[i][j] = current
                current += r.randint(1, 8)
    
    return matrix

def print_matrix(matrix):
    """Вывод матрицы"""
    for row in matrix:
        print("\t".join(map(str, row)))


def main():
    N = int(input("Введите количество строк N: "))
    M = int(input("Введите количество столбцов M: "))
    
    matrix = generate_matrix(N, M)
    
    print("\nСгенерированная матрица:")
    print_matrix(matrix)
    
    all_numbers = []
    for row in matrix:
        all_numbers.extend(row)
    
    unique_numbers = set(all_numbers)
    K = int(input("\nВведите число для поиска: "))
    
    found, steps = search_binary_diagonal(matrix, K)
    
    if found:
        print(f"\nЧисло {K} найдено \nКоличество шагов: {steps}")
    else:
        print(f"\nЧисло {K} не найдено \nКоличество шагов: {steps}")


if __name__ == "__main__":
    main()