SBANK - Sorting Bank Accounts


In one of the internet banks thousands of operations are being performed every day. Since certain customers do business more actively than others, some of the bank accounts occur many times in the list of operations. Your task is to sort the bank account numbers in ascending order. If an account appears twice or more in the list, write the number of repetitions just after the account number. The format of accounts is as follows: 2 control digits, an 8-digit code of the bank, 16 digits identifying the owner (written in groups of four digits), for example (at the end of each line there is exactly one space):

30 10103538 2222 1233 6160 0142 

Banks are real-time institutions and they need FAST solutions. If you feel you can meet the challenge within a very stringent time limit, go ahead! A well designed sorting algorithm in a fast language is likely to succeed.

Input


t [the number of tests <= 5]
n [the number of accounts<= 100 000]
[list of accounts]
[empty line]
[next test cases]

Output


[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]

Example

Input:
2
6
03 10103538 2222 1233 6160 0142 
03 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0141 
30 10103538 2222 1233 6160 0142 

5
30 10103538 2222 1233 6160 0144 
30 10103538 2222 1233 6160 0142 
30 10103538 2222 1233 6160 0145 
30 10103538 2222 1233 6160 0146 
30 10103538 2222 1233 6160 0143 

Output:
03 10103538 2222 1233 6160 0141 1
03 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0141 2
30 10103538 2222 1233 6160 0142 2

30 10103538 2222 1233 6160 0142 1
30 10103538 2222 1233 6160 0143 1
30 10103538 2222 1233 6160 0144 1
30 10103538 2222 1233 6160 0145 1
30 10103538 2222 1233 6160 0146 1

hide comments
s_jindal00: 2016-10-14 20:07:29

for a particular test case, is the bank 8-digit code same for all accounts??

davidgalehouse: 2016-09-19 08:18:57

@ciglesias lexicographic by the account number string

Last edit: 2016-09-19 08:19:18
davidgalehouse: 2016-09-19 07:27:10

Tried it using SortedDictionary, SortedList, and sorting an array in C#, with StringBuilder to build up output for each test case but nothing is fast enough. Can someone teach me? EDIT: Oh okay now I wanna die... I even tried wrapping my int in a reference type to lessen the lookups... but in the end using a normal Dictionary worked. I guess I only need to sort it once so it doesn't make sense to pay the overhead of keeping it sorted after every add?? EDIT: Err but yeah now I recommend you use LSD radix sort to get the most out of this problem!

Last edit: 2016-09-29 06:40:16
ciglesias: 2016-08-19 22:39:59

Did you solve it using lexicographic sorting or by ocurrences? Thanks in advance.

Rajat Sharma: 2016-08-18 21:44:17

JAVA : used maps (Hashmap), learned about entrySet of maps.

jasbir_220b2: 2016-08-17 11:35:08

got idea about stl::map... good one.

vinit payal: 2016-08-01 21:55:31

Used BST AC in first Go. Good question. Using BST recommended.

sonu: 2016-07-27 15:10:46

seriously somebody explain why you need to use scanf("%d\n,&n)....got 4 WA's because of it.

baadshah_: 2016-07-12 15:12:57

AC in one go!!
Used SET and MAP

sonali9696: 2016-06-27 10:20:38

AC in one go! But learnt a lot! Simply used qsort and array. No STL. Feeling awesome! :D


Added by:mima
Date:2004-06-01
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:-