Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Maintain the Queue

By biqarboy · Limits 3s, 512 MB

“Ajob Desh” is a strange country. Anyone who wants to buy train tickets need to go to the railway station and buy the tickets. There is no way to buy train tickets online. And, as you might expect, there is always a queue in front of the ticket counter.

Suppose N customers want to buy tickets by standing in a queue in front of the ticket booth at the railway station. For every customer ci, you will be given the height of the customer hi, and the number of customers ti who are taller than ci and will be standing in front of ci in the queue. For this problem you can assume that the customer heights are unique.

You need to find the actual height ordering of the customers in the queue.

Input

The first line of the input will contain an integer T (T ≤ 30), denoting the number of test cases.

Each test case starts with a line containing a single integer N (1 ≤ N ≤ 106), representing the number of customers for this test case. Each of the next N lines contains two integers, hi (1 ≤ hi ≤ 109) and ti (ti ≥ 0), described before.

There will be a new line before every test case.

Output

For each test case, print "Case X: " (where X is the case number) in the beginning. Then you need to print either a list of integers:

h1 h2 h3 .... hN-1 hN

... representing the actual height ordering of the customers.

Or, print "No ordering possible!" if ordering does not exist.

If multiple solutions exist, you need to print the numerically smallest one.

Sample

InputOutput
2

2
2 0
1 1

2
1 0
2 1

Case 1: 2 1
Case 2: No ordering possible!

Discussion

Statistics


54% Solution Ratio

foyaz05Earliest, Dec '16

TurinhstuFastest, 0.2s

oneoff.P27Aj11uhsLightest, 18 MB

SIR.24Shortest, 845B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.