개의 정점으로 구성된 무향 그래프를 생각하자. 각 정점은 번부터 번까지 정수 번호가 부여되어 있으며, 어느 두 정점도 번호를 공유하지 않는다.
이때 이상 이하의 서로 다른 두 양의 정수 와 에 대하여 다음 조건을 만족하는 그래프를 서로소 그래프라 한다.
- 와 가 서로소라면 번 정점과 번 정점을 연결하는 간선이 단 하나 존재한다.
- 와 가 서로소가 아니라면 번 정점과 번 정점을 연결하는 간선은 존재하지 않는다.
서로소 그래프에서 최단 거리를 구하는 개의 쿼리를 해결해 보자.
Input
첫 줄에 정점의 개수 과 쿼리의 개수 가 공백으로 구분되어 주어진다. (, )
2번째 줄부터 개의 줄에 양의 정수 가 한 줄에 하나씩 주어진다. ()
Output
각 쿼리에 대해, 번 정점과의 최단 거리가 최대인 정점의 번호를 라 하자.
번 정점과 번 정점 사이의 최단 거리를 줄바꿈으로 구분하여 출력한다.
단, 임의의 정점 에 대해 와 사이의 최단 거리는 으로 정의한다.
Samples
입력
5 4
1
2
4
5
출력
1
2
2
1