무인 택시

이노폴리스 중앙 광장에서 무인 택시의 시연이 열릴 예정이다. 광장은 $n \times m$ 미터 크기의 직사각형이며 단위 정사각형으로 나뉘어 있다. 행은 1번부터 $n$번까지, 열은 1번부터 $m$번까지 번호가 매겨져 있다. 각 정사각형은 행 번호 $r$과 열 번호 $c$로 정해진다. 택시는 단위 정사각형 사이를 움직인다. 한 번의 이동으로 현재 정사각형에서 변을 공유하는 정사각형으로 갈 수 있다.

올겨울에는 눈이 많이 내려서, 시연 중에 무인 제설차로 광장을 치울 계획이다. 제어 시스템은 아직 시험 중이므로, 광장에는 무인 차량이 한 번에 한 대만 있을 수 있다.

시연 내내 눈이 계속 내린다. 각 단위 정사각형의 눈 깊이는 항상 음이 아닌 정수다. 택시에는 음이 아닌 정수인 통과 능력이 있다. 택시는 눈 깊이가 통과 능력 이하인 정사각형 위에서만 움직일 수 있다. 엔지니어는 각 주행 전에 택시의 통과 능력을 설정할 수 있다.

처음에는 광장 전체의 눈 깊이가 0이다. 매 시간이 시작될 때마다 모든 정사각형의 눈 깊이가 1씩 증가한다. 그다음 제어 시스템은 다음 세 가지 작업 중 하나를 수행한다. 각 작업은 정확히 한 시간이 걸린다.

1. 행 $r_i$를 따라 제설차를 운행한다. 그러면 그 행에 있는 모든 정사각형의 눈 깊이가 0이 된다.
2. 열 $c_i$를 따라 제설차를 운행한다. 그러면 그 열에 있는 모든 정사각형의 눈 깊이가 0이 된다.
3. 택시를 시연한다. 통과 능력을 $k_i$로 설정하고 출발 정사각형과 도착 정사각형을 고른 뒤, 출발 정사각형에서 도착 정사각형까지 주행을 시도한다.

출발에서 도착까지 주행이 가능한 조건은 다음과 같다. 출발 정사각형에서 시작해 도착 정사각형에서 끝나는 정사각형의 경로가 있고, 경로에서 이웃한 두 정사각형이 변을 공유하며, 경로에 포함된 모든 정사각형의 눈 깊이가 통과 능력 이하이면 주행이 가능하다. 통과 능력으로 주행이 가능하면 택시는 이동 횟수가 가장 적은 경로를 사용해야 한다.

각 주행에 대해 주행이 가능한지 판단하고, 가능하다면 필요한 최소 이동 횟수를 구한다.

첫 줄에는 세 정수 $n$, $m$, $q$가 주어진다. 이는 광장의 크기와 제어 시스템이 수행하는 작업의 수다($1 \le n, m \le 10^6$, $1 \le q \le 300\,000$). 다음 $q$개 줄에는 아래 형식 중 하나의 작업이 한 줄에 하나씩 주어진다.

• 1 r_i: 행 $r_i$를 따라 제설차를 운행한다($1 \le r_i \le n$).
• 2 c_i: 열 $c_i$를 따라 제설차를 운행한다($1 \le c_i \le m$).
• 3 r_{i,1} c_{i,1} r_{i,2} c_{i,2} k_i: 통과 능력을 $k_i$로 설정하고, 정사각형 $(r_{i,1}, c_{i,1})$에서 정사각형 $(r_{i,2}, c_{i,2})$까지 주행을 시도한다($1 \le r_{i,1}, r_{i,2} \le n$, $1 \le c_{i,1}, c_{i,2} \le m$, $0 \le k_i \le q$, 두 정사각형은 서로 다르다).

입력에는 3번 유형의 작업이 적어도 하나 있다.

3번 유형의 작업마다 한 줄을 출력한다. 주행이 가능하면 필요한 최소 이동 횟수를, 불가능하면 $-1$을 출력한다.

그림은 예제에서 각 작업 전의 정사각형별 눈 깊이와, 주행에 성공한 각 경우의 최적 경로를 보여준다.