스케줄링

상사가 자신의 회의 일정을 유효하게 짜 달라고 부탁했습니다. 회의는 $n$개 있고, $i$번째 회의는 시간 구간 $[\ell_i, r_i]$ 안에서 시작해서 끝나야 합니다. 시간 단위는 시간(hour)입니다. 각 회의는 정확히 1시간이 걸리며, 상사는 같은 시간에 두 회의에 참석할 수 없습니다.

경쟁 프로그래머로서 당신은 이 고전적인 스케줄링 문제를 수없이 풀어 왔지만, 이제서야 그것이 비현실적이라는 점을 알아챕니다. 이동 시간도 쉬는 시간도 없이, 서로 다른 장소에서 십만 건이 넘는 회의에 한 사람이 어떻게 참석할 수 있겠습니까? 회의가 항상 정확히 1시간 동안 열리지는 않으며, 누군가 늦는 바람에 시작이 늦어지는 회의도 많습니다.

이런 심오한 철학적 질문은 인류에게 큰 문제일 수 있지만, 당신이 직접 그 회의에 참석할 필요는 없으므로 이 질문을 전부 풀 만큼 신경 쓰지는 않습니다. 그래도 상사에게 좋은 인상을 주면 이득이 되니, 일정을 조금이라도 개선해 보려고 합니다.

모든 두 회의 사이에 적어도 1시간의 간격이 있는 유효한 일정을 하나 찾거나, 그런 일정이 없다고 보고하세요. 고전적인 문제에서 아주 작은 변화일 뿐이죠, 그렇죠?

각 테스트 파일에는 여러 개의 테스트 케이스가 들어 있습니다. 첫 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \leq t \leq 10^5$)가 하나 주어집니다. 이어서 각 테스트 케이스가 설명됩니다.

각 테스트 케이스의 첫 줄에는 회의의 개수를 나타내는 정수 $n$ ($1 \leq n \leq 2 \cdot 10^5$)이 하나 주어집니다. 다음 $n$개의 줄에는 각각 두 정수 $\ell_i$와 $r_i$ ($1 \leq \ell_i < r_i \leq 10^6$)가 주어지며, 이는 $i$번째 회의의 시간 구간입니다.

모든 테스트 케이스의 $n$ 합은 $2 \cdot 10^5$를 넘지 않습니다.

유효한 일정이 없으면 $-1$을 한 줄에 출력합니다. 그렇지 않으면 $n$개의 정수 $a_i$를 한 줄에 출력합니다. 여기서 $a_i$는 $i$번째 회의의 시작 시각입니다.

첫 번째 테스트 케이스에서 첫 회의는 1시 정각에 시작해 2시 정각까지 1시간 동안 진행됩니다. 그 뒤 상사는 1시간 쉬고, 3시 정각부터 4시까지 세 번째 회의에 참석합니다. 다시 1시간 쉰 뒤, 5시 정각부터 6시까지 두 번째 회의에 참석합니다.

세 번째 회의를 4시 정각에 시작하는 것은 불가능합니다. 이 회의가 5시에 끝나기 때문입니다.