Labyrinth Right-Then-Down with Teleports

Starting from the top-left corner, prefer moving right; move down only when the cell to the right is not walkable. When you step on a teleport start, teleport immediately and continue.

输入格式

n m; the number of obstacles b and b lines of 0-based coordinates; the number of teleports k and k lines of sr sc er ec. Teleport starts are unique, an end is never a start, and no teleport endpoint is an obstacle. This site adds: n,m≤100.

输出格式

If the bottom-right corner is reached, output the number of cells passed through (the start, teleport starts, and teleport ends all count); if there is no path, output -1; if revisiting a cell causes an infinite loop, output -2.

样例 1

输入：

3 4
1
0 1
1
1 1 2 2

输出：

5

样例 2

输入：

3 3
2
0 1
1 0
0

输出：

-1

样例 3

输入：

3 3
0
2
0 1 1 0
1 1 0 1

输出：

-2