어떤 회사의 직원 간 관계는 계층 구조로 이루어져 있다. 회사에는 총 $n$명의 직원이 있다. 각 직원에게는 $1$부터 $n$까지의 서로 다른 번호가 부여되어 있으며, 사장의 번호는 $1$이다. 사장을 제외한 모든 직원에게는 정확히 한 명의 직속 상사가 있다. 직원 $i$의 직속 상사 번호는 $p_i$이며, $p_i<i$이다.

$p_x=y$이면 직원 $x$를 직원 $y$의 $1$단계 부하 직원이라고 한다. $k>1$일 때, 직원 $p_x$가 직원 $y$의 $(k-1)$단계 부하 직원이면 직원 $x$를 직원 $y$의 $k$단계 부하 직원이라고 한다.

사장에게 일부 직원을 직무 능력 향상 교육에 보낼 기회가 생겼다. 이를 위해 두 수 $L$과 $R$을 선택하고, 번호 $i$가 $L\le i\le R$을 만족하는 모든 직원을 교육에 보내기로 했다.

$L$과 $R$을 선택하기 전에 사장은 직원들로부터 $m$개의 요청을 받았다. $j$번째 요청은 두 수 $u_j$와 $k_j$로 주어지며, 직원 $u_j$가 자신의 $k_j$단계 부하 직원 중 한 명을 교육에 보내 달라고 요청한다는 뜻이다. 비용을 절약하기 위해 사장은 모든 요청을 충족하면서 교육에 보내는 직원 수가 가능한 한 작아지도록 $L$과 $R$을 선택하려 한다.

회사의 상사와 부하 직원 관계 및 직원들의 요청이 주어졌을 때, 번호가 $L$부터 $R$까지인 모든 직원을 교육에 보내면 모든 요청이 충족되고 교육에 보내는 직원 수가 최소가 되는 두 수 $L$과 $R$을 구하는 프로그램을 작성하라. 최적의 쌍 $L,R$이 여러 개라면 그중 $L$이 가장 작은 쌍을 찾아야 한다.

입력

첫째 줄에는 회사의 직원 수 $n$이 주어진다($2\le n\le200\,000$). 둘째 줄에는 직원들의 직속 상사 번호를 나타내는 $n-1$개의 수 $p_2,p_3,\ldots,p_n$이 주어진다($1\le p_i<i$).

셋째 줄에는 직원들의 요청 수 $m$이 주어진다.

다음 $m$개의 줄에는 직원들의 요청을 나타내는 두 정수 $u_j,k_j$가 각각 주어진다($1\le u_j<n$, $1\le k_j<n$). 직원 $u_j$에게 $k_j$단계 부하 직원이 적어도 한 명 존재함이 보장된다.

출력

구하려는 두 수 $L$과 $R$을 출력한다. 최적의 쌍 $(L,R)$이 여러 개라면 $L$이 가장 작은 쌍을 출력해야 한다.

예제

입력 1

7
1 1 2 2 3 3
3
1 1
3 1
1 2

출력 1

3 6

참고

번호가 $3,4,5,6$인 직원들이 능력 향상 교육에 보내진다. 직원 $3$은 직원 $1$의 $1$단계 부하 직원이고, 직원 $4$는 직원 $1$의 $2$단계 부하 직원이며, 직원 $6$은 직원 $3$의 $1$단계 부하 직원이다.

서브태스크

각 서브태스크의 점수는 해당 서브태스크와 필요한 서브태스크의 모든 테스트를 통과한 경우에만 주어진다.

최종 채점 결과 정보

요청하면 각 서브태스크의 점수를 알려 준다.