정수가 적힌 모자

$n$명의 현명한 사람이 있다. 각 사람은 모자를 쓰고 있고, 모자에는 정수가 적혀 있다. 각 사람은 다른 사람들의 모자에 적힌 수는 볼 수 있지만 자기 모자의 수는 볼 수 없다. $a_i$는 $i$번째 현명한 사람의 모자에 적힌 수를 나타낸다.

길이가 $n-1$인 정수 배열 $b$와 $c$도 주어진다. 모자에 정수를 배정한 결과가 다음 조건 중 하나 이상을 만족하는 $i$ (단, $1 \le i \le n-1$)가 적어도 하나 존재하면 이 배정을 유효하다고 한다.

1. $a_{i+1} < a_i + b_i$
2. $a_{i+1} > a_i + c_i$

현명한 사람들은 실제 배정, 즉 배열 $a$가 유효하다는 것을 알고 있다.

다음 과정이 진행된다. 매일 첫 번째 사람부터 차례로 확인한다. 그날 시작할 때 $a_i \neq x$인 정수 $x$를 알고 있는 $i$번째 현명한 사람이 있으면, 즉 자기 모자에 적히지 않았다고 확실히 아는 수가 있으면, 그 사람은 그날 끝에 이를 발표하고 과정이 끝난다. 그런 사람이 없으면 과정은 다음 날로 넘어가 같은 방식으로 이어진다.

과정이 끝나는지 판단하고, 끝난다면 그 날짜를 구하라.

첫 줄에 현명한 사람의 수를 나타내는 정수 $n$ ($2 \le n \le 10^5$)이 주어진다.

둘째 줄에 정수 $a_i$ ($-10^{10} \le a_i \le 10^{10}$)가 $n$개 주어진다.

셋째 줄에 정수 $b_i$ ($-10^{10} \le b_i \le 10^{10}$)가 $n-1$개 주어진다.

넷째 줄에 정수 $c_i$ ($-10^{10} \le c_i \le 10^{10}$)가 $n-1$개 주어진다.

배열 $a$가 유효하다는 것이 보장된다.

과정이 끝나지 않으면 -1을 출력한다. 그렇지 않으면 과정이 끝나는 날짜를 출력한다.

첫 번째 예제를 보자. 배열 $b$와 $c$가 주는 제약은 "모든 정수가 같지는 않다"로 바꿔 쓸 수 있다.

첫째 날에는 어떤 현명한 사람도 자기 모자에 적히지 않은 수를 추론할 수 없다.

둘째 날에는 세 번째 현명한 사람이 다음을 안다. 자기 모자의 수가 2라면, 첫째 날 첫 번째 현명한 사람은 다른 두 사람의 모자에 모두 2가 적힌 것을 보고 자기 모자에 2가 없다는 것을 추론했을 것이다. 따라서 둘째 날 세 번째 현명한 사람은 자기 모자에 2가 적혀 있지 않다는 것을 안다.

이 설명은 읽기 쉬운가? 아마 아닐 것이다. 더 읽기 쉽게 쓸 수 있었을까? 아마 그렇지 못할 것이다.