输入格式处为题面描述。

下面的是原输入格式：

In this problem the initial board is specified as a set of $m$ rectangles. All cells that lie inside at least one of these rectangles are colored white and the rest are colored black.

In the first line of input three space-spereated integers $n,m,k(1\le k\le n\le 10^9,1\le m\le 5\times 10^4)$ follow, denoting size of the board, number of rectangles and maximum size of the turn square during the game, respectively.

In $i$ - th line of the next $m$ lines four space-seperated integers $a_i,b_i,c_i,d_i(1≤a_i≤c_i≤n, 1≤b_i≤d_i≤n)$ are given meaning that $i$ - th rectangle determining the initial board is a rectangle with upper-left cell at $(a_i,b_i)$ and lower-right cell at $(c_i,d_i)$.

In this problem the initial board is specified as a set of $m$ rectangles. All cells that lie inside at least one of these rectangles are colored white and the rest are colored black.

In the first line of input three space-spereated integers $n,m,k(1\le k\le n\le 10^9,1\le m\le 5\times 10^4)$ follow, denoting size of the board, number of rectangles and maximum size of the turn square during the game, respectively.

In $i$ - th line of the next $m$ lines four space-seperated integers $a_i,b_i,c_i,d_i(1≤a_i≤c_i≤n, 1≤b_i≤d_i≤n)$ are given meaning that $i$ - th rectangle determining the initial board is a rectangle with upper-left cell at $(a_i,b_i)$ and lower-right cell at $(c_i,d_i)$.