Travelling Businessmen Problem

There are $N$ cities numbered 1 to $N$, connected by $M$ bidirectional roads. Every city is reachable from every other city. City $i$ has economic value $S_i$.

There are $Q$ queries to process in order. Each query consists of three integers $A_i$, $B_i$ and $C_i$.

If $A_i = 0$, change the economic value of city $B_i$ to $C_i$.

If $A_i = 1$, assume two businessmen start in city $B_i$ and city $C_i$. They agree on a nonnegative integer $X$. On each of the next $X$ days, each businessman moves to a city adjacent to the one he is in. Staying in place is not allowed, but revisiting cities is allowed. After $X$ days, consider the absolute difference of the economic values of the two cities they occupy, and minimize it over all choices of $X$ and all walks. Output that minimum. The two businessmen may finish in the same city. Each query chooses its own $X$ independently.

The first line contains $N$ and $M$ ($1 \le N \le 100000$, $1 \le M \le 200000$). The second line contains the economic values $S_1, S_2, \dots, S_N$ ($0 \le S_i \le 1000000000$). Each of the next $M$ lines contains two cities $u_i$ and $v_i$ joined by a road ($1 \le u_i, v_i \le N$, $u_i \ne v_i$). Every city is reachable from every other city. The next line contains $Q$ ($1 \le Q \le 100000$). Each of the next $Q$ lines contains one query $A_i$, $B_i$ and $C_i$ ($0 \le A_i \le 1$). If $A_i = 0$ then $1 \le B_i \le N$ and $0 \le C_i \le 1000000000$. If $A_i = 1$ then $1 \le B_i, C_i \le N$. At least one query has $A_i = 1$.

For each query with $A_i = 1$, print the minimum achievable difference of economic values on its own line. The value of $X$ is independent between queries.

Study how the set of reachable cities changes as $X$ grows. Moving to a neighbor and back extends a walk by 2, so reachability depends on the parity of $X$. If the graph has an odd cycle, the two businessmen can always meet in one city. If the graph is bipartite, each businessman stays on the side fixed by the start city and the parity of $X$. Two starts on the same side always give 0. Two starts on opposite sides give the closest pair of economic values across the two sides.