주가 예측

김 씨는 주식 시장 분석가다. 최근 그는 여러 회사의 주가 차트를 보다가 흥미로운 사실을 발견했다. 나흘 연속으로 오른 주식은 대부분 다음 날 하락했다. 또한, 닷새째에 하락한 주가는 상승세였던 나흘 동안의 주가 중 둘째 날과 셋째 날 가격 사이에 위치하는 경우가 많았다. 예를 들어 A 회사의 주가가 나흘 연속으로 500원, 560원, 600원, 680원이었고, A 회사의 닷새째 주가가 580원이었다. 또한 B 회사의 주가가 나흘 연속으로 1,000원, 1,200원, 1,400원, 1,700원이었고, B 회사의 닷새째 주가가 1,350원이었다.

김 씨는 이전 주가 수열에서 최근 며칠간의 가격 변동 패턴과 일치하는 부분을 찾으면 다음 날의 주가를 상당히 정확하게 예측할 수 있다고 생각한다. 그는 또한 두 주가 수열의 상대 순위가 같으면 차트에서의 모양도 비슷하게 보이므로, 실제 가격보다 주가 수열에서의 상대 순위가 더 중요하다고 생각한다. 위 예에서 A 회사의 닷새 연속 주가 500원, 560원, 600원, 680원, 580원은 다섯 수 중 500이 가장 작고, 560이 두 번째로 작고, 600이 네 번째로 작은 식이므로 $(1, 2, 4, 5, 3)$으로 나타낼 수 있다. 또한 B 회사의 닷새 연속 주가 1,000원, 1,200원, 1,400원, 1,700원, 1,350원도 같은 이유로 $(1, 2, 4, 5, 3)$으로 나타낼 수 있다. 두 회사의 상대 순위가 같고, 그림 K.1에서 보듯이 닷새 연속 차트도 매우 비슷하게 보인다.

그림 K.1 A와 B 회사의 닷새 연속 차트

김 씨는 두 수열의 같은 위치에 있는 모든 상대 순위가 같으면 두 수열이 일치한다고 보기로 했다. 김 씨는 길이가 같은 두 수열의 R-match를 다음과 같이 정의했다. 길이가 같은 두 정수 수열 $x = (x_1, \cdots , x_m)$과 $y = (y_1, \cdots , y_m)$은, 각 $i$ ($1 ≤ i ≤ m$)에 대해 $x$에서의 $x_i$의 순위와 $y$에서의 $y_i$의 순위가 같을 때 그리고 그때만 R-match이다. 다음으로 그는 R-패턴 매칭 문제를 다음과 같이 정의했다. 길이 $m$인 정수 수열 $x$와 길이 $n$인 정수 수열 $y$ ($m ≤ n$)가 주어질 때, $x$와 $(y_i ,\cdots , y_{i+m-1})$이 R-match가 되는 $y$의 모든 위치 $i$를 찾는다. 예를 들어 $x = (33, 40, 22, 40, 41, 28)$이고 $y = (10, 20, 16, 27, 32, 12, 32, 33, 20, 25, 15, 25, 31, 17)$일 때, $x$와 $(y_4, \cdots , y_9)$는 R-match이다. 또한 $x$와 $(y_9, \cdots , y_{14})$도 R-match이다.

길이 $m$인 정수 수열 $x$와 길이 $n$인 정수 수열 $y$ ($m ≤ n$)가 주어질 때, $x$와 $y$에 대한 R-패턴 매칭 문제를 푸는 프로그램을 작성하시오.

프로그램은 표준 입력에서 읽는다. 입력은 두 정수 $m$과 $n$ ($1 ≤ m ≤ 10,000$, $1 ≤ n ≤ 1,000,000$, $m ≤ n$)이 있는 한 줄로 시작한다. 여기서 $m$은 $x$의 길이이고 $n$은 $y$의 길이이다. 둘째 줄에는 $x$의 $m$개 정수가 차례로 주어진다. 셋째 줄에는 $y$의 $n$개 정수가 차례로 주어진다. $x$와 $y$의 각 정수는 $1$부터 $10^9$까지이다.

프로그램은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 그 줄에는 $x$와 $(y_i ,\cdots , y_{i+m-1})$이 R-match가 되는 $y$의 모든 위치 $i$가 들어 있어야 한다. 각 위치는 증가하는 순서로 나와야 한다. 그러한 위치가 없으면 0을 출력한다.