보물

아주 오래전, 호루스와 세트는 오시리스의 뒤를 이어 왕이 될 사람을 두고 다투었다. 라는 두 사람의 다툼을 심판하고, 누가 왕위에 더 적합한지 가리기 위해 여러 도전 과제를 내렸다. 호루스는 모든 과제에서 이겼지만, 라는 호루스가 어린 나이 때문에 이집트를 다스릴 자격이 있는지 아직 확신하지 못한다. 그래서 라는 호루스에게 마지막 과제를 내어 그의 힘을 증명하게 하고, 이 싸움을 확실히 끝내기로 했다.

호루스에게 주어진 마지막 과제는 이집트 곳곳에 흩어진 $0$부터 $N - 1$까지 번호가 매겨진 보물 상자 $N$개를 모으는 것이다. 상자 $i$ ($0 \le i < N$)의 위치는 2차원 평면 위의 점 $(X[i], Y[i])$이다. $X[i]$와 $Y[i]$는 모두 $0$ 이상 $5 \cdot 10^8$ 이하의 정수이다. 서로 다른 두 상자의 위치는 겹치지 않는다.

호루스는 파피루스 노트에 메모를 적어 상자의 위치를 기록한다. 노트의 한 장에는 $2 \cdot 10^9$ 이하의 음이 아닌 정수 하나를 적을 수 있다. 호루스가 메모를 모두 적은 뒤에는 세트가 장을 섞는다.

여러분의 과제는 호루스를 도와 다음 두 절차를 구현하는 것이다.

• 노트의 장에 수를 적어 상자의 위치를 기록한다.
• 임의의 순서로 섞인 노트의 장이 주어졌을 때 상자의 위치를 복원한다.

점수는 사용한 장의 수, 즉 노트에 적은 수의 개수에 따라 정해진다.

• $1 \le T \le 100$
• $1 \le N \le 40\,000$
• $0 \le X[i] \le 5 \cdot 10^8$ ($0 \le i < N$)
• $0 \le Y[i] \le 5 \cdot 10^8$ ($0 \le i < N$)
• 서로 다른 두 상자의 위치는 겹치지 않는다.
• 모든 시나리오의 상자 개수 합은 $2 \cdot 10^5$를 넘지 않는다.
• 배열 $S$는 $E$의 순열이다.