 Previously such a separation was known only for k = 2. We stress that for k= 2 , there are only finitely many distinct problems to consider.
<meaning-changed>  Previously such a separation was known only for k = 2. We stress that for k= 2 , there are only finitely many distinct problems to consider.
 We also extend previously known results in the insertion-only setting to a wide variety of cases, and in particular the case of k = 2. We stress that for k= 2 , there are only finitely many distinct problems to consider.