Crafty Coloring (Hard)

**This is the hard version of the problem. The only difference between this version and the easy version is that here, $N$ and $M$ can be as large as $10^9$.** Alice and Bob want to play a game on a grid with $N$ rows and $M$ columns. The cell at the intersection of the $i$-th row and $j$-th column is denoted $(i, j)$. Initially, all cells of the grid are colored white. On a player's turn, t