Bài tập

Alice sưu tầm và lưu lại một danh sách các số nguyên dương mà mình yêu thích, gọi là các số nguyên dương đẹp.

Hiện tại, Alice đang có một danh sách \(A\) gồm \(N\) số nguyên dương đẹp
\(A_1, A_2, \dots, A_N\),
trong đó các phần tử đôi một khác nhau và được sắp xếp theo thứ tự tăng dần
\(A_1 < A_2 < \dots < A_N\).

Các số nguyên dương không xuất hiện trong danh sách \(A\) được gọi là các phần tử thiếu.

Alice cần trả lời \(Q\) truy vấn độc lập.
Mỗi truy vấn cho một số nguyên dương \(k\), yêu cầu xác định phần tử thiếu thứ \(k\) khi liệt kê các phần tử thiếu theo thứ tự tăng dần.

\InputFile

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\)
  \((1 \le N, Q \le 10^5)\).
• Dòng thứ hai chứa \(N\) số nguyên dương
  \(A_1, A_2, \dots, A_N\)
  \((1 \le A_i \le 10^{18})\), dữ liệu đảm bảo dãy được sắp xếp tăng nghiêm ngặt.
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k_i\)
  \((1 \le k_i \le 10^{18})\).

\OutputFile

Gồm \(Q\) dòng, dòng thứ \(i\) in ra một số nguyên --- giá trị của phần tử thiếu thứ \(k_i\).

\Scoring

• \(40\%\) số test: \(N, Q \le 2 \cdot 10^3\).
• \(30\%\) số test: \(A_i \le 10^6\).
• \(30\%\) số test còn lại: không có ràng buộc gì thêm.

Example

5 3
1 3 9 12 17
2
9
19

4
13
24

Tập đoàn DEPTRAI là một công ty nhỏ sở hữu một chiếc máy bay. Khách hàng của công ty là các công ty hàng không thuê máy bay để đáp ứng tình trạng quá tải thường xuyên.

 Khách hàng gửi đơn đặt hàng thuê bao gồm một khoảng thời gian và giá mà khách hàng sẵn sàng trả cho việc thuê máy bay trong khoảng thời gian nhất định. Đơn đặt hàng của tất cả các khách hàng được biết trước. Tất nhiên, không phải tất cả các đơn đặt hàng đều có thể được cung cấp và một số đơn đặt hàng phải bị từ chối. Huy là giám đốc của công ty muốn tối đa hóa lợi nhuận của công ty. Bạn được Huy yêu cầu tính toán một giải pháp tối ưu nhất khi cho thuê các máy bay của công ty.

 Ví dụ: xem xét trường hợp công ty có $4$ đơn đặt hàng:


      + Đơn hàng $1$ (thời gian bắt đầu $1$, thời gian $5$, giá $10$)


      + Đơn hàng $2$ (thời gian bắt đầu $3$, thời gian $7$, giá $8$)


      + Đơn hàng $3$ (thời gian bắt đầu $5$, thời gian $9$, giá $9$)


      + Đơn hàng $4$ (thời gian bắt đầu $6$, thời gian $9$, giá $8$)

 Giải pháp tối ưu bao gồm cho thuê đơn hàng $1$ và $4$ và mức doanh thu là $10 + 8 = 18$. Trong ví dụ này nếu chọn đơn hàng $1$ thì không thể chọn đơn hàng $3$ vì bị trùng thời gian.

Input

• Dòng đầu tiên của đầu vào chứa số \(T ≤ 10\) cho biết số lượng trường hợp kiểm tra.

• Dòng đầu tiên của mỗi trường hợp thử nghiệm chứa số lượng đơn hàng \(n (n ≤ 5000)\).

• Trong n dòng sau đây các đơn đặt hàng được đưa ra. Mỗi đơn hàng được mô tả bởi \(3\) giá trị nguyên: Thời gian bắt đầu của đơn hàng \(st (0 ≤ st ≤ 10^9)\), thời lượng \(d\) của đơn hàng \((0 ≤ d ≤ 10^9)\) và tiền thuê \(p\) \((0 ≤ p ≤ 10^9)\).

Output

• Bạn được yêu cầu tính toán một giải pháp tối ưu. Đối với mỗi trường hợp thử nghiệm, chương trình của bạn phải ghi tổng tiền lớn nhất mà công ty thu được.

Example

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

18
15

Đất nước "vui vẻ" có \(n\) thành phố được đánh số từ \(1\) đến \(n\), và \(n − 1\) con đường hai chiều nối một số cắp thành phố. Giữa hai thành phố bất kỳ luôn có đường đi trực tiếp hoặc đường đi gián tiếp qua một số thành phố trung gian.

Có \(k\) thành phố nổi tiếng mà khách du lịch luôn muốn đến thăm. Khách du lịch sẽ bắt đầu từ một thành phố nào đó trong \(n\) thành phố, đi theo các con đường nối giữa các thành phố để thăm đủ k thành phố nổi tiếng (mỗi con đường/thành phố có thể đi qua nhiều lần). Đất nước khá là vui vẻ trừ giá taxi ở đây, nên khách du lịch muốn chọn
lộ trình có tổng độ dài phải đi là nhỏ nhất. Nhưng bạn biết đấy, sẽ thật phiền phức khi vừa đi du lịch vừa phải code, họ sẽ rất vui vẻ nếu nhận được sự giúp đỡ của bạn

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\)

• \(n − 1\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên dương \(u, v, L\); cho biết có một con đường độ dài \(L\) nối giữa hai thành phố \(u, v\)

• Dòng tiếp theo chứa \(k\) số nguyên dương là số hiệu của \(k\) thành phố nổi tiếng

Output

Gồm n dòng, dòng thứ \(i\) là tổng độ dài phải đi của lộ trình tốt nhất nếu khách du lịch bắt đầu từ thành phố \(i\)

Example

13 5
1 2 1
2 3 1
3 4 1
2 5 1
1 7 1
6 7 1
7 10 1
1 8 1
8 9 1
8 11 1
8 12 1
12 13 1
2 4 7 9 13

13
12
11
10
13
13
12
12
11
13
13
11
10

Scoring

• \(1 ≤ k ≤ n ≤ 10^5\)

• \(1 ≤ L ≤ 10^9\)

• Có \(50\%\) số test với \(n ≤ 1000\).