题目描述

有一个长度为 $n$ 的整数数列 $f$，现在可以进行无限次操作，每次操作的要求如下：

选择一个长度不大于 $k$ 的区间 $[l,r]$，将这个区间中的每一个数减去 $m$。在减去 $m$ 后的数列中，记：

• $a=\max\begin{Bmatrix}f_l,f_{l+1},\cdots,f_r\end{Bmatrix}$；

• $b=\min\begin{Bmatrix}f_l,f_{l+1},\cdots,f_r\end{Bmatrix}$；

这时候将区间 $[l,r]$ 内的每一个数都加上 $|a| \oplus |b|$，其中 $\oplus$ 为按位异或（xor，即 C/C++ 的 ˆ 或 Pascal 的 xor，如果您不知道什么是异或您可以查看这里）。请你求出最少进行多少次操作后，这个数列中最小的数小于等于 $s$。如果无论怎样操作也没有办法使这个数列中的最小的数小于等于 $s$，请输出 Impossible!。

输入格式

输入包含多组测试数据。

第一行一个整数 $T$，表示数据组数。

接下来有 $2 \times T$ 行，对于第 $i$ 组数据：第 $2 \times i$ 行四个整数 $n,m,k,s$。第 $2 \times i+1$ 行有 $n$ 个整数 $f_i(1 \leq i \leq n)$，表示这个数列。

输出格式

共 $T$ 行，对于每组数据，如果可以达到目标请输出最少需要的操作次数，否则输出 Impossible!。

输入输出样例

3
4 4 4 9
6 7 6 7
4 2 3 7
8 9 8 9
4 0 2 5
7 8 7 8

0
1
Impossible!

说明/提示

子任务测试采用捆绑方式计分。

样例解释

对于输入 #1 中的第一组数据，

• 由于 $6 \leq s$，故不需要进行任何一次操作，输出 0。

对于输入 #1 中的第二组数据，

• 可以选择区间 $[1, 3]$。注意，选择区间 $[1, 4]$ 是不合法的，因为区间长度 $4 > k$。
• 先将区间中的每一个数减去 $m$，$[8, 9, 8, 9] \to [6, 7, 6, 9]$。
• 计算得此时 $a = 7, b = 6,7 \oplus 6 = 1$。
• 这时候将区间内的每一个数都加上 $1$，$[6, 7, 6, 9] \to [7, 8, 7, 9]$。
• 由于 $7 \leq s$，故只需要进行一次操作，输出 1。

对于输入 #1 中的第三组数据，

• 无论进行多少次操作，都无法使最小值小于等于 $s$，故输出 Impossible!。

数据范围

• $\texttt{Subtask 1(5 pts)}$：即样例。
• $\texttt{Subtask 2(10 pts)}$：$m=0$。
• $\texttt{Subtask 3(25 pts)}$：$1 \leq n \leq 100$。
• $\texttt{Subtask 4(60 pts)}$：无特殊限制。

对于 $100\%$ 的数据，$1 \leq T \leq 10^3,1 \leq k \leq n \leq 10^3,0 \leq m \leq 10^6,-10^6 \leq f_i,s \leq 10^6$。