Cơ Học Lượng Tử Bò

Bessie thi nghiem voi $N$ hat (so chan) gom mootrino va antimootrino xen ke tren mot duong thang. Hat $i$ o vi tri $p_i$ voi toc do $s_i$. Mootrino (hat o vi tri le: 1, 3, 5, ...) di sang phai, antimootrino (hat o vi tri chan: 2, 4, 6, ...) di sang trai.

Khi hai hat gap nhau, chung triet tieu va bien mat. Bessie quan sat tai cac thoi diem tich luy $1,3,6,10,\dots$ giay (tuc la sau $1$ giay, them $2$ giay, them $3$ giay, ...). Tai moi lan quan sat, tat ca cac hat con lai doi huong.

Hay xac dinh voi moi hat, no bien mat tai lan quan sat thu may.

Du lieu vao

• Dong 1: So nguyen $T$ ($1\le T\le 10$) -- so test case.
• Voi moi test case:
  • Dong 1: So nguyen $N$ (chan, $2\le N\le 2\times {10}^5$).
  • Dong 2: $N$ so nguyen $p_1,p_2,\dots ,p_N$ ($0\le p_1<p_2<\cdots <p_N\le {10}^{18}$).
  • Dong 3: $N$ so nguyen $s_1,s_2,\dots ,s_N$ ($1\le s_i\le {10}^9$).
• Tong $N$ qua cac test case $\le 2\times {10}^5$.

Du lieu ra

Voi moi test case, in $N$ so nguyen tren mot dong -- lan quan sat ma moi hat bien mat.

Rang buoc

• $2\le N\le 2\times {10}^5$, $N$ chan
• $0\le p_1<p_2<\cdots <p_N\le {10}^{18}$
• $1\le s_i\le {10}^9$
• Tong $N\le 2\times {10}^5$

Vi du