명절 분위기를 보여 주려고 소들은 그림을 그리려 합니다! 그림은 단위 정사각형의 $R$ $\times$ $C$ 격자 $(1 \le R \le 50,000; 1 \le C \le 15)$이며 각 칸은0 또는1입니다. 행 번호는 $1,\ldots,R$, 열 번호는 $1,\ldots,C$입니다.
시간이 부족해 국경 북쪽 이웃에게 도움을 청했습니다. 친절한 큰사슴 Canmuu의 지도 아래 페인트를 통째로 던지는 기계를 만들었습니다! 격자는 처음 모두0이고 기계는 직사각형에 색0 또는1을 칠합니다. Canmuu는 $Q$번 $(1 \le Q \le 10,000)$ 작업을 제안했습니다. 작업 $i$는 다섯 정수 $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)$로 주어지며 행 $R1_{i}$부터 $R2_{i}$, 열 $C1_{i}$부터 $C2_{i}$까지 양 끝을 포함한 모든 칸을 색 $X_{i}$으로 칠합니다.
하지만 이런 방법은 실수하기 쉬워 Canmuu는 매 작업 뒤 색이 맞는 단위 칸 수를 구해 달라고 합니다.
메모리 제한:64 MB
시간 제한:1.5초
입력
- 1행: 공백으로 구분한 세 정수 $R$, $C$, $Q$.
- $2,\ldots,R+1$행: $i+1$행은 '0' 또는 '1'인 $C$개 문자로 격자의 $i$행을 나타냅니다.
- $R+2,\ldots,R+Q+1$행: $R+i+1$행은 작업을 나타내는 공백으로 구분한 다섯 정수 $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$입니다.
출력
- $1,\ldots,Q$행: $i+1$행에 작업 $i$ 뒤 일치하는 칸 수를 한 정수로 출력합니다.
예제
입력 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
출력 1
113 94 95 91 87 93 91 87 93 93
참고
소들은 명절 나무를 그리려 합니다.
첫 작업 뒤 격자는 다음과 같습니다:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
나무 그림의 해당 칸과 일치하는113칸을 아래 'x'로 표시합니다 (다른 비트는 첫 페인트 작업 뒤 상태입니다):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
문제 작성자: Brian Hamrick과 Neal Wu, 2008