Breadboard Capacity (hard version)

This is a harder version of the problem H with modification queries.

Lester and Delbert work at an electronics company. They are currently working on a microchip component serving to connect two independent parts of a large supercomputer.

The component is built on top of a breadboard — a grid-like base for a microchip. The breadboard has $$$n$$$ rows and $$$m$$$ columns, and each row-column intersection contains a node. Also, on each side of the breadboard there are ports that can be attached to adjacent nodes. Left and right side have $$$n$$$ ports each, and top and bottom side have $$$m$$$ ports each. Each of the ports is connected on the outside to one of the parts bridged by the breadboard, and is colored red or blue respectively.

Ports can be connected by wires going inside the breadboard. However, there are a few rules to follow:

• Each wire should connect a red port with a blue port, and each port should be connected to at most one wire.
• Each part of the wire should be horizontal or vertical, and turns are only possible at one of the nodes.
• To avoid interference, wires can not have common parts of non-zero length (but may have common nodes). Also, a wire can not cover the same segment of non-zero length twice.

The capacity of the breadboard is the largest number of red-blue wire connections that can be made subject to the rules above. For example, the breadboard above has capacity $$$7$$$, and one way to make seven connections is pictured below.

Up to this point statements of both versions are identical. Differences follow below.

As is common, specifications of the project change a lot during development, so coloring of the ports is not yet fixed. There are $$$q$$$ modifications to process, each of them has the form of "colors of all ports in a contiguous range along one of the sides are switched (red become blue, and blue become red)". All modifications are persistent, that is, the previous modifications are not undone before the next one is made.

To estimate how bad the changes are, Lester and Delbert need to find the breadboard capacity after each change. Help them do this efficiently.