시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB67621314239.227%

문제

하노이 탑 문제를 들어 보았을 것이다. 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으로 나눈 나머지를 출력한다.

예제 입력 1

7
2 1 4
2 1
3
7 6 5 4

예제 출력 1

3
4
W3sicHJvYmxlbV9pZCI6IjIyNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NThcdWIxNzhcdWM3NzQgXHVkMGQxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NThcdWIxNzhcdWM3NzQgXHVkMGQxIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gM1x1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWFlMzAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YWMwMCBcdWFmNDJcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzQ0IFx1YjJlNFx1Yjk3OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWI4NWMgXHVjNjJlXHVhZTMwXHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODAgXHViNTRjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWFjMDAgMlx1MjA3Zi0xXHVjNzg0XHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzYzRcdWM4MDRcdWQ1ODhcdWIyOTRcdWIzNzAsIFx1YjMwMFx1YjdiNSBcdWM4MTVcdWMyZTBcdWM3NzQgXHViYTRkXHVkNTc0XHVjOWM0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFkZjhcdWI5Y2MgXHVjMmU0XHVjMjE4XHViODVjIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YjRlNFx1Yzc0NCBcdWM3OThcdWJhYmIgXHVjNjJlXHVhY2E4XHViYzg0XHViODM4XHViMmU0LiBcdWFkZjhcdWI3OThcdWIzYzQgXHVkNTU4XHViMTc4XHVjNzc0IFx1ZDBkMSBcdWJiMzhcdWM4MWNcdWM3NTggXHVhZTMwXHViY2Y4XHVjODAxXHVjNzc4IFx1YWRkY1x1Y2U1OVx1Yzc0MCBcdWM1YjRcdWFlMzBcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjMTFjLCBuXHVhYzFjXHVjNzU4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YjRlNFx1Yzc0NCBcdWQ1NWMgXHViOWM5XHViMzAwXHVhZTMwXHViODVjIFx1YzYyZVx1YWUzOCBcdWMyMThcdWIyOTQgXHVjNzg4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzc0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMGMxXHVkMGRjXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWM3NzRcdWIzZDlcdWM3M2NcdWI4NWMgXHVkNTVjIFx1YjljOVx1YjMwMFx1YWUzMFx1Yjg1YyBcdWJhYThcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM1YjRcdWIyOTAgXHViOWM5XHViMzAwXHVhZTMwXHViODVjIFx1YmFhOFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjNzc0XHViM2Q5XHVjNzQwIFx1YmE4NyBcdWJjODhcdWM3NzhcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjJmNVx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCAxLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1YjljY1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBuKDEgJmxlOyBuICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggYSwgYiwgY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgMSwgMiwgM1x1YmM4OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWM1ZDAgXHVhZjQyXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWI1MTRcdWMyYTRcdWQwNmNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWIyOTQgMFx1Yzc3NFx1YzBjMSBuXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwLCBhICsgYiArIGMgPSBuXHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgM1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIDEsIDIsIDNcdWJjODggXHViOWM5XHViMzAwXHVhZTMwXHVjNWQwIFx1YWY0Mlx1ZDYwMCBcdWM3ODhcdWIyOTQgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJjMTFcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxLCAyLCAmaGVsbGlwOywgblx1Yzc3NFx1YmE3MCwgXHVjNzk4XHViYWJiXHViNDFjIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWI5YzlcdWIzMDBcdWFlMzBcdWM3NTggXHViYzg4XHVkNjM4KDEsIDIsIDMgXHVjOTExIFx1ZDU1OFx1YjA5OClcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyAxLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjI3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvd2VycyBvZiBIYW5vaSIsImRlc2NyaXB0aW9uIjoiPHA+U3VyZWx5IHlvdSBoYXZlIGFscmVhZHkgY29tZSBhY3Jvc3MgdGhlIFRvd2VycyBvZiBIYW5vaSBwcm9ibGVtOiBXb29kZW4gZGlza3Mgb2YgZGlmZmVyZW50IHNpemVzIGFyZSBzdGFja2VkIG9uIHRocmVlIHBlZ3MsIGFuZCBpbml0aWFsbHksIGFsbCBkaXNrcyBhcmUgc3RhY2tlZCBvbiB0aGUgc2FtZSBwZWcgc29ydGVkIGJ5IHNpemUsIHdpdGggdGhlIGxhcmdlc3QgZGlzayBhdCB0aGUgYm90dG9tLiBUaGUgb2JqZWN0aXZlIGlzIHRvIHRyYW5zZmVyIHRoZSBlbnRpcmUgdG93ZXIgdG8gb25lIG9mIHRoZSBvdGhlciBwZWdzLCBtb3Zpbmcgb25seSBvbmUgZGlzayBhdCBhIHRpbWUgYW5kIG5ldmVyIHB1dHRpbmcgYSBsYXJnZXIgZGlzayBvbnRvIGEgc21hbGxlciBvbmUuPFwvcD5cclxuXHJcbjxwPkFjY29yZGluZyB0byBhbiBvbGQgbXl0aCwgdGhlIG1vbmtzIGF0IGFuIGFuY2llbnQgVGliZXRpYW4gbW9uYXN0ZXJ5IGhhdmUgYmVlbiB0cnlpbmcgdG8gc29sdmUgYW4gZXNwZWNpYWxseSBsYXJnZSBpbnN0YW5jZSBvZiB0aGlzIHByb2JsZW0gd2l0aCA0NyBkaXNrcyBmb3IgdGhvdXNhbmRzIG9mIHllYXJzLiBTaW5jZSB0aGlzIHJlcXVpcmVzIGF0IGxlYXN0IDI8c3VwPjQ3PFwvc3VwPiAmbWludXM7IDEgbW92ZXMgYW5kIHRoZSBtb25rcyBzdGFydGVkIG91dCB3aXRob3V0IGEgc3RyYXRlZ3ksIHRoZXkgbWVzc2VkIGl0IGFsbCB1cCB3aGlsZSBzdGlsbCBmb2xsb3dpbmcgdGhlIHJ1bGVzLiBOb3cgdGhleSB3b3VsZCBsaWtlIHRvIGhhdmUgdGhlIGRpc2tzIHN0YWNrZWQgdXAgbmVhdGx5IG9uIGFueSBhcmJpdHJhcnkgcGVnIHVzaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3Zlcy4gQnV0IHRoZXkgYWxsIHRvb2sgYSB2b3cgd2hpY2ggZm9yYmlkcyB0aGVtIHRvIG1vdmUgdGhlIGRpc2tzIGNvbnRyYXJ5IHRvIHRoZSBydWxlcy4gVGhleSB3YW50IHRvIGtub3cgb24gd2hpY2ggcGVnIHRoZXkgc2hvdWxkIGJlc3Qgc3RhY2sgdGhlIGRpc2tzLCBhbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIG5lZWRlZC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgc29sdmVzIHRoaXMgcHJvYmxlbSBmb3IgdGhlIG1vbmtzLiBZb3VyIHByb2dyYW0gc2hvdWxkIGFsc28gYmUgYWJsZSB0byBoYW5kbGUgYW55IG51bWJlciBOICgwICZsdDsgTiAmbGU7IDEwMCAwMDApIG9mIGRpc2tzLiBUaGUgbnVtYmVycyBpbnZvbHZlZCBpbiB0aGUgY29tcHV0YXRpb24gY2FuIGJlY29tZSBxdWl0ZSBsYXJnZS4gQmVjYXVzZSBvZiB0aGF0LCB0aGUgbW9ua3MgYXJlIG9ubHkgaW50ZXJlc3RlZCBpbiB0aGUgbnVtYmVyIG9mIG1vdmVzIG1vZHVsbyAxIDAwMCAwMDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIHRoZSBudW1iZXIgTiBvZiBkaXNrcy4gVGhlIHNlY29uZCBsaW5lIGNvbnNpc3RzIG9mIHRocmVlIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgczxzdWI+MzxcL3N1Yj4gd2l0aCAwICZsZTsgczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCBzPHN1Yj4zPFwvc3ViPiAmbGU7IE4gYW5kIHM8c3ViPjE8XC9zdWI+K3M8c3ViPjI8XC9zdWI+K3M8c3ViPjM8XC9zdWI+ID0gTiwgdGhlIG51bWJlciBvZiBkaXNrcyBvbiBlYWNoIG9mIHRoZSB0aHJlZSBwZWdzLiBMaW5lcyB0aHJlZSB0byBcdWZiMDF2ZSBlYWNoIGNvbnRhaW4gdGhlIHNpemVzIG9mIHRoZSBkaXNrcyBmb3Igb25lIHBlZy4gTW9yZSBwcmVjaXNlbHk6IFRoZSAoaSArIDIpLXRoIGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnNpc3RzIG9mIGludGVnZXIgbnVtYmVycyBtPHN1Yj5pLDE8XC9zdWI+IC4gLiAuIG08c3ViPmksczxzdWI+aTxcL3N1Yj48XC9zdWI+IHdpdGggMSAmbGU7IG08c3ViPmksajxcL3N1Yj4gJmxlOyBOLCB0aGUgc2l6ZXMgb2YgdGhlIGRpc2tzIG9uIHBlZyBpLiBUaGUgZGlza3MgYXJlIGdpdmVuIGZyb20gYm90dG9tIHRvIHRvcCwgdGh1cyBtPHN1Yj5pLDE8XC9zdWI+ICZndDsgbTxzdWI+aSwyPFwvc3ViPiAmZ3Q7IC4gLiAuICZndDsgbTxzdWI+aSxzPHN1Yj5pPFwvc3ViPjxcL3N1Yj4uIE5vdGUgdGhhdCBhbiBlbXB0eSBzdGFjayBpcyBnaXZlbiBieSBhbiBlbXB0eSBsaW5lLiBUaGUgc2V0IG9mIE4gZGlza3MgaGF2ZSBkaWZmZXJlbnQgc2l6ZXMuIEFsbCBudW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQgY29uc2lzdHMgb2YgdGhlIG51bWJlciBkICZpc2luOyB7MSwgMiwgM30gb2YgdGhlIHBlZyBvbnRvIHdoaWNoIHRoZSBkaXNrcyBjYW4gYmUgc3RhY2tlZCB1c2luZyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMuIFRoZSBzZWNvbmQgbGluZSBjb25zaXN0cyBvZiB0aGUgbnVtYmVyIE0gb2YgcmVxdWlyZWQgbW92ZXMgbW9kdWxvIDEgMDAwIDAwMC48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZvbGxvd2luZyBleGFtcGxlIGNhbiBiZSBzb2x2ZWQgaW4gZm91ciBtb3Zlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oYW5vaS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDhweDsgd2lkdGg6NTQ4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=