<|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). Even with M=5000 full-row updates, that’s ~5000·(1000/64) ≈78 million 64-bit ops, which is fine in optimized C++.  
- A further √-decomposition over rows can reduce the constant by lazily applying masks to blocks of rows, but it is not strictly necessary for N=1000 and M=5000 in C++.

3. Full Solution Approach  
a) Preprocess  
   - Read N, M.  
   - Create an array `grid` of N bitsets (or Python ints) initialized to all 1s (all white).  
   - Precompute a full mask of N ones for convenience.

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. For i from x1 to x2:  
       - If C=='w', do `grid[i] |= mask`.  
       - Else do `grid[i] &= ~mask`.

c) After all operations, sum up the 1-bits in each `grid[i]` to get the answer.

(Optional √-decomposition optimization)  
- Partition the N rows into B≈√N row-blocks. For each block maintain two lazy masks:  
    • `lazy_set1` (OR-masks) and `lazy_set0` (AND-masks).  
- When repainting a rectangle:  
    • For blocks fully inside [x1…x2], update their lazy masks instead of touching each row.  
    • For partial blocks at the ends, “push” (apply) the block’s lazy masks to its rows, clear the lazies, then update those rows directly.  
- At the end, push all lazies and count bits.

4. C++ Implementation with Detailed Comments  

```cpp
#include <bits/stdc++.h>
using namespace std;

// Max N
static const int MAXN = 1000;

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

    int N, M;
    cin >> N >> M;

    // grid[i] is a bitset of length N: bit j=1 means cell (i,j) is white.
    vector< bitset<MAXN> > grid(N);
    // Prepare a bitset with N ones: all cells initially white
    bitset<MAXN> fullMask;
    for(int j = 0; j < N; j++) 
        fullMask.set(j);
    for(int i = 0; i < N; i++) 
        grid[i] = fullMask;

    while(M--) {
        int x1, y1, x2, y2;
        char C;
        cin >> x1 >> y1 >> x2 >> y2 >> C;
        // Convert to 0-based
        --x1; --y1; --x2; --y2;
        // Ensure x1<=x2, y1<=y2
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);

        // Build mask with bits y1..y2 set to 1
        int length = y2 - y1 + 1;
        bitset<MAXN> mask;
        // Create (1<<length)-1 at low bits, then shift left by y1
        // We do it manually since shifting a full bitset by (MAXN-length) then right
        // is a trick, but here N≤1000 so we can loop:
        for(int j = y1; j <= y2; j++) {
            mask.set(j);
        }

        if(C == 'w') {
            // Paint white: OR each row in [x1..x2] with mask
            for(int i = x1; i <= x2; i++) {
                grid[i] |= mask;
            }
        } else {
            // Paint black: AND each row with bitwise complement of mask
            for(int i = x1; i <= x2; i++) {
                grid[i] &= ~mask;
            }
        }
    }

    // Count total white cells
    long long answer = 0;
    for(int i = 0; i < N; i++) {
        answer += grid[i].count();
    }
    cout << answer << "\n";
    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()
```