The required polynomials are all polynomials of an even degree $d \geq 2$, and all polynomials of odd degree $d \geq 3$ with a negative leading coefficient.

Part I. We begin by showing that any (non-constant) polynomial $S(x)$ not listed above is not $(A, B)$-nice for some pair $(A, B)$ with either $|A|=|B|=2$, or $|A|=|B|=3$.

If $S(x)$ is linear, then so are all the polynomials appearing on the board. Therefore, none of them will be $(A, B)$-nice, say, for $A=\{1,2,3\}$ and $B=\{1,2,4\}$, as desired.

Otherwise, $\operatorname{deg} S=d \geq 3$ is odd, and the leading coefficient is positive. In this case, we make use of the following technical fact, whose proof is presented at the end of the solution.

Claim. There exists a positive constant $T$ such that $S(x)$ satisfies the following condition:

$$S(b)-S(a) \geq b-a \quad \text { whenever } \quad b-a \geq T$$

Fix a constant $T$ provided by the Claim. Then, an immediate check shows that all newly appearing polynomials on the board also satisfy $(*)$ (with the same value of $T$ ). Therefore, none of them will be $(A, B)$-nice, say, for $A=\{0, T\}$ and $B=\{0, T / 2\}$, as desired.

Part II. We show that the polynomials listed in the Answer satisfy the requirements. We will show that for any $a_{1}\max _{x \in \Delta} S(x)$. Therefore, for any $x, y, z$ with $x \leq \alpha \leq y \leq \beta \leq z$ we get $S(x) \leq S(\alpha) \leq$ $S(y) \leq S(\beta) \leq S(z)$.

We may decrease $\alpha$ and increase $\beta$ (preserving the condition above) so that, in addition, $S^{\prime}(x)>3$ for all $x \notin[\alpha, \beta]$. Now we claim that the number $T=3(\beta-\alpha)$ fits the bill.

Indeed, take any $a$ and $b$ with $b-a \geq T$. Even if the segment $[a, b]$ crosses $[\alpha, \beta]$, there still is a segment $\left[a^{\prime}, b^{\prime}\right] \subseteq[a, b] \backslash(\alpha, \beta)$ of length $b^{\prime}-a^{\prime} \geq(b-a) / 3$. Then

$$S(b)-S(a) \geq S\left(b^{\prime}\right)-S\left(a^{\prime}\right)=\left(b^{\prime}-a^{\prime}\right) \cdot S^{\prime}(\xi) \geq 3\left(b^{\prime}-a^{\prime}\right) \geq b-a$$

for some $\xi \in\left(a^{\prime}, b^{\prime}\right)$.
Proof of Lemma 1. If $S(x)$ has an even degree, then the polynomial $T(x)=S\left(x+a_{2}\right)-S\left(x+a_{1}\right)$ has an odd degree, hence there exists $x_{0}$ with $T\left(x_{0}\right)=S\left(x_{0}+a_{2}\right)-S\left(x_{0}+a_{1}\right)=b_{2}-b_{1}$. Setting $G(x)=S\left(x+x_{0}\right)$, we see that $G\left(a_{2}\right)-G\left(a_{1}\right)=b_{2}-b_{1}$, so a suitable shift $F(x)=G(x)+\left(b_{1}-G\left(a_{1}\right)\right)$ fits the bill.

Assume now that $S(x)$ has odd degree and a negative leading coefficient. Notice that the polynomial $S^{2}(x):=S(S(x))$ has an odd degree and a positive leading coefficient. So, the polynomial $S^{2}\left(x+a_{2}\right)-S^{2}\left(x+a_{1}\right)$ attains all sufficiently large positive values, while $S\left(x+a_{2}\right)-$ $S\left(x+a_{1}\right)$ attains all sufficiently large negative values. Therefore, the two-variable polynomial $S^{2}\left(x+a_{2}\right)-S^{2}\left(x+a_{1}\right)+S\left(y+a_{2}\right)-S\left(y+a_{1}\right)$ attains all real values; in particular, there exist $x_{0}$ and $y_{0}$ with $S^{2}\left(x_{0}+a_{2}\right)+S\left(y_{0}+a_{2}\right)-S^{2}\left(x_{0}+a_{1}\right)-S\left(y_{0}+a_{1}\right)=b_{2}-b_{1}$. Setting $G(x)=S^{2}\left(x+x_{0}\right)+S\left(x+y_{0}\right)$, we see that $G\left(a_{2}\right)-G\left(a_{1}\right)=b_{2}-b_{1}$, so a suitable shift of $G$ fits the bill.

Proof of Lemma 2. Let $\Delta$ denote the segment $\left[a_{1} ; a_{n}\right]$. We modify the proof of Lemma 1 in order to obtain a polynomial $F$ convex (or concave) on $\Delta$ such that $F\left(a_{1}\right)=F\left(a_{2}\right)$; then $F$ is a desired polynomial. Say that a polynomial $H(x)$ is good if $H$ is convex on $\Delta$.

If $\operatorname{deg} S$ is even, and its leading coefficient is positive, then $S(x+c)$ is good for all sufficiently large negative $c$, and $S\left(a_{2}+c\right)-S\left(a_{1}+c\right)$ attains all sufficiently large negative values for such $c$. Similarly, $S(x+c)$ is good for all sufficiently large positive $c$, and $S\left(a_{2}+c\right)-S\left(a_{1}+c\right)$ attains all sufficiently large positive values for such $c$. Therefore, there exist large $c_{1}T \quad \text { whenever } \quad b-a>T
$$$$

Let us sketch an alternative approach for Part II. It suffices to construct, for each $i$, a polynomial $f_{i}(x)$ such that $f_{i}\left(a_{i}\right)=b_{i}$ and $f_{i}\left(a_{j}\right)=0, j \neq i$. The construction of such polynomials may be reduced to the construction of those for $n=3$ similarly to what happens in the proof of Lemma 2. However, this approach (as well as any in this part) needs some care in order to work properly.