题目描述

给定两个长度为n的单调不降序列，询问q次，每次询问给定1≤k≤2n，请你求 出这两个序列一共2n个元素中，第k小的元素

输入格式

从文件search.in 中读入数据。 第一行两个整数n,q。 第二行n个整数$a^{'}_ 1,...,_n$，第一个序列的第 i 个元素为 $\ sum_{j=1}^i a_j^{'}$ 第三行n个整数$b^{'}_ 1,...,_n$，第二个序列的第 i 个元素为 $\ sum_{j=1}^i b_j^{'}$ 接下来q行，每行一个整数表示k。

输出格式

输出到文件search.out 中。 输出q行，第i行输出一个整数表示第i个询问的答案

Samples

见选手目录下的search/search1.in 与 search/search1.out。 更多样例见下发文件

数据范围

本题的 为70MB。 对于30%的数据，n,q≤2000。 对于50%的数据，n≤3.75×106。 对于另30%的数据，q≤3×105。 对于100% 的数据，1≤n≤7.5×106,1 ≤ q ≤106，序列里的元素绝对值都小于等 于109，∀2 ≤i≤n,a′ i,b′ i ≥ 0。 本题输入输出量较大，请使用效率较高的输入输出方式。