#HTR001A. 操作

操作

题目描述

有一个长度为 nn 的整数数列 ff,现在可以进行无限次操作,每次操作的要求如下:

选择一个长度不大于 kk 的区间 [l,r][l,r],将这个区间中的每一个数减去 mm。在减去 mm 后的数列中,记:

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

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

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

输入格式

输入包含多组测试数据。

第一行一个整数 TT,表示数据组数。

接下来有 2×T2 \times T 行,对于第 ii 组数据:第 2×i2 \times i 行四个整数 n,m,k,sn,m,k,s。第 2×i+12 \times i+1 行有 nn 个整数 fi(1in)f_i(1 \leq i \leq n),表示这个数列。

输出格式

TT 行,对于每组数据,如果可以达到目标请输出最少需要的操作次数,否则输出 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 中的第一组数据,

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

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

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

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

  • 无论进行多少次操作,都无法使最小值小于等于 ss,故输出 Impossible!

数据范围

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

对于 100%100\% 的数据,1T103,1kn103,0m106,106fi,s1061 \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