Low Budget Sanitization

**This is an Interactive Problem.** Chef found a dirty-looking square plate in his kitchen. Obviously, it is full of germs. Specifically, there are $N$ germs lying in the whole plate. The plate has dimensions $M\times M$ and can be imagined as a 2-dimensional square space bounded by the lines $X=0$, $Y=0$, $X=M$ and $Y=M$. Chef knows that each germ lies at a point with integer coordinates withi