먼지 청소기

Paolo는 큰 창고의 관리인으로 일한다. 그의 업무 중 두 가지는 청소기를 돌리는 것과 창고 안의 물건을 옮기는 것이다. Paolo는 청소에 대해 실용적인 편이라, 먼지가 너무 쌓여 물건을 더 이상 옮길 수 없게 될 때까지 기다린다. 상황을 더 나쁘게 만드는 것은 그가 최근 직접 청소하는 대신 로봇 청소기를 풀어놓기 시작했다는 점이다. 이 로봇 청소기는 고장 나서 방향을 바꿀 수 없다. 벽에 부딪혀 배터리가 다할 때까지 직선으로만 움직인다.

창고는 $N \times M$ 격자로 나타낼 수 있다. 행은 1번부터 $N$번까지, 열은 1번부터 $M$번까지 번호가 매겨져 있다. 처음에는 모든 칸의 먼지가 0 단위이다. 이후 $Q$일이 지나간다. 매일은 모든 칸의 먼지가 1씩 늘어나면서 시작한다. 그다음 아래 세 가지 중 정확히 하나가 일어난다.

1. $1$ $r$ 형태의 사건은 Paolo가 $r$번 행을 따라 로봇 청소기를 풀어놓는다는 뜻이다. 그러면 그 행의 모든 칸의 먼지가 0이 된다.
2. $2$ $c$ 형태의 사건은 Paolo가 $c$번 열을 따라 로봇 청소기를 풀어놓는다는 뜻이다. 그러면 그 열의 모든 칸의 먼지가 0이 된다.
3. $3$ $r_1$ $c_1$ $r_2$ $c_2$ $k$ 형태의 사건은 Paolo가 $(r_1, c_1)$ 칸에서 $(r_2, c_2)$ 칸으로 무언가를 옮겨야 한다는 뜻이다. $k$는 그 물건의 먼지 내성이다. 물건은 먼지가 $k$ 단위 이하인 칸 위로만 옮길 수 있다. 예를 들어 $(r_1, c_1)$ 또는 $(r_2, c_2)$ 칸의 먼지가 $k$ 단위를 넘으면 이 임무는 완료할 수 없다.

3번 사건마다 Paolo가 물건을 옮기는 데 필요한 최소 걸음 수를 출력한다. 한 걸음에는 변을 공유하는 인접한 칸으로 이동한다. 가장자리에 있는 칸은 인접한 칸이 네 개보다 적다. 물건을 옮길 수 없다면 $-1$을 출력한다.

첫 줄에 세 정수 $N$, $M$, $Q$가 주어진다 ($1 \leq N,M \leq 10^6$, $1 \leq Q \leq 3 \cdot 10^5$).

이어지는 $Q$개의 줄은 각각 하나의 사건을 나타낸다. 각 줄은 사건의 종류 $t$로 시작하며, $t$는 1, 2, 3 중 하나이다. $t = 1$이면 같은 줄에 행 번호 $r$ ($1 \leq r \leq N$)이 주어진다. $t = 2$이면 열 번호 $c$ ($1 \leq c \leq M$)가 주어진다. $t = 3$이면 같은 줄에 $r_1$, $c_1$, $r_2$, $c_2$, $k$의 다섯 정수가 주어진다 ($1 \leq r_1, r_2 \leq N$, $1 \leq c_1, c_2 \leq M$, $0 \leq k \leq Q$).

종류 3의 사건마다 $(r_1, c_1)$과 $(r_2, c_2)$는 서로 다른 칸이다. 종류 3의 사건은 적어도 하나 있다.

종류 3의 사건마다 물건을 옮기는 데 필요한 최소 걸음 수를 한 줄에 출력한다. 옮길 수 없다면 $-1$을 출력한다.