시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 242 91 63 48.837%

문제

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