题目描述

为了冲击下半年的算法竞赛，小凯最近学习了八大排序算法，但是粗心大意的小凯却将八大排序算法的时空复杂度和稳定性记混了。现在，无助的小凯找到了你，希望你能给他写一个程序，输入一行字符串 s ，表示排序的英文名字。随后输出一行，时空复杂度和稳定性。

附：八大排序的时空复杂度和稳定性

输入格式

第一行一个正整数 $T(1 \leq T \leq 10^3)$ ，表示有 $T$ 组测试样例

对于每一组测试样例，每次给出一行字符串 $s$ ，表示

输出格式

对于每一组测试样例，输出一行，时间复杂度，空间复杂度和稳定性，中间用空格分隔

输入输出样例

8
quick sort
merge sort
heap sort
shell sort
counting sort
insertion sort
bubble sort
selection sort

O(nlogn) O(logn) No
O(nlogn) O(n) Yes
O(nlogn) O(1) No
O(n^{1.3~2}) O(1) No
O(n+m) O(n+m) Yes
O(n^2) O(1) Yes
O(n^2) O(1) Yes
O(n^2) O(1) No

提示

读入一行字符串可以使用getline哦