장난감 자동판매기

E시의 한 놀이공원에 신형 게임기가 설치되었다. 게임기에 동전을 넣으면 동전이 위에서 아래로 갈라지는 관 미로를 따라 내려가는 것을 지켜볼 수 있다. 미로에는 $n$개의 노드가 있고, 노드에는 1부터 $n$까지 번호가 붙어 있다. 동전을 넣으면 동전은 첫 번째 노드에 들어간다. 첫 번째 노드를 제외한 모든 노드에는 위쪽에서 들어오는 관이 정확히 하나 있어, 동전이 그 관을 통해 노드로 들어갈 수 있다. 각 노드에서는 아래로 향하는 관이 최대 두 개 나오며, 하나는 왼쪽으로, 다른 하나는 오른쪽으로 이어진다. 각 관에는 너비가 있다. 동전은 더 넓은 관으로 떨어지고, 두 관의 너비가 같으면 왼쪽 관으로 떨어진다.

동전이 관을 지나고 나면 그 관의 너비는 1만큼 줄어든다. 동전은 너비가 0인 관을 지날 수 없다. 동전이 더 이상 아래로 내려갈 수 없는 노드에 도달하면 게임기가 멈추고, 다음 동전이 들어오기를 기다린다.

처음에 미로의 각 노드에는 장난감이 하나씩 있다. 동전이 어떤 노드에 처음 들어가면, 그 노드에 있는 장난감은 그 동전을 넣은 플레이어가 가져간다.

판크라트는 번호가 $v$인 노드에 있는 장난감을 마음에 들어 한다.

판크라트가 $v$번 노드의 장난감을 얻으려면 게임기에 동전을 몇 개 넣어야 하는지 구하는 프로그램을 작성하시오.

첫째 줄에 미로의 노드 수 $n$이 주어진다. 다음 $n$개 줄에는 모든 노드의 정보가 주어지며, $k$번째 줄에는 번호가 $k$인 노드의 정보가 주어진다.

$k$번 노드의 정보는 네 정수 $a_k$, $u_k$, $b_k$, $w_k$로 이루어진다. $k$번 노드에서 왼쪽 관이 나오면 $a_k$는 그 관이 이어지는 노드의 번호($k < a_k \leqslant n$)이고 $u_k$는 그 관의 너비이다. 왼쪽 관이 없으면 $a_k = u_k = 0$이다. $k$번 노드에서 오른쪽 관이 나오면 $b_k$는 그 관이 이어지는 노드의 번호($k < b_k \leqslant n$)이고 $w_k$는 그 관의 너비이다. 오른쪽 관이 없으면 $b_k = w_k = 0$이다.

마지막 줄에는 판크라트가 마음에 들어 한 장난감이 있는 노드의 번호 $v$가 주어진다($1 \leqslant v \leqslant n$).

첫 번째 노드를 제외한 모든 노드에는 관이 정확히 하나 들어온다.

판크라트가 $v$번 노드에 있는 장난감을 얻으려면 게임기에 넣어야 하는 동전의 수를 한 줄에 출력한다. 원하는 장난감을 얻을 수 없으면 $-1$을 출력한다.

• $1 \le n \leqslant 10^5$
• $1 \le u_k, w_k \leqslant 10^9$

첫 번째 예에서 첫 번째 동전은 다음 경로를 따라 미로를 지나며, 플레이어는 1, 3, 4번 노드의 장난감을 얻는다:

두 번째 동전은 다음 경로를 따라 미로를 지나며, 플레이어는 2번과 6번 노드의 장난감을 얻는다:

세 번째 동전은 다음 경로를 따라 미로를 지나며, 플레이어는 5번과 7번 노드의 장난감을 얻는다: