우편 개혁

플랫랜드에 개혁의 바람이 불고 있다. 최근 도로를 개혁해서 나라의 모든 도시가 서로 이어지게 되었고, 두 도시 사이의 경로는 단 하나뿐이다. 마법사도 개혁하여 각 도시에 마법사가 정확히 한 명씩 남았다. 이제 우편 제도 개혁이 시작되었다.

최근 설립된 우편 회사 "Экс-Федя"는 공동 소포라는 독특한 서비스를 내놓았다. 이 서비스를 쓰면 어떤 경로 위에 있는 모든 도시의 주민에게 일반 소포 요금으로 소포를 보낼 수 있다. 놀랍게도 이 서비스를 쓰기 시작한 쪽은 플랫랜드의 마법사뿐이며, 그들은 서로에게 마법 선인장을 대량으로 보내고 있다.

회사에 예상치 못한 문제가 생겼다. 마법사는 모두 탑에 살고, 탑으로 올라가는 계단은 짓지 않는다. 게다가 탑의 높이를 수시로 바꾼다. 따라서 높이가 $h$인 탑에 사는 마법사에게 소포를 전하려면 배달원이 최소 $h$ 미터의 밧줄을 가지고 있어야 한다.

당신은 물류 부서를 맡았다. 탑의 높이와 그 변화 정보를 바탕으로, 도시 $i$와 $j$ 사이로 소포를 배달하는 배달원에게 지급해야 할 밧줄의 최소 길이를 구하라.

첫 줄에 플랫랜드의 도시 수 $n$ ($1 \le n \le 50000$)이 주어진다. 둘째 줄에는 각 도시의 탑 높이를 나타내는 양의 정수 $n$개가 주어지며, 모두 $10^5$를 넘지 않는다. 다음 $n-1$개 줄에는 도로 하나씩을 나타내는 두 정수 $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어진다. 그다음 줄에 질의 수 $k$ ($1 \le k \le 100000$)가 주어진다. 이후 $k$개 줄에는 다음 중 하나의 질의가 주어진다.

• 도시 $i$의 마법사가 탑 높이를 $h$로 바꾸었음을 알리는 질의. 형식은 $!$ $i$ $h$이며, $1 \le i \le n$, $1 \le h \le 10^5$이다.
• 배달원이 도시 $i$에서 $j$까지 경로 위의 모든 도시(양 끝 포함)에 소포를 전하기 위해 밧줄을 요청하는 질의. 형식은 $?$ $i$ $j$이며, $1 \le i, j \le n$이다.

배달 질의마다 배달원에게 지급해야 할 밧줄의 최소 길이를 한 줄에 하나씩 출력한다.