28461번 - WHY DON'T YOU JUST GET UP AND DANCE MAN?

"펌프 잇 업" 의 개발사 "모른다미로" 에 개발자로 취직하게 된 아티초크는 펌프 잇 업의 후속작 개발을 맡게 되었다. 후속작에서 가장 크게 달라지는 점은, 발판의 개수가 $N (1 \le N \le 250\,000)$개라는 점이다.

아티초크는 되도록 기존 코드를 그대로 가져다 쓰려고 했지만, 문제가 생겼다. 기존 코드는 발판 개수가 $10$개라는 전제하에 짜여 있던 터라, 그 코드에 바뀐 발판의 개수를 적용하기 만만치 않았다! 그래서 기존 코드를 수정할지, 아니면 아예 새로 짤지 고민하던 아티초크는 결국 다 엎고 처음부터 다시 짜기로 했다.

아티초크의 동업자인 당신은 먼저 판정, 콤보 시스템과 게임 결과 창을 화면에 표시하는 코드를 짜는 업무를 맡게 되었다. 해당 부분은 기본적으로 펌프 잇 업의 시스템을 그대로 따라가기로 했다.

게임 목표

펌프 잇 업의 목표는 기본적으로 "노트" 가 등장하는 시점에 맞게 발판을 밟는 것이다. 이때 노트와 관련된 용어의 정의는 다음과 같다.

• 노트란, 플레이어가 판정 발생 시점에 맞춰 처리해야 할 목표다.
• 롱노트란, 등장하는 시점과 끝나는 시점이 존재하는 노트로, 플레이어는 그동안 발생하는 판정에 유의해야 한다.
• 일반노트란, 등장하는 시점만이 존재하는 노트로, 플레이어는 이때 발생하는 판정에 유의해야 한다.
• 다중노트란, 같은 시점에 여러 개의 발판에 등장하는 롱노트 또는 일반노트 모두의 집합을 의미한다.

판정

발판을 밟은 시점 근처에 해당 발판에 노트가 있었을 경우, "판정" 이 발생한다. 판정 시스템은 롱노트인지 일반노트인지 여부에 따라 다른데, 세부 사항과 관련 용어의 정의는 다음과 같다.

• 판정이란, 판정 기준과 플레이어가 발판을 밟은 시점이 얼마나 비슷한지 나타내는 것으로, 롱노트인지 일반노트인지 여부에 따라 판정 산정 방식이 다르다.
• 판정 기준 시점이란, 각 노트의 판정 계산에 있어 기준이 되는 시점으로, 판정 기준 시점과 판정 발생 시점의 차이로 판정을 계산한다.
• 일반노트의 판정 기준 시점은 노트의 등장 시점이며, PERFECT, GREAT, GOOD, BAD, MISS의 총 5가지 판정이 있다. 각각의 기준은 다음과 같다.
  • PERFECT: 판정 기준 시점과 플레이어가 발판을 밟기 시작한 시점의 차이가 $t_p (1 \le t_p \le 10^9)$ 이하인 경우 부여한다.
  • GREAT: 판정 기준 시점과 플레이어가 발판을 밟기 시작한 시점의 차이가 $t_p$ 초과 $t_{gr} (t_p < t_{gr} ≤ 10^9)$ 이하인 경우 부여한다.
  • GOOD: 판정 기준 시점과 플레이어가 발판을 밟기 시작한 시점의 차이가 $t_{gr}$ 초과 $t_{gd} (t_{gr} < t_{gd} ≤ 10^9)$ 이하인 경우 부여한다.
  • BAD: 판정 기준 시점과 플레이어가 발판을 밟기 시작한 시점의 차이가 $t_{gd}$ 초과 $t_b (t_{gd} < t_b \le 10^9)$ 이하인 경우 부여한다.
  • MISS: 플레이어가 판정 기준 시점 근처에 해당 발판을 아예 밟지 않았을 경우 부여한다.
• 롱노트의 경우, 각 판정 기준 시점마다 발판을 밟고 있는 상태인 경우 PERFECT, 발판을 밟고 있지 않은 상태인 경우 MISS 판정을 받는다. 이때 판정 기준 시점은 다음 항목 중 하나 이상에 해당하는 경우를 의미한다.
  • 해당 롱노트가 등장하는 시점
  • 해당 롱노트가 끝나는 시점
  • 해당 롱노트 구간에 다른 발판에 일반노트가 등장하는 시점
  • 해당 롱노트 구간에 다른 발판에 롱노트가 등장하거나 끝나는 시점
• 롱노트의 판정 기준 시점과 해당 롱노트가 등장한 발판에서 발을 뗀 시점이 동일한 경우, 해당 시점에는 PERFECT 판정이 발생한 것으로 본다.
• 다중노트의 판정 기준 시점은 해당 시점에 등장하는 일반노트나 롱노트가 있는 경우 해당 노트의 등장 시점이며, 해당 시점에 끝나는 롱노트가 있는 경우 해당 노트가 끝나는 시점이 된다.
• 판정 우선순위는 PERFECT, GREAT, GOOD, BAD, MISS 순이다.
• 다중노트의 경우, 포함하는 노트 중 가장 우선순위가 낮은 판정을 받은 노트의 판정을 따른다.

판정의 발생

플레이어가 발판을 밟아 등장한 노트에 대한 판정이 부여되는 것을 "판정의 발생" 이라 한다. 이때 판정이 발생하는 시점도 해당 노트가 롱노트인지, 일반노트인지에 따라 달라진다.

• 롱노트의 경우, 판정 항목에서 언급한 판정 발생 시점에 판정이 발생한 것으로 본다.
• 일반노트의 경우, 해당 노트의 등장 시점과의 차이가 $t_b$ 이하인 시점에 발판을 밟았다면 발판을 밟은 시점에 판정이 발생한 것으로 보고, 해당 시점에 발판을 밟지 않았다면 노트의 등장 시점으로부터 $t_b$만큼 지난 뒤에 MISS 판정이 발생한 것으로 본다.
• 한 발판에서, 이전에 등장한 일반노트 혹은 롱노트의 판정이 발생하기 전까지 새로 등장한 일반노트 혹은 롱노트의 판정은 발생하지 않는다.
• 다중노트의 경우 구성하는 노트들의 판정을 개별적으로 계산하되, 다중노트 자체의 판정은 구성하는 노트 중 판정이 가장 늦게 발생한 노트의 판정 발생 시점에 판정이 발생한 것으로 본다.
• 단, 다중노트를 구성하는 노트 중 MISS 판정이 발생한 노트가 있는 경우, 해당 다중노트는 MISS 판정이 발생한 노트 중 가장 일찍 발생한 노트의 판정 발생 시점에 MISS 판정이 발생한 것으로 본다.

콤보

플레이어가 연속하여 노트를 좋은 판정으로 처리하면 "콤보", 플레이어가 연속하여 노트를 놓치면 "미스콤보" 가 발생한다. 자세한 내용은 다음과 같다.

• 콤보란, 플레이어가 노트를 놓치지 않고 연속으로 처리한 횟수를 의미한다. 플레이어가 PERFECT나 GREAT 판정을 받으면 콤보가 $1$만큼 증가하고, BAD나 MISS 판정을 받으면 콤보가 $0$으로 초기화되며, GOOD 판정을 받았을 때는 콤보가 그대로 유지된다.
• 미스콤보란, 플레이어가 연속으로 MISS 판정을 받은 횟수를 의미한다. 플레이어가 MISS 판정을 받으면 미스콤보가 $1$만큼 증가하고, BAD 이상의 판정을 받으면 미스콤보가 $0$으로 초기화된다.
• 콤보와 미스콤보 모두 $4$ 이상이 되었을 때부터 화면에 판정과 함께 현재 콤보수도 같이 출력하는데, 이때 콤보 수가 $2$자리 이하일 경우 앞에 $0$을 추가로 붙여 $3$자리로 표기한다.
• 미스콤보의 경우, $51$ 이상이 되는 순간 "HEY!! WHY DON'T YOU JUST GET UP AND DANCE MAN?" 메시지를 출력하며 이후 다른 출력을 하지 않는다.
• 콤보 및 미스콤보의 변화는 판정의 발생 순서대로 이루어지며, 같은 시점에 여러 개의 판정이 발생했을 경우, 판정 기준 시점 순서로 적용한다.
• 다중노트의 경우 묶음으로 하나의 노트로 보므로, 콤보 및 미스콤보 계산 시에 다중노트를 구성하는 개별 노트의 판정은 무시한다.

결과창

미스콤보가 $51$ 이상이 되지 않는 한, 게임이 종료된 후 게임 결과를 출력한다. 자세한 내용은 다음과 같다.

• 처음 $5$줄에는 PERFECT, GREAT, GOOD, BAD, MISS 판정을 받은 횟수를 출력한다. 횟수의 출력 형식은 콤보 수의 출력 형식과 동일하며, 이때 다중노트를 구성하는 개별 노트의 판정은 무시한다.
• 그다음 줄에는 맥스콤보를 출력한다. 맥스콤보의 출력 형식 또한 콤보 수의 출력 형식과 동일하다.
• 맥스콤보란, 플레이어가 플레이한 결과 달성한 콤보 수의 최댓값이다. 이때 미스콤보는 고려하지 않는다.

당신은 노트들의 등장 시점과 플레이어가 발판을 밟기 시작한 시점, 발판을 뗀 시점이 모두 주어질 때, 상황에 맞는 판정, 콤보수, 게임 결과를 출력하는 프로그램을 구현하게 되었다. 뭘 하는진 모르겠지만 아무튼 바쁜 아티초크를 대신하여 구현해 보자.

첫 번째 줄에 발판의 개수 $N (1 \le N \le 250\,000)$이 주어진다.

두 번째 줄에 판정 범위를 나타내는 $t_p, t_{gr}, t_{gd}, t_b (1 \le t_p < t_{gr} < t_{gd} < t_b \le 10^9)$가 주어진다.

다음 $N$개의 줄 중 $i (1 \le i \le N)$ 번째 줄의 첫 번째 수는 $i$번째 발판에 등장하는 일반노트의 개수 $S_i$를 의미한다. 그리고 다음 $S_i$개의 수는 노트가 등장하는 시점 $s_1, s_2, \cdots , s_{S_i} (1 \le s_j < s_{j+1} \le 10^9, 1 \le j < S_i)$을 의미한다. 이때 $S_i \ge 0$이고, $\sum_{i=1}^{N} {S_i} \le 250\,000$이다.

다음 $N$개의 줄 중 $(1 \le i \le N)$ 번째 줄의 첫 번째 수는 $i$번째 발판에 등장하는 롱노트의 개수 $L_i$를 의미한다. 그리고 다음 $2L_i$개의 수는 플레이어가 발판을 밟은 시점 $l_1, l_2, \cdots , l_{2L_i} (1 \le l_j < l_{j+1} \le 10^9, 1 \le j < 2L_i)$을 의미한다. 이때 $L_i \ge 0$이며, $\sum_{i=1}^{N} {L_i} \le 250\,000$이고, 각 줄의 $2L_i$개의 수 중 홀수 번째로 등장하는 수는 롱노트가 시작하는 시점, 짝수 번째로 등장하는 수는 롱노트가 끝나는 시점을 의미한다. 롱노트가 시작하는 시점과 끝나는 시점 사이에 같은 발판에 일반노트가 등장하는 경우는 없다.

다음 $N$개의 줄 중 $i (1 \le i \le N)$번째 줄의 첫 번째 수는 플레이어가 $i$번째 발판을 밟은 횟수 $U_i$를 의미한다. 그리고 다음 $2U_i$개의 수는 플레이어가 발판을 밟은 시점 $u_1, u_2, \cdots , u_{2K_i} (1 \le u_j < u_{j+1} \le 10^9, 1 \le j < 2U_i)$을 의미한다. 이때 $U_i \ge 0$이며, $\sum_{i=1}^{N} {U_i} \le 500\,000$이고, 각 줄의 $2U_i$개의 수 중 홀수 번째로 등장하는 수는 발판을 밟기 시작한 시점, 짝수 번째로 등장하는 수는 발판을 뗀 시점을 의미한다.

노트 수(단, 다중노트는 하나의 노트로 취급한다)에 해당하는 줄 만큼, 해당 노트의 판정과, 필요하다면 현재 콤보 또는 미스콤보 수를 출력한다. 단, 도중에 미스콤보가 $51$ 이상이 되는 경우, 이후 노트의 판정 및 결과창을 출력하지 않은 채로 프로그램을 종료한다.

한 번도 미스콤보가 $51$을 넘지 않은 채로 게임이 종료되었을 경우, 다음 $6$줄에는 결과창을 출력한다.

자세한 출력형식은 예체를 참고하도록 하자.