#1503 Radix Sorting

90  10 s   512 MB  

Description

A record consists of 3 fields. Construct a program that sorts n records. The first field has the highest priority, the second field has the next highest priority and the third field has the lowest priority.

Constraints for test case:

  1. The number of records is bigger than 216 and less than 224.
  2. Each field of record is a positive integer less than 212.
  3. Your score depends on the running time.
  4. You may adjust the bucket size depending on the number of records.

Input

 

Output

 

Sample Input

Sample Output

5
1 900 30 40 300 60 35 10 500 20 300 1004 35 10 405
4
40 300 60 35 10 500 20 300 1004 20 500 60
-1
1 900 30 20 300 1004 35 10 405 35 10 500 40 300 60
20 300 1004 20 500 60 35 10 500 40 300 60