Một trong những công việc đồng áng mà bác nông dân John ghét nhất là vận chuyển những lượng lớn phân bò. Để đơn giản hóa quá trình này, ông nghĩ ra một ý tưởng thú vị: thay vì chở phân giữa hai điểm bằng chiếc xe kéo phía sau máy kéo, tại sao không bắn nó qua không trung bằng một chiếc ná bắn phân khổng lồ? (quả thật, liệu có chuyện gì có thể xảy ra chứ...)

Trang trại của bác nông dân John nằm dọc theo một con đường thẳng rất dài, nên mỗi vị trí trong trang trại có thể được mô tả đơn giản bằng vị trí của nó trên con đường này (tương ứng với một điểm trên trục số). Bác nông dân John xây \(N\) chiếc ná (\(1 \leq N \leq 10^5\)), trong đó chiếc ná thứ \(i\) được mô tả bởi ba số nguyên \(x_i\), \(y_i\) và \(t_i\), cho biết chiếc ná này có thể bắn phân từ vị trí \(x_i\) đến vị trí \(y_i\) chỉ trong tổng cộng \(t_i\) đơn vị thời gian.

Bác nông dân John có \(M\) đống phân cần vận chuyển (\(1 \leq M \leq 10^5\)). Đống thứ \(j\) cần được chuyển từ vị trí \(a_j\) đến vị trí \(b_j\). Chở phân bằng máy kéo trên quãng đường \(d\) mất \(d\) đơn vị thời gian. Bác nông dân John hy vọng giảm được thời gian này bằng cách cho phép sử dụng tối đa một lần bất kỳ chiếc ná nào khi vận chuyển mỗi đống phân. Thời gian bác nông dân John di chuyển máy kéo mà không chở phân không được tính.

Với mỗi trong số \(M\) đống phân, hãy giúp bác nông dân John xác định thời gian vận chuyển nhỏ nhất có thể, biết rằng ông có thể dùng tối đa một chiếc ná trong quá trình vận chuyển.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một chiếc ná bằng các số nguyên \(x_i\), \(y_i\) và \(t_i\) (\(0 \leq x_i, y_i, t_i \leq 10^9\)). \(M\) dòng cuối mô tả các đống phân cần vận chuyển bằng các số nguyên \(a_j\) và \(b_j\).

Dữ liệu ra

In ra \(M\) dòng, mỗi dòng ứng với một đống phân và cho biết thời gian nhỏ nhất cần để vận chuyển đống phân đó.

Ví dụ

2 3
0 10 1
13 8 2
1 12
5 2
20 7

4
3
10

Nguồn

USACO 2018 February Contest, Platinum — Slingshot

Tác giả bài toán: Brian Dean.