题目内容

给出正整数 $L$，以及 $p$ 种可用的前缀轮转：第 $i$ 种会把串开头连续 $a_i$ 个符号挪到尾巴。每种轮转都能用任意多次（同一种 $a_i$ 允许反复用）。

对目标偏移 $d$（$0\le d<L$），约定目标串等于把原串循环左移 $d$ 位（开头 $d$ 个符号被挪到尾巴）。现有 $q$ 次询问：每次给出偏移 $d_i$，求用上述前缀轮转把串变到该偏移最少要几次；变不到则输出 $-1$。

【名词解释】

• 前缀轮转：前缀轮转 指把串 $w$ 开头连续 $a$ 个符号挪到尾巴，例如把 "$pqrst$" 开头 $2$ 个符号轮过去会变成“$rstpq$”。

输入描述

开头那行写入三个整型值

$L,p,q$（$1\le L\le 5\times 10^4$；$1\le p\le 100$；$1\le q\le 10^5$），依次为串长、可用轮转种数、询问次数；

第二行 $p$ 个整数 $a_1,a_2,\ldots,a_p$（$1\le a_i\le L$），即各前缀轮转的长度；

第三行 $q$ 个整数 $d_1,d_2,\ldots,d_q$（$0\le d_i<L$），即各次询问的目标偏移。

输出描述

对每次询问 $d_i$，按读入顺序单独一行打印一个整数：把 $w$ 循环左移 $d_i$ 位（开头 $d_i$ 个符号挪到尾巴）所需的最少前缀轮转次数；达不到则打印 $-1$。

样例1

输入

7 2 4
2 5
0 2 4 1

输出

0
1
2
3

说明

本组数据含义如下：

• 偏移 $0$ ：不用动手；

• 偏移 $2$ ：使用 $a_1=2$ 一次；

• 偏移 $4$ ：连续使用 $a_1=2$ 两次；

• 偏移 $1$ ：使用 $a_2=5$ 三次，$5+5+5\equiv 1\pmod 7$，共 $3$ 次。

样例2

输入

8 2 4
4 8
0 4 2 6

输出

0
1
-1
-1

说明

本组数据里，仅 $0$、$4$ 两个偏移能走到。