Stuart the Snail's Rainy Day Problem

Stuart the Snail lives on an infinite two-dimensional grid. Every integer coordinate has an edible plant, and his home is at \( (0,0) \). When it rains, Stuart can move easily: in one hour he may move to any of the four adjacent coordinates \( (x+1, y) \), \( (x-1, y) \), \( (x, y+1) \), or \( (x, y-1) \) and eat the plant there. He may also choose to stay in place.

However, there are \( n \) water pits in the field. The \( i\)-th water pit covers all integer coordinates \( (x,y) \) satisfying \( a_i \le x \le b_i \) and \( c_i \le y \le d_i \). These regions are dangerous, and Stuart cannot enter any point in a water pit. Note that water pits may overlap.

You are given \( q \) queries. Each query is specified by a type \( t \):

• If \( t = 1 \), you are given a target coordinate \( (x_j, y_j) \). Compute the minimum hours needed for Stuart to move from \( (0,0) \) to \( (x_j,y_j) \), avoiding water pits. If the target is unreachable, output \( -1 \).
• If \( t = 2 \), you are given an integer \( m_j \). Compute the number of distinct positions that Stuart can reach within at most \( m_j \) hours, starting from \( (0,0) \).

Note: In one hour, Stuart can choose to move to any of the four adjacent positions or remain at his current position (which is also considered a reachable position). The positions covered by water pits are off-limits for movement.

inputFormat

The first line contains two integers \( n \) and \( q \) -- the number of water pits and the number of queries.

The next \( n \) lines each contain four integers \( a_i, b_i, c_i, d_i \) describing a water pit that covers all positions \( (x, y) \) with \( a_i \le x \le b_i \) and \( c_i \le y \le d_i \).

The following \( q \) lines each describe a query. Each query starts with an integer \( t \). If \( t = 1 \), two integers \( x_j \) and \( y_j \) follow; if \( t = 2 \), one integer \( m_j \) follows.

outputFormat

For each query, output a single line with the answer:

• For a query of type 1, output the minimum number of hours required to reach the target, or \( -1 \) if it is unreachable.
• For a query of type 2, output the number of distinct positions that can be reached within at most \( m_j \) hours.

sample

1 2
1 2 1 2
1 3 3
2 2

6
12