베시는 여가 시간에 실험 물리학을 연구하는 것을 좋아한다. 최근 베시는 무트리노와 반무트리노라는 새로운 아원자 입자 한 쌍을 발견했다. 일반적인 물질과 반물질처럼 무트리노와 반무트리노는 서로 만나면 소멸하여 사라진다. 이 입자들의 독특한 점은 베시가 관찰할 때마다 속력은 유지한 채 운동 방향을 반대로 바꾼다는 것이다.

최근 실험을 위해 베시는 짝수인 \(N\)개의 입자를 일직선 위에 놓았다. 가장 왼쪽에는 무트리노가 있고, 그 뒤로 두 종류의 입자가 번갈아 놓인다. \(i\)번째 입자의 위치는 \(p_i\)이다. 무트리노는 처음에 오른쪽으로 움직이고 반무트리노는 처음에 왼쪽으로 움직이며, \(i\)번째 입자는 초당 \(s_i\)의 일정한 속력으로 움직인다.

베시는 다음 시점에 입자들을 관찰한다.

• 실험을 시작한 뒤 \(1\)초가 지난 시점
• 첫 번째 관찰로부터 \(2\)초가 지난 시점
• 두 번째 관찰로부터 \(3\)초가 지난 시점
• \(\ldots\)
• \(n\)번째 관찰로부터 \(n+1\)초가 지난 시점

각 관찰에서 베시는 어떤 입자가 사라졌는지 기록한다.

이 실험이 끝나기까지는 매우 오랜 시간이 걸릴 수 있으므로, 베시는 먼저 결과를 시뮬레이션하려 한다. 실험의 초기 상태가 주어질 때, 각 입자가 사라진 것을 몇 번째 관찰에서 확인하게 되는지 구하여라. 모든 입자는 결국 사라짐을 증명할 수 있다.

입력

첫째 줄에 독립적인 테스트 케이스의 수 \(T\)가 주어진다. (\(1\le T\le 10\))

각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에 짝수 \(N\)이 주어진다. (\(2\le N\le 2\cdot 10^5\))

둘째 줄에 \(N\)개의 위치 \(p_1,p_2,\ldots,p_N\)이 주어진다. (\(0\le p_1<\cdots<p_N\le 10^{18}\))

셋째 줄에 \(N\)개의 속력 \(s_1,s_2,\ldots,s_N\)이 주어진다. (\(1\le s_i\le 10^9\))

모든 테스트 케이스에 대한 \(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\)번의 관찰 동안 입자들의 위치는 다음과 같다.

• 처음에 오른쪽으로 움직이는 무트리노: \(2\to0\to3\to-1\to4\to-2\to5\to-3\)
• 처음에 왼쪽으로 움직이는 반무트리노: \(10\to12\to9\to13\to8\to14\to7\to15\)

이후 정확히 아홉 번째 관찰에서 두 입자가 위치 \(6\)에서 만나 서로 소멸한다.

두 번째 테스트 케이스에서는 반무트리노가 오른쪽으로 한 칸 더 떨어진 곳에서 시작하므로, 두 입자는 열한 번째 관찰의 \(0.5\)초 전 위치 \(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

첫 번째 테스트 케이스에서 가장 왼쪽의 두 입자는 정확히 첫 번째 관찰에서 위치 \(2\)에서 만난다. 가장 오른쪽의 두 입자는 세 번째 관찰의 \(0.5\)초 전 위치 \(6.5\)에서 만난다.

서브태스크

출처

USACO 2024 February Contest, Gold, Problem 3. Quantum Moochanics