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$번째 관측 $n + 1$초 뒤입니다.

각 관측에서 어떤 입자가 사라졌는지 기록합니다.

실험이 매우 오래 걸릴 수 있어서 결과를 먼저 시뮬레이션하고 싶습니다. 실험 설정을 보고 각 입자의 소멸을 언제, 즉 몇 번째 관측에서 발견할지 구하세요. 모든 입자가 결국 사라짐을 보일 수 있습니다.

입력

각 입력은 독립적인 $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$단위 더 오른쪽에서 시작하여 $11$번째 관측 반 초 전에 $6.5$에서 만납니다.

시각이나 위치가 아닌 관측 번호만 중요합니다.

입력 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

참고

첫 케이스에서는:

• 맨 왼쪽 두 입자는 정확히 $1$번째 관측에서 $2$에서 만납니다.
• 맨 오른쪽 두 입자는 $3$번째 관측 반 초 전에 $6.5$에서 만납니다.

서브태스크

• 입력 셋은 $N = 2$를 만족합니다.
• 입력 넷은 $N \leq 2000$과 모든 소에 대해 $p_i \leq 10^4$를 만족합니다.
• 입력 다섯부터 일곱까지는 $N \leq 2000$을 만족합니다.
• 입력 여덟부터 열둘까지는 추가 제약이 없습니다.

문제 작성자: Aryansh Shrivastava, Benjamin Qi