We are given an infinite boolean array A[1.., 1..] as input. We are promised that there exist R, S 1 such that

A[i, j] = {1 if i R and j S or 0 otherwise.

1. Give a divide-and-conquer algorithm that outputs R and S in time O(log(R + S)).

2. Argue that your algorithm work correctly and that it runs in time O(log(R + S)).