시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 151 59 40 44.944%

문제

하노이 탑 문제를 들어 보았을 것이다. 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

힌트

W3sicHJvYmxlbV9pZCI6IjIyNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NThcdWIxNzhcdWM3NzQgXHVkMGQxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NThcdWIxNzhcdWM3NzQgXHVkMGQxIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gM1x1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWFlMzAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YWMwMCBcdWFmNDJcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzQ0IFx1YjJlNFx1Yjk3OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWI4NWMgXHVjNjJlXHVhZTMwXHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODAgXHViNTRjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWQ2OGNcdWMyMThcdWFjMDAgMlx1MjA3Zi0xXHVjNzg0XHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwIFx1YjNjNFx1YzgwNFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHViMzAwXHViN2I1IFx1YzgxNVx1YzJlMFx1Yzc3NCBcdWJhNGRcdWQ1NzRcdWM5YzQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWRmOFx1YjljYyBcdWMyZTRcdWMyMThcdWI4NWMgXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzQ0IFx1Yzc5OFx1YmFiYiBcdWM2MmVcdWFjYThcdWJjODRcdWI4MzhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YjNjNCBcdWQ1NThcdWIxNzhcdWM3NzQgXHVkMGQxIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFlMzBcdWJjZjhcdWM4MDFcdWM3NzggXHVhZGRjXHVjZTU5XHVjNzQwIFx1YzViNFx1YWUzMFx1YzljMCBcdWM1NGFcdWM1NDRcdWMxMWMsIG5cdWFjMWNcdWM3NTggXHViNTE0XHVjMmE0XHVkMDZjXHViNGU0XHVjNzQ0IFx1ZDU1YyBcdWI5YzlcdWIzMDBcdWFlMzBcdWI4NWMgXHVjNjJlXHVhZTM4IFx1YzIxOFx1YjI5NCBcdWM3ODhcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcbjxwPlx1YjUxNFx1YzJhNFx1ZDA2Y1x1YjRlNFx1Yzc3NCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1YjRlNFx1Yzc0NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjNzc0XHViM2Q5XHVjNzNjXHViODVjIFx1ZDU1YyBcdWI5YzlcdWIzMDBcdWFlMzBcdWI4NWMgXHViYWE4XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjljOVx1YjMwMFx1YWUzMFx1Yjg1YyBcdWJhYThcdWM1NDRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjZDVjXHVjMThjXHVjNzU4IFx1Yzc3NFx1YjNkOVx1Yzc0MCBcdWJhODcgXHViYzg4XHVjNzc4XHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZjVcdWM3NDAgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMSwwMDAsMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5Y2NcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBuKDEmbGU7biZsZTsxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBhLCBiLCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyAxLCAyLCAzXHViYzg4IFx1YjljOVx1YjMwMFx1YWUzMFx1YzVkMCBcdWFmNDJcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCAwXHVjNzc0XHVjMGMxIG5cdWM3NzRcdWQ1NThcdWM3NzRcdWJhNzAsIGErYitjPW5cdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyAzXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgMSwgMiwgM1x1YmM4OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWM1ZDAgXHVhZjQyXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWI1MTRcdWMyYTRcdWQwNmNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YmMxMVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWI1MTRcdWMyYTRcdWQwNmNcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDEsIDIsICZoZWxsaXA7LCBuXHVjNzc0XHViYTcwLCBcdWM3OThcdWJhYmJcdWI0MWMgXHVjNzg1XHViODI1XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOFx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViOWM5XHViMzAwXHVhZTMwXHVjNzU4IFx1YmM4OFx1ZDYzOCgxLCAyLCAzIFx1YzkxMSBcdWQ1NThcdWIwOTgpXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1Yzc3NFx1YjNkOSBcdWQ2OGNcdWMyMThcdWI5N2MgMSwwMDAsMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjI3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRvd2VycyBvZiBIYW5vaSIsImRlc2NyaXB0aW9uIjoiPHA+U3VyZWx5IHlvdSBoYXZlIGFscmVhZHkgY29tZSBhY3Jvc3MgdGhlIFRvd2VycyBvZiBIYW5vaSBwcm9ibGVtOiBXb29kZW4gZGlza3Mgb2YgZGlmZmVyZW50IHNpemVzIGFyZSBzdGFja2VkIG9uIHRocmVlIHBlZ3MsIGFuZCBpbml0aWFsbHksIGFsbCBkaXNrcyBhcmUgc3RhY2tlZCBvbiB0aGUgc2FtZSBwZWcgc29ydGVkIGJ5IHNpemUsIHdpdGggdGhlIGxhcmdlc3QgZGlzayBhdCB0aGUgYm90dG9tLiBUaGUgb2JqZWN0aXZlIGlzIHRvIHRyYW5zZmVyIHRoZSBlbnRpcmUgdG93ZXIgdG8gb25lIG9mIHRoZSBvdGhlciBwZWdzLCBtb3Zpbmcgb25seSBvbmUgZGlzayBhdCBhIHRpbWUgYW5kIG5ldmVyIHB1dHRpbmcgYSBsYXJnZXIgZGlzayBvbnRvIGEgc21hbGxlciBvbmUuPFwvcD5cclxuXHJcbjxwPkFjY29yZGluZyB0byBhbiBvbGQgbXl0aCwgdGhlIG1vbmtzIGF0IGFuIGFuY2llbnQgVGliZXRpYW4gbW9uYXN0ZXJ5IGhhdmUgYmVlbiB0cnlpbmcgdG8gc29sdmUgYW4gZXNwZWNpYWxseSBsYXJnZSBpbnN0YW5jZSBvZiB0aGlzIHByb2JsZW0gd2l0aCA0NyBkaXNrcyBmb3IgdGhvdXNhbmRzIG9mIHllYXJzLiBTaW5jZSB0aGlzIHJlcXVpcmVzIGF0IGxlYXN0IDI8c3VwPjQ3PFwvc3VwPiAmbWludXM7IDEgbW92ZXMgYW5kIHRoZSBtb25rcyBzdGFydGVkIG91dCB3aXRob3V0IGEgc3RyYXRlZ3ksIHRoZXkgbWVzc2VkIGl0IGFsbCB1cCB3aGlsZSBzdGlsbCBmb2xsb3dpbmcgdGhlIHJ1bGVzLiBOb3cgdGhleSB3b3VsZCBsaWtlIHRvIGhhdmUgdGhlIGRpc2tzIHN0YWNrZWQgdXAgbmVhdGx5IG9uIGFueSBhcmJpdHJhcnkgcGVnIHVzaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3Zlcy4gQnV0IHRoZXkgYWxsIHRvb2sgYSB2b3cgd2hpY2ggZm9yYmlkcyB0aGVtIHRvIG1vdmUgdGhlIGRpc2tzIGNvbnRyYXJ5IHRvIHRoZSBydWxlcy4gVGhleSB3YW50IHRvIGtub3cgb24gd2hpY2ggcGVnIHRoZXkgc2hvdWxkIGJlc3Qgc3RhY2sgdGhlIGRpc2tzLCBhbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIG5lZWRlZC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgc29sdmVzIHRoaXMgcHJvYmxlbSBmb3IgdGhlIG1vbmtzLiBZb3VyIHByb2dyYW0gc2hvdWxkIGFsc28gYmUgYWJsZSB0byBoYW5kbGUgYW55IG51bWJlciBOICgwICZsdDsgTiAmbGU7IDEwMCAwMDApIG9mIGRpc2tzLiBUaGUgbnVtYmVycyBpbnZvbHZlZCBpbiB0aGUgY29tcHV0YXRpb24gY2FuIGJlY29tZSBxdWl0ZSBsYXJnZS4gQmVjYXVzZSBvZiB0aGF0LCB0aGUgbW9ua3MgYXJlIG9ubHkgaW50ZXJlc3RlZCBpbiB0aGUgbnVtYmVyIG9mIG1vdmVzIG1vZHVsbyAxIDAwMCAwMDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIHRoZSBudW1iZXIgTiBvZiBkaXNrcy4gVGhlIHNlY29uZCBsaW5lIGNvbnNpc3RzIG9mIHRocmVlIGludGVnZXJzIHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgczxzdWI+MzxcL3N1Yj4gd2l0aCAwICZsZTsgczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCBzPHN1Yj4zPFwvc3ViPiAmbGU7IE4gYW5kIHM8c3ViPjE8XC9zdWI+K3M8c3ViPjI8XC9zdWI+K3M8c3ViPjM8XC9zdWI+ID0gTiwgdGhlIG51bWJlciBvZiBkaXNrcyBvbiBlYWNoIG9mIHRoZSB0aHJlZSBwZWdzLiBMaW5lcyB0aHJlZSB0byBcdWZiMDF2ZSBlYWNoIGNvbnRhaW4gdGhlIHNpemVzIG9mIHRoZSBkaXNrcyBmb3Igb25lIHBlZy4gTW9yZSBwcmVjaXNlbHk6IFRoZSAoaSArIDIpLXRoIGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnNpc3RzIG9mIGludGVnZXIgbnVtYmVycyBtPHN1Yj5pLDE8XC9zdWI+IC4gLiAuIG08c3ViPmksczxzdWI+aTxcL3N1Yj48XC9zdWI+IHdpdGggMSAmbGU7IG08c3ViPmksajxcL3N1Yj4gJmxlOyBOLCB0aGUgc2l6ZXMgb2YgdGhlIGRpc2tzIG9uIHBlZyBpLiBUaGUgZGlza3MgYXJlIGdpdmVuIGZyb20gYm90dG9tIHRvIHRvcCwgdGh1cyBtPHN1Yj5pLDE8XC9zdWI+ICZndDsgbTxzdWI+aSwyPFwvc3ViPiAmZ3Q7IC4gLiAuICZndDsgbTxzdWI+aSxzPHN1Yj5pPFwvc3ViPjxcL3N1Yj4uIE5vdGUgdGhhdCBhbiBlbXB0eSBzdGFjayBpcyBnaXZlbiBieSBhbiBlbXB0eSBsaW5lLiBUaGUgc2V0IG9mIE4gZGlza3MgaGF2ZSBkaWZmZXJlbnQgc2l6ZXMuIEFsbCBudW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQgY29uc2lzdHMgb2YgdGhlIG51bWJlciBkICZpc2luOyB7MSwgMiwgM30gb2YgdGhlIHBlZyBvbnRvIHdoaWNoIHRoZSBkaXNrcyBjYW4gYmUgc3RhY2tlZCB1c2luZyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMuIFRoZSBzZWNvbmQgbGluZSBjb25zaXN0cyBvZiB0aGUgbnVtYmVyIE0gb2YgcmVxdWlyZWQgbW92ZXMgbW9kdWxvIDEgMDAwIDAwMC48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZvbGxvd2luZyBleGFtcGxlIGNhbiBiZSBzb2x2ZWQgaW4gZm91ciBtb3Zlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oYW5vaS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDhweDsgd2lkdGg6NTQ4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==