퍼즐 게임 Output Only 제출 불가 컴파일 명령

심심한 나나는 누구나 즐길 수 있는, n × 1 크기, 즉 단위 격자 n개가 일렬로 놓여 있는 격자판에서 하는 퍼즐 게임을 생각해 냈습니다. 격자들에는 n 이하의 자연수 번호가 왼쪽 끝에서부터 차례대로 붙어있습니다. i (1 ≤ i ≤ n)번째 격자에는 색이 b_i인 블록이 하나 놓여 있습니다. 격자판 아래에는 "대기열"이라고 불리는 격자판과 별개인 공간이 있는데, 여기에는 m개의 블록들이 일렬로 놓여 있으며, 이 중 j (1 ≤ j ≤ m)번째 블록의 색은 s_j입니다. 블록의 색들은 1 이상 c 이하의 자연수로 표현할 수 있습니다. (즉 블록에 칠해져 있는 색의 종류는 c가지입니다.)

여러분은 격자판에서 색이 같은 연속한 블록들을 선택하여 제거할 수 있습니다. 블록은 왼쪽에서부터 차례대로 제거되며, 격자에서 블록을 제거할 때마다 대기열의 맨 앞에 있는 블록이 그 격자 속으로 들어가게 됩니다.

이 게임의 목적은 블록들을 적절히 제거하여, 대기열에 있는 모든 블록을 없애는 것입니다. 물론 제거 작업을 무한히 할 수 있다면 게임이 너무 쉬워지므로, 제거 작업은 최대 t번까지만 할 수 있습니다. 만약 t번 안에 대기열의 모든 블록들을 소모하지 못했다면 부분 점수만을 얻게 되고, t번 미만의 제거 작업으로 대기열의 모든 블록들을 소모했다면 추가 점수를 얻게 됩니다. 단, 대기열에 블록들이 없는데도 격자판의 블록을 제거하면 안 됩니다.

입력 형식

첫 번째 줄에는 격자의 수 n과 색의 종류의 수 c가 공백을 사이로 두고 주어집니다.

두 번째 줄에는 격자판 안에 있는 블록들의 색을 나타내는 n개의 자연수 b₁, b₂, ..., b_n이 공백을 사이로 두고 주어집니다.

세 번째 줄에는 대기열에 있는 블록의 수 m과 제거 작업의 최대 횟수 t가 주어집니다.

네 번째 줄에는 대기열에 있는 블록들의 색을 나타내는 m개의 자연수 s₁, s₂, ..., s_m이 공백을 사이로 두고 주어집니다. 앞에 있는 블록 (즉, 번호가 작은 블록)이 먼저 사용됩니다.

출력 형식

첫 번째 줄에는 사용한 제거 작업의 횟수 u (1 ≤ u ≤ t)를 출력합니다.

이후 u개의 줄을 출력하는데, 이 중 i (1 ≤ i ≤ u)번째 줄에는 두 개의 자연수 L_i와 R_i (1 ≤ L_i ≤ R_i ≤ n)를 공백을 사이로 두고 출력합니다. 이는 i번째 제거 작업에서 L_i, L_i + 1, ..., R_i - 1, R_i번 블록을 제거했다는 것을 의미합니다.

파일 정보

각 입력의 파라미터는 다음과 같습니다. 게임 보드와 대기열은 주어진 파라미터를 이용하여 랜덤하게 만들어졌습니다. 입력 파일은 여기에서 내려받을 수 있습니다.

채점 방식

각 출력 파일에 대한 여러분의 점수는 아래와 같이 계산됩니다.

• 만약 여러분의 계획이 문제에서 제시한 조건을 만족하지 않는다면 0점입니다.
• 만약 여러분의 계획이 문제에서 제시한 조건을 만족한다면, 다음과 같이 점수가 계산됩니다. 여러분이 사용한 제거 작업의 횟수를 u, 대기열에서 제거한 블록의 수를 w로 둡시다.
  • w = m이면 점.
  • 그렇지 않으면 점

제출한 답안의 점수는 각 출력 파일에서 받은 점수들의 합이 됩니다.

예제

점수는 20점입니다.