PopcountRobot

In this problem, popcount(n) denotes the number of ones in the binary representation of n. For example, popcount(2015) = 10 because 2015 is 11111011111 in binary.

The horizontal plane is divided into an infinite grid of unit square cells. All cells are currently white. Cat Snuke has just bought a strange robot and placed it onto the grid. The current coordinates of the robot are (0, 0). The robot is going to paint some of the cells black.

You are given a long T. For each t from 0 to T-1, inclusive, the robot will execute the following sequence of steps:

1. The robot paints the current cell black. (If the cell is already black, the robot does nothing.)
2. If popcount(t) mod 4 = 0, the robot increases its x-coordinate by 1.
3. If popcount(t) mod 4 = 1, the robot increases its y-coordinate by 1.
4. If popcount(t) mod 4 = 2, the robot decreases its x-coordinate by 1.
5. If popcount(t) mod 4 = 3, the robot decreases its y-coordinate by 1.

You are also given four ints: Q, M, x, and y. Compute ans in the following pseudocode:

ans = 0;
for(i = 0; i < Q; i++){
	if(the cell (x,y) is black after the robot stops working) ans++;
	x = ((x + M) * 7180087 + 5205425) % (2 * M + 1) - M;
	y = ((y + M) * 6132773 + 9326231) % (2 * M + 1) - M;
}
return ans;