题目背景

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，$39$ 个犹太人与Josephus及他的朋友躲到一个山洞中，$39$ 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，$41$ 个人排成一个圆圈，由第 $1$ 个人开始报数，每报数到第 $3$ 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第 $16$ 个和第 $31$ 个位置，于是逃过了这场死亡游戏。

题目描述

将问题简化并变形，$n$ 个人围成一个圆圈，每个人的编号依次是 $1、2、3、……、n$。从第一个人开始数数，数到 $m$ 的人分以下情况处理：

1. 如果数到 $m$ 的人和上次出圈的人性别不同，则本次数到 $m$ 的人出圈，然后由出圈的下一个人重新数数（第 $1$ 轮因为没有上次出圈的人，数到 $m$ 的人直接出圈）；
2. 如果数到 $m$ 的人和上次出圈的人性别相同 且 圈里没有其他与他（她）们是不同性别的人，则本次数到 $m$ 的人出圈，然后由出圈的下一个人重新数数；
3. 如果数到 $m$ 的人和上次出圈的人性别相同 且 圈里有其他与他（她）们是不同性别的人，则从本次数到 $m$ 的人开始循环查找，第一个与他（她）不是同一个性别的人出圈，然后由出圈的下一个人重新数数；

按照上述过程重复执行，直到所有人都出圈。

输入 $n$ 和 $m$ 以及 $n$ 个人的姓名和性别，依次输出出圈人的信息。

需要特别注意的是，$m$ 可能远大于 $n$。

输入格式

第 $1$ 行是两个正整数 $n,m$；

紧接着有 $n$ 行，依次是编号从 $1$ 开始的 $n$ 个人的姓名和性别，姓名和性别都是不包含空格且长度不超过 $10$ 的字符串，性别只会是 Male 或 Femal 中的一种，两者之间用一个空格隔开。

输出格式

$n$ 行，每行依次是出圈人的编号、姓名和性别，用一个空格隔开每项数据。

输入输出样例

5 2
Jerry Male
Jack Male
Lucy Femal
Tim Male
Sara Femal

2 Jack Male
5 Sara Femal
4 Tim Male
3 Lucy Femal
1 Jerry Male

7 3
Jerry Male
Jack Male
Lucy Femal
Tim Male
Sara Femal
Tom Male
Hellon Male

3 Lucy Femal
6 Tom Male
5 Sara Femal
2 Jack Male
1 Jerry Male
4 Tim Male
7 Hellon Male

说明/提示

👀️ 对于$100\%$的数据，$1 \leq n \leq 1000，1 \leq m \leq 10^8$。