Statement

Note the unusual memory limit for this problem. Inspired by Carlo's success, Alessandro has decided to start his own software company in the mountains. However, unlike Carlo, he settled in a city where the weather is highly unpredictable. Initially, the entire city is dry, but over the course of Q days, rainfall and droughts will continuously change its conditions. The city is represented as an N × M grid, with cells indexed from (1,1) to (N,M). On day i (0 < i < Q), a rectangular region of the grid undergoes a weather change. Given integers x_1, x_2, y_1, y_2, all cells (x,y) satisfying: x_1< x< x_2\qquad and\qquad y_1< y< y_2 will switch their state -- wet cells become dry, and dry cells become wet. At the end of each day, Alessandro wonders: What is the total perimeter of the wet regions? Unfortunately, he struggles to find this value. Can you help him determine the perimeter after each day's changes?