Một máy giải trí tự động thế hệ mới được lắp đặt ở công viên thành phố. Máy có ~n~ nút đánh số từ ~1~ đến ~n~. Trừ nút đầu tiên (nút số 1) ở các nút còn lại đều có một đường ống dẫn đến. Mỗi nút có 2 đường ống dẫn ra, một ống đi sang trái và một ống đi sang phải. Mỗi đường ống có đường kính ban đầu của mình. Khi người chơi bỏ đồng xu vào nút số 1, đồng xu sẽ theo các đường ống trượt xuống dưới. Tới mỗi nút có 2 đường ống dẫn ra, đồng xu luôn trượt theo đường ống có đường kính lớn hơn. Nếu 2 đường ống có cùng đường kính thì đồng xu sẽ trượt theo ống dẫn sang trái. Sau khi đồng xu trượt qua, đường kính của đường ống này sẽ giảm đi 1. Đồng xu không thể trượt theo đường ống có đường kính bằng 0. Nếu tại một nút nào đó, đồng xu không trượt tiếp xuống dưới được thì máy sẽ dừng lại, chờ người chơi bỏ tiếp đồng xu mới.

Ban đầu ở mỗi nút có một đồ chơi. Khi lần đầu tiên đồng xu trượt tới một nút, đồ chơi ở nút đó được đẩy ra ngoài, rơi vào giỏ quà của người chơi.

Hùng rất thích đồ chơi đặt ở nút ~v~. Hãy xác định số lượng xu tối thiểu cần bỏ vào máy để có được đồ chơi này. Nếu không có cách nào nhận được đồ chơi này thì đưa ra số ~-1~.

Yêu cầu: Hãy giúp Hùng xác định số lượng xu tối thiểu cần bỏ vào máy để có được đồ chơi ở nút ~v~. Nếu không có cách nào nhận được đồ chơi này thì đưa ra số ~-1~.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~);
• Dòng thứ ~i~ trong ~n~ dòng sau chứa 4 số nguyên ~a_i, u_i, b_i, w_i~ cho biết từ nút thứ ~i~ đường ống bên trái dẫn tới nút ~a_i~ với đường kính ~u_i~, đường ống bên phải dẫn tới nút ~b_i~ với đường kính ~w_i~. Nếu đường ống bên phải (trái) không có thì cặp số tương ứng là ~0~ và ~0~ (~1 \le a_i, b_i \le n~; ~1 \le u_i, w_i \le 10^9~);
• Dòng cuối cùng chứa số nguyên ~v~ (~1 \le v \le n~).

Kết quả

Một số nguyên là kết quả tìm được.

Ví dụ

TOY.INP

7
2 1 3 2
0 0 6 3
4 1 5 1
0 0 0 0
7 2 0 0
0 0 0 0
0 0 0 0
5

TOY.OUT

3