你正在玩一个名为“Among Ourselves”的游戏。游戏中有 $n$ 名玩家，编号为 $1$ 到 $n$，你是 $1$ 号玩家。每个玩家要么是船员（crewmate），要么是内鬼（imposter）。你是一名船员。

在游戏的投票阶段，玩家们会互相指责或提供不在场证明，例如“1 号玩家行为有点可疑，他一定是内鬼”。然而，在这个特定的游戏中，船员总是说真话，而内鬼总是说假话。由于交流通常很激烈，玩家可能会多次重复相同的指责或不在场证明，但他们绝不会对自己发表言论。

在其中一个投票阶段，你突然急需去释放一些“巧克力人质”（即上厕所），但你想弄清楚某个特定玩家是船员还是内鬼。给定该投票阶段将要交流的所有发言列表，以及你在上厕所期间将错过的连续发言数量，你是否仍有可能确定给定玩家是船员还是内鬼？

输入格式

第一行包含四个空格分隔的整数 $n$ ($2 \le n \le 10^5$)、$m$ ($1 \le m \le 10^5$)、$k$ ($1 \le k \le n$) 和 $t$ ($1 \le t \le m$)：游戏中的玩家人数、投票阶段交流的发言数量、你希望确定其身份的玩家编号，以及你在上厕所时将错过的连续发言数量。

接下来的 $m$ 行格式为 a b s，其中 $a$ ($2 \le a \le n$) 和 $b$ ($1 \le b \le n$) 是表示玩家编号的整数，$s$ 为 crewmate 或 imposter。每行代表一个发言：“玩家 $a$ 声称玩家 $b$ 是 $s$”。保证这些发言是一致的（即存在某种玩家是船员/内鬼的身份分配，与所有发言均不冲突）。

输出格式

输出你可以错过的最早发言的索引（从 1 开始计数），使得你仍能确定玩家 $k$ 的身份，并同时输出其身份（crewmate 或 imposter）。如果无法确定其身份，则输出 -1。

说明

你最迟不能在第 $(m - t)$ 条发言之后还憋着你的“巧克力人质”。也就是说，你必须恰好错过 $t$ 条连续的发言。

样例

输入样例 1

7 7 2 3
3 1 imposter
2 5 imposter
4 3 crewmate
4 6 imposter
6 5 crewmate
6 7 crewmate
5 4 imposter

输出样例 1

4 imposter