בזמנה הפנוי 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