시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 66 23 16 38.095%

문제

하노이 탑 문제를 들어 보았을 것이다. 3개의 막대기 중 하나에 n개의 디스크가 꽂혀 있고, 이 디스크들을 다른 막대기로 옮기는 문제이다. 이 문제를 풀 때의 이동 회수가 2ⁿ-1임은 잘 알려져 있다.

동혁이는 이 문제에 도전했는데, 대략 정신이 멍해진 사이에 그만 실수로 디스크들을 잘못 옮겨버렸다. 그래도 하노이 탑 문제의 기본적인 규칙은 어기지 않아서, n개의 디스크들을 한 막대기로 옮길 수는 있게 되었다.

디스크들이 놓여 있는 상태가 입력으로 주어졌을 때, 이 디스크들을 최소의 이동으로 한 막대기로 모으려고 한다. 어느 막대기로 모아야 하는지, 그리고 최소의 이동은 몇 번인지를 알아내는 프로그램을 작성하시오. 답은 매우 커질 수 있기 때문에, 1,000,000으로 나눈 나머지만을 출력한다.

입력

첫째 줄에 정수 n(1≤n≤100,000)이 주어진다. 둘째 줄에는 세 정수 a, b, c가 주어진다. 이는 차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크의 개수이다. 이는 0이상 n이하이며, a+b+c=n이다. 다음 3개의 줄에는 차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크들의 번호가 밑에서부터 주어진다. 각 디스크들의 번호는 1, 2, …, n이며, 잘못된 입력은 주어지지 않는다.

출력

첫째 줄에 모아야 하는 막대기의 번호(1, 2, 3 중 하나)를 출력한다. 그 다음 줄에는 최소의 이동 회수를 1,000,000으로 나눈 나머지를 출력한다.

예제 입력

7
2 1 4
2 1
3
7 6 5 4

예제 출력

3
4

힌트