Shortly after solving their previous dilemma, the Plutonian government has asked for your help once again. There is a special vault in the heart of the Plutonian capitol, and the government needs to unlock it (don't ask why), but the process of doing so is quite complex so they've requested your help.

The vault has a lock consisting of $$$n$$$ switches, numbered $$$1...n$$$, where $$$n$$$ is odd. The initial state of the lock is given as a bitstring of length $$$n$$$, where the $$$i$$$-th character represents the state of the switch $$$i$$$, and a '1' denotes that the switch is up while a '0' denotes that it is down. To unlock the safe, all of the switches need to be down. You want to unlock the lock, but you can only perform the following two operations on the lock:

• Flip two adjacent switches. In other words, choose some $$$i$$$ such that $$$1 \leq i \leq n - 1$$$ and flip the value of switch $$$i$$$ and $$$i + 1$$$ simulatneously.
• Flip all switches simultaneously.

The Plutonian government is short on time, so they want you to determine the minimum number of operations necessary to set all switches to the down ('0') state.

Of course it isn't that simple though. After all, the government is short on time because every minute for $$$q$$$ minutes the state of the lock changes. During the $$$i$$$th update, all switches $$$j$$$ such that $$$l_i \leq j \leq r_i$$$ are flipped. Note that the updates persist. Please help the Plutonians and output the minimum number of operations to set all switches to the down state after each update.