만드는 중입니다

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

집으로 돌아가기

면접 대비

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

요약
각 버튼은 현재 우주 번호와 OR 연산을 합니다. A에서 B로 가는 100회 이하의 버튼 누름 순서를 찾고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 4점

유형
그리디, 비트 연산
정답자
아직 제출이 없습니다

문제

콜라이더가 폭발한 뒤 스파이더맨 마일스 모랄레스는 평행 우주로 떨어졌다. 상황을 살펴보고 도움이 필요하다는 것을 깨달은 마일스는 곧바로 이 우주의 스파이더맨인 피터 파커를 찾아가 자신의 이야기를 들려주었다. 마일스가 실수로 가져온 콜라이더 설계도와 여러 변수를 분석한 두 사람은 마일스가 지금 우주 번호 AA에 있고, 그의 우주 번호는 BB라는 사실을 알아냈다. 몇 달 동안 작업한 끝에 두 사람은 마일스를 집으로 돌려보낼 수 있는 우주 간 이동 장치를 만들었다. 이 장치에는 a1,a2,…,ana_1, a_2, \ldots, a_n이라는 수가 적힌 nn개의 버튼이 있다. 버튼 aia_i를 누르면 현재 우주 번호 xx에서 우주 번호 x∨aix \lor a_i로 이동한다 (∨\lor는 비트 단위 OR 연산). 다만 자원이 부족해서 장치의 전력은 100번의 이동만큼만 남아 있다. 마일스와 피터는 마일스를 집으로 보내려면 버튼을 어떤 순서로 눌러야 하는지 고민하고 있다. 두 사람을 도와 달라.

입력

첫 줄에 세 정수 nn, AA, BB가 주어진다. nn은 버튼의 개수, AA는 마일스가 지금 있는 우주의 번호, BB는 마일스가 돌아가야 할 우주의 번호이다 (1≤n≤1051 \le n \le 10^5, 0≤A,B≤1090 \le A, B \le 10^9). 둘째 줄에는 버튼에 적힌 수 a1,a2,…,ana_1, a_2, \ldots, a_n이 주어진다 (1≤ai≤1091 \le a_i \le 10^9).

출력

마일스를 집으로 돌려보낼 수 없으면 −1-1을 한 줄에 출력한다. 돌려보낼 수 있으면 첫 줄에 버튼을 누르는 횟수 kk (0≤k≤1000 \le k \le 100)를 출력하고, 둘째 줄에 눌러야 할 버튼 번호를 누르는 순서대로 공백으로 구분해 출력한다. 답이 여러 개이면 아무거나 출력해도 된다.

힌트

첫 번째 예제에서는 먼저 1번 버튼을 눌러 우주 2에서 2∨3=32 \lor 3 = 3인 우주 3으로 이동한다. 그다음 4번 버튼을 눌러 우주 3에서 3∨10=113 \lor 10 = 11인 우주 11로 이동한다.

예제2

  1. 예제 1

    입력
    4 2 11
    3 2 6 10
    
    예상 출력
    2
    1 4
    
  2. 예제 2

    입력
    4 4 11
    3 2 6 10
    
    예상 출력
    -1