Нарешті задача без легенди

Дано три масиви $a,b,c$ довжини $n$.

Будується неорієнтований зважений граф, що складається з $n$ вершин, так що ребро між двома різними вершинами $u$ і $v$ існує тоді і тільки тоді, коли $a_u|a_v$ не є надмаскою $b_u\&b_v$, а вага цього ребра буде $c_u+c_v$.

Вам потрібно відповісти на $q$ запитів, кожен з яких визначається двома числами $u$ і $v$. Для кожного запиту потрібно вивести довжину найкоротшого шляху від вершини $u$ до вершини $v$, або $-1$, якщо такого шляху не існує. Довжина шляху — це сума ваг його ребер, а найкоротший шлях — це той, що має мінімальну довжину.

Тут $\mid$ означає бітове OR, а $\&$ означає бітове AND.

Ми вважаємо ціле число $a$ надмаскою цілого числа $b$, якщо і тільки якщо всі біти, які увімкнені в $b$, також увімкнені в $a$, більш формально, якщо $a\&b=b$.

Вхідні дані

Перший рядок містить одне ціле число $n(2\le n\le 10^5)$ — розмір графа.

Другий рядок містить $n$ цілих чисел $a_i(0\le a_i\le 10^{18})$.

Третій рядок містить $n$ цілих чисел $b_i(0\le b_i\le 10^{18})$.

Четвертий рядок містить $n$ цілих чисел $c_i(0\le c_i\le 10^{12})$.

П'ятий рядок містить одне ціле число $q(1\le q\le 10^6)$.

Наступні $q$ рядків містять пару різних цілих чисел $u,v(1\le u,v\le n)$ — вершини, між якими потрібно знайти найкоротший шлях.

Вихідні дані

Для кожного запиту потрібно вивести довжину найкоротшого шляху, або $-1$, якщо такого шляху не існує.

Приклади

Примітка

Граф для першого прикладу.

У першому запиті запитується про найкоротший шлях між вершиною $2$ і $5$, оптимальний шлях — $2$ — $4$ — $5$, довжина — $18+10=28$.

Оцінювання

1. ($6$ балів): $a_1=a_i(1\le i\le n)$, $b_1=b_i(1\le i\le n)$;

2. ($12$ балів): $n\le 100$, $q\le 100$;

3. ($12$ балів): $n\le 1000$;

4. ($12$ балів): $n\le 10000$, $a_i\le 10^6(1\le i\le n)$, $b_i\le 10^6(1\le i\le n)$;

5. ($12$ балів): $c_i=0$;

6. ($25$ балів): $a_i\le 10^{12}(1\le i\le n)$, $b_i\le 10^{12}(1\le i\le n)$;

7. ($71$ балів): без додаткових обмежень.