Морж на крижинах#4365
Морж Олександр знаходиться в океані у точці (x_A, y_A). Крижин навколо нього повно. Він хоче дістатися до точки (x_B, y_B) за мінімальну кількість стрибків. Олександр може стрибати максимум на дві клітини в одному з чотирьох напрямків. Якщо він знаходиться в точці , то за один стрибок він може потрапити в одну з наступних клітин: (x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+2, y), (x-2, y), (x, y+2), (x, y-2). Олександр буде стрибати в клітку тільки якщо вона знаходиться на крижині. Гарантується, що точки (x_A, y_A) і (x_B, y_B) знаходяться на крижинах.
У першому рядку дається чотири цілих числа - координати точок (x_A, y_A) і (x_B, y_B) (1 \le x_i, y_i \le 10^9). Координати крижин будуть задаватися відрізками. У другому рядку йде кількість цих відрізків (1 \le n \le 10^5). Кожен з наступних рядків містить три цілих числа: (1 \le x \le 10^9), y_L і y_R (1 \le y_L \le y_R \le 10^9). Це означає, що клітини з координатами (x, y_i) (y_L \le y_i \le y_R) знаходяться на крижинах. Загальна кількість таких клітин не перевищить 10^5.
Мінімальна кількість стрибків, за яку Олександр добереться з точки (x_A, y_A) в точку (x_B, y_B), або , якщо цього зробити не можна.
Приклад 1