تحب Bessie ممارسة الفيزياء التجريبية في فراغها. اكتشفت مؤخرًا جسيمين دون ذريين جديدين، mootrinos وantimootrinos. مثل أزواج المادة والمادة المضادة العادية، يفنيان بعضهما ويختفيان عند اللقاء. لكنهما مميزان بأنهما يعكسان اتجاه الحركة، مع الحفاظ على السرعة، كلما نظرت إليهما Bessie.

في تجربتها الأخيرة، وضعت عددًا زوجيًا $N$ ($2 \leq N \leq 2 \cdot 10^5$) من الجسيمات على خط. يبدأ من اليسار بـmootrino ثم يتناوب النوعان. الجسيم $i$ في الموضع $p_i$ ($0 \leq p_1 < \cdots < p_N \leq 10^{18}$). تتحرك mootrinos بدايةً يمينًا وantimootrinos يسارًا، وبسرعة ثابتة للجسيم $i$ مقدارها $s_i$ وحدة في الثانية ($1 \leq s_i \leq 10^9$).

تراقب Bessie في الأوقات التالية:

• أولًا، بعد $1$ ثانية من بداية التجربة.
• ثم بعد $2$ ثانية من المراقبة الأولى.
• ثم بعد $3$ ثانية من المراقبة الثانية.
• ...
• ثم بعد $n + 1$ ثانية من المراقبة $n$.

تسجل في كل مراقبة أي الجسيمات اختفت.

قد تستغرق التجربة وقتًا طويلًا جدًا، لذا تريد محاكاة النتيجة أولًا. حسب إعداد التجربة، حدد متى، أي في أي رقم مراقبة، ستلاحظ اختفاء كل جسيم. يمكن إثبات أن جميع الجسيمات ستختفي في النهاية.

الإدخال

يحتوي كل إدخال على $T$ ($1\le T\le 10$) حالات مستقلة.

كل حالة ثلاثة أسطر: الأول يحتوي على $N$، والثاني على $p_1,\dots,p_N$، والثالث على $s_1\dots,s_N$.

يُضمن أن مجموع جميع $N$ لا يتجاوز $2\cdot 10^5$.

الإخراج

لكل حالة، اطبع رقم مراقبة اختفاء كل جسيم، مفصولة بفراغات.

أمثلة

الإدخال 1

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

الإخراج 1

9 9
11 11
1 1
3 3

ملاحظة

في الحالة الأولى، تبدو المراقبات $8$ الأولى هكذا:

• يظهر mootrino، المتحرك بدايةً يمينًا، في المواضع $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$.
• يظهر antimootrino، المتحرك بدايةً يسارًا، في المواضع $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$.

عند المراقبة $9$ بالضبط، يلتقيان في الموضع $6$ ويفنيان بعضهما.

في الحالة الثانية يبدأ antimootrino أبعد يمينًا بمقدار $1$ وحدة، فيلتقيان في $6.5$ قبل المراقبة $11$ بنصف ثانية.

نهتم بأرقام المراقبات فقط، لا الأزمنة أو المواضع.

الإدخال 2

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

الإخراج 2

1 1 3 3
7 2 2 7

ملاحظة

بالنسبة للحالة الأولى:

• يلتقي الجسيمان الأيسرَان في $2$ عند المراقبة $1$ بالضبط.
• يلتقي الجسيمان الأيمنان في $6.5$ قبل المراقبة $3$ بنصف ثانية.

المهام الفرعية

• يحقق الإدخال الثالث $N = 2$.
• يحقق الإدخال الرابع $N \leq 2000$ و$p_i \leq 10^4$ لكل الأبقار.
• تحقق الإدخالات من الخامس إلى السابع $N \leq 2000$.
• الإدخالات من الثامن إلى الثاني عشر بلا قيود إضافية.

مؤلفا المسألة: Aryansh Shrivastava وBenjamin Qi