Đường từ Nha Trang tới Thanh Hóa có thể được mô tả dưới ma trận ~n \times m~ với Nha Trang ở ô ~(1,1)~ và Thanh Hóa ở ô ~(n,m)~. Vì bảo mật ở đây rất nghiêm nên sẽ có ~k~ chốt chặn trên đường đi. Chốt chặn thứ ~i~ có vị trí tại ô ~(x_i,y_i)~ với bán kính chặn là ~r_i~. Một ô ~(x_j,y_j)~ gọi là bị chặn nếu khoảng cách từ ô đó tới ít nhất một chốt chặn bất kỳ thỏa mãn

~(x_i-x_j)^2+(y_i-y_j)^2 \le r_i^2~.

Bạn xuất phát từ Nha Trang và điểm tới là Thanh Hóa. Tại mỗi lượt, bạn có thể bước tới một trong bốn ô kề cạnh nếu ô đó không bị chặn. Hãy tìm số bước ít nhất để tới Thanh Hóa. Nếu không có đường đi, hãy in ra -1.

Input

• Dòng đầu gồm ba số nguyên ~n,m,k~ ~(1 \le n,m \le 1000,\ 1 \le k \le 10^5)~.
• ~k~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~x_i,y_i,r_i~, lần lượt là tọa độ và bán kính chặn của chốt chặn thứ ~i~ ~(1 \le x_i \le n,\ 1 \le y_i \le m,\ 0 \le r_i \le n+m)~.

Output

In ra một số nguyên duy nhất là số bước ít nhất cần tìm, hoặc -1 nếu không tồn tại đường đi.

Subtask

• Subtask 1 (30 điểm): ~n,m,k \le 100~.
• Subtask 2 (30 điểm): ~n,m \le 1000,\ k \le 10^5~ và ~r_i=0~ với mọi ~i~.
• Subtask 3 (40 điểm): không có ràng buộc bổ sung.

Ví dụ

3 5 2
1 5 1
3 1 1

6