N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 정점은 가중치를 가지고 있다.</p>

아래의 두 쿼리를 수행하는 프로그램을 작성하시오.

• 1 u v: u에서 v로 가는 경로에서 최대 연속합(비어있을 수도 있기 때문에 정답은 0보다 크거나 같다)을 구해 출력한다.
• 2 u v w: u에서 v로 가는 경로 상에 있는 모든 정점의 가중치를 w로 바꾼다.

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄에는 정점의 가중치가 1번 정점부터 순서대로 주어진다.

셋째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.

다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

정점의 가중치는 절댓값이 10,000보다 작거나 같은 정수이다.

출력 형식

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력

5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5

예제 출력

5
9