Problem: Problem

There are W white square tiles in the horizontal direction and H in the vertical direction, for a total of W x H tiles.

On the morning of day i, Taro has a tile that exists in a rectangular area with the axith tile from the left and the ayith tile from the top on the upper left, and the bxith tile from the left and the byith tile from the top on the lower right. Make sure it's all white. If all tiles are white, fill them all black. At other times, do nothing.

For each of the N days, print out how many tiles are filled in black at the end of the day's work.

Constraints

* 2 ≤ W ≤ 100000
* 2 ≤ H ≤ 100000
* 2 ≤ N ≤ 100000
* 1 ≤ axi ≤ bxi ≤ W (1 ≤ i ≤ N)
* 1 ≤ ayi ≤ byi ≤ H (1 ≤ i ≤ N)

Input

The input is given in the following format.


W H
N
ax1 ay1 bx1 by1
ax2 ay2 bx2 by2
...
axN ayN bxN byN


On the first line, two integers W and H are given, separated by blanks. The second line is given one integer N. Of the N lines from the 3rd line, the ith line is given four integers axi ayi bxi byi, which represent the rectangular area to be confirmed on the morning of the i day, separated by blanks.

Output

In each of the N days, output the number of tiles filled in black at the end of the work on the i-day on the i-line.

Example

Input

5 4
5
1 1 3 3
3 2 4 2
4 3 5 4
1 4 5 4
4 1 4 1


Output

9
9
13
13
14

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree
{
  vector< set< pair< int, int > > > seg, add;
  int sz;
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, set< pair< int, int > >());
    add.assign(2 * sz - 1, set< pair< int, int > >());
  }
  bool Check(set< pair< int, int > >& seg, int x, int y)
  {
    if(!seg.empty()) {
      auto pos = seg.lower_bound({x, y});
      if(pos != seg.begin()) {
        --pos;
        if(pos -> second > x) return(true);
        ++pos;
      }
      if(pos != seg.end()) {
        if(pos -> first < y) return(true);
      }
    }
    return(false);
  }
  bool Query(const int a, const int b, const int x, const int y, int k, int l, int r)
  {
    if(a >= r || b <= l) return(false);
    if(a <= l && r <= b) return(Check(seg[k], x, y) || Check(add[k], x, y));
    return(Check(add[k], x, y) || Query(a, b, x, y, 2 * k + 1, l, (l + r) >> 1) || Query(a, b, x, y, 2 * k + 2, (l + r) >> 1, r));
  }
  bool Query(int a, int x, int b, int y)
  {
    return(Query(a, b, x, y, 0, 0, sz));
  }
  inline void Insert(set< pair< int, int > >& seg, const int x, const int y)
  {
    if(seg.empty()) {
      seg.insert({x, y});
    } else {
      bool flag = true;
      pair< int, int > range(x, y);
      while(!seg.empty() && flag) {
        auto pos = seg.lower_bound(range);
        flag = false;
        if(pos != seg.begin()) {
          --pos;
          if(pos -> second > x) {
            range = {min(pos -> first, range.first), max(pos -> second, range.second)};
            flag = true;
            pos = seg.erase(pos);
          } else {
            ++pos;
          }
        }
        if(pos != seg.end()) {
          if(pos -> first < y) {
            range = {min(pos -> first, range.first), max(pos -> second, range.second)};
            flag = true;
            seg.erase(pos);
          }
        }
      }
      seg.insert(range);
    }
  }
 
  void Add(const int a, const int b, const int x, const int y, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      Insert(add[k], x, y);
      return;
    }
    Add(a, b, x, y, 2 * k + 1, l, (l + r) >> 1);
    Add(a, b, x, y, 2 * k + 2, (l + r) >> 1, r);
    Insert(seg[k], x, y);
  }
  void Add(int a, int x, int b, int y)
  {
    Add(a, b, x, y, 0, 0, sz);
  }
};
 
 
int main()
{
  int W, H, N;
  scanf("%d %d", &W, &H);
  SegmentTree tree(100000);
  scanf("%d", &N);
  long long sum = 0;
  while(N--) {
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    --x1, --y1;
    if(!tree.Query(x1, y1, x2, y2)) {
      sum += 1LL * (x2 - x1) * (y2 - y1);
      tree.Add(x1, y1, x2, y2);
    }
    printf("%lld\n", sum);
  }
}