Matrix

아침에 평소처럼 일어났지만, 낮 동안 세상에서 이상한 오류들이 보이기 시작한다. 하루가 끝날 무렵 당신은 자신이 매트릭스 안에 있다고 확신하고 그곳을 빠져나가고 싶어 한다. 설계자(Architect)가 당신을 찾아와 그의 문제 하나를 도와주면 탈출할 방법을 주겠다고 제안한다.

설계자의 행렬은 $N \times M$ 크기이며, 처음에는 모든 칸의 값이 0이다. 낮 동안 행렬의 일부가 수정되고, 설계자는 때때로 특정 칸의 값을 알고 싶어 한다.

설계자는 행렬이 $N$행 $M$열이라고 알려 준 뒤, 다음과 같은 $K$개의 연산을 보낸다.

• UPDATE X Y1 Y2: $X$행에서 $Y1$열부터 $Y2$열까지(양 끝 포함) 모든 칸의 값을 1씩 증가시킨다.
• QUERY X Y: $X$행 $Y$열 칸의 값을 구한다.

설계자는 당신을 완전히 믿지 않기 때문에, 이 문제는 일반적인 배치(batch) 방식으로 채점되지 않는다. 대신 다음 함수들을 구현해야 한다.

• void initialize(long long N, long long M)
• void update(long long X, long long Y1, long long Y2)
• int query(long long X, long long Y)

소스 파일에서는 이 함수 원형을 정확히 그대로 사용한다. 다른 함수와 지역 변수, 전역 변수는 자유롭게 선언할 수 있다. 제출한 코드는 표준 입출력이나 다른 파일과 어떤 방식으로도 상호작용해서는 안 된다. main 함수는 선언하지 않는다. 제출한 소스 파일은 위원회가 제공하는 소스 파일(grader.cpp)과 함께 컴파일되고 링크되며, 그 파일이 입출력을 처리하고 제출한 함수들을 호출한다.

• $1 \le N, M \le 10^{18}$
• $0 \le K \le 500000$
• 행과 열은 1부터 번호가 매겨진다.

마지막 연산 후 행렬은 다음과 같다.

0 1 0 0 0
1 2 2 2 1