13641364 SUSTech Online Judge
Problem 1364 --[Easy III] Which is better?

1364: [Easy III] Which is better?

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 902  Solved: 245
[Submit][Status][Web Board]

Description

Given an integer array, try to sort it by Selection Sort Algorithm and Insertion Sort Algorithm. Also, you need to justify which algorithm performs better in this case. The performance is measured by the sum of comparison times and swap times, the lower, the better. It's guaranteed that performances are not the same in each test case.

Input

The first line contains an integer T(1 ≤ T ≤ 10), representing the number of test cases.

For each test case, the first line will be an integer n (2 ≤ n ≤ 103) showing the length of array. Then there are n integers.

Output

For each test case, the first line you need to output the sorted array in the ascending order.

The secondline, you need to output the better algorithm in this case.

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

1 2 3
Insertion Sort wins!
1 2 3
Selection Sort wins!

HINT

Source

 

[Submit][Status]