문제
어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.
- 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
- 예를 들어, $\{1,1,5\}$는 $\{3,\underline{\color{blue} 1} ,4,\underline{\color{blue} 1} ,\underline{\color{blue} 5} ,9\}$의 부분 수열이지만, $\{1,5,1\}$의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.
- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 0ドル$인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 $N$인 수열 $\{A_1,\cdots ,A_N\}$이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 $M$인 수열 $\{B_1,\cdots ,B_M\}$이 주어집니다.
수열 $A$와 수열 $B$가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.
출력
$A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 $K$를 출력하세요.
$K \ne 0$이라면, 다음 줄에 $K$개의 수를 공백으로 구분해 출력하세요. $i$번째 수는 $A$와 $B$의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 $i$번째 수입니다.
다음 수열들은 모두 $A$와 $B$의 공통 부분 수열입니다.
$$\begin{array}{cccc}\{\} & \{1\} & \{1,3\} & \{1,7\} \\\{1,7,3\} & \{3\} & \{7\} & \{7,3\} \\\end{array}$$
이 중 사전 순으로 가장 나중인 수열은 $\{7,3\}$입니다.
W3sicHJvYmxlbV9pZCI6IjMwODA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVjODA0IFx1YzIxYyBcdWNkNWNcdWIzMDAgXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjVhNCBcdWMyMThcdWM1ZjRcdWM3NzQgXHViMmU0XHViOTc4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDU3NFx1YjJmOSBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHViNGU0XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWMyMThcdWM1ZjQgXHViMGI0XHVjNWQwXHVjMTFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI0ZjFcdWM3YTVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICRcXHsxLDEsNVxcfSRcdWIyOTQgJFxcezMsXFx1bmRlcmxpbmV7XFxjb2xvcntibHVlfSAxfSAsNCxcXHVuZGVybGluZXtcXGNvbG9ye2JsdWV9IDF9ICxcXHVuZGVybGluZXtcXGNvbG9ye2JsdWV9IDV9ICw5XFx9JFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHVjOWMwXHViOWNjLCAkXFx7MSw1LDFcXH0kXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDAgXHVjNTQ0XHViMmQ5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjYxMFx1ZDU1YywgXHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVjMjE4XHVjNWY0XHViY2Y0XHViMmU0IFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHViMDk4XHVjOTExXHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjQ1MCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHVhYzAwIFx1ZDA3MCBcdWNhYmRcdWM3NDAgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWIwOThcdWM5MTFcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWFjMDAgXHVhYzE5XHViMmU0XHViYTc0LCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWJlN2NcdWFjZTAgXHViNDUwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHViZTQ0XHVhZDUwXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YjA5OFx1YzkxMVx1Yzc3OCBcdWNhYmRcdWM3NzQgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWIwOThcdWM5MTFcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NFx1YWMwMCAkMCRcdWM3NzggXHVjMjE4XHVjNWY0XHVhY2ZjIFx1YjJlNFx1Yjk3OCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViZTQ0XHVhZDUwXHVkNTU4XHViYTc0LCBcdWIyZTRcdWI5NzggXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHViMDk4XHVjOTExXHVjNzg1XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCAkTiRcdWM3NzggXHVjMjE4XHVjNWY0ICRcXHtBXzEsXFxjZG90cyAsQV9OXFx9JFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgJE0kXHVjNzc4IFx1YzIxOFx1YzVmNCAkXFx7Ql8xLFxcY2RvdHMgLEJfTVxcfSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgJEEkXHVjNjQwIFx1YzIxOFx1YzVmNCAkQiRcdWFjMDAgXHVhY2Y1XHVkMWI1XHVjNzNjXHViODVjIFx1YWMxNlx1YjI5NCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHViNGU0IFx1YzkxMSBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWIwOThcdWM5MTFcdWM3NzggXHVhYzgzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0ICRBJFx1Yzc1OCBcdWFlMzhcdWM3NzQgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgTiBcXGxlIDEwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJEFfMSxBXzIsXFxjZG90cyxBX04kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgQV9pIFxcbGUgMTAwKSQ8XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1ZjQgJEIkXHVjNzU4IFx1YWUzOFx1Yzc3NCAkTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkKDEgXFxsZSBNIFxcbGUgMTAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMTM3XHVjOWY4IFx1YzkwNFx1YzVkMCAkTSRcdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkQl8xLEJfMixcXGNkb3RzLEJfTSRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkKDEgXFxsZSBCX2kgXFxsZSAxMDApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRBJFx1YzY0MCAkQiRcdWM3NTggXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YjA5OFx1YzkxMVx1Yzc3OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwICRLJFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuXHJcbjxwPiRLIFxcbmUgMCRcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgJEskXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gJGkkXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCAkQSRcdWM2NDAgJEIkXHVjNzU4IFx1YWNmNVx1ZDFiNSBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IFx1YzkxMSBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWIwOThcdWM5MTFcdWM3NzggXHVjMjE4XHVjNWY0XHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YjJlNFx1Yzc0YyBcdWMyMThcdWM1ZjRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwICRBJFx1YzY0MCAkQiRcdWM3NTggXHVhY2Y1XHVkMWI1IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiQkXFxiZWdpbnthcnJheX17Y2NjY31cXHtcXH0gJmFtcDsgXFx7MVxcfSAmYW1wOyBcXHsxLDNcXH0gJmFtcDsgXFx7MSw3XFx9IFxcXFxcXHsxLDcsM1xcfSAmYW1wOyBcXHszXFx9ICZhbXA7IFxcezdcXH0gJmFtcDsgXFx7NywzXFx9IFxcXFxcXGVuZHthcnJheX0kJDxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjOTExIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YjA5OFx1YzkxMVx1Yzc3OCBcdWMyMThcdWM1ZjRcdWM3NDAgJFxcezcsM1xcfSRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzA4MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMZXhpY29ncmFwaGljYWxseSBMYXJnZXN0IENvbW1vbiBTdWJzZXF1ZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+SWYgYSBzZXF1ZW5jZSBpcyBhIHN1YnNlcXVlbmNlIG9mIGFub3RoZXIgc2VxdWVuY2UsIGl0IG1lZXRzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlIGFwcGVhcnMgaW4gdGhlIG90aGVyIHNlcXVlbmNlIGluIG9yZGVyLjxcL2xpPlxyXG5cdDxsaT5Gb3IgZXhhbXBsZSwgJFxcezEsMSw1XFx9JCBpcyBhIHN1YnNlcXVlbmNlIG9mICRcXHszLFxcdW5kZXJsaW5le1xcY29sb3J7Ymx1ZX0gMX0gLDQsXFx1bmRlcmxpbmV7XFxjb2xvcntibHVlfSAxfSAsXFx1bmRlcmxpbmV7XFxjb2xvcntibHVlfSA1fSAsOVxcfSQgYnV0IGl0IGlzIG5vdCBhIHN1YnNlcXVlbmNlIG9mICRcXHsxLDUsMVxcfSQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gYWRkaXRpb24sIGlmIGEgc2VxdWVuY2UgY29tZXMgbGF0ZXIgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyIGNvbXBhcmVkIHRvIGFub3RoZXIgc2VxdWVuY2UsIGl0IG1lZXRzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgdHdvIHNlcXVlbmNlcywgdGhlIHNlcXVlbmNlJm5ic3A7d2hvc2UmbmJzcDtmaXJzdCBlbGVtZW50IGlzIGxhcmdlciBjb21lcyBsYXRlciBpbiBsZXhpY29ncmFwaGljYWwgb3JkZXIuPFwvbGk+XHJcblx0PGxpPklmIHRoZWlyIGZpcnN0IGVsZW1lbnRzIGFyZSBlcXVhbCwgcmVtb3ZlIHRoZSBmaXJzdCBlbGVtZW50Jm5ic3A7ZnJvbSBib3RoIHNlcXVlbmNlcyBhbmQgY29tcGFyZSB0aGVtIGFnYWluLiBUaGUgb25lIHdoaWNoIGNvbWVzIGxhdGVyIGluIGxleGljb2dyYXBoaWNhbCBvcmRlciBhZnRlciB0aGUgcmVtb3ZhbCZuYnNwO2NvbWVzIGxhdGVyIGluIGxleGljb2dyYXBoaWNhbCBvcmRlci48XC9saT5cclxuXHQ8bGk+SWYgYSBzZXF1ZW5jZSBvZiBsZW5ndGggJDAkIGlzIGNvbXBhcmVkIHRvIGFub3RoZXIgc2VxdWVuY2UsIHRoZSBvdGhlciBzZXF1ZW5jZSBhbHdheXMgY29tZXMgbGF0ZXIgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBsZW5ndGggJE4kIGNvbnNpc3Rpbmcgb2YgcG9zaXRpdmUgaW50ZWdlcnMgJFxce0FfMSxcXGNkb3RzICxBX05cXH0kLiBZb3UgYXJlIGFsc28gZ2l2ZW4gYW5vdGhlciBzZXF1ZW5jZSBvZiBsZW5ndGggJE0kIGNvbnNpc3Rpbmcgb2YgcG9zaXRpdmUgaW50ZWdlcnMgJFxce0JfMSxcXGNkb3RzICxCX01cXH0kLjxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBjb21tb24gc3Vic2VxdWVuY2Ugb2YgJEEkIGFuZCAkQiQgd2hpY2ggY29tZXMgbGFzdCBpbiBsZXhpY29ncmFwaGljYWwgb3JkZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyICROJCwgZGVub3RpbmcgdGhlIGxlbmd0aCBvZiBzZXF1ZW5jZSAkQSQuICQoMSBcXGxlIE4gXFxsZSAxMDApJDxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgJE4kIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycyAkQV8xLEFfMixcXGNkb3RzLEFfTiQuICQoMSBcXGxlIEFfaSBcXGxlIDEwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgJE0kLCBkZW5vdGluZyB0aGUgbGVuZ3RoIG9mIHNlcXVlbmNlICRCJC4gJCgxIFxcbGUgTSBcXGxlIDEwMCkkPFwvcD5cclxuXHJcbjxwPlRoZSBmb3VydGggbGluZSBvZiBpbnB1dCBjb250YWlucyAkTSQgc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzICRCXzEsQl8yLFxcY2RvdHMsQl9NJC4gJCgxIFxcbGUgQl9pIFxcbGUgMTAwKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbGVuZ3RoICRLJCBvZiB0aGUgY29tbW9uIHN1YnNlcXVlbmNlIG9mICRBJCBhbmQgJEIkIHdoaWNoIGNvbWVzIGxhc3QgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiAkSyBcXG5lIDAkLCBwcmludCAkSyQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGluIHRoZSBuZXh0IGxpbmUuIFRoZSAkaSQtdGggb2YgdGhlIGludGVnZXJzIHNob3VsZCBiZSB0aGUgJGkkLXRoIGVsZW1lbnQgb2YgdGhlIGNvbW1vbiBzdWJzZXF1ZW5jZSBvZiAkQSQgYW5kICRCJCB3aGljaCBjb21lcyBsYXN0IGluIGxleGljb2dyYXBoaWNhbCBvcmRlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlRoZSBmb2xsb3dpbmcgYXJlIGFsbCBjb21tb24gc3Vic2VxdWVuY2VzIG9mICRBJCBhbmQgJEIkLjxcL3A+XHJcblxyXG48cD4kJCBcXGJlZ2lue2FycmF5fXtjY2NjfSBcXHtcXH0gJmFtcDsgXFx7MVxcfSAmYW1wOyBcXHsxLDNcXH0gJmFtcDsgXFx7MSw3XFx9IFxcXFwgXFx7MSw3LDNcXH0gJmFtcDsgXFx7M1xcfSAmYW1wOyBcXHs3XFx9ICZhbXA7IFxcezcsM1xcfSBcXFxcIFxcZW5ke2FycmF5fSAkJDxcL3A+XHJcblxyXG48cD5UaGUgb25lIHdoaWNoIGNvbWVzIGxhc3QgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyIGFtb25nIHRoZW0gaXMgJFxcezcsM1xcfSQuPFwvcD5cclxuIn1d