퍼즐 게임 Output Only Compilation commands

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

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

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

입력 형식

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

두 번째 줄에는 격자판 안에 있는 블록들의 색을 나타내는 $n$개의 자연수 $b_{1}, b_{2}, ..., b_{n}$이 공백을 사이로 두고 주어집니다.

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

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

출력 형식

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

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

파일 정보

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

입력 파일명	출력 파일명	n	c	m	t
F1.in	F1.out	10	4	1,000	420
F2.in	F2.out	20	5	3,000	1,300
F3.in	F3.out	30	5	10,000	4,320
F4.in	F4.out	40	6	10,000	4,490
F5.in	F5.out	50	6	10,000	4,440

채점 방식

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

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

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

예제

입력

10
4
1 2 2 3 3 3 4 4 4 4
8 2
3 1 2 3 4 3 2 1

출력

2
7 10
4 7

점수는 20점입니다.