310431: CF1832D2. Red-Blue Operations (Hard Version)

D2. Red-Blue Operations (Hard 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 2 \cdot 10^5$) — 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≤2×10^5）——数组中元素的数量和查询的数量。
第二行包含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≤2×10^5）——数组中元素的数量和查询的数量。 第二行包含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 ```