시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 200 75 53 49.533%

문제

하노이 탑 문제를 들어 보았을 것이다. 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+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVG93ZXJzIG9mIEhhbm9pIiwiZGVzY3JpcHRpb24iOiI8cD5TdXJlbHkgeW91IGhhdmUgYWxyZWFkeSBjb21lIGFjcm9zcyB0aGUgVG93ZXJzIG9mIEhhbm9pIHByb2JsZW06IFdvb2RlbiBkaXNrcyBvZiBkaWZmZXJlbnQgc2l6ZXMgYXJlIHN0YWNrZWQgb24gdGhyZWUgcGVncywgYW5kIGluaXRpYWxseSwgYWxsIGRpc2tzIGFyZSBzdGFja2VkIG9uIHRoZSBzYW1lIHBlZyBzb3J0ZWQgYnkgc2l6ZSwgd2l0aCB0aGUgbGFyZ2VzdCBkaXNrIGF0IHRoZSBib3R0b20uIFRoZSBvYmplY3RpdmUgaXMgdG8gdHJhbnNmZXIgdGhlIGVudGlyZSB0b3dlciB0byBvbmUgb2YgdGhlIG90aGVyIHBlZ3MsIG1vdmluZyBvbmx5IG9uZSBkaXNrIGF0IGEgdGltZSBhbmQgbmV2ZXIgcHV0dGluZyBhIGxhcmdlciBkaXNrIG9udG8gYSBzbWFsbGVyIG9uZS48XC9wPlxyXG5cclxuPHA+QWNjb3JkaW5nIHRvIGFuIG9sZCBteXRoLCB0aGUgbW9ua3MgYXQgYW4gYW5jaWVudCBUaWJldGlhbiBtb25hc3RlcnkgaGF2ZSBiZWVuIHRyeWluZyB0byBzb2x2ZSBhbiBlc3BlY2lhbGx5IGxhcmdlIGluc3RhbmNlIG9mIHRoaXMgcHJvYmxlbSB3aXRoIDQ3IGRpc2tzIGZvciB0aG91c2FuZHMgb2YgeWVhcnMuIFNpbmNlIHRoaXMgcmVxdWlyZXMgYXQgbGVhc3QgMjxzdXA+NDc8XC9zdXA+ICZtaW51czsgMSBtb3ZlcyBhbmQgdGhlIG1vbmtzIHN0YXJ0ZWQgb3V0IHdpdGhvdXQgYSBzdHJhdGVneSwgdGhleSBtZXNzZWQgaXQgYWxsIHVwIHdoaWxlIHN0aWxsIGZvbGxvd2luZyB0aGUgcnVsZXMuIE5vdyB0aGV5IHdvdWxkIGxpa2UgdG8gaGF2ZSB0aGUgZGlza3Mgc3RhY2tlZCB1cCBuZWF0bHkgb24gYW55IGFyYml0cmFyeSBwZWcgdXNpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzLiBCdXQgdGhleSBhbGwgdG9vayBhIHZvdyB3aGljaCBmb3JiaWRzIHRoZW0gdG8gbW92ZSB0aGUgZGlza3MgY29udHJhcnkgdG8gdGhlIHJ1bGVzLiBUaGV5IHdhbnQgdG8ga25vdyBvbiB3aGljaCBwZWcgdGhleSBzaG91bGQgYmVzdCBzdGFjayB0aGUgZGlza3MsIGFuZCB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgbmVlZGVkLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBzb2x2ZXMgdGhpcyBwcm9ibGVtIGZvciB0aGUgbW9ua3MuIFlvdXIgcHJvZ3JhbSBzaG91bGQgYWxzbyBiZSBhYmxlIHRvIGhhbmRsZSBhbnkgbnVtYmVyIE4gKDAgJmx0OyBOICZsZTsgMTAwIDAwMCkgb2YgZGlza3MuIFRoZSBudW1iZXJzIGludm9sdmVkIGluIHRoZSBjb21wdXRhdGlvbiBjYW4gYmVjb21lIHF1aXRlIGxhcmdlLiBCZWNhdXNlIG9mIHRoYXQsIHRoZSBtb25rcyBhcmUgb25seSBpbnRlcmVzdGVkIGluIHRoZSBudW1iZXIgb2YgbW92ZXMgbW9kdWxvIDEgMDAwIDAwMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29uc2lzdHMgb2YgdGhlIG51bWJlciBOIG9mIGRpc2tzLiBUaGUgc2Vjb25kIGxpbmUgY29uc2lzdHMgb2YgdGhyZWUgaW50ZWdlcnMgczxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCBzPHN1Yj4zPFwvc3ViPiB3aXRoIDAgJmxlOyBzPHN1Yj4xPFwvc3ViPiwgczxzdWI+MjxcL3N1Yj4sIHM8c3ViPjM8XC9zdWI+ICZsZTsgTiBhbmQgczxzdWI+MTxcL3N1Yj4rczxzdWI+MjxcL3N1Yj4rczxzdWI+MzxcL3N1Yj4gPSBOLCB0aGUgbnVtYmVyIG9mIGRpc2tzIG9uIGVhY2ggb2YgdGhlIHRocmVlIHBlZ3MuIExpbmVzIHRocmVlIHRvIFx1ZmIwMXZlIGVhY2ggY29udGFpbiB0aGUgc2l6ZXMgb2YgdGhlIGRpc2tzIGZvciBvbmUgcGVnLiBNb3JlIHByZWNpc2VseTogVGhlIChpICsgMiktdGggbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29uc2lzdHMgb2YgaW50ZWdlciBudW1iZXJzIG08c3ViPmksMTxcL3N1Yj4gLiAuIC4gbTxzdWI+aSxzPHN1Yj5pPFwvc3ViPjxcL3N1Yj4gd2l0aCAxICZsZTsgbTxzdWI+aSxqPFwvc3ViPiAmbGU7IE4sIHRoZSBzaXplcyBvZiB0aGUgZGlza3Mgb24gcGVnIGkuIFRoZSBkaXNrcyBhcmUgZ2l2ZW4gZnJvbSBib3R0b20gdG8gdG9wLCB0aHVzIG08c3ViPmksMTxcL3N1Yj4gJmd0OyBtPHN1Yj5pLDI8XC9zdWI+ICZndDsgLiAuIC4gJmd0OyBtPHN1Yj5pLHM8c3ViPmk8XC9zdWI+PFwvc3ViPi4gTm90ZSB0aGF0IGFuIGVtcHR5IHN0YWNrIGlzIGdpdmVuIGJ5IGFuIGVtcHR5IGxpbmUuIFRoZSBzZXQgb2YgTiBkaXNrcyBoYXZlIGRpZmZlcmVudCBzaXplcy4gQWxsIG51bWJlcnMgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIG91dHB1dCBjb25zaXN0cyBvZiB0aGUgbnVtYmVyIGQgJmlzaW47IHsxLCAyLCAzfSBvZiB0aGUgcGVnIG9udG8gd2hpY2ggdGhlIGRpc2tzIGNhbiBiZSBzdGFja2VkIHVzaW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3Zlcy4gVGhlIHNlY29uZCBsaW5lIGNvbnNpc3RzIG9mIHRoZSBudW1iZXIgTSBvZiByZXF1aXJlZCBtb3ZlcyBtb2R1bG8gMSAwMDAgMDAwLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgZm9sbG93aW5nIGV4YW1wbGUgY2FuIGJlIHNvbHZlZCBpbiBmb3VyIG1vdmVzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2hhbm9pLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0OHB4OyB3aWR0aDo1NDhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=