MULSORT - MultiSort


Members of the famous ENSI Competitive Programming Club try to gather a huge database of problem sets. They need to sort all the problems according to their difficulty levels. Each of the M club members takes N problems and brings back the sorted list. The score (difficulty level) is a real value evaluated as a combination of many criterions. Write a program that outputs the global sorted list of N*M problems.

Input

First line of input consists of an integer T denoting the number of test cases. Then T test cases follow. Each case begins with two lines containing two integers M and N (N*M<=10^6). Each of the M next lines contains N space separated real numbers (scores) in descending order. All the scores are guaranteed to be in [0, 10].

Output

A single line for each test case consisting of N*M space separeted problems. Each problem is represented by i,j where i is the input member position (from 1 to M) and j is the position in the original list (from 1 to N). Problems are sorted by score (descending order) then by member's position (ascending order) and finally by problem's position in the original member’s list (ascending order).

Input File is large. Use fast I/O methods.

Example

Input:
1
3 
4
9.195 4.17 2.532 0.03
8.28 5.5 4 2.69 
8.8320 7.9 2.18 0
 
Output:
1,1 3,1 2,1 3,2 2,2 1,2 2,3 2,4 1,3 3,3 1,4 3,4

 


hide comments
vineetjai: 2020-09-05 09:21:54

AC in n*m*logm

chaks03: 2018-07-07 05:08:33

Getting NZEC again and again (java) even with bufferedreader. I am unable to verify the inputs. The test inputs work fine locally.

prajjyadv0904: 2018-06-28 18:21:56

O(n*m*logn) is also giving tle : (

tanya02_11: 2018-06-13 07:34:19

can anyone give a hint to solve my answer is getting timel limit exceed
RE: you have to use :
1) a better than an O(N*M*log(N*M)) algorithm and
2) a fastscan functions ( https://www.geeksforgeeks.org/fast-io-for-competitive-programming/)

Last edit: 2018-06-13 15:41:07
ryuuk: 2018-06-02 21:41:17

@mehmetin, you will get TLE if your solution is in O(N*M*log(N*M))

mehmetin: 2018-06-02 20:03:15

My previous AC code gets TLE, I think a rejudge should be made, if possible.

nils75: 2018-06-02 13:28:41

@nadstratosfer : I increased it a little. If I do more non intended solutions will be accepted.

nadstratosfer: 2018-06-01 20:17:48

Please increase TL so that PyPy solutions can pass. It's not even possible to just read a million lines in 0.3s (see http://www.spoj.com/ranks/INTEST/lang=PYPY2.4 ).

ryuuk: 2018-06-01 14:39:16

nice problem :D


Added by:adminensi
Date:2018-05-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All