Problem K
Among Ourselves

You are playing the game “Among Ourselves.” There are $n$ players numbered from $1$ to $n$ in this game, and you are player number $1$. Each player is either a crewmate or an imposter. You are a crewmate.

During the voting phase of the game, the players exchange accusations and alibis such as “Player 1 is acting a bit sus, they must be an imposter.” However, crewmates always tell the truth and imposters always lie in this particular game. Since the exchange usually gets heated, players might repeat the same accusation or alibi multiple times, but they never make statements about themselves.

During one of the voting phases, you happen to be in urgent need to release some chocolate hostages (i.e. run to the bathroom) but you want to figure out whether a specific player is a crewmate or an imposter. Given the list of all of the statements that will be exchanged during this voting phase and how many consecutive statements you will miss while you are in the bathroom, is it still possible for you to be certain whether a given player is a crewmate or an imposter?

Input

The first line contains four space-separated integers $n$ $(2 \leq n \leq 10^5)$, $m$ $(1 \leq m \leq 10^5)$, $k$ $(1 \leq k \leq n)$, and $t$ $(1 \leq t \leq m)$: the number of players in this game, the number of statements exchanged during the voting phase, the number of player whom you wish to determine the identity of, and the number of statements you will miss while in the bathroom.

Another $m$ lines follow in the format of a b s, where $a$ $(2 \leq a \leq n)$ and $b$ $(1 \leq b \leq n)$ are integers representing player numbers and $s$ is either crewmate or imposter. Each line represents a statement “Player $a$ claims that player $b$ is a(n) $s$”. The statements are guaranteed to be consistent (i.e. there exists some assignment of players to crewmates/imposters that is consistent with all statements).

Output

Print the index ($1$-based) of the earliest statement you can miss to still be certain of player $k$’s identity, alongside with their identity. If it is impossible to determine their identity, print $-1$.

Note

You cannot hold your chocolate hostages later than the $(m - t)$-th statement. That is, you will have to miss exactly $t$ consecutive statements.

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

4 imposter