<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

177. Square
time limit per test: 1.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



You have given the square NxN on a checkered sheet. Size of each cell is 1x1, (1, 1) is leftmost top corner and (N, N) is rightmost bottom corner.
Initially all cells are white.
There are M repaintings inside of the square, where one repainting changes color of specified rectangle to some color (white or black). All sides of repainted rectangles are parallel to sides of square.
You need to find amount of white cells after all repaintings.

Input
The first line of input consists of two numbers N and M (1<=N<=1000, 1<=M<=5000). Each of the next M lines consists of X1 Y1 X2 Y2 C, where (X1, Y1) and (X2, Y2) are indexes of opposite corners of the rectangular, and C is a symbol 'b' or 'w' ('b' means black color and 'w' - white) (1<=X1,X2,Y1,Y2<=N). All numbers in input are integer.

Output
Write amount of white cells after all repaintings.

Sample test(s)

Input
9 6
2 2 4 6 b
4 3 3 3 w
6 2 8 6 b
5 3 6 9 w
8 3 9 9 w
1 5 3 5 w

Output
63
Author:	Stanislav Angelyuk
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003

<|response|>
1. Abridged Problem Statement  
You have an N×N grid (1≤N≤1000), initially all cells are white. You must process M (1≤M≤5000) operations; each operation repaints all cells in a given axis-aligned rectangle either black or white. After all operations, output the total number of white cells.

2. Key Observations  
- A naïve per-cell repaint for each rectangle would be O(M·N²) in the worst case, too slow.  
- We can represent each row as a bitmask of length N (using C++'s std::bitset or a Python integer). A bit =1 means "white," =0 means "black."  
- Repainting columns [y₁…y₂] in one row to white is just `row_bits |= mask`, and to black is `row_bits &= ~mask`, where `mask` has 1s in positions y₁…y₂.  
- Each bitwise operation across N bits takes O(N/word_size) machine operations (≈N/64).  
- A √-decomposition over rows reduces the constant further: group rows into buckets of ≈√N rows and lazily apply OR/AND masks to fully covered buckets, touching individual rows only at the two boundary buckets.

3. Full Solution Approach  
a) Preprocess  
   - Read N, M.  
   - Create an array `grid` of N bitsets initialized to all 1s (all white).  
   - Precompute a full mask of N ones for convenience.  
   - Partition the N rows into buckets of size sq≈√N; for each bucket keep two lazy masks: `set_1_lazy` (pending OR / paint white) and `set_0_lazy` (pending AND-out / paint black).

b) For each operation `(x1,y1,x2,y2,C)`:  
   1. Convert to 0-based indices and ensure x1≤x2, y1≤y2.  
   2. Build `mask = ((1<<(y2−y1+1))−1) << y1`.  
   3. Let r1=x1/sq, r2=x2/sq. If r1=r2, flush bucket r1 and update rows x1..x2 directly. Otherwise flush the two boundary buckets and update their partial rows directly, and for each fully covered interior bucket only update its lazy masks (OR into set_1_lazy and clear set_0_lazy for white; the reverse for black).

c) After all operations, flush every bucket's lazies into its rows, then sum the 1-bits across all rows to get the answer.

4. C++ Implementation  

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int B = 1024;

int n, m;
int sq;
vector<bitset<B>> grid;
vector<bitset<B>> set_1_lazy, set_0_lazy;
bitset<B> full_m;

void apply_lazy(int bucket) {
    int start = bucket * sq;
    int end = min(n, (bucket + 1) * sq);
    for(int i = start; i < end; i++) {
        grid[i] |= set_1_lazy[bucket];
        grid[i] &= ~set_0_lazy[bucket];
    }

    set_1_lazy[bucket] = bitset<B>(0);
    set_0_lazy[bucket] = bitset<B>(0);
}

void read() { cin >> n >> m; }

void solve() {
    // Sqrt decomposition over rows, each row stored as a bitset of columns.
    // Rows are grouped into buckets of size sq = sqrt(n); each bucket carries
    // two lazy column masks set_1_lazy / set_0_lazy describing pending "set to
    // white" / "set to black" operations that apply uniformly to every row in
    // the bucket. A repaint of rows [x1, x2], columns [y1, y2] touches the two
    // boundary buckets directly (apply_lazy flushes them first, then we edit
    // the affected rows by OR-ing / AND-ing the column mask) and updates only
    // the lazy masks of fully covered interior buckets in O(1). Setting one
    // colour clears the conflicting lazy bits for the same columns. At the end
    // all buckets are flushed and we count the white (set) bits.

    sq = sqrt(n) + 1;
    grid.assign(n, bitset<B>());
    set_1_lazy.assign(sq, bitset<B>());
    set_0_lazy.assign(sq, bitset<B>());

    full_m = bitset<B>();
    for(int i = 0; i < n; i++) {
        full_m.set(i);
    }

    for(int i = 0; i < n; i++) {
        grid[i] = full_m;
    }

    while(m--) {
        int x1, y1, x2, y2;
        string c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        x1--;
        y1--;
        x2--;
        y2--;

        if(x1 > x2) {
            swap(x1, x2);
        }

        if(y1 > y2) {
            swap(y1, y2);
        }

        bool color = (c == "w");
        bitset<B> mask = (full_m >> (n - (y2 - y1 + 1))) << y1;

        int r1 = x1 / sq, r2 = x2 / sq;

        if(r1 == r2) {
            apply_lazy(r1);
            for(int i = x1; i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }
        } else {
            apply_lazy(r1);
            for(int i = x1; i < (r1 + 1) * sq && i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }

            apply_lazy(r2);
            for(int i = r2 * sq; i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }

            for(int i = r1 + 1; i < r2; i++) {
                if(color) {
                    set_1_lazy[i] |= mask;
                    set_0_lazy[i] &= ~mask;
                } else {
                    set_0_lazy[i] |= mask;
                    set_1_lazy[i] &= ~mask;
                }
            }
        }
    }

    int ans = 0;
    for(int bucket = 0; bucket * sq < n; bucket++) {
        apply_lazy(bucket);
    }

    for(int i = 0; i < n; i++) {
        ans += grid[i].count();
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  

```python
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    # rows[i] is an integer whose binary bits [0..N-1] represent row i.
    # bit j=1 means white, 0 means black.
    # Initialize each row to (1<<N)-1 -> all N bits =1 (white).
    rows = [(1 << N) - 1 for _ in range(N)]

    for _ in range(M):
        x1, y1, x2, y2, c = input().split()
        x1, y1, x2, y2 = map(int, (x1, y1, x2, y2))
        # Convert to 0-based
        x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
        # Ensure x1 <= x2, y1 <= y2
        if x1 > x2:
            x1, x2 = x2, x1
        if y1 > y2:
            y1, y2 = y2, y1

        # Build mask with 1s in bits [y1..y2]
        length = y2 - y1 + 1
        mask = ((1 << length) - 1) << y1

        # Apply to each row i in [x1..x2]
        if c == 'w':
            # paint white -> OR with mask
            for i in range(x1, x2 + 1):
                rows[i] |= mask
        else:
            # paint black -> AND with complement of mask
            comp = ~mask
            for i in range(x1, x2 + 1):
                rows[i] &= comp

    # Sum up the number of 1-bits in all rows
    total_white = 0
    for r in rows:
        # Python 3.8+: int.bit_count()
        total_white += r.bit_count()

    print(total_white)

if __name__ == "__main__":
    main()
```
