27504번 - 상대음감의 노래찾기

상대음감은 음을 절대적인 높이로 구분하는 것이 아닌 어떤 음과의 상대적인 높이로 음을 인식하는 능력을 말한다. 상대음감은 절대음감에 비해 불리한 점이 있지만, 노래를 찾을 때 어렴풋한 멜로디 만으로도 노래를 찾을 수 있다는 장점이 있다.

기령이는 이러한 점에서 착안하여 상대음감의 노래찾기 서비스를 만들려고 한다. 노래찾기 서비스는 데이터베이스에 노래의 음 데이터를 갖고 있으며 사용자가 멜로디를 입력했을 때 그 멜로디가 데이터베이스의 노래에 포함되어 있으면 해당 노래를 안내해 주는 서비스이다. 상대음감의 노래찾기 서비스는 상대적인 멜로디가 포함되어 있어도 일치하는 것으로 판단해 노래를 안내해준다. 즉, 찾으려는 멜로디가 $a_1,\ a_2,\ \cdots, \ a_L$일때, 임의의 정수 $x$에 대하여 $a_1+x,\ a_2+x,\ \cdots, \ a_L+x$를 포함하면 일치하는 것으로 판단한다.

예를 들어 사용자가 "1 2 1 2"의 멜로디를 입력했을 때, "3 4 3 4 5 5"라는 노래에는 이러한 멜로디가 포함되어 있으며 따라서 해당 노래를 안내해줄 것이다.

상대음감의 노래찾기 서비스를 구현해보자.

첫째 줄에 데이터베이스에 존재하는 노래의 수 $N$이 주어진다. $(1 \leq N \leq 1\ 000)$

이후 $N$개의 줄에 걸쳐 $i(1 \leq i \leq N)$번 노래의 길이 $K_i$$(2 \leq K_i \leq 100\ 000)$, 음 데이터 $a_1\ a_2\ \cdots \ a_{K_i}$가 공백으로 구분되어 주어진다. 단, 모든 $K_i$의 합은 $1\ 000\ 000$을 넘기지 않는다.

다음 줄에 찾으려는 멜로디의 길이 $L$가 주어진다.$(2 \leq L \leq 10\ 000)$ 그 다음 줄에 길이가 $L$인 멜로디 데이터 $b_1\ b_2\ ... \ b_{L}$가 주어진다.

데이터의 모든 값은 $1$보다 크거나 같고 $10\ 000$보다 작거나 같다.

찾으려는 멜로디 데이터가 존재하는 노래의 번호를 공백으로 구분하여 오름차순으로 출력한다. 존재하지 않을 경우 -1을 출력한다.