Máy Phóng

Trên một con đường thẳng (trục số), có $N$ máy phóng và $M$ truy vấn vận chuyển. Mỗi máy phóng $i$ có thể phóng hàng từ vị trí $x_i$ đến vị trí $y_i$ trong thời gian $t_i$. Mỗi truy vấn $j$ yêu cầu vận chuyển hàng từ vị trí $a_j$ đến vị trí $b_j$.

Để vận chuyển hàng từ $a_j$ đến $b_j$, có hai lựa chọn:

• Không dùng máy phóng: mất $|a_j-b_j|$ đơn vị thời gian.
• Dùng máy phóng $i$: đi bộ từ $a_j$ đến $x_i$, phóng đến $y_i$, rồi đi bộ đến $b_j$; tổng thời gian là $|a_j-x_i|+t_i+|y_i-b_j|$.

Với mỗi truy vấn, hãy tìm thời gian vận chuyển nhỏ nhất (có thể dùng tối đa một máy phóng).

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $x_i$, $y_i$, $t_i$ mô tả máy phóng $i$.
• $M$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a_j$, $b_j$ mô tả truy vấn $j$.

Dữ liệu ra

In ra $M$ dòng, dòng thứ $j$ là thời gian vận chuyển nhỏ nhất cho truy vấn $j$.

Ràng buộc

• $1\le N,M\le {10}^5$
• $0\le x_i,y_i,t_i\le {10}^9$
• $0\le a_j,b_j\le {10}^9$

Ví dụ

Ghi chú

Bài toán yêu cầu xử lý nhanh $M$ truy vấn với $N$ máy phóng; thuật toán $O(NM)$ sẽ không đủ nhanh.