Một con đường thẳng được xem như trục số. Có \(N\) công trình sửa đường. Công trình thứ \(i\) chặn vị trí \(X_i\) từ thời điểm \(S_i-0.5\) tới thời điểm \(T_i-0.5\).

Có \(Q\) người xuất phát từ vị trí \(0\). Người thứ \(j\) bắt đầu đi vào thời điểm \(D_j\), đi theo chiều dương với tốc độ \(1\). Khi tới một vị trí đang bị chặn, người đó dừng lại. Với mỗi người, hãy tìm quãng đường đã đi; nếu người đó không bao giờ gặp vị trí bị chặn, trả về \(-1\).

Dữ liệu vào

• Dòng đầu chứa \(N,Q\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(S_i,T_i,X_i\).
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(D_j\).

Dữ liệu ra

In \(Q\) dòng, dòng thứ \(j\) là kết quả của người thứ \(j\).

Ràng buộc

• \(1\le N,Q\le2\cdot10^5\).
• \(0\le S_i<T_i\le10^9\).
• \(1\le X_i\le10^9\).
• \(0\le D_1<D_2<\cdots<D_Q\le10^9\).
• Nếu \(i\ne j\) và \(X_i=X_j\), hai khoảng \([S_i,T_i)\) và \([S_j,T_j)\) không giao nhau.
• Mọi giá trị đầu vào đều là số nguyên.

Ví dụ

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

2
2
10
-1
13
-1

Nguồn

AtCoder Beginner Contest 128 — E: Roadwork.