만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

크라바이체

시간 제한1초메모리 제한1024 MB

요약
n개 집 가운데 일부를 골라 얻은 크라바이체 총합이 k의 배수가 되도록 하는 집 번호들을 출력한다.
난이도

보통10점 중 7점

유형
누적 합, 조합론, 수학, 해시맵
정답자
아직 제출이 없습니다

문제

쿨레브차 마을의 콜레다리들은 오래된 전통에 따라 크리스마스에 마을 집집마다 주인에게서 크라바이체(전통 과자)를 받는다. 각 집 주인은 몇 개의 크라바이체를 줄지 정해 두었다. 이 수는 콜레다리들의 수와 무관하며 해마다 같다. 어떤 집의 크라바이체가 모든 콜레다리에게 돌아가지 않을 수도 있다. 그래서 콜레다리들은 모든 크라바이체를 한곳에 모아 아침에 똑같이 나누기로 했다.

콜레다리들은 각 집에서 몇 개의 크라바이체를 받을지 알고 있다. 이들은 어떤 집을 방문할지 정해서 받은 크라바이체의 총 개수를 자기들끼리 똑같이 나눌 수 있게 해야 한다.

콜레다리들이 받은 크라바이체를 똑같이 나눌 수 있도록 방문해야 할 집을 정하는 프로그램 kravaiche를 작성해 도와주자.

입력

표준 입력의 첫째 줄에 두 수가 주어진다. k는 콜레다리들의 수, n은 마을의 집 수이다. 이어서 n개의 수 a1, a2, a3, …, an이 주어지는데, ai는 i번째 집을 방문하면 콜레다리들이 받게 될 크라바이체의 개수이다.

출력

표준 출력의 한 줄에 콜레다리들이 모은 크라바이체를 똑같이 나눌 수 있도록 방문해야 할 집들의 번호를 출력한다(첫 번째 집은 1, 두 번째 집은 2 등). 답이 여러 개면 그중 아무거나 출력한다. 답이 없으면 "no kravaiche"를 출력한다.

제한

  • 1 ≤ k ≤ n ≤ 100000
  • 1 ≤ ai ≤ 100000

예제2

  1. 예제 1

    입력
    3 6
    7 11 2 5 13 17
    
    예상 출력
    2 3 4
    
  2. 예제 2

    입력
    4 5
    1 2 3 7 5
    
    예상 출력
    3 5