Giáo sư X vừa chế tạo ra các con robot có thể leo cầu thang. Để thử nghiệm, ông cho dựng một cầu thang với ~n~ bậc. Bậc thứ ~i~ cao hơn bậc liền trước đó ~a_i~ cm. Cụ thể, coi mặt đất có độ cao là ~0~, bậc đầu tiên cao hơn mặt đất ~a_1~ cm, bậc thứ ~2~ cao hơn bậc thứ nhất ~a_2~ cm...

Ông có ~q~ con robot, chân của mỗi con lần lượt có chiều cao là ~k_1, k_2, ..., k_q~. Biết rằng, con thứ ~i~ chỉ leo được các bậc cầu thang có độ cao nhỏ hơn hoặc bằng chiều cao của chân nó.

Yêu cầu: Hãy xác định độ cao tối đa của các con robot so với mặt đất khi nó leo qua các bậc cầu thang của Giáo sư X.

Input

• Dòng đầu tiên là số ~t~ - số lượng test ~(1 \le t \le 100)~.

• Dòng đầu tiên của mỗi test chứa hai số nguyên ~n, q~ ~(1 \le n, q \le 2 \times 10^5)~ — tương ứng là số bậc cầu thang và số con robot.

• Dòng thứ hai của mỗi test chứa ~n~ số nguyên dương ~(1 \le a_i \le 10^9)~ — chiều cao của các bậc thang so với bậc liền trước đó.

• Dòng thứ ba của mỗi test chứa ~q~ số nguyên ~(0 \le k_i \le 10^9)~ — là chiều cao chân của ~q~ con robot.

• Dữ liệu đảm bảo rằng tổng của các số ~n~ trong các test không vượt quá ~2 \times 10^5~, và tổng của ~q~ không vượt quá ~2 \times 10^5~.

Output

• Ứng với mỗi test, hãy ghi ra một dòng gồm ~q~ số nguyên tương ứng với từng độ cao của con robot khi leo cầu thang.

Scoring

Sample Input 1

3
4 5
1 2 1 4
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

Sample Output 1

1 4 8 8 8 
0 2 
3000000000

Notes

Giải thích test 1:

• Con robot 1: chiều dài chân là ~1~ cm, thì nó chỉ có thể leo được bậc ~1~ (có độ cao ~1~ cm), vì vậy chiều cao cao nhất mà nó có thể đạt tới là ~1~ cm.

• Con robot 2 và 3: chiều dài chân tương ứng là ~2~ và ~4~, nó có thể leo cầu thang ~1, 2~ và ~3~, vì vậy chiều cao cao nhất mà cả hai con có thể đạt tới là ~1+2+1=4~ cm.

• Con robot 4 và 5: chiều dài chân tương ứng là ~9~ và ~10~, cả hai con đều có thể leo toàn bộ cầu thang, vì vậy chiều cao cao nhất mà hai con robot này có thể đạt tới là ~1+2+1+4=8~ cm.