There are several rectangular sheets placed on a flat surface. Create a program to find the area and perimeter of the part covered by these sheets.

However, when the plane is regarded as the coordinate plane, the arrangement of the sheets shall satisfy the following conditions (1) and (2).

(1) The x and y coordinates of the four vertices of the rectangle on each sheet are all integers from 0 to 10000, and each side of the rectangle is parallel to the x-axis or y-axis.

(2) The number of sheets is at most 10,000 or less.

The number n of rectangles and the integer r indicating the type of problem are separated by a space in the first line of the input data. In each line after the second line, the coordinates of the lower left vertex of each sheet (x1, y1) and The coordinates of the upper right vertex coordinates (x2, y2) are written in the order of x1, y1, x2, y2, separated by a blank.

The output outputs the area on the first line when r = 1, the area on the first line when r = 2, and the perimeter on the second line. In either case, insert a line break at the end.

In 40% of the test data, the coordinates of the vertices of the rectangle are 0 or more and 100 or less, and 1/2 of them is the problem of finding only the area. Furthermore, 1/2 of the whole is the problem of finding only the area.

Input Example 1 | Input Example 2 | Input Example 3 | Input Example 4
--- | --- | --- | ---
|
5 1 | 5 2 | 2 2 | 3 2
0 0 3 2 | 0 0 3 2 | 0 0 8 9 | 2 2 8 8
1 1 2 5 | 1 1 2 5 | 0 0 9 8 | 3 0 4 9
0 4 6 5 | 0 4 6 5 | | 5 0 7 9
3 3 5 6 | 3 3 5 6 | |
5 0 7 6 | 5 0 7 6 | |
Output example 1 | Output example 2 | Output example 3 | Output example 4
29 | 29 | 80 | 45
38 | 36 | 36

input

The input consists of multiple datasets. Input ends when both n and r are 0. The number of datasets does not exceed 10.

output

For each dataset, the area is output on the first line when r = 1, the area is output on the first line when r = 2, and the perimeter is output on the second line.





Example

Input

5 1
0 0 3 2
1 1 2 5
0 4 6 5
3 3 5 6
5 0 7 6
5 2
0 0 3 2
1 1 2 5
0 4 6 5
3 3 5 6
5 0 7 6
2 2
0 0 8 9
0 0 9 8
3 2
2 2 8 8
3 0 4 9
5 0 7 9
0 0


Output

29
29
38
80
36
45
36
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int n,r;
vector<P> x[10002];
vector<P> xx[10002];
int main(void){
  while(cin >> n >> r && n){
    for(int i = 0; i < 10002; i++){
      x[i].clear();
      xx[i].clear();
    }

    for(int i = 0; i < n; i++){
      int x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      for(int j = x1; j < x2; j++){
	bool f = true;
	for(int k = 0; k < (int)x[j].size(); k++){
	  if(x[j][k].F <= y2 && x[j][k].S >= y1){
	    x[j][k].F = min(x[j][k].F,y1);
	    x[j][k].S = max(x[j][k].S,y2);
	    f = false;
	    break;
	  }
	}
	if(f) x[j].push_back(P(y1,y2));
      }
    }

    for(int i = 0; i < 10000; i++){
      if(x[i].empty()) continue;
      sort(x[i].begin(),x[i].end());
      xx[i].push_back(x[i][0]);
      for(int j = 1,k = 0; j < (int)x[i].size(); j++){
	if(xx[i][k].S >= x[i][j].F){
	  xx[i][k].S = max(xx[i][k].S,x[i][j].S);
	}else{
	  xx[i].push_back(x[i][j]);
	  k++;
	}
      }
      //x[i].clear();
      /*
      cout << "x = " << i << endl;
      for(int j = 0; j < (int)xx[i].size(); j++){
	cout << "( " << xx[i][j].F << " , " << xx[i][j].S << " )" << endl;
      }
      cout << endl;
      //*/
    }

    int res = 0;
    for(int i = 0; i < 10000; i++){
      for(int j = 0; j < (int)xx[i].size(); j++){
	res += xx[i][j].S - xx[i][j].F;
      }
    }
    cout << res << endl;

    if(r-1){
      res = 0;
      for(int i = 0; i < 10000; i++){
	res += 2 * (int)xx[i].size();
	for(int j = 0; j < (int)xx[i].size(); j++){
	  res += 2 * (xx[i][j].S - xx[i][j].F);
	  if(i){
	    for(int k = 0; k < (int)xx[i-1].size(); k++){
	      if(xx[i][j].F < xx[i-1][k].S && xx[i][j].S > xx[i-1][k].F){
		res -= min(xx[i][j].S,xx[i-1][k].S) - max(xx[i][j].F,xx[i-1][k].F);
	      }
	    }	
	  }  
	  if(i+1 < 10000){
	    for(int k = 0;k < (int)xx[i+1].size(); k++){
	      if(xx[i][j].F < xx[i+1][k].S && xx[i][j].S > xx[i+1][k].F){
		res -= min(xx[i][j].S,xx[i+1][k].S) - max(xx[i][j].F,xx[i+1][k].F);
	      }
	    }
	  }
	}
      }
      cout << res << endl;
    }
  }
}