#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        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];
    }
    cout << s.searchMatrix(test_mat, 3);
}