길드

어떤 게임에 $N$명의 사용자들이 있다. 이 사용자들은 친구 관계를 맺고 있는데, 친구 관계인 쌍의 개수가 정확히 $N-1$이라고 한다. 또, 어떤 두 사용자를 보더라도 한번 이상의 친구 관계로 연결이 되어 있다고 한다. 각 사용자는 실력 값을 가지고 있다. 실력 값은 정수 값이다. 실력 값은 음수가 될 수도 있음에 주의하라.

위 그림은 $8$명의 사용자와 그 친구 관계, 그리고 각 사용자의 실력 값을 보여 준다. 사용자들은 길드를 만들 수 있는데, 길드는 $1$명 이상의 사용자를 포함해야 한다. 또, 같은 길드에 포함된 두명의 사용자는 길드에 포함된 사용자들 간의 친구 관계 한번 이상으로 연결이 되어 있어야 한다. 길드의 실력 값은 길드에 포함된 사용자들의 실력 값의 합이다.

위의 상황에서 가장 실력 값이 큰 길드를 만드는 방법은 실력 값이 $3$과 $2$인 두 사용자가 길드를 만드는 방법이다. 이 경우 길드의 실력 값은 $5$가 된다. 물론 실력 값이 $5$인 사용자 혼자 길드를 만들어도 같은 실력 값을 가진다.

그림에서 제일 위쪽의 실력 값이 $-4$인 사용자의 실력이 $3$으로 증가했다고 하자. 그렇다면 이제는 $4$명의 사용자가 모여서 실력 값이 $9$인 길드를 만들 수 있다. 이 상태에서 왼쪽 아래의 실력 값이 $2$인 사용자의 실력이 $5$로 증가했다고 하면, $6$명의 사용자가 모여서 실력 값이 $10$인 길드를 만들 수 있다.

사용자들의 친구 관계, 초기 실력 값과 실력 값이 증가하는 상황들을 입력 받아 모든 상황에서 가장 실력 값이 큰 길드를 만드는 방법을 출력하는 프로그램을 작성하라.

입력 형식

첫째 줄에 사용자의 수를 나타내는 자연수 $N$이 주어진다. ($1 \le N \le 100\,000$) 사용자들은 $1$번부터 $N$번까지 번호가 붙어 있다.

다음 줄에 $1$번 사용자부터 순서대로 실력 값이 $N$개 주어진다. 실력 값은 $-10^9$이상 $10^9$이하의 정수이다.

다음 $N-1$개의 줄에 친구 관계인 사용자들의 번호 쌍이 주어진다. 그 다음 줄에 변화의 개수 $U$가 주어진다. ($0 \le U \le 100\,000$)

다음 $U$개의 줄에 사용자의 실력 변화가 주어진다. 한 변화는 사용자 번호 $n$과, 증가값 $v$의 쌍이다. 번호가 $n$인 사용자의 실력 값이 $v$만큼 더해진다는 뜻이다. 이 때, $v$는 $1$이상 $10^9$이하인 자연수이다.

출력 형식

출력은 $U+1$개의 줄로 구성된다. 첫 줄에는 초기 상태에서 만들 수 있는 가장 실력 값이 높은 길드의 실력 값을 출력한다. 다음 줄부터 각 변화가 적용된 후에 만들 수 있는 가장 실력 값이 높은 길드의 실력 값을 출력한다. 변화는 중첩되어 적용됨에 주의하라.

예제

8
1 -4 3 2 2 -4 -6 5
1 2
2 3
3 4
3 6
6 5
3 7
8 7
2
2 7
5 3

5
9
10

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설