뱀의 이동

이 문제는 인터랙티브 문제이다.

앨리스는 $N \times N$ 크기의 미로에 갇혀 있다. 각 칸은 빈 칸이거나 장애물이 있는 칸이다.

앨리스는 처음에 $(1,1)$에 서 있으며, 목표는 $(N,N)$에 도착하는 것이다. $(1,1)$과 $(N,N)$은 항상 빈 칸이다. 하지만 미로가 너무 어두워서 앨리스는 미로의 상태를 직접 볼 수 없다. 대신 앨리스는 다음과 같은 방식으로만 이동 경로를 정할 수 있다.

현재 위치가 $(i,j)$일 때, 한 번의 이동으로 다음 두 위치 중 하나로 이동할 수 있다.

• $(i+1,j)$: 아래쪽으로 한 칸 이동 (D)
• $(i,j+1)$: 오른쪽으로 한 칸 이동 (R)

단, 격자 밖으로 나가는 이동은 할 수 없다.

$(1,1)$에서 $(N,N)$까지 도달하는 경로는 정확히 $2N-2$번의 이동으로 이루어진다. 이러한 경로를 문자열 $s$로 나타내자. 문자열 $$의 각 문자는 또는 이며, 는 아래쪽 이동, 은 오른쪽 이동을 의미한다. 에는 가 정확히 번, 이 정확히 번 등장해야 한다. 이러한 문자열 를 이라고 부른다.

앨리스는 최대 $N^2$번까지 임의의 경로 문자열 $s$를 질의할 수 있다.

질의를 하면, 인터랙터는 앨리스가 문자열 $s$가 나타내는 경로를 따라 이동했을 때 지나가는 장애물 칸의 개수를 알려준다. 모든 질의를 마친 뒤, 앨리스는 $(1,1)$에서 $(N,N)$으로 가는 장애물을 하나도 지나지 않는 경로를 하나 출력해야 한다.

장애물을 하나도 지나지 않는 경로가 존재하지 않는다면 $!\ -1$을 출력해야 한다.

장애물을 하나도 지나지 않는 경로가 존재함에도 $!\ -1$을 출력하면 오답 판정을 받는다.

처음에 참가자의 프로그램은 정수 $N$을 입력받는다.

그 후 참가자는 다음 형식으로 질의할 수 있다. $s$는 길이가 $2N-2$인 올바른 경로 문자열이어야 한다.

• $?\ s$

각 질의에 대해, 인터랙터는 해당 경로가 지나가는 장애물 칸의 개수를 나타내는 정수 하나를 출력한다. 질의는 최대 $N^2$번까지 할 수 있다.

• $2 \le N \le 100$.
• $(1,1)$과 $(N,N)$은 빈 칸이다.
• 질의 횟수는 최대 번이다.