Построим двумерный массив префикс сумм, в котором будем хранить количество закрашенных клеток. С его помощью мы сможем узнать количество закрашенных клеток внутри произвольного прямоугольника внутри сетки.

Для каждого отрезка выполним следующие шаги:

1. Для текущего отрезка определяем прямоугольник который он занимает.

2. Для данного прямоугольника вычисляем количество закрашенных в нем клеток. (при помощи префикс массива)

3. Посчитаем количество клеток которые пересекал бы отрезок, если бы он начинался не в середине клетки, а на пересечении клеток. Это количество равно длина прямоугольника + ширина прямоугольника — НОД(длина, ширина). Если же отрезок начинается в середине клетки, то это число может либо равно, либо больше посчитанного. (для дальнейшего сравнения можно этим пренебречь). Если это количество больше числа клеток посчитанных на 2 шаге, то значит отрезок пересекает хотя бы одну закрашенную клетку.

4. Если текущий прямоугольник состоит из одной клетки, то в данной области отрезок не пересекает закрашенные клетки.

5. Иначе делим данный прямоугольник пополам и для каждой половины повторяем со 2 шага.