Gravity Balls Convergence

In the Gravity Balls Convergence game, two balls are placed on an n×n grid. The cell in the i-th row from the top and the j-th column from the left is denoted by \( (i,j) \).

The grid contains \( m \) obstacles located at \( (x_i,y_i) \) for \( 1\le i\le m \). In addition, all cells outside the boundary of the grid are considered obstacles.

You are given two balls at positions \( (a,b) \) and \( (c,d) \). In one operation, you can set the gravity direction to one of the four directions: up, down, left, or right. When you do so, both balls will roll in that direction until they hit an obstacle.

Your task is to use the minimum number of operations to make the two balls meet at the same cell, or report that it is impossible. There are \( q \) games; in each game, only the initial positions of the balls change, while the obstacles remain fixed.

inputFormat

The first line contains three integers \( n \), \( m \), and \( q \) --- the size of the grid, the number of obstacles, and the number of games.

The next \( m \) lines each contain two integers \( x_i \) and \( y_i \) representing the position of an obstacle.

The following \( q \) lines each contain four integers \( a \), \( b \), \( c \), and \( d \), representing the initial positions of the two balls.

outputFormat

For each game, output a single line containing the minimum number of operations required for the two balls to meet at the same cell. If it is impossible, output -1.

sample

3 0 1
1 1 3 3

2