산책로

KOI 산에는 $1$번부터 $N$번까지 번호가 부여된 $N$개의 쉼터가 있고, 그 쉼터들을 잇는 $N - 1$개의 양방향 산책로가 있다.

$i$ ($1 \le i \le N$)번 쉼터에 사람이 얼마나 많은지를 나타내는 밀집도는 양의 정수 $A_i$로 나타낼 수 있다.

$j$ ($1 \le j \le N - 1$)번째 산책로는 $j$번 쉼터와 $C_j$번 쉼터를 이으며 ($j + 1 \le C_j \le N$), 그 길이는 $L_j$이다. 즉, 쉼터들은 산책로를 통해 연결된 트리 구조를 이룬다.

고독한 산책가 교준이는 서로 다른 두 쉼터를 골라, 두 쉼터 사이의 유일한 단순 경로를 따라 산책하려고 한다. 어떤 경로를 선택했을 때,

• 경로에 포함된 산책로의 길이의 합을 $S$,
• 경로에 포함된 쉼터의 밀집도의 최댓값을 $M$

이라고 하자. 교준이는 산책을 길게, 그러나 사람이 적은 곳에서 고독하게 즐기고 싶기 때문에, 이 경로의 만족도는 $S - M$으로 정의된다.

교준이가 산책할 경로의 만족도를 최대화하기 위해서는 어떤 두 쉼터를 골라야 하는지 계산하는 프로그램을 작성하라.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 300\,000$
• 정수 $i$ ($1 \le i \le N$)에 대하여 $1 \le A_i \le 10^{18}$
• 정수 $j$ ($1 \le j \le N - 1$)에 대하여 $j + 1 \le C_j \le N$이고 $1 \le L_j \le 10^{12}$

1. (8점) $N \le 300$
2. (12점) $N \le 7\,500$
3. (11점) $A_1 = A_2 = \cdots = A_N$
4. (15점) 정수 $j$ ($1 \le j \le N - 1$)에 대하여 $C_j = j + 1$
5. (17점) $C_1 = C_2 = \cdots = C_{N - 1} = N$
6. (36점) 집합 $\left\{ A_1, A_2, \cdots, A_N \right\}$에 등장하는 서로 다른 정수의 개수는 $20$ 이하이다.
7. (51점) 추가 제약 조건 없음.

첫 줄에 정수 $N$이 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N - 1$개의 정수 $C_1, C_2, \cdots, C_{N - 1}$이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N - 1$개의 정수 $L_1, L_2, \cdots, L_{N - 1}$이 공백으로 구분되어 차례대로 주어진다.

첫 줄에 경로의 만족도가 최대가 되는 서로 다른 두 쉼터의 번호를 공백으로 구분하여 출력한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.