27874번 - MiniEgg MiniGame 스페셜 저지

아인(AIN)이는 MiniEgg NFT(미니에그 NFT)를 홍보하기 위해 간단한 미니게임을 만들고 있다. 이 미니게임은 메타버스에서 여러 사람이 함께 협동하여 진행하는 턴제 게임으로, 메타버스에 순간적으로 나타나는 미니에그를 얻어 최대한 많은 점수를 모으는 것이 목적이다.

이 게임의 메타버스는 $N \times M$ 크기의 격자이다. 먼저, 격자의 위에서 $x$번째, 왼쪽에서 $y$번째에 있는 칸을 $(x,y)$로 나타내자.

게임에는 총 $K$명의 사람이 참가하며, 각자 $1$번부터 $K$번까지의 번호가 붙어 있다. $i$번 사람은 게임이 시작될 때 칸 $(x_i, y_i)$ 위에 있다.

게임이 진행되는 동안 메타버스에는 총 $E$개의 미니에그가 나타난다. 각 미니에그에는 $1$번부터 $E$번까지 번호가 붙어 있으며, $j$번 미니에그는 $st_j$번째 턴이 시작될 때 칸 $(sx_j, sy_j)$에 나타나고 그 턴이 끝날 때 격자에서 사라진다.

만약 어떤 미니에그가 나타났을 때 그 칸에 사람이 있었다면, 그 사람은 이 미니에그를 얻을 수 있다. $j$번 미니에그를 얻으면 $pt_j$점을 얻을 수 있지만, 미니에그에는 신비로운 힘이 있어서 미니에그를 얻은 사람은 격자 위에서 사라지고 $et_j$번째 턴이 끝날 때 칸 $(ex_j, ey_j)$로 다시 돌아오게 된다.

게임은 총 $T$턴 동안 진행되며, 매 턴이 시작되면 격자 위에 있는 사람들은 각자 적절한 커맨드를 선택해야 한다. 사람들이 선택할 수 있는 커맨드는 다음과 같다.

• 가만히 있기(P) : 아무것도 하지 않고 현재 위치에 가만히 있는다.
• 위로 움직이기(U) : 칸 $(x,y)$에 있을 때 칸 $(x-1,y)$로 이동한다.
• 아래로 움직이기(D) : 칸 $(x,y)$에 있을 때 칸 $(x+1,y)$로 이동한다.
• 왼쪽으로 움직이기(L) : 칸 $(x,y)$에 있을 때 칸 $(x,y-1)$로 이동한다.
• 오른쪽으로 움직이기(R) : 칸 $(x,y)$에 있을 때 칸 $(x,y+1)$로 이동한다.
• 미니에그 얻기(M) : 현재 위치에 미니에그가 있을 때 그 미니에그를 얻는다. 다만 미니에그가 있다고 해서 반드시 이 커맨드를 선택해야 하는 것은 아니다.

격자 위에 있는 사람들이 모두 커맨드를 선택하고 나면, 모두가 각자 선택한 커맨드를 따라 동시에 행동한 뒤 턴이 끝난다. 다만 사람들이 선택한 커맨드에 오류가 있다면 아무도 행동할 수 없고 턴이 진행되지 않는다. 따라서 사람들은 서로 협력하여 오류가 발생하지 않도록 커맨드를 선택해야 한다.

오류란 사람들이 각자 선택한 커맨드에 따라 행동할 때 다음과 같은 상황이 발생하는 경우를 말한다.

• 어떤 사람이 격자 밖으로 이동한다.
• 어떤 두 사람이 인접한 칸에서 서로 마주보는 방향으로 이동해 충돌이 일어난다.
• 턴이 끝났을 때, 즉, 격자 위에 있던 사람들이 모두 행동을 마치고, 이번 턴에 격자로 돌아오게 되는 미니에그를 얻었던 사람들이 예정된 위치로 돌아왔을 때 두 명 이상의 사람이 한 칸에 있게 된다.
• 어떤 사람이 미니에그를 얻을 때, 현재 격자 위에 없거나 마찬가지로 이번 턴에 미니에그를 얻는 다른 사람과 같은 턴에 같은 칸으로 돌아오게 된다.
• 어떤 사람이 미니에그가 없는 칸에서 미니에그를 얻으려고 한다.

게임의 초기 설정을 모두 마친 아인이는 이 게임에서 사람들이 어떻게 행동해야 최고 점수를 얻을 수 있는지 궁금해졌다. 아인이를 도와주자.

첫 번째 줄에 격자의 크기를 나타내는 두 정수 $N$과 $M$, 게임을 진행하는 사람의 수 $K$, 게임 중에 나타나는 미니에그의 수 $E$, 게임이 진행되는 턴 수 $T$가 주어진다.

다음 $K$개의 줄에는 각 사람이 게임을 시작하는 칸의 위치가 주어진다. $i$번째 줄에는 두 정수 $x_i,y_i$가 주어지며, $i$번 사람이 칸 $(x_i,y_i)$에서 게임을 시작함을 나타낸다.

다음 $E$개의 줄에는 각 미니에그의 정보가 주어진다. $j$번째 줄에는 일곱 정수 $st_j, sx_j, sy_j, et_j, ex_j, ey_j, pt_j$가 주어진다. 이는 $j$번 미니에그가 $st_j$번째 턴이 시작될 때 칸 $(sx_j, sy_j)$에 나타나며, 이 미니에그를 얻으면 $pt_j$점을 얻고, 이 미니에그를 얻은 사람은 $et_j$번째 턴이 끝날 때 칸 $(ex_j, ey_j)$으로 다시 돌아오게 됨을 나타낸다.

첫 번째 줄에 얻을 수 있는 총점의 최대치를 출력한다.

다음 $K$개의 줄에는 해당 점수를 얻기 위해 각 사람들이 선택할 커맨드 나열의 예시를 하나 출력한다. $i$번째 줄에는 $i$번 사람의 커맨드 나열을 LRUDPM-의 일곱 종류의 문자로 이루어진 길이가 $T$인 문자열로 출력해야 한다. 출력하는 문자열의 $t$번째 문자는 그 사람이 $t$번째 턴에 선택하는 커맨드이다.

-를 제외한 각 문자의 의미는 문제에서 설명된 것과 같으며, -는 그 사람이 그 턴의 커맨드를 선택하는 시점에 격자 위에 없음을 의미한다.

• $1 \leq N, M \leq 10$
• $1 \leq K \leq \min(10, N \times M)$
• $1 \leq E \leq 100\,000$
• $1 \leq T \leq 1\,000$
• $1 \leq x_i \leq N$
• $1 \leq y_i \leq M$
• 같은 $(x_i, y_i)$가 여러 번 등장하지 않는다.
• $1 \leq st_j \leq et_j \leq T$
• $1 \leq sx_j, ex_j \leq N$
• $1 \leq sy_j, ey_j \leq M$
• $1 \leq pt_j \leq 1\,000\,000\,000$
• 같은 시점, 같은 위치에 여러 미니에그가 나타나지 않는다. 즉, 같은 $(st_j, sx_j, sy_j)$가 여러 번 등장하지 않는다.