#include <vector>
#include <iostream>

using namespace std;
class Solution
{
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target)
    {
        // vector<int> flat_mat(matrix.size()*matrix[0].size());
        // cout<<matrix.back();
        if (matrix.back().back() < target)
        {
            cout << "Not possible";
            return false;
        }
        int left_prt = 0;
        int right_prt = matrix.size() * matrix[0].size();
        int mat_row_num = matrix[0].size();
        while (left_prt <= right_prt)
        {
            int mid = (left_prt + right_prt) / 2;
            if (matrix[mid/ mat_row_num][mid % mat_row_num] == target)
                return true;
            else if (matrix[mid / mat_row_num][mid % mat_row_num] > target)
                right_prt = mid-1;
            else if (matrix[mid / mat_row_num][mid % mat_row_num] < target)
                left_prt = mid+1;

        }
        return false;
    }
};

int main()
{
    Solution s;
    int test_data[16] = {1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60, 62, 66, 72, 192};

    vector<vector<int> > test_mat(3, vector<int>(4));
    for (int i = 0; i < 12; i++)
    {
        test_mat[i / test_mat[0].size()][i % test_mat[0].size()] = test_data[i];
    }
    // for (int i = 0; i < 4; i++)
    // {
    //     for (int j = 0; j < 4; j++)
    //     {
    //         cout << test_mat[i][j] << ' ';
    //     }
    // }
    cout << s.searchMatrix(test_mat, 3);
}