트리와 쿼리 10

정점이 $N$개인 트리가 있다. 트리는 사이클이 없는 연결 무방향 그래프다. 정점에는 1번부터 $N$번까지 번호가 붙어 있고, 정점마다 정수 가중치가 하나씩 있다.

아래 두 종류의 쿼리를 처리하는 프로그램을 작성하시오.

• 1 u v: $u$에서 $v$로 가는 경로 위의 정점을 지나는 순서대로 늘어놓았을 때, 연속한 구간의 가중치 합 중 최댓값을 구한다. 빈 구간도 고를 수 있으므로 답은 항상 0 이상이다.
• 2 u v w: $u$에서 $v$로 가는 경로 위의 모든 정점의 가중치를 $w$로 바꾼다.

트리에서 두 정점을 잇는 경로는 하나뿐이므로 각 쿼리가 가리키는 경로는 유일하다. $u$와 $v$가 같으면 경로는 그 정점 하나로 이루어진다.

첫째 줄에 정점의 개수 $N$ ($2 \le N \le 100{,}000$)이 주어진다.

둘째 줄에 1번 정점부터 $N$번 정점까지의 가중치가 순서대로 주어진다. 가중치는 절댓값이 10,000 이하인 정수다.

셋째 줄부터 $N-1$개 줄에 걸쳐 간선이 잇는 두 정점의 번호 $u$와 $v$가 주어진다. 주어지는 간선은 트리를 이룬다.

다음 줄에 쿼리의 개수 $M$ ($1 \le M \le 100{,}000$)이 주어진다.

다음 $M$개 줄에 쿼리가 한 줄에 하나씩 1 u v 또는 2 u v w 형식으로 주어진다. $1 \le u, v \le N$이고, $w$는 절댓값이 10,000 이하인 정수다.

1번 쿼리마다 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다. 2번 쿼리는 아무것도 출력하지 않는다.