Cho một đoạn đường được biểu diễn bởi các điểm đánh số từ ~0~ đến ~10^9~, với điểm ~0~ là biên trái của đường. Đoạn đường được chia làm hai làn, gọi lần lượt là chiều dương và chiều âm. Trên làn đường chiều dương, bạn chỉ có thể đi xe từ một điểm tới một điểm khác có vị trí lớn hơn vị trí của điểm xuất phát. Ở chiều âm, bạn chỉ có thể đi xe từ một điểm tới một điểm khác có vị trí bé hơn vị trí của điểm xuất phát.

Hai làn đường được ngăn cách bởi các dải phân cách cứng. Ngoài ra, sẽ có ~n~ đoạn đường không giao nhau ~[L, R]~ mà ở đó không có dải phân cách và bạn có thể di chuyển qua lại giữa hai làn đường thông qua các đoạn đường đó.

Bạn có ~q~ kế hoạch, với kế hoạch thứ ~i~, bạn cần di chuyển từ vị trí có tọa độ ~x~ trên làn đường theo chiều âm tới vị trí có tọa độ ~y~ trên làn đường theo chiều dương. Theo luật giao thông, bạn không thể di chuyển bằng xe máy theo chiều dương khi đang ở làn đường theo chiều âm và ngược lại. Tuy nhiên, bạn có thể xuống xe và dắt bộ ngược chiều đường. Với mỗi đơn vị độ dài mà bạn dắt xe đi bộ, bạn sẽ tốn ~1~ thể lực.

Hiện tại, bạn đang có ~k~ thể lực và bạn muốn biết mình sẽ phải di chuyển ít nhất bao nhiêu đơn vị độ dài (bao gồm cả đi xe và dắt bộ) để đến được vị trí mình cần.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~) — số đoạn đường không có dải phân cách và số kế hoạch.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~L_i~ và ~R_i~ (~0 \le L_i \le R_i \le 10^9~) — hai đầu mút trái và phải của đoạn đường không có dải phân cách thứ ~i~. Đầu vào đảm bảo không có hai đoạn đường nào giao nhau.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa ba số nguyên ~x~, ~y~ và ~k~ (~0 \le x, y, k \le 10^9~) mô tả một kế hoạch.

Output

In ra ~q~ dòng, mỗi dòng chứa một số nguyên là đáp án của kế hoạch tương ứng. Trong trường hợp không tồn tại cách di chuyển, in ra -1.

Scoring

Sample Input 1

3 4
2 3
5 6
8 9
3 4 0
4 4 2
9 3 10
1 1 1

Sample Output 1

1
2
6
-1

Notes

Ở truy vấn đầu tiên, cách đi tối ưu là qua đường tại vị trí ~3~ rồi đi xe tới vị trí ~4~.

Ở truy vấn thứ hai, có hai cách di chuyển:

• Đi xe từ vị trí ~4~ tới vị trí ~3~ trên làn đường âm, qua đường và đi xe từ vị trí ~3~ tới vị trí ~4~ trên làn đường dương, tốn ~0~ thể lực.

• Dắt bộ từ vị trí ~4~ tới vị trí ~5~ trên làn đường âm, qua đường và dắt bộ từ vị trí ~5~ tới vị trí ~4~ trên làn đường dương, tốn ~2~ thể lực.

Ở truy vấn cuối cùng, không có cách nào để di chuyển mà chỉ tốn tối đa ~1~ thể lực.