31218번 - 자료 구조의 왕 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 585 | 306 | 255 | 49.515% |
문제
흐즈로는 어느 날 집 주변 잔디밭에 무성히 자란 잔디를 보고, 새로 산 잔디깎이 로봇의 성능을 시험해 보기로 했습니다. 잔디밭은 $n$개의 행과 $m$개의 열을 가진 2차원 격자로 구성되어 있으며, 그 중 $r$번째 행의 $c$번째 열에 해당하는 칸을 $(r,c)$로 표기합니다. 초기에 잔디밭의 모든 칸에는 잔디가 있습니다.
잔디깎이 로봇에 네 정수 $d_y$, $d_x$, $y$, $x$를 입력하면, 초기에 $(y,x)$ 에서 출발하여 $\langle d_y,d_x \rangle$ 방향으로 이동하도록 설정됩니다. 이때 $|d_y|+|d_x|=1$이 항상 성립해야 합니다. 다시 말해, 잔디깎이 로봇은 항상 일정한 방향을 따라 이동하며, 상하좌우로 인접한 칸으로만 이동합니다. 잔디깎이 로봇은 다음과 같이 작동합니다.
- $(y,x)$에 잔디가 없다면 잔디 깎기를 종료합니다.
- $(y,x)$에 있는 잔디를 제거합니다.
- 조건 $y+d_y<1$, $y+d_y>n$, $x+d_x<1$, $x+d_x>m$ 중 하나 이상이 참이라면 잔디 깎기를 종료합니다.
- $(y, x)$를 $(y+d_y, x+d_x)$로 변경한 뒤, 1번으로 돌아갑니다.
흐즈로는 성능 시험의 일환으로 다음과 같은 쿼리 $Q$개에 대한 답을 찾아야 합니다.
- $1 \ d_y \ d_x \ y \ x$: 방향이 $\langle d_y,d_x \rangle$로 설정된 잔디깎이 로봇을 $(y,x)$에서 출발시킨 뒤, 해당 잔디깎이 로봇의 잔디 깎기가 끝날 때까지 대기합니다.
- $2 \ y \ x$: 쿼리가 들어오기 전 시작한 잔디 깎기가 순서대로 끝나고 난 뒤 $(y,x)$의 상태를 출력합니다. $(y,x)$에 잔디가 있다면 상태는 $0$, 잔디가 없다면 상태는 $1$입니다.
- $3$: 잔디밭에 잔디가 남아있는 칸의 개수를 출력합니다.
모든 쿼리에 대해 정확한 답을 알지 못하면 잔디깎이 로봇이 제대로 작동하는지 확인할 수 없습니다. 주어진 $Q$개의 쿼리에 대해 정확히 대답하는 프로그램을 작성해 주세요.
입력
첫 번째 줄에 행의 개수 $n$, 열의 개수 $m$, 쿼리의 개수 $Q$가 공백으로 분리되어 주어집니다. ($1 \le n,m \le 1000$, $1 \le Q \le 2\times 10^5$)
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어집니다. 모든 쿼리는 본문에서 주어진 종류 중 하나입니다.
모든 쿼리에 대해 $1 \le y \le n$, $1 \le x \le m$이며, 모든 $1$번 쿼리에 대해 $|d_y|+|d_x|=1$입니다.
출력
모든 $2$, $3$번 쿼리에 대해 정답을 한 줄에 하나씩 출력합니다.
예제 입력 1
3 3 8 3 2 2 2 1 1 0 1 2 1 0 -1 3 3 2 2 2 2 3 3 2 3 1 3
예제 출력 1
9 0 1 1 0 5