these exist). Further let $Z_2$ be a set that contains a witness for each position in $Z_1$ and each existential constraint, and let $Z {\ensuremath{\mathrel{\smash{\stackrel{\scriptscriptstyle{
    \text{def}}}{=}}}} \;}Z_1 \cup Z_2$. Observe that $Z_1$ and $Z_2$ are of size polynomial in $|\Sigma| |\Gamma|$.

We reassign some of the binary $T$-types of ${\ensuremath{\mathfrak{A}}}$ in order to obtain ${\ensuremath{\mathfrak{A}}}'$. The goal is that every element $a$ in ${\ensuremath{\mathfrak{A}}}'$ has a set $W'(a)$ of witnesses for $C_\exists$ such that (1) $W(a)$ and $W'(a)$ coincide with respect to local witnesses, and (2) all non-local witnesses in $W'(a)$ are from $Z$. To this end let $\sigma, \tau \in \Sigma$ and $d {\ensuremath{\mathrel{\smash{\stackrel{\scriptscriptstyle{
    \text{def}}}{=}}}} \;}x < y \wedge \neg {\ensuremath{{S}}}(x,y)$. Denote $\bar d {\ensuremath{\mathrel{\smash{\stackrel{\scriptscriptstyle{
    \text{def}}}{=}}}} \;}y < x \wedge \neg {\ensuremath{{S}}}(y,x)$.

If there is a $(\sigma, \tau, k)$-rich position $u$ in ${\ensuremath{\mathfrak{A}}}$ then we reassign the binary types of all $\sigma$- and $\tau$-positions $a$ and $b$ satisfying $d$ by using a technique employed by Otto for constructing small models for satisfiable ${\ensuremath{\mathrm{FO}^2}\xspace}(<)$-sentences [@Otto01]. For completeness we recall the construction. Let $A = A_1 \cup A_2 \cup A_3$ with disjoint $A_i$ and $|A_i| = |\Gamma|$ contain the first $k$ $\sigma$-labeled elements. Similarly let $B = B_1 \cup B_2 \cup 