14858번 - GCD 테이블과 연속 부분 수열

문제

크기가 n×m인 행렬 G가 있다. G[i][j]에는 i와 j의 최대공약수가 저장되어져 있다. (1 ≤ i ≤ n, 1 ≤ j ≤ m)

크기가 k인 수열 a₁, a₂, ..., a_k가 주어졌을 때, G에 이 수열이 연속 부분 수열로 등장하는지 안하는지 구하는 프로그램을 작성하시오. 즉, 모든 1 ≤ l ≤ k에 대해서, G[i][j+l-1] = a_l인 1 ≤ i ≤ n, 1 ≤ j ≤ m-k+1가 존재하는지 아닌지를 구해야 한다.

입력

첫째 줄에 n, m, k (1 ≤ n, m ≤ 10¹², 1 ≤ k ≤ 10000)가 주어진다.

둘째 줄에는 a₁, a₂, ..., a_k (1 ≤ a_i ≤ 10¹²)가 주어진다.

출력

G에 주어진 수열이 연속 부분 수열로 등장하면 YES를, 아니면 NO를 출력한다.

제한

힌트

예제 1의 경우에 G[10][5]부터 G[10][9]까지가 일치한다.