시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

전 세계에 걸쳐 첩보 비밀 조직망을 구축하고 있는 아이리스의 정체는 베일에 싸여 있다. 그러나 국가간 분쟁 조장이나 무기 매매 등의 방법으로 거액의 자금을 운용하고 있음이 알려져 있다. 아이리스의 조직원들은 평범한 학생으로부터 학계, 금융계, 정치계의 주요 인물에까지 광범위하게 배치되어 있다. 그들은 때론 평범한 텍스트를 통해 서로에게 조직의 암호를 전달하기도 한다. 영업사원의 감사 편지, CNN 머리기사나 입사시험 문제지 속에도 조직의 암호가 숨어 있을 수 있다. 암호를 푸는 방법은 개별 조직원에게 부정기적으로 전달된다.

최근 아이리스 조직원 ‘ 백산’ 은 텍스트로부터 비밀번호를 풀어 내는 방법을 전달받았다. 주어진 단어가 텍스트에 등장하는 횟수와 위치가 비밀번호가 된다. 비밀번호의 첫 숫자는 등장횟수이고 나머지 숫자들은 위치들이다. 만약 등장횟수가 2 회이면 2 X Y 가 비밀번호가 되고 3 회이면 3 X Y Z 가 비밀번호가 된다 (X,Y,Z 는 정수). 단어의 각 문자는 텍스트 안에서 연속하지 않아도 된다. 단어의 위치는 단어의 마지막 문자의 위치로써 표시된다. 만약 단어의 마지막 문자가 중복될 때 맨 처음 것이 채택된다. 문자의 위치는 텍스트의 시작 문자를 1 로 봤을 때의 상대위치로써 표시된다. 대소문자는 구분하지 않는다.

다음의 표에 단어와 텍스트로부터 비밀번호를 풀어내는 예제들이 나와 있다. 예제 1 에서 주어진 단어는 텍스트에 한번도 등장하지 않으므로 등장횟수가 0 이고 비밀번호도 0 이다. 예제 2 에서 등장횟수는 1 이고 단어의 마지막 문자 a 의 위치는 2 이므로 비밀번호는 1 2 이다 . 예제 3 은 대소문자를 구분하지 않음을 보여주는데 등장횟수는 1 이고 마지막 문자 i 의 위치는 4 이므로 비밀 번호가 1 4 가 된다. 이 예제는 단어의 문자들이 순서대로 등장하지 않으면 등장하지 않은 것으로 봄도 보여준다. 예제 4 는 단어의 문자들이 연속하지 않아도 등장한 것으로 봄을 보여주는데 등장횟수가 2 이고 위치가 3 과 4 이므로 비밀번호는 2 3 4 이다. 예제 5 는 단어의 마지막 문자가 중복될 때 맨 처음 것이 채택됨을 보여 준다. 예제 6 은 단어의 각 문자가 텍스트에서 연속해서 나오는 경우를 보여준다. 

  단어 텍스트 비밀번호
예제 1 sample elpmas 0
예제 2 ca cab 1 2
예제 3 Bi ibbie 1 4
예제 4 bo bboo 2 3 4
예제 5 Abc aabccbcc 2 4 7
예제 6 Boy bbboooyyy 3 7 8 9

입력

입력은 표준입력 (standard input)을 통해 받아 들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1<=T<=20)가 주어진다. 각 테스트케이스의 첫 줄에는 단어가 입력된다. 단어는 영문자와 숫자만 포함할 수 있다. 둘째 줄에는 텍스트가 입력된다. 텍스트는 영문자와 숫자와 공란을 포함할 수 있으나 첫 문자는 공란이 아니다. 단어의 최대 길이는 10이고 텍스트의 최대 길이는 200,000이다. 단어는 텍스트에서 최대 40,000회까지 등장할 수 있다. 대소문자를 구분하지 않았을 때 같은 문자는 단어 내에 두 번 이상 나올 수 없다. 

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 단어가 텍스트에 등장하는 횟수와 위치들이 출력된다. 대소문자는 구분하지 않는다. 단어의 위치는 단어의 마지막 문자의 위치로써 표시된다. 만약 단어의 마지막 문자가 중복될 때 맨 처음 것이 채택된다. 문자의 위치는 텍스트의 시작 문자를 1 로 봤을 때의 상대위치로써 표시된다.

각 테스트 케이스는 각각 한 줄의 숫자(integer)들을 출력한다. 한 줄의 숫자들 중 첫 번째 숫자는 등장횟수이고 나머지는 위치들이다. 만약 등장 횟수가 3 회 이상이라면 위치들 중 처음 3 개만 출력한다. 따라서 등장 횟수가 3 회 이상인 테스트 케이스에 대해서는 4 개의 숫자만 출력한다. 

예제 입력 1

6
Cat
At a car
B
Def abc
key
yeey kkk yey yeyy
Al
Qaeda No 2 speaks on flotilla incident
R
Rrrrrrr
ac
aaaaaabbbbbbcccccc

예제 출력 1

0
1 6
2 12 16
3 23 27 28
7 1 2 3
6 13 14 15