킥

인셉션은 다른 사람의 꿈에 들어가 무의식에 어떤 개념을 심어 두고, 꿈에서 깬 뒤에 그 개념을 스스로 떠올렸다고 믿게 만드는 일이다. 표적이 꿈을 현실이라고 믿게 만들기가 워낙 어려워서 오랫동안 불가능한 일로 여겨졌다.

꿈에서 표적의 정보를 빼내 오던 PurpleNoon 팀은 꿈 속의 꿈을 쓰면 꿈과 현실의 경계가 흐려져서 인셉션이 가능하다고 보았다. 꿈 속의 꿈은 매우 불안정해서 약을 써야 하는데, 약을 쓰면 좀처럼 깨어나지 못하는 경우가 있어서 킥을 함께 쓰기로 했다. 킥은 꿈꾸는 사람을 넘어뜨려 낙하하는 감각으로 잠을 깨우는 방법이다. 꿈 속에서나 현실에서나 같은 원리로 작동해서 잠든 사람을 깨울 수 있다.

PurpleNoon 팀은 꿈 속의 꿈, 또는 그보다 더 깊은 꿈까지 계획하고 있다. 상황에 따라 더 깊은 꿈으로 들어갈 수 있다. 모든 층에서 킥을 동시에 해야 하므로 현실에서 음악으로 미리 신호를 주고, 음악이 끝난 직후에 킥을 해서 모든 층에서 한 번에 현실로 돌아오려고 한다. 그런데 지금 몇 층 깊이의 꿈에 들어와 있는지 알아내기가 쉽지 않다. 그래서 만일에 대비해 지금 들리는 소리로 가능한 가장 얕은 깊이와 가장 깊은 깊이를 계산하려고 한다.

깊이는 음악의 빠르기로 짐작한다. 꿈으로 한 층 들어갈 때마다 음과 음 사이의 간격이 정확히 $1$씩 늘어나서 음악이 그만큼 느리게 들린다. 현실에서 1 2 3으로 들리던 음악은 한 층 들어가면 … 1 x 2 x 3 …으로, 한 층 더 들어가면 … 1 x x 2 x x 3 …으로 들린다. x 자리에는 어떤 음이 와도 되고 서로 달라도 된다. 앞뒤로 다른 음이 더 들릴 수도 있다.

정리하면 깊이가 $d$라는 말은, 꿈에서 들리는 음 중 어떤 위치에서 시작해 $d+1$칸씩 건너뛰며 읽었을 때 현실의 음 $n$개가 순서대로 나온다는 뜻이다. 현실은 깊이 $0$이다. 현실에서 들리는 음과 지금 꿈에서 들리는 음이 주어질 때, 가능한 꿈의 깊이 중 가장 얕은 값과 가장 깊은 값을 구하라.

첫째 줄에 현실에서 들리는 음의 개수 $n$이 주어진다. 둘째 줄에 현실에서 들리는 음 $n$개가 공백으로 구분되어 주어진다. 셋째 줄에 꿈에서 들리는 음의 개수 $m$이 주어진다. 넷째 줄에 꿈에서 들리는 음 $m$개가 공백으로 구분되어 주어진다.

$2 \le n \le m \le 1000$이고, 모든 음은 $10^9$ 이하의 자연수이다. 꿈에서 들리는 음에는 현실에 없는 음이 섞일 수 있다.

가능한 꿈의 깊이 중 가장 얕은 값과 가장 깊은 값을 공백으로 구분해 한 줄에 출력한다. 가능한 깊이가 하나도 없으면 -1만 출력한다.