设 $L(x,r)$ 表示当前显示 $x$，可能的范围是 $[x+1,r]$ 的最少次数。同理，$R(l,x)$ 表示当前显示 $x$，可能的范围是 $[l,x-1]$ 的最少次数。转移就是 $L(x,r)=\min_{x< i\le r}\{\mathrm{dis}(x,i)+1+\max\{L(i,r),R(x+1,i)\}\}$，其中 $\mathrm{dis}(a,b)$ 表示从 $a$ 变成 $b$ 的次数。这样的复杂度是 $O(n^3)$，无法承受。

观察到答案其实非常小 (事实上不超过 $m=45$)，并且 DP 数组有单调性。我们不妨设 $\mathrm{rangeL}(c,x)$ 表示最大的 $r$ 满足 $L(x,r)\le c$，$\mathrm{rangeR}(c,x)$ 表示最小的 $l$ 满足 $R(l,x)\le c$。这样状态数就是 $O(nm)$ 了。

考虑按照 $c$ 从小到大算出所有 DP 值。注意到 $\mathrm{rangeL}(c,x)\ge y$ 当且仅当存在 $i$ 使得 $\mathrm{rangeL}(c-\mathrm{dis}(x,i)-1,i)\ge y$ 且 $\mathrm{rangeR}(c-\mathrm{dis}(x,i)-1,i)\le x+1$。对一个 $x$，我们可以枚举需要改变的位 (共 $2^5$ 种可能)，要改变的位可以匹配任意数字。然后我们在枚举 $x$ 的过程中，需要对所有 $11^5$ 个串 (每一位是数字或者通配符) 中的每一个 (记为 $w$) 维护所有满足 $\mathrm{rangeR}(c-d-1,i)\le x+1$ (其中 $d$ 是 $w$ 中的通配符个数) 且 $i$ 能匹配 $w$ 的最大的 $\mathrm{rangeL}(c-d-1,i)$。计算 $\mathrm{rangeR}$ 的方法也类似。

重复上述过程直到求出所有 DP 值。每次询问枚举第一次询问哪个数即可。