Nəhayət, Legendası Olmayan Problem

Üç ədəd $a,b,c$ uzunluğu $n$ olan massivlər verilir.

Biz $n$ zirvədən ibarət istiqamətsiz çəkili qrafik quracağıq ki, iki fərqli zirvə $u$ və $v$ arasında bir kənar yalnız $a_u|a_v$ deyil $b_u\&b_v$-nin supermaskı olduqda mövcuddur və bu kənarın çəkisi $c_u+c_v$ olacaq.

Siz $q$ sorğuya cavab verməlisiniz, hər biri iki ədəd $u$ və $v$ ilə müəyyən edilir. Hər bir sorğu üçün, $u$ zirvəsindən $v$ zirvəsinə ən qısa yolun uzunluğunu çıxarmalısınız, ya da belə bir yol yoxdursa $-1$ çıxarmalısınız. Bir yolun uzunluğu onun kənarlarının çəkilərinin cəmidir və ən qısa yol minimal uzunluğa malik olanıdır.

Burada, $\mid$ bitwise OR əməliyyatı deməkdir, və $\&$ bitwise AND əməliyyatı deməkdir.

Bir tam ədəd $a$ yalnız o zaman $b$ tam ədədinin supermaskı hesab olunur ki, $b$-də açıq olan bütün bitlər $a$-da da açıq olsun, daha rəsmi desək, $a\&b=b$.

Giriş verilənləri

Birinci sətir bir tam ədəd $n(2\le n\le 10^5)$ — qrafikin ölçüsü.

İkinci sətir $n$ tam ədəd $a_i(0\le a_i\le 10^{18})$ ehtiva edir.

Üçüncü sətir $n$ tam ədəd $b_i(0\le b_i\le 10^{18})$ ehtiva edir.

Dördüncü sətir $n$ tam ədəd $c_i(0\le c_i\le 10^{12})$ ehtiva edir.

Beşinci sətir bir tam ədəd $q(1\le q\le 10^6)$ ehtiva edir.

Sonrakı $q$ sətirində fərqli tam ədədlər $u,v(1\le u,v\le n)$ — ən qısa yolu tapmalısınız.

Çıxış verilənləri

Hər bir sorğu üçün, ən qısa yolun uzunluğunu çıxarmalısınız, ya da belə bir yol yoxdursa $-1$ çıxarmalısınız.

Nümunələr

Qeyd

İlk nümunə üçün Qrafik.

İlk sorğuda $2$ və $5$ zirvələri arasında ən qısa yol soruşulur, optimal yol $2$ — $4$ — $5$-dir, uzunluğu $18+10=28$-dir.

Qiymətləndirmə

1. ($6$ xal): $a_1=a_i(1\le i\le n)$, $b_1=b_i(1\le i\le n)$;

2. ($12$ xal): $n\le 100$, $q\le 100$;

3. ($12$ xal): $n\le 1000$;

4. ($12$ xal): $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$ xal): $c_i=0$;

6. ($25$ xal): $a_i\le 10^{12}(1\le i\le n)$, $b_i\le 10^{12}(1\le i\le n)$;

7. ($71$ xal): əlavə məhdudiyyət yoxdur.