310430: CF1832D1. Red-Blue Operations (Easy Version)

D1. Red-Blue Operations (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between easy and hard versions is the maximum values of $n$ and $q$.

You are given an array, consisting of $n$ integers. Initially, all elements are red.

You can apply the following operation to the array multiple times. During the $i$-th operation, you select an element of the array; then:

• if the element is red, it increases by $i$ and becomes blue;
• if the element is blue, it decreases by $i$ and becomes red.

The operations are numbered from $1$, i. e. during the first operation some element is changed by $1$ and so on.

You are asked $q$ queries of the following form:

• given an integer $k$, what can the largest minimum in the array be if you apply exactly $k$ operations to it?

Note that the operations don't affect the array between queries, all queries are asked on the initial array $a$.

Input

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 1000$) — the number of elements in the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line contains $q$ integers $k_1, k_2, \dots, k_q$ ($1 \le k_j \le 10^9$).

Output

For each query, print a single integer — the largest minimum that the array can have after you apply exactly $k$ operations to it.

ExamplesInput

4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10

Output

3 4 5 6 7 8 8 10 8 12

Input

5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10

Output

3 4 5 6 7 8 9 8 11 8

Input

2 5
2 3
10 6 8 1 3

Output

10 7 8 3 3

题目大意：
这个题目分为简单和困难两个版本，唯一的区别在于n和q的最大值。你有一个由n个整数组成的数组，初始时所有元素都是红色的。你可以多次对数组执行以下操作：在第i次操作中，你选择数组中的一个元素，然后：如果该元素是红色的，它增加i并变为蓝色；如果该元素是蓝色的，它减少i并变为红色。操作从1开始编号，即在第一次操作中某个元素变化1，依此类推。你会被问q个查询，形式如下：给定一个整数k，如果你对数组执行恰好k次操作，数组的最小值最大可以是多少？注意，操作不会在查询之间影响数组，所有查询都是基于初始数组a。

输入数据格式：
第一行包含两个整数n和q（1≤n, q≤1000）——数组中元素的数量和查询的数量。
第二行包含n个整数a1, a2, …, an（1≤ai≤10^9）。
第三行包含q个整数k1, k2, …, kq（1≤kj≤10^9）。

输出数据格式：
对于每个查询，打印一个整数——在你对数组执行恰好k次操作后，数组的最小值最大可以是多少。

示例：
输入：
4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10

输出：
3 4 5 6 7 8 8 10 8 12

输入：
5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10

输出：
3 4 5 6 7 8 9 8 11 8

输入：
2 5
2 3
10 6 8 1 3

输出：
10 7 8 3 3题目大意： 这个题目分为简单和困难两个版本，唯一的区别在于n和q的最大值。你有一个由n个整数组成的数组，初始时所有元素都是红色的。你可以多次对数组执行以下操作：在第i次操作中，你选择数组中的一个元素，然后：如果该元素是红色的，它增加i并变为蓝色；如果该元素是蓝色的，它减少i并变为红色。操作从1开始编号，即在第一次操作中某个元素变化1，依此类推。你会被问q个查询，形式如下：给定一个整数k，如果你对数组执行恰好k次操作，数组的最小值最大可以是多少？注意，操作不会在查询之间影响数组，所有查询都是基于初始数组a。 输入数据格式： 第一行包含两个整数n和q（1≤n, q≤1000）——数组中元素的数量和查询的数量。 第二行包含n个整数a1, a2, …, an（1≤ai≤10^9）。 第三行包含q个整数k1, k2, …, kq（1≤kj≤10^9）。 输出数据格式： 对于每个查询，打印一个整数——在你对数组执行恰好k次操作后，数组的最小值最大可以是多少。 示例： 输入： 4 10 5 2 8 4 1 2 3 4 5 6 7 8 9 10 输出： 3 4 5 6 7 8 8 10 8 12 输入： 5 10 5 2 8 4 4 1 2 3 4 5 6 7 8 9 10 输出： 3 4 5 6 7 8 9 8 11 8 输入： 2 5 2 3 10 6 8 1 3 输出： 10 7 8 3 3