Byteram 村的所有农场都位于一条长公路的同一侧，因为公路的另一侧是 Byteland 国家公园。Byteram 的镇长决定通过垄断家具行业来促进村庄的经济增长。

村里建造了与农场数量相等的锯木厂，它们都沿着村里唯一的一条公路分布。镇长决定，每家锯木厂将只为一家农场供应木材，用于家具生产。

不幸的是，他们遇到了物流问题——由于村里唯一的公路过于拥挤且危险，无法通过该公路运输木材。因此决定修建连接锯木厂和农场的道路（一家锯木厂只能连接一家农场）。出于安全考虑，这些道路不能相互交叉。此外，由于不能位于 Byteland 国家公园内，这些道路只能建在主公路的同一侧。

Byteram 的镇长遇到了严重的难题，因为她不知道如何规划这些道路。因此，她开始寻找一名程序员来帮助她。

编写一个程序，完成以下任务：

• 从标准输入读取沿公路分布的农场和锯木厂的位置；
• 计算出一种锯木厂到农场的分配方案，使得所有要求的道路都能被修建；
• 将答案写入标准输出。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示村里的农场数量。第二行包含一个长度为 $2 \cdot n$ 的字符串，仅由字母 g 和 t 组成，确定了农场（波兰语中 gospodarstwo 为农场）和锯木厂（波兰语中 tartak 为锯木厂）沿公路的位置。公路从西向东延伸，农场和锯木厂按从西到东的顺序给出，Byteland 国家公园位于公路的南侧（见样例图片）。

输出格式

如果不存在这样的分配方案，程序应仅向标准输出写入一个单词 NIE（波兰语中的“不”）。如果存在这样的分配方案，程序应输出 $n$ 行。每行包含一对由空格分隔的整数。这两个整数分别标识要连接的农场和锯木厂。农场从西到东编号为 $1$ 到 $n$（锯木厂以相同方式编号；农场和锯木厂拥有独立的编号池）。如果存在多种正确的分配方案，程序可以输出其中任意一种。

样例

输入 1

3
gtggtt

输出 1

2 1
1 3
3 2

锯木厂（白色圆圈）和农场（黑色圆圈）的分配示例。

说明： 农场、锯木厂与主公路之间的距离仅为更好地说明情况。在“现实世界”中，锯木厂和农场紧邻公路，无法在锯木厂或农场与主公路之间修建道路。