题目描述

这是一道背包模板题。有 $n$ 个物品，第 $i$ 个物品的价值是 $a_i$。

有 $m$ 次询问，每次询问给出一个整数 $x$，表示有一个大小为 $x$ 的背包。你需要选出一段非空区间，使得其中的物品在价值和不大于背包大小的前提下，价值和尽可能大，请输出价值和。

输入格式

从文件 backpack.in 中读入数据。

第一行，两个正整数 $n,m$，表示物品数量和询问次数。

第二行，$n$ 个整数 $a_i$，表示第 $i$ 个物品的价值。

接下来 $m$ 行，每行一个整数 $x$，表示询问的背包大小。

输出格式

输出到文件 backpack.out 中。

共 $m$ 行，每行一个整数，表示询问的答案。

特别地，如果不存在非空区间，其中的物品价值和不大于 $x$，则输出 No Solution 。

样例 1

输入

4 3
5 -3 -1 2
2
3
6

输出

2
3
5

样例 2

输入

见下发文件中的backpack2.in

输出

见下发文件中的backpack2.out

数据范围与提示

对于 $30\%$ 的数据，满足 $1\leqslant n\leqslant10$。

对于 $100\%$ 的数据，满足 $1\leqslant n\times m\leqslant 10^6,0\leqslant|a_i|\leqslant10^9,0\leqslant|x|\leqslant10^{18}$。