여행하는 사업가 문제

$N$개의 도시가 있고 각 도시에는 1부터 $N$까지 번호가 붙어 있다. 도시는 $M$개의 양방향 도로로 연결되며 어떤 도시에서도 다른 모든 도시로 이동할 수 있다. 도시 $i$는 경제값 $S_i$를 가진다.

$Q$개의 질의가 순서대로 주어진다. 각 질의는 세 정수 $A_i$, $B_i$, $C_i$로 이루어진다.

$A_i = 0$이면 도시 $B_i$의 경제값을 $C_i$로 바꾼다.

$A_i = 1$이면 두 사업가가 각각 도시 $B_i$와 도시 $C_i$에서 출발한다고 가정한다. 두 사람은 음이 아닌 정수 $X$를 함께 정하고 $X$일 동안 매일 반드시 현재 도시와 인접한 도시로 이동한다. 제자리에 머무를 수는 없지만 이미 방문한 도시를 다시 방문할 수는 있다. $X$일이 지난 뒤 두 사람이 머무는 도시의 경제값 차이의 절댓값이 가장 작아지도록 하며 그 최솟값을 출력한다. 두 사람이 같은 도시에 머물 수도 있다. $X$는 각 질의마다 독립적으로 정한다.

첫째 줄에 도시와 도로의 수 $N$, $M$이 주어진다 ($1 \le N \le 100000$, $1 \le M \le 200000$). 둘째 줄에 각 도시의 경제값 $S_1, S_2, \dots, S_N$이 주어진다 ($0 \le S_i \le 1000000000$). 다음 $M$개의 줄에는 도로가 연결하는 두 도시 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le N$, $u_i \ne v_i$). 어떤 도시에서도 다른 모든 도시로 이동할 수 있다. 다음 줄에는 질의의 수 $Q$가 주어진다 ($1 \le Q \le 100000$). 다음 $Q$개의 줄에는 각 질의 $A_i$, $B_i$, $C_i$가 주어진다 ($0 \le A_i \le 1$). $A_i = 0$이면 $1 \le B_i \le N$이고 $0 \le C_i \le 1000000000$이며 $A_i = 1$이면 $1 \le B_i, C_i \le N$이다. $A_i = 1$인 질의가 하나 이상 있다.

$A_i = 1$인 각 질의에 대해 두 사업가가 도달할 수 있는 경제값 차이의 최솟값을 한 줄에 하나씩 출력한다. $X$의 값은 각 질의마다 독립이다.

$X$가 커질 때 각 사업가가 도달할 수 있는 도시가 어떻게 달라지는지 살펴본다. 이웃 도시로 이동했다가 되돌아오면 이동 일수를 2만큼 늘릴 수 있으므로 도달 가능한 도시는 $X$의 홀짝에 따라 정해진다. 그래프에 홀수 길이 사이클이 있으면 두 사업가는 항상 같은 도시에서 만날 수 있다. 그래프가 이분 그래프이면 각 사업가는 시작 도시와 $X$의 홀짝에 따라 정해진 쪽에 머문다. 같은 쪽에서 출발한 두 사업가의 답은 항상 0이며 다른 쪽에서 출발한 경우에는 양쪽에 걸친 가장 가까운 경제값 쌍이 답이 된다.