Để thể hiện tinh thần ngày lễ, các bò muốn vẽ tranh! Tranh là lưới $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ ô vuông đơn vị, mỗi ô0 hoặc1. Hàng đánh số $1,\ldots,R$, cột $1,\ldots,C$.
Gấp thời gian, chúng nhờ hàng xóm phía bắc biên giới. Dưới hướng dẫn tận tình của nai sừng tấm Canmuu, chúng làm máy ném sơn nguyên xô! Lưới ban đầu toàn0, máy tô một hình chữ nhật màu0 hoặc1. Canmuu đề nghị $Q$ thao tác $(1 \le Q \le 10,000)$; thao tác $i$ gồm năm số nguyên $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_{i} \le 1)$, tô màu $X_{i}$ mọi ô có hàng từ $R1_{i}$ đến $R2_{i}$ và cột từ $C1_{i}$ đến $C2_{i}$, gồm cả đầu mút.
Cách vẽ này dễ sai, nên Canmuu nhờ bạn xác định sau mỗi thao tác số ô có màu đúng.
Giới hạn bộ nhớ:64 MB
Giới hạn thời gian:1.5 giây
Dữ liệu vào
- Dòng1: ba số nguyên cách nhau dấu cách $R$, $C$, $Q$.
- Các dòng $2,\ldots,R+1$: dòng $i+1$ có $C$ ký tự '0' hoặc '1', biểu diễn hàng $i$.
- Các dòng $R+2,\ldots,R+Q+1$: dòng $R+i+1$ có năm số nguyên cách nhau dấu cách của thao tác: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Dữ liệu ra
- Các dòng $1,\ldots,Q$: ở dòng $i+1$ in một số nguyên, số ô khớp sau thao tác $i$.
Ví dụ
Dữ liệu vào 1
17 15 10 111111101111111 111111000111111 111110000011111 111100000001111 111000000000111 111100000001111 111000000000111 110000000000011 111000000000111 110000000000011 100000000000001 110000000000011 100000000000001 000000000000000 111111000111111 111111000111111 111111000111111 5 8 2 14 1 8 17 3 7 1 4 5 10 15 0 7 16 12 14 1 2 17 13 14 0 2 6 2 3 1 13 14 4 8 1 3 6 6 7 1 1 16 10 11 0 7 16 10 10 0
Dữ liệu ra 1
113 94 95 91 87 93 91 87 93 93
Ghi chú
Bò muốn vẽ cây ngày lễ.
Sau thao tác đầu lưới như sau:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 ô khớp các ô tương ứng của hình cây, được đánh dấu 'x' dưới đây (các bit khác là trạng thái sau lần ném sơn đầu):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Tác giả bài toán: Brian Hamrick và Neal Wu, 2008