题目描述

恩奎准备发布手机游戏“银河在线”，并希望通过广告和线下活动吸引新用户。

共有 $N$ 个目标国家，每个国家都有 $M$ 座城市。国家编号为 $1$ 到 $N$，每个国家中的城市编号为 $1$ 到 $M$。

如果在国家 $i$ 的城市 $j$ 投放广告，预计可以吸引

名新用户。

为了避免过度投放广告，恩奎决定：

1. 在每个国家中恰好选择一座城市投放广告，因此一共选择 $N$ 座城市；

2. 在这 $N$ 座被选中的城市中，再选择至多一座举办线下活动；

3. 线下活动可以额外吸引任意整数 $t$ 名用户，其中

   $$0\le t\le C.$$

   也可以令 $t=0$，即不通过活动吸引额外用户。

广告和活动吸引的用户总数必须不少于目标值 $P$。

恩奎希望各个国家吸引的用户数尽量均衡。定义一个营销方案的不均衡度为：各国最终吸引用户数的最大值与最小值之差。

对于每个目标值 $P$，需要在所有可行营销方案中求最小不均衡度。

现在给出 $Q$ 个目标值

请分别回答。

输入格式

第一行包含三个整数 $N,M,C$。

接下来 $N$ 行，第 $i$ 行包含 $M$ 个整数

下一行包含一个整数 $Q$。

接下来 $Q$ 行，第 $k$ 行包含一个整数 $p_k$，表示第 $k$ 个目标值。

输出格式

输出 $Q$ 行。

第 $k$ 行输出达到目标 $p_k$ 时能够得到的最小不均衡度。

如果不存在任何方案能使总用户数达到 $p_k$，输出 -1。

数据范围

样例

输入

3 3 15
2 1 3
1 9 8
6 5 4
2
30
40

输出

9
-1

说明

对于目标值 $p_1=30$，可以在三个国家中分别选择广告预计吸引 $3,9,6$ 名用户的城市。

在预计吸引 $3$ 名用户的城市举办线下活动，再额外吸引 $12$ 名用户。三个国家最终吸引的用户数为

总数为 $30$，满足目标要求；不均衡度为