Công ty AlphaZone đang thực hiện việc giao nhận hàng dọc trên tuyến đường quốc lộ. Ta có thể xem tuyến quốc lộ này như một đoạn thẳng và các vị trí giao nhận là một điểm trên đoạn thẳng này, được đánh chỉ số liên tiếp từ ~0~ đến ~10^9~. Các điểm lân cận nhau cách nhau ~1~ đơn vị chiều dài.

Hiện tại công ty dùng xe tải để giao hàng, với phương thức này thì thời gian để giao hàng từ điểm ~a~ đến điểm ~b~ sẽ là ~|a - b|~. Việc giao hàng bằng xe tải có thể thực hiện trên bất kỳ đoạn đường nào của quốc lộ. Các đoạn đường trên quốc lộ sử dụng xe tải giao hàng là hai chiều.

Công ty đang thử nghiệm giao hàng bằng máy bay không người lái (drone) và đã thiết lập một số tuyến đường có thể vận chuyển bằng drone. Một tuyến đường giao hàng bằng drone được mô tả bằng ~3~ tham số ~(x, y, t)~ cho biết drone có thể giao hàng một chiều từ điểm ~x~ đến điểm ~y~ và tốn thời gian là ~t~. Có thể giả sử công ty có sẵn xe tải tại tất cả điểm trên quốc lộ và drone có sẵn tại những tuyến đường được chọn triển khai thử nghiệm, và bạn được tuỳ chọn hình thức giao hàng bằng xe tải, drone hay kết hợp cả hai. Mỗi đơn hàng bạn chỉ được tối đa một lần sử dụng drone, số lần dùng xe tải để giao hàng là không giới hạn.

Yêu cầu: Cho trước ~M~ đơn hàng cần giao và thông tin về các tuyến đường được chọn thử nghiệm giao hàng bằng drone. Hãy viết một chương trình cho biết thời gian tối thiểu để giao từng đơn hàng.

Input

Dòng đầu là hai số nguyên ~N, M~ lần lượt cho biết số tuyến đường giao hàng bằng drone và số đơn hàng. Dòng thứ ~i~ trong ~N~ dòng tiếp theo mô tả một tuyến đường giao hàng bằng drone gồm ~3~ số ~x_i, y_i~ và ~t_i~ cho biết drone có thể giao hàng từ ~x_i~ đến ~y_i~ và tốn ~t_i~ thời gian ~(0 \le x_i, y_i, t_i \le 10^9)~. Dòng thứ ~j~ trong ~M~ dòng tiếp theo gồm hai số nguyên ~a_j, b_j~ cho biết đơn hàng thứ ~j~ cần giao từ vị trí ~a_j~ đến vị trí ~b_j~ ~(0 \le a_j, b_j \le 10^9)~.

Output

Gồm ~M~ dòng, dòng thứ ~j~ là một số nguyên cho biết thời gian tối thiểu cần để giao đơn hàng thứ ~j~.

Scoring

Sample Input 1

5 3
5 10 2
12 20 1
18 7 3
15 25 3
22 12 4
6 20
12 30
15 22

Sample Output 1

7
11
6

Notes

Đơn hàng ~1~: Xe tải giao hàng từ điểm ~6~ đến điểm ~12~, tốn thời gian: ~6~; dùng drone giao từ điểm ~12~ đến ~20~, tốn thời gian: ~1~. Tổng thời gian là: ~7~

Đơn hàng ~2~: Có thể để drone giao hàng từ điểm ~12~ đến điểm ~20~, tốn thời gian: ~1~; xe tải giao hàng từ điểm ~20~ đến điểm ~30~, tốn thời gian: ~10~. Tổng thời gian là: ~11~

Đơn hàng ~3~: Xe tải giao hàng từ điểm ~15~ về điểm ~12~, tốn thời gian: ~3~; Dùng drone giao hàng từ điểm ~12~ đến ~20~, tốn thời gian: ~1~; xe tải giao hàng từ điểm ~20~ đến ~22~, tốn thời gian: ~2~. Tổng thời gian là: ~6~.