Морж на крижинах
Морж Олександр знаходиться в океані у точці (x_A,y_A). Крижин навколо нього повно. Він хоче дістатися до точки (x_B,y_B) за мінімальну кількість стрибків. Олександр може стрибати максимум на дві клітини в одному з чотирьох напрямків. Якщо він знаходиться в точці (x,y), то за один стрибок він може потрапити в одну з наступних клітин: (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 ≤ x_i,y_i ≤ 10^9). Координати крижин будуть задаватися відрізками. У другому рядку йде кількість цих відрізків n (1 ≤ n ≤ 10^5). Кожен з наступних n рядків містить три цілих числа: x (1 ≤ x ≤ 10^9), y_L і y_R (1 ≤ y_L≤y_R ≤ 10^9). Це означає, що клітини з координатами (x, y_i) (y_{L }≤ y_{i }≤ y_R) знаходяться на крижинах. Загальна кількість таких клітин не перевищить 10^5.
Вихідні дані
Мінімальна кількість стрибків, за яку Олександр добереться з точки (x_A,y_A) в точку (x_B,y_B), або -1, якщо цього зробити не можна.