문제
정올시의 4세대 이동 전화 기지국은 다음과 같은 방식으로 운영된다.
기지국이 있는 영역들은 정사각형 칸으로 구분된다.
정사각형들은 S*S 크기의 행렬을 이루며, 칸의 가로 세로 위치는 0부터 S-1까지 번호가 매겨져 있다.
각 영역 안에서 볼 때, 개통중인 이동 전화의 개수는 시시각각 변할 수 있다.
전화를 가진 사람이 다른 칸(영역)으로 이동할 수 있고, 전화기 전원을 켜거나 끌 수도 있기 때문이다.
그런 일이 생기면 각 기지국은 자기 영역 내에서 생긴 변화를 이동전화 본부로 보고한다.
여러 기지국에서 날아오는 보고를 받아들인 뒤,
임의의 직사각형 영역에 켜져 있는 이동 전화의 총 개수를 묻는 물음에 제대로 응답해 주는 프로그램을 작성하라.
입력
입력은 임의의 명령(최대 60,002개)으로 이루어진다.
명령은 다음과 같다.
0 S | 기지국 영역의 크기를 알려준다. 이는 각 구역의 크기를 S*S(S≤1024)로 잡고 각 구역의 개통 전화 수를 모두 0으로 초기화 하도록 하는 명령이다. 이 명령은 프로세스를 시작할 때, 한번만 주어진다. |
1 X Y A | X Y위치에 전화의 개수가 A개 추가되었음을 알린다. A의 값은 양수이거나 음수이다 (음수일 경우 사라진 전화의 개수를 의미한다.) 이 명령에서 추가된 전화의 개수가 정수 범위를 넘기는 경우는 없다고 가정한다. |
2 L B R T | 가로(L≤X≤R) 세로(B≤Y≤T)에 속하는 직사각형 영역에서 개통중인 전화의 모든 개수를 묻는다. X와 Y는 0~S-1의 숫자이다. |
3 | 프로그램을 종료시킨다. |
[제약사항]
영역의 크기는 0*0 <= S * S < 1024 * 1024 이다.
모든 정사각형의 칸(셀)의 값 V는 항상 0 <= V <= 32767 이다.
업데이트 값 A는 -32768 < = A <= 32767이다.
전체 명령수 U는 3<= U <= 60002이다.
영역 전체의 전화 대수의 총합 M은 230 이하이다.
출력
2번 명령에 대한 명령의 답을 한 줄에 하나씩 출력한다.
질의에 대하여 230을 넘어가는 경우는 존재하지 않는다.
예제1
04
1123
20022
1112
112-1
21123
3
3
4