35035번 - 레이저

문제

전설적인 대부호 준혁이는 자신의 막대한 재산을 보호하기 위해 세상에서 가장 안전한 금고를 특수 제작했다. 이 금고는 2차원 평면 상에서 $x$축 방향으로 $N+1,ドル $y$축 방향으로 $L$의 크기를 가지는 직사각형 형태의 복도로 모델링할 수 있다.

준혁이는 도둑을 막기 위해 복도의 $x$좌표가 1,2,ドル\dots ,N$인 각 지점에 양쪽 벽($y=0$과 $y=L$)에서 수직으로 발사되는 레이저 보안 장치를 설치했다. 각 지점에는 다음과 같은 두 개의 레이저가 존재한다.

• $x=i$이고 $y\in[0 , A_i)$인 $(x , y)$를 감시하는 레이저
• $x=i$이고 $y\in (L-B_i , L]$인 $(x,y)$를 감시하는 레이저

오작동을 막기 위해 모든 $i$에 대하여 레이저는 $A_i+B_i<L$를 지키며 설치된다. 즉, 같은 $x$좌표에 있는 두 레이저는 서로 겹치거나 닿지 않는다.

준혁이는 보안 시스템의 빈틈을 점검하기 위해 가상의 침입 시뮬레이션을 돌려보려고 한다. 구체적으로 준혁이는 침입자가 $(x_s+0.5,y_s)$ 위치에서 출발하여 $(x_t+0.5,y_t)$ 위치까지 다음과 같은 제약을 따르며 이동하는 최단거리를 계산해보려고 한다.

• 침입자는 평면 상의 한 점으로 간주한다. 즉, 침입자의 크기는 무시한다.
• 침입자는 항상 $x$축 또는 $y$축에 평행한 방향으로만 이동할 수 있다.
• 침입자는 금고의 벽이나 레이저가 감시하는 영역을 지나갈 수 없다.

준혁이는 보안을 강화하기 위해 수시로 레이저의 길이를 변경하기도 한다. 준혁이를 도와 침입자의 최단 경로를 계산하거나 레이저의 설정을 바꾸는 $Q$개의 쿼리를 수행해보자.

입력

첫 번째 줄에 $N,L,Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $A_1,A_2,\dots ,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $B_1,B_2,\dots ,B_N$이 공백으로 구분되어 주어진다.

네 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. 쿼리는 다음 두 가지 형식 중 하나이다.

• 1 $x_s$ $y_s$ $x_t$ $y_t$: 현재의 레이저 배치 상에서 침입자가 $(x_s+0.5,y_s)$에서 출발하여 $(x_t+0.5,y_t)$까지 이동하는 최단 거리를 출력한다. (0ドル\le x_s,x_t\le N,ドル 0ドル<y_s,y_t<L$)
• 2 $i$ $a$ $b$: $i$번째 위치의 레이저 길이를 $A_i=a,ドル $B_i=b$로 변경한다. (1ドル\le i\le N,ドル 1ドル\le a,b,ドル $a+b<L$)

출력

1번 쿼리가 주어질 때마다 한 줄에 하나씩 해당 경로의 최단 거리를 정수로 출력한다. 주어진 제약 조건 하의 모든 입력에서 항상 이동이 가능함과 그 최단 거리가 정수임을 증명할 수 있다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le N,Q\le 300,円 000$
• 3ドル\le L\le 10^9$
• 1ドル\le A_i,B_i<L(1\le i\le N)$
• $A_i+B_i<L(1\le i\le N)$
• 모든 1번 쿼리에서 0ドル\le x_s,x_t\le N$이 성립한다.
• 모든 1번 쿼리에서 0ドル<y_s,y_t<L$이 성립한다.
• 모든 2번 쿼리에서 1ドル\le i\le N$이 성립한다.
• 모든 2번 쿼리에서 1ドル\le a,b<L$이 성립한다.
• 모든 2번 쿼리에서 $a+b<L$이 성립한다.

노트

다음은 예제 중 첫 번째 쿼리의 답으로 가능한 경로 중 한 가지이다. 그림의 경로는 레이저에 감시당하지 않으며 $(0.5, 5)$에서 $(3.5, 4)$로 이동하는 경로이며 모든 조건을 만족한다. 침입자의 경로는 레이저의 끝점을 스쳐도 무방하다. 전체 경로의 길이는 10ドル$임을 계산할 수 있다.