Lúc rảnh, Bessie thích thử nghiệm vật lý. Cô vừa phát hiện hai loại hạt hạ nguyên tử mới, mootrinos và antimootrinos. Như các cặp vật chất-phản vật chất thông thường, chúng hủy nhau và biến mất khi gặp. Điểm đặc biệt là mỗi khi Bessie nhìn chúng, chúng đảo hướng nhưng giữ nguyên tốc độ.

Trong thí nghiệm mới nhất, cô đặt số chẵn $N$ ($2 \leq N \leq 2 \cdot 10^5$) hạt trên một đường thẳng. Bên trái bắt đầu bằng mootrino rồi hai loại xen kẽ. Hạt thứ $i$ ở $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). Mootrinos ban đầu đi sang phải, antimootrinos sang trái; hạt thứ $i$ có tốc độ cố định $s_i$ đơn vị mỗi giây ($1 \leq s_i \leq 10^9$).

Bessie quan sát ở các thời điểm sau:

• Đầu tiên, $1$ giây sau khi bắt đầu.
• Tiếp theo, $2$ giây sau lần quan sát đầu.
• Tiếp theo, $3$ giây sau lần quan sát thứ hai.
• ...
• Tiếp theo, $n + 1$ giây sau lần quan sát thứ $n$.

Mỗi lần quan sát, cô ghi những hạt đã biến mất.

Thí nghiệm có thể rất lâu nên cô muốn mô phỏng kết quả trước. Với thiết lập đã cho, xác định khi nào, tức là lần quan sát số mấy, cô phát hiện mỗi hạt biến mất. Có thể chứng minh tất cả hạt cuối cùng đều biến mất.

Dữ liệu vào

Mỗi đầu vào chứa $T$ ($1\le T\le 10$) bộ kiểm thử độc lập.

Mỗi bộ có ba dòng: dòng đầu chứa $N$, dòng hai $p_1,\dots,p_N$, dòng ba $s_1\dots,s_N$.

Đảm bảo tổng mọi $N$ không vượt quá $2\cdot 10^5$.

Dữ liệu ra

Với mỗi bộ, in số thứ tự lần quan sát hạt biến mất cho từng hạt, cách nhau bởi dấu cách.

Ví dụ

Dữ liệu vào 1

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

Dữ liệu ra 1

9 9
11 11
1 1
3 3

Ghi chú

Ở bộ đầu, $8$ lần quan sát đầu như sau:

• Mootrino, ban đầu đi sang phải, ở các vị trí $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• Antimootrino, ban đầu đi sang trái, ở các vị trí $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

Đúng ở lần quan sát $9$, hai hạt gặp tại $6$ và hủy nhau.

Ở bộ thứ hai, antimootrino bắt đầu xa hơn $1$ đơn vị về bên phải, nên gặp nhau ở $6.5$ nửa giây trước lần quan sát $11$.

Chỉ cần số thứ tự quan sát, không phải thời gian hay vị trí.

Dữ liệu vào 2

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

Dữ liệu ra 2

1 1 3 3
7 2 2 7

Ghi chú

Với bộ đầu:

• Hai hạt ngoài cùng bên trái gặp ở $2$ đúng lúc quan sát $1$.
• Hai hạt ngoài cùng bên phải gặp ở $6.5$ nửa giây trước lần quan sát $3$.

Nhiệm vụ con

• Đầu vào thứ ba thỏa mãn $N = 2$.
• Đầu vào thứ tư thỏa mãn $N \leq 2000$ và $p_i \leq 10^4$ với mọi cô bò.
• Các đầu vào thứ năm đến thứ bảy thỏa mãn $N \leq 2000$.
• Các đầu vào thứ tám đến thứ mười hai không có ràng buộc bổ sung.

Tác giả bài toán: Aryansh Shrivastava, Benjamin Qi