题目描述

农夫约翰的牛棚门上贴着一张按字母顺序排列的N头奶牛（1 ≤ N ≤ 50,000）的名单。每头奶牛的名字由1到20个小写字母组成的唯一字符串表示。

调皮的奶牛Bessie重新排列了名单顺序，并且还打乱了每头奶牛名字中的字母顺序。给定这个被修改后的名单，请帮助农夫约翰计算：对于名单中的每个名字，它在原始名单中可能出现的最高和最低位置。

输入格式

第一行：一个整数N

接下来N行：每行包含一个被打乱顺序的奶牛名字

输出格式

输出N行：每行包含两个整数，表示对应名字在原始名单中可能出现的最低和最高位置

输入输出样例

输入 #1

4
essieb
a
xzy
elsie

输出 #1

2 3
1 1
4 4
2 3

样例解释

原始名单可能是按以下顺序排列的：

1. "a"（无论如何排列字母都排第一）
2. "bessie"（"essieb"的字母排序后形式）
3. "elsie"（字母顺序不变）
4. "xyz"（"xzy"的字母排序后形式）

分析：

• "a"：最低和最高位置都是1
• "xzy"：无论如何排列字母都排最后（位置4）
• "essieb"和"elsie"：
  • 如果原始是"bessie"和"elsie"，则分别位于2和3
  • 如果原始是"sisbee"和"ilees"，则分别位于3和2 因此它们的位置范围都是2-3