시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1136 528 455 49.349%

문제

먹고또자니 <거기 누구세요> 코너에서는 "돌림판"을 돌려 상품을 얻을 수 있다. 이 돌림판은 큰 원형판이 N등분되어있는 형태이다.

N등분 된 각 부분은 0부터 9사이의 숫자가 하나씩 적혀있다. 게임이 시작되면, 임의의 M자리의 수 X와 Y(X ≤ Y)가 주어진다. (단, 이 수는 0으로 시작될 수도 있다.)
그리고 참가자는 돌림판을 힘차게 돌린다. 힘차게 돌던 돌림판이 완전히 멈추게 되는 순간, 12시 방향의 스피너가 특정 부분을 가리키게 될 것이다. 거기서부터 시계방향으로 M칸 연속되는 수를 읽으면 M자리의 수 Z를 얻을 수 있다.

이때 얻은 Z가 X ≤ Z ≤ Y를 만족한다면 게임을 승리하고 Z만원을 얻을 수 있다!

The wheel of Numbers

예를 들어, 돌림판이 N = 8 등분되어있고, 시계방향으로 읽었을 때 [3, 7, 8, 3, 1, 9, 2, 7] 과 같다고 하자. X = 200 이고 Y = 311일 경우 "숫자 2"가 적힌 부분부터 시작한다면 Z = 273 으로 X = 200 ≤ 273 ≤ 311 = Y 를 만족하여 게임을 승리한다.

돌림판의 상태와 X, Y가 주어질 때 어느 부분부터 시작하면 게임을 승리할 수 있을 지 알 수 있다. 주어진 조건에 대해서 게임을 승리할 수 있는 가지수를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에 테스트케이스의 개수 T가 주어진다.

각 테스트케이스의 첫 줄에는 돌림판을 N등분할 정수 N (1 ≤ N ≤ 100)과 X, Y의 길이 M (1 ≤ M ≤ 9, M ≤ N) 이 주어진다. 그리고 다음 3개의 줄에 X의 각 자리수, Y의 각 자리수, 돌림판의 상태가 주어진다.

X와 Y의 각 자리수는 공백으로 구분되어 0~9사이의 숫자가 한자리씩 주어진다.

돌림판의 상태는 어느 부분부터 시계방향으로 읽었을 때 나타나는 순서대로 주어진다. 돌림판의 숫자도 0~9사이의 숫자가 공백으로 구분되어 주어진다.

출력

각 테스트케이스에 대하여 한 줄씩 정답을 출력한다.

즉, 돌림판에서 X ≤ Z ≤ Y를 만족하는 M자리의 수 Z가 몇 개가 있는 지를 출력한다. 단, 같은 수라도 시작 부분이 다르다면 다른 가지수로 센다. 예를 들어, X와 Y 사이에 있는 수가 123 밖에 없는 데 돌림판에서 2번 나온다면, 1이 아닌 2를 출력한다.

예제 입력 1

3
8 3
2 0 0
3 1 1
3 7 8 3 1 9 2 7
5 2
8 8
9 9
1 3 2 5 4
6 3
0 0 0
9 9 9
1 2 3 4 5 6

예제 출력 1

1
0
6
W3sicHJvYmxlbV9pZCI6IjExNTA0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjXHViODI0IFx1YjNjY1x1YjgyNCBcdWIzY2NcdWI5YmNcdWQzMTAhIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhMzlcdWFjZTBcdWI2MTBcdWM3OTBcdWIyYzgmbmJzcDsmbHQ7XHVhYzcwXHVhZTMwJm5ic3A7XHViMjA0XHVhZDZjXHVjMTM4XHVjNjk0Jmd0OyBcdWNmNTRcdWIxMDhcdWM1ZDBcdWMxMWNcdWIyOTQgJnF1b3Q7XHViM2NjXHViOWJjXHVkMzEwJnF1b3Q7XHVjNzQ0IFx1YjNjY1x1YjgyNCBcdWMwYzFcdWQ0ODhcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIzY2NcdWI5YmNcdWQzMTBcdWM3NDAgXHVkMDcwIFx1YzZkMFx1ZDYxNVx1ZDMxMFx1Yzc3NCBOXHViNGYxXHViZDg0XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YjRmMVx1YmQ4NCBcdWI0MWMgXHVhYzAxJm5ic3A7XHViZDgwXHViZDg0XHVjNzQwIDBcdWJkODBcdWQxMzAgOVx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5Jm5ic3A7XHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NzQgXHVjMmRjXHVjNzkxXHViNDE4XHViYTc0LCBcdWM3ODRcdWM3NThcdWM3NTgmbmJzcDtNXHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOCBYXHVjNjQwIFkoWCAmbGU7IFkpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFx1YjJlOCwgXHVjNzc0IFx1YzIxOFx1YjI5NCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0Lik8YnIgXC8+XHJcblx1YWRmOFx1YjlhY1x1YWNlMCBcdWNjMzhcdWFjMDBcdWM3OTBcdWIyOTQmbmJzcDtcdWIzY2NcdWI5YmNcdWQzMTBcdWM3NDQgXHVkNzk4XHVjYzI4XHVhYzhjIFx1YjNjY1x1YjliMFx1YjJlNC4gXHVkNzk4XHVjYzI4XHVhYzhjIFx1YjNjY1x1YjM1OCBcdWIzY2NcdWI5YmNcdWQzMTBcdWM3NzQgXHVjNjQ0XHVjODA0XHVkNzg4Jm5ic3A7XHViYTQ4XHVjZDk0XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWFjMDQsIDEyXHVjMmRjIFx1YmMyOVx1ZDVhNVx1Yzc1OCBcdWMyYTRcdWQ1M2NcdWIxMDhcdWFjMDAgXHVkMmI5XHVjODE1IFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYTRcdWFjOGMgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWFjNzBcdWFlMzBcdWMxMWNcdWJkODBcdWQxMzAgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIE1cdWNlNzggXHVjNWYwXHVjMThkXHViNDE4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWM3N2RcdWM3M2NcdWJhNzQgTVx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWMyMTggWlx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjJm5ic3A7XHVjNWJiXHVjNzQwIFpcdWFjMDAmbmJzcDtYICZsZTsgWiAmbGU7IFlcdWI5N2MgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0XHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWFjZTAgWlx1YjljY1x1YzZkMFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNCE8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiVGhlIHdoZWVsIG9mIE51bWJlcnNcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE1MDRcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQwcHg7IHdpZHRoOjM2NnB4XCIgdGl0bGU9XCJUaGUgd2hlZWwgb2YgTnVtYmVyc1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIzY2NcdWI5YmNcdWQzMTBcdWM3NzQgTiA9IDggXHViNGYxXHViZDg0XHViNDE4XHVjNWI0XHVjNzg4XHVhY2UwLCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0YyBbMywgNywgOCwgMywgMSwgOSwgMiwgN10mbmJzcDtcdWFjZmMgXHVhYzE5XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gWCA9IDIwMCBcdWM3NzRcdWFjZTAgWSA9IDMxMVx1Yzc3YyBcdWFjYmRcdWM2YjAgJnF1b3Q7XHVjMjJiXHVjNzkwIDImcXVvdDtcdWFjMDAgXHVjODAxXHVkNzhjIFx1YmQ4MFx1YmQ4NFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTRcdWJhNzQgWiA9IDI3MyBcdWM3M2NcdWI4NWMmbmJzcDtYID0gMjAwICZsZTsgMjczICZsZTsgMzExID0gWSBcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHVjNWVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjY1x1YjliY1x1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWM2NDAgWCwgWVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1YzViNFx1YjI5MCBcdWJkODBcdWJkODRcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWM5YzAgXHVjNTRjJm5ic3A7XHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzg3MFx1YWM3NFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJiOVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzljMFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzY2NcdWI5YmNcdWQzMTBcdWM3NDQgTlx1YjRmMVx1YmQ4NFx1ZDU2MCBcdWM4MTVcdWMyMTgmbmJzcDtOJm5ic3A7KDEgJmxlOyBOICZsZTsgMTAwKVx1YWNmYyBYLCBZXHVjNzU4IFx1YWUzOFx1Yzc3NCBNJm5ic3A7KDEgJmxlOyBNJm5ic3A7JmxlOyA5LCZuYnNwO00gJmxlOyBOKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAmbmJzcDtcdWIyZTRcdWM3NGMgM1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgWFx1Yzc1OCBcdWFjMDEgXHVjNzkwXHViOWFjXHVjMjE4LCBZXHVjNzU4IFx1YWMwMSBcdWM3OTBcdWI5YWNcdWMyMTgsIFx1YjNjY1x1YjliY1x1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5YXHVjNjQwIFlcdWM3NTggXHVhYzAxIFx1Yzc5MFx1YjlhY1x1YzIxOFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IDB+OVx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAmbmJzcDtcdWQ1NWNcdWM3OTBcdWI5YWNcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzY2NcdWI5YmNcdWQzMTBcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YzViNFx1YjI5MCBcdWJkODBcdWJkODRcdWJkODBcdWQxMzAgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3ZFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjNjY1x1YjliY1x1ZDMxMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWIzYzQgMH45XHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWQ1NWMgXHVjOTA0XHVjNTI5IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzk4OSwgXHViM2NjXHViOWJjXHVkMzEwXHVjNWQwXHVjMTFjJm5ic3A7WCAmbGU7IFogJmxlOyBZXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBNXHVjNzkwXHViOWFjXHVjNzU4IFx1YzIxOCBaXHVhYzAwIFx1YmE4NyBcdWFjMWNcdWFjMDAgXHVjNzg4XHViMjk0IFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yjc3Y1x1YjNjNCBcdWMyZGNcdWM3OTEmbmJzcDtcdWJkODBcdWJkODRcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWFjMDBcdWM5YzBcdWMyMThcdWI4NWMgXHVjMTNjXHViMmU0LiZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFhcdWM2NDAgWSBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCAxMjMgXHViYzE2XHVjNWQwIFx1YzVjNlx1YjI5NCBcdWIzNzAgXHViM2NjXHViOWJjXHVkMzEwXHVjNWQwXHVjMTFjIDJcdWJjODggXHViMDk4XHVjNjI4XHViMmU0XHViYTc0LCAxXHVjNzc0IFx1YzU0NFx1YjJjYyAyXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTUwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoZWVsIG9mIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbmV3IGdhbWJsaW5nIG1hY2hpbmUgY2FsbGVkICZsZHF1bzt0aGUgd2hlZWwgb2YgbnVtYmVycyZyZHF1bzsgaXMgaW50cm9kdWNlZC4gSXQgaXMgbWFkZSB1cCB3aXRoIGEgbGFyZ2Ugd2hlZWwsIHdoaWNoIGlzIGVxdWFsbHkgZGl2aWRlZCBpbnRvIG4mbmJzcDtzZWdtZW50cy4gRWFjaCBzZWdtZW50IGNvbnRhaW5zIGEgZGlnaXQgYmV0d2VlbiAwIGFuZCA5LCBpbmNsdXNpdmVseS4gSW5pdGlhbGx5IHlvdSBhcmUgZ2l2ZW4gdHdvIG0tZGlnaXQgbnVtYmVycyBYIGFuZCBZIChYICZsZTsgWSkuIE5vdGUgdGhhdCB0aGVzZSBudW1iZXJzIG1heSBiZWdpbiB3aXRoIDAuIFRoZW4sIHlvdSBzaG9vdCBhIGJhbGwgYWltaW5nIGF0IHRoZSBmYXN0LXJvdGF0aW5nIHdoZWVsLiBZb3VyIGJhbGwgd2lsbCBoaXQgb25lIG9mIGl0cyBzZWdtZW50cy4gVGhlbiwgeW91IHRha2UgbSZuYnNwO2NvbnNlY3V0aXZlIHNlZ21lbnRzIGNsb2Nrd2lzZSBmcm9tIHRoZXJlIGFuZCBvYnRhaW4gYW4gbS1kaWdpdCBudW1iZXIgWi4gWW91IHdpbiBpZiBYICZsZTsgWiAmbGU7IFkgYW5kIGxvc2Ugb3RoZXJ3aXNlLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE1MDRcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQwcHg7IHdpZHRoOjM2NnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBhc3N1bWUgdGhhdCB0aGUgd2hlZWwgaXMgZGl2aWRlZCBpbnRvIG4gPSA4IHNlZ21lbnRzLCBhbmQgbGV0IFszLCA3LCA4LCAzLCAxLCA5LCAyLCA3XSBiZSB0aGUgbnVtYmVycyBieSBwaWNraW5nIG9uZSBzZWdtZW50IGFuZCByZWFkaW5nIG51bWJlcnMgY2xvY2t3aXNlLiBJZiBYID0gMjAwIGFuZCBZID0gMzExLCB5b3Ugd2luIGlmIHlvdXIgYmFsbCBoaXRzIHRoZSBzZWdtZW50IHdpdGggMiBhcyB5b3VyIG51bWJlciBaID0gMjczIGFuZCBzdXJlbHkgWCA9IDIwMCAmbGU7IDI3MyAmbGU7IDMxMSA9IFkuPFwvcD5cclxuXHJcbjxwPk9uY2UgeW91IGFyZSBnaXZlbiB0aGUgd2hlZWwsIFggYW5kIFksIHlvdSB3b3VsZCBsaWtlIHRvIGtub3cgeW91ciB3aW5uaW5nIHByb2JhYmlsaXR5LiBJdCBjYW4gYmUgY2FsY3VsYXRlZCBlYXNpbHkgaWYgeW91IGtub3cgaG93IG1hbnkgdGltZXMgdGhlIG51bWJlcnMgc2F0aXNmeWluZyB0aGUgYWJvdmUgbWVudGlvbmVkIGNvbmRpdGlvbiBhcHBlYXIgb24gdGhlIHdoZWVsLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjb3VudHMgdGhlIG51bWJlciBvZiB0aGVpciBvY2N1cnJlbmNlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzLCBuICgxICZsZTsgbiAmbGU7IDEwMCkgYW5kIG0gKDEgJmxlOyBtICZsZTsgOSBhbmQgbSAmbGU7IG4pLCB3aGVyZSBuIGlzIHRoZSBudW1iZXIgb2Ygc2VnbWVudHMgaW4gdGhlIHdoZWVsIGFuZCBtIGlzIHRoZSBsZW5ndGggb2YgWCBhbmQgWS4gVGhlIG5leHQgbGluZSBjb250YWlucyBtIGRpZ2l0cyByZXByZXNlbnRpbmcgWCB3aGVyZSBlYWNoIGRpZ2l0IGlzIGJldHdlZW4gMCBhbmQgOSwgaW5jbHVzaXZlbHksIGFuZCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIG5leHQgbGluZSBjb250YWlucyBtIGRpZ2l0cyByZXByZXNlbnRpbmcgWSBhcyBtZW50aW9uZWQgYWJvdmUuIFRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBuIGRpZ2l0cywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIG9idGFpbmVkIGJ5IHJlYWRpbmcgbnVtYmVycyBjbG9ja3dpc2Ugc3RhcnRpbmcgYXQgc29tZSBzZWdtZW50IG9mIHRoZSB3aGVlbC4gQWdhaW4gZWFjaCBkaWdpdCBpcyBiZXR3ZWVuIDAgYW5kIDksIGluY2x1c2l2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIG9jY3VycmVuY2VzIG9mIG0tZGlnaXQgbnVtYmVyIFogY29udGFpbmVkIGluIHRoZSB3aGVlbCBzdWNoIHRoYXQgWCAmbGU7IFogJmxlOyBZLiBOb3RlIHRoYXQgaWYgdGhlIHNhbWUgbnVtYmVyIGFwcGVhcnMgbW9yZSB0aGFuIHR3aWNlLCBjb3VudCB0aGVtIHNlcGFyYXRlbHkuIEZvciBleGFtcGxlLCBpZiAxMjMgaXMgdGhlIG9ubHkgbnVtYmVyIGJldHdlZW4gWCBhbmQgWSBhbmQgaXQgYXBwZWFycyB0d2ljZSBvbiB0aGUgd2hlZWwsIHRoZSBhbnN3ZXIgaXMgMiwgbm90IDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2015 L번