가위바위보 도마뱀 스팍

레오는 컴퓨터를 상대로 rock, paper, scissors, lizard, Spock 게임을 한다. 게임은 여러 라운드로 진행되고, 각 라운드에서 두 사람은 rock, paper, scissors, lizard, Spock 다섯 가지 중 하나를 동시에 낸다. 각 선택은 나머지 넷 가운데 정확히 둘을 이긴다.

둘이 같은 것을 내면 그 라운드는 무승부다.

그림 F.1: 게임의 승패 관계. 그림은 VidTheKid가 그렸고 Wikimedia Commons에 있다.

컴퓨터는 선형 합동 생성기로 낼 것을 고른다. 생성기는 알려진 소수 $p = 127$과 레오가 모르는 두 정수 $0 \le a < p$, $0 \le b < p$를 쓴다. 상태 $0 \le x < p$도 있는데, 그 처음 값 역시 레오는 모른다. 컴퓨터는 라운드마다 먼저 상태를 갱신하고,

$x \leftarrow (a \cdot x + b) \bmod p,$

다음 표에서 낼 것을 읽는다.

레오는 처음 $n$개 라운드를 지켜보면서 컴퓨터가 낸 것을 모두 적어 두었다. 이제 남은 $m$개 라운드를 전부 이기려고 한다. 어떤 선택이든 그것을 이기는 선택은 둘인데, 레오는 언제나 rock, paper, scissors, lizard, Spock 순서에서 앞서는 쪽을 낸다.

레오가 다음 $m$개 라운드에서 낼 것을 출력하라.

첫 줄에 정수 $n$과 $m$이 주어진다 ($1 \le n \le 1000$, $1 \le m \le 1000$).

다음 $n$개 줄에는 rock, paper, scissors, lizard, Spock 중 하나가 순서대로 주어진다. 컴퓨터가 그 라운드에 낸 것이다.

기록된 라운드는 위 형태의 생성기가 만든 것이고, 그다음 $m$개 선택을 하나로 결정한다. 기록된 $n$개를 그대로 재현하는 $(a, b, x)$는 모두 그 뒤의 $m$개 선택도 똑같이 만든다.

$m$개 줄을 출력한다. $i$번째 줄에는 레오가 $n + i$번째 라운드에 낼 것을 적는다. 그 라운드에서 컴퓨터가 낸 것을 이기는 선택이고, 이기는 선택이 둘이면 rock, paper, scissors, lizard, Spock 순서에서 앞서는 쪽이다.