Langton's Ant

An ant lives on an endless grid of squares, each white or black. Squares are named by coordinates (x, y), where x grows to the right and y grows upward. The ant starts on square (0, 0) facing up, toward larger y. At every step:

• on a white square, the ant turns 90 degrees to the right, paints the square black and moves forward one square;
• on a black square, it turns 90 degrees to the left, paints the square white and moves forward one square.

Write black_squares(steps, black) that returns how many squares are black after the ant has taken steps steps. black is the list of squares that are black at the start (often empty); every other square starts white.

Examples

black_squares(1, [])         # returns 1
black_squares(4, [])         # returns 4
black_squares(5, [])         # returns 3
black_squares(1, [(0, 0)])   # returns 0

On an all-white grid the ant turns right four times in a row and paints a small square of 4 black squares, which brings it back to (0, 0). That square is now black, so on step 5 it turns left and paints it white again. In the last example the starting square is black, so the first step paints it white.

Constraints

• 0 <= steps <= 20,000
• black has at most 100 squares, with no repeats.

Note

• On an all-white grid the ant wanders in a chaotic blob for about 10,000 steps, then suddenly starts building a straight diagonal "highway" and keeps building it forever.