2.  Perform the marking stage on the suffix of $x$ of length $n-i$.

3.  Perform the marking stage on the resulting, partially marked, string.

Since $x$ and $x+e_i$ agree on all but the $i^{\text{th}}$ coordinate, the running of the marking stage in steps 1 and 2 yield the same marking. That is, prior to the third step, the strings $x$ and $x+e_i$ have the same bits marked. Denote by $s \in {\{0,1,\hat{0}, \hat{1}\}^{i-1}}$ and $t \in {\{0,1,\hat{0}, \hat{1}\}^{n-i}}$ the two partially marked strings such that the resulted strings after the second step on inputs $x$ and $x+e_i$ are $s \circ 0 \circ t$ and $s \circ 1 \circ t$ respectively. Let us suppose for concreteness that the string $s$ contains $a$ unmarked zeros and $b$ unmarked ones, and the string $t$ contains $c$ unmarked zeros and $d$ unmarked ones. Recall that at the end of the marking stage, all unmarked zeros are to the left of all unmarked ones in both $s$ and $t$.

By Claim \[claim:mark to infl\], the only coordinates that may contribute to ${{\sf distance}}({\psi}(x),{\psi}(x+e_i))$ are the unmarked coordinates prior to the third step, and so $${{\sf distance}}({\psi}(x),{\psi}(x+e_i)) = {{\sf distance}}({\psi}(0^a 1^b \circ 0 \circ 0^c 1^d),{\psi}(0^a 