Overdose Runner

스킵이는 신작 게임 Overdose Runner를 플레이하고 있다. 게임의 목표는 플레이어가 특정 지점에 도착하는 것이다. 이 게임은 $N\times M$ 크기의 2차원 좌표계로 나타낼 수 있다. 좌표 안에는 플레이어, 빈칸, 몬스터, 장애물, 목적지가 존재한다. 플레이어는 공격력, 공격 사거리, 이동속도, 레벨, 경험치, 요구 경험치 6가지의 능력치를 가진다. 플레이어는 행동력을 소모해 특정 행동을 할 수 있는데 그 행동은 아래와 같다.

• 순간이동 - 행동력 1을 소모해 상하좌우 중 한 방향을 정해 정확히 $p$만큼 떨어진 위치로 이동한다. 이때 $p$는 캐릭터의 이동속도다. 이동할 위치가 좌표 범위 밖이거나 장애물 혹은 몬스터가 있으면 움직일 수 없다.
• 대기 - 행동력 1을 소모해 아무 행동도 하지 않는다.
• 공격 - 행동력 3을 소모해 상하좌우 중 한 방향으로 투사체를 발사한다. 투사체는 발사된 방향으로 공격 사거리만큼의 거리를 한 칸씩 움직이며 투사체와 몬스터가 같은 위치에 있게 되면 몬스터의 체력이 (플레이어의 공격력 - 몬스터의 방어력)만큼 감소한다. 단, 플레이어의 공격력이 몬스터의 방어력보다 낮은 경우 몬스터의 체력은 감소하지 않는다. 만약 이 행동으로 인해 몬스터의 체력이 0 이하가 되면 그 자리는 빈칸이 되고 플레이어는 경험치를 획득한다. 투사체가 이동할 다음 좌표에 장애물이 있는 경우 투사체는 사라진다. 투사체가 사라진 후 다음 행동을 처리한다. 투사체는 장애물을 제외한 다른 물체를 만나도 사라지거나 행동을 멈추지 않는다.
• 약 먹기 - 행동력 2를 소모해 이동속도가 1 증가 혹은 감소하는 약을 먹는다. 이동속도가 0인 경우 음수로 내려가지 않는다. 이때 행동력은 그대로 소모된다. 약을 5번 먹을 때마다 OVERDOSE 상태가 되며 OVERDOSE 상태에서는 순간이동, 대기를 제외한 다른 행동을 할 수 없다. OVERDOSE 상태가 된 후 행동력을 10 이상 소모할 경우 OVERDOSE 상태는 해제된다.
• 클리어 - 플레이어가 목적지와 같은 좌표에 있으면 행동력 0을 소모해 스테이지를 클리어한다. 게임을 클리어한 후 캐릭터는 다른 행동을 할 수 없다.

한 가지 행동이 끝난 후 경험치를 얻어 요구 경험치 이상이 되면, 경험치 < 요구 경험치를 만족할 때까지 레벨이 상승하고 경험치를 요구 경험치만큼 뺀다.

캐릭터는 게임을 처음 시작했을 때 공격력 5, 공격 사거리 1, 이동속도 1, 요구 경험치 10, 경험치 0, 레벨 1로 시작하며 레벨이 $l$일 때 레벨이 상승하면 레벨이 $l+1$이 되고, 공격력이 $l$만큼, 공격 사거리가 1만큼, 요구 경험치가 10만큼 증가한다.

스킵이가 게임을 시작한 후 한 행동이 차례대로 주어진다. 만약 스킵이가 한 행동이 불가능한 행동이었을 경우 게임은 그 행동을 무시하고 다음 행동을 실행한다. 이 때 행동력은 소모되지 않는다. 모든 행동을 실행한 뒤 게임 화면을 출력해보자!

첫 번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. $(5 \leq N, M \leq 50)$

그 다음 줄부터 $N$개의 줄에는 초기 게임의 상태를 나타내는 $M$개의 문자가 주어진다. p는 플레이어, .은 빈칸, m은 몬스터, *은 장애물, g는 목적지를 나타낸다. p와 g는 하나만 주어지며 m은 하나 이상 주어진다. $y$ 좌표가 $0$ 혹은 $N-1$이거나 $x$ 좌표가 $0$ 혹은 $M-1$인 경우 장애물이 있다는 것이 보장된다.

그 다음 줄에는 몬스터의 수 $k$가 주어진다. $(1 \leq k \leq N \times M)$ $k$는 주어진 $m$의 개수와 같다.

$i$번째 몬스터는 몬스터의 좌표를 $y$ 좌표가 같다면 $x$ 좌표가 증가하는 순서대로, $y$ 좌표가 다르다면 $y$ 좌표가 증가하는 순서대로 정렬했을 때 $i$번째에 오는 몬스터다.

그 다음 줄에는 각 몬스터의 체력 $mh\_i$이 공백으로 구분되어 주어진다. $(1 \leq mh\_i \leq 50)$

그 다음 줄에는 각 몬스터의 방어력 $md\_i$이 공백으로 구분되어 주어진다. $(1 \leq md\_i \leq 50)$

그 다음 줄에는 각 몬스터의 체력을 0 이하로 만들었을 경우 얻을 수 있는 경험치 $mexp\_i$가 공백으로 구분되어 주어진다. $(1 \leq mexp\_i \leq 50)$

좌표는 맵에서 왼쪽 위가 $(0,0)$이고 오른쪽 아래가 $(N-1,M-1)$이라 가정한다.

그 다음 줄에는 스킵이가 한 행동의 수 $s$가 주어진다. $(1 \leq s \leq 50)$

그 다음 줄에는 스킵이가 한 행동이 공백으로 구분되어 주어지는데 u는 위로 순간이동, d는 아래로 순간이동, l은 왼쪽으로 순간이동, r은 오른쪽으로 순간이동, w는 대기, au는 위로 공격, ad는 아래로 공격, al는 왼쪽으로 공격, ar는 오른쪽으로 공격, du는 약 먹기(이동속도 1 증가), dd는 약 먹기(이동속도 1 감소), c는 클리어를 나타낸다.

첫 번째 줄에 레벨과 경험치를 공백으로 구분하여 출력한다.

그 다음 줄에 스킵이가 사용한 행동력을 출력한다.

그 다음 줄부터 $N$개의 줄에 모든 행동이 끝난 후 게임판의 상태를 입력 형식에 맞춰서 출력한다. 만약 목적지와 플레이어가 같은 위치에 있었을 경우 p만 출력한다.

그 다음 줄에는 남아있는 몬스터의 체력을 공백으로 구분하여 출력한다. 만약 몬스터가 하나도 남아있지 않았을 경우 출력하지 않는다. 몬스터의 순서는 $y$ 좌표가 같다면 $x$ 좌표가 증가하는 순서대로 $y$ 좌표가 다르다면 $y$ 좌표가 증가하는 순서대로 출력한다.