题目描述

黑王站在一个 $10^9$ 行、$10^9$ 列的棋盘上。行从上到下编号 1 到 $10^9$，列从左到右编号 1 到 $10^9$。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

已知棋盘上某些格子是允许通行的。所有允许通行的格子以 $n$ 个线段的形式给出：每个线段用三个整数 $r_i, a_i, b_i$（$a_i \le b_i$）描述，表示第 $r_i$ 行中从第 $a_i$ 列到第 $b_i$ 列（含）的所有格子允许通行。

你的任务是求国王从格子 $(x_0, y_0)$ 走到 $(x_1, y_1)$ 所需的最少步数，要求只走允许通行的格子——也就是说，国王一路上只能位于允许通行的格子上。

提醒：国际象棋的王一步可以走到任何一个相邻格子。若两个格子至少共享一个点，就称它们相邻。

输入格式

第一行包含四个用空格隔开的整数 $x_0, y_0, x_1, y_1$（$1 \le x_0, y_0, x_1, y_1 \le 10^9$），表示国王的起点和终点。

第二行包含一个整数 $n$（$1 \le n \le 10^5$），表示允许通行格子组成的线段数。接下来 $n$ 行描述这些线段：第 $i$ 行包含三个用空格隔开的整数 $r_i, a_i, b_i$（$1 \le r_i, a_i, b_i \le 10^9$，$a_i \le b_i$）。

输出格式

输出一个整数——国王从 $(x_0, y_0)$ 到 $(x_1, y_1)$ 所需的最少步数。如果无法到达，输出 -1。

5 7 6 11
3
5 3 8
6 7 11
5 2 5

4

3 4 3 10
3
3 1 4
4 5 9
3 10 10

6

1 1 2 10
2
1 1 3
2 6 10

-1