시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 9 9 90.000%

문제

파급효과가 가능한 퍼즐인지 판별하여라.

파급효과는 여러개의 폴리오미노로 구성된 직사각형의 그리드에서 발생한다. 폴리오미노는 하나 이상의 같은 크기의 정사각형을 이어붙여 만든 도형이다.

우리는 그리드 안의 모든 칸에 자연수를 배치해야한다. 이 때 다음과 같은 규칙을 따르며, 일부 자연수는 미리 주어질 수 있다.

  • 1 ~ (폴리노미오 안의 칸 수) 의 자연수들은 해당 폴리노미오 안에 반드시 한번씩만 배치되어야 한다.
  • 하나의 줄이나 행에 동일한 숫자가 배치되기 위해선 두 숫자 사이에 해당 숫자만큼의 다른 칸이 존재해야 한다.
    예를 들어, '1'이 배치된 칸은 서로 인접할 수 없으며, 다른 숫자가 쓰여진 칸이 두 '1' 사이에 하나 이상 존재해야 한다.
    같은 줄이나 행에 '3'이 배치되기 위해선 다른 숫자가 쓰여진 칸이 사이에 세개 이상 존재해야 한다.

이 문제에서 폴리노미오의 크기는 최대 8이다.

 

입력

입력의 첫째 줄에는 테스트 케이스 T가 주어진다. (T<=100)

각각의 테스트 케이스의 첫째 줄에는 두 정수 R, C 가 주어진다. (4<=R, C<=15)

이후 R개 줄에는 그리드에 쓰여진 숫자들을 나태는 C개의 숫자 d_i로 구성된 문자열이 입력된다. (1<=d_i<=8)

이후 R개 줄에는 퍼즐의 각 칸이 폴리노미오로 연결된 방향을 나타내는 C개의 숫자가 입력된다. (이는 RxC 의 테이블이며, 이를 "descr" 라고 하자. 0<=descr(r,c)<=15)

descr(r,c)의 값은 이웃된 칸과의 연결 여부에 따라 다음과 같이 결정된다.

descr(r,c)=0
if(connected((r,c),(r-1,c)) descr(r,c)+=1; (UP)
if(connected((r,c),(r,c+1)) descr(r,c)+=2; (RIGHT)
if(connected((r,c),(r+1,c)) descr(r,c)+=4; (DOWN)
if(connected((r,c),(r,c-1)) descr(r,c)+=8; (LEFT)

예를 들어, 크기가 1인 폴리노미오의 칸은 주변의 어떠한 칸과도 이어져있지 않으므로 0의 값을 가지며, 위쪽의 칸과 아래의 칸에 이어져있는 칸들은 5의 값을 가지게 된다.

출력

각각의 테스트 케이스에 대해 한 "valid" 또는 "invalid" 를 출력하여라.

예제 입력 1

2
6 6
241321
312432
131243
423121
214312
141231
2 12 4 4 6 8
4 5 1 5 5 4
5 1 0 5 1 5
3 8 4 1 4 1
2 10 9 2 9 4
0 2 10 10 8 1
6 6
421321
312432
131243
423121
214312
141231
2 12 4 4 6 8
4 5 1 5 5 4
5 1 0 5 1 5
3 8 4 1 4 1
2 10 9 2 9 4
0 2 10 10 8 1

예제 출력 1

valid
invalid
W3sicHJvYmxlbV9pZCI6IjE4OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWFlMDlcdWQ2YThcdWFjZmMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VzZXJ1cGxvYWRcL2piX2N1YmVkclwvMjAxNjAxMjFcLzI1ZGU4MDEzODRkZDQxMzM4NjlmYWMwZWZiYzY2MzZiLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNDZweDsgbGluZS1oZWlnaHQ6MjAuOHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MzQ3cHhcIiBcLz5cdWQzMGNcdWFlMDlcdWQ2YThcdWFjZmNcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDM3Y1x1Yzk5MFx1Yzc3OFx1YzljMCBcdWQzMTBcdWJjYzRcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1ZDMwY1x1YWUwOVx1ZDZhOFx1YWNmY1x1YjI5NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVkM2Y0XHViOWFjXHVjNjI0XHViYmY4XHViMTc4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyZuYnNwO1x1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViYzFjXHVjMGRkXHVkNTVjXHViMmU0LiBcdWQzZjRcdWI5YWNcdWM2MjRcdWJiZjhcdWIxNzhcdWIyOTQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWFjMTlcdWM3NDAgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWM1YjRcdWJkOTlcdWM1ZWMgXHViOWNjXHViNGUwIFx1YjNjNFx1ZDYxNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkYyBcdWM1NDhcdWM3NTggXHViYWE4XHViNGUwIFx1Y2U3OFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHViYzMwXHVjZTU4XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YmE3MCwgXHVjNzdjXHViZDgwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjI5NCBcdWJiZjhcdWI5YWMgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSB+IChcdWQzZjRcdWI5YWNcdWIxNzhcdWJiZjhcdWM2MjQgXHVjNTQ4XHVjNzU4IFx1Y2U3OCBcdWMyMTgpIFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI0ZTRcdWM3NDAgXHVkNTc0XHViMmY5IFx1ZDNmNFx1YjlhY1x1YjE3OFx1YmJmOFx1YzYyNCBcdWM1NDhcdWM1ZDAgXHViYzE4XHViNGRjXHVjMmRjIFx1ZDU1Y1x1YmM4OFx1YzUyOVx1YjljYyBcdWJjMzBcdWNlNThcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQ1NThcdWIwOThcdWM3NTggXHVjOTA0XHVjNzc0XHViMDk4IFx1ZDU4OVx1YzVkMCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMjAgXHViNDUwIFx1YzIyYlx1Yzc5MCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVkNTc0XHViMmY5IFx1YzIyYlx1Yzc5MFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWIyZTRcdWI5NzggXHVjZTc4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPGJyIFwvPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICYjMzk7MSYjMzk7XHVjNzc0IFx1YmMzMFx1Y2U1OFx1YjQxYyBcdWNlNzhcdWM3NDAgXHVjMTFjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTcwLCBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzRmMFx1YzVlY1x1YzljNCBcdWNlNzhcdWM3NzQgXHViNDUwICYjMzk7MSYjMzk7IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPGJyIFwvPlxyXG5cdFx1YWMxOVx1Yzc0MCBcdWM5MDRcdWM3NzRcdWIwOTggXHVkNTg5XHVjNWQwICYjMzk7MyYjMzk7XHVjNzc0IFx1YmMzMFx1Y2U1OFx1YjQxOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMjAgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM5YzQgXHVjZTc4XHVjNzc0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWMxMzhcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzg3NFx1YzdhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWQzZjRcdWI5YWNcdWIxNzhcdWJiZjhcdWM2MjRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1Y2Q1Y1x1YjMwMCA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChUJmx0Oz0xMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBSLCBDIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg0Jmx0Oz1SLCBDJmx0Oz0xNSk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM5YzQgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzQ0IFx1YjA5OFx1ZDBkY1x1YjI5NCZuYnNwO0NcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwIGRfaVx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gKDEmbHQ7PWRfaSZsdDs9OCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzc0IFx1ZDNmNFx1YjlhY1x1YjE3OFx1YmJmOFx1YzYyNFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBDXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuJm5ic3A7KFx1Yzc3NFx1YjI5NCBSeEMgXHVjNzU4IFx1ZDE0Y1x1Yzc3NFx1YmUxNFx1Yzc3NFx1YmE3MCwgXHVjNzc0XHViOTdjICZxdW90O2Rlc2NyJnF1b3Q7IFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIDAmbHQ7PWRlc2NyKHIsYykmbHQ7PTE1KTxcL3A+XHJcblxyXG48cD5kZXNjcihyLGMpXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWM3NzRcdWM2YzNcdWI0MWMgXHVjZTc4XHVhY2ZjXHVjNzU4IFx1YzVmMFx1YWNiMCBcdWM1ZWNcdWJkODBcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhY2IwXHVjODE1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5kZXNjcihyLGMpPTBcclxuaWYoY29ubmVjdGVkKChyLGMpLChyLTEsYykpIGRlc2NyKHIsYykrPTE7IChVUClcclxuaWYoY29ubmVjdGVkKChyLGMpLChyLGMrMSkpIGRlc2NyKHIsYykrPTI7IChSSUdIVClcclxuaWYoY29ubmVjdGVkKChyLGMpLChyKzEsYykpIGRlc2NyKHIsYykrPTQ7IChET1dOKVxyXG5pZihjb25uZWN0ZWQoKHIsYyksKHIsYy0xKSkgZGVzY3IocixjKSs9ODsgKExFRlQpPFwvcHJlPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkMDZjXHVhZTMwXHVhYzAwIDFcdWM3NzggXHVkM2Y0XHViOWFjXHViMTc4XHViYmY4XHVjNjI0XHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWM4ZmNcdWJjYzBcdWM3NTggXHVjNWI0XHViNWEwXHVkNTVjIFx1Y2U3OFx1YWNmY1x1YjNjNCBcdWM3NzRcdWM1YjRcdWM4MzhcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNzNjXHViYmMwXHViODVjIDBcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YmE3MCwgXHVjNzA0XHVjYWJkXHVjNzU4IFx1Y2U3OFx1YWNmYyBcdWM1NDRcdWI3OThcdWM3NTggXHVjZTc4XHVjNWQwIFx1Yzc3NFx1YzViNFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWI0ZTRcdWM3NDAgNVx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhYzAwXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjICZxdW90O3ZhbGlkJnF1b3Q7IFx1YjYxMFx1YjI5NCAmcXVvdDtpbnZhbGlkJnF1b3Q7IFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTg5NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJpcHBsZSBFZmZlY3QiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE4OTZcLzEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjM0NnB4OyB3aWR0aDozNDdweFwiIFwvPkNoZWNrIGlmIGEgc29sdXRpb24gdG8gYSBSaXBwbGUgRWZmZWN0IHB1enpsZSBpcyB2YWxpZC48XC9wPlxyXG5cclxuPHA+UmlwcGxlIEVmZmVjdCBpcyBwbGF5ZWQgb24gYSByZWN0YW5ndWxhciBncmlkIGRpdmlkZWQgaW50byBwb2x5b21pbm9lcy4gQSBwb2x5b21pbm8gaXMgYSBwbGFuZSBnZW9tZXRyaWMgZmlndXJlIGZvcm1lZCBieSBqb2luaW5nIG9uZSBvciBtb3JlIGVxdWFsIHNxdWFyZXMgZWRnZSB0byBlZGdlLjxcL3A+XHJcblxyXG48cD5UaGUgc29sdmVyIG11c3QgcGxhY2Ugb25lIHBvc2l0aXZlIGludGVnZXIgaW50byBlYWNoIGNlbGwgb2YgdGhlIGdyaWQgLSBzb21lIG9mIHdoaWNoIG1heSBiZSBnaXZlbiBpbiBhZHZhbmNlIC0gYWNjb3JkaW5nIHRvIHRoZXNlIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkV2ZXJ5IGludGVnZXIgZnJvbSAxIHRvIHRoZSBxdWFudGl0eSBvZiBjZWxscyBpbiBhIHBvbHlvbWlubyBtdXN0IGFwcGVhciBleGFjdGx5IG9uY2UgaW4gdGhhdCBwb2x5b21pbm8uPFwvbGk+XHJcblx0PGxpPklmIHR3byBpZGVudGljYWwgbnVtYmVycyBhcHBlYXIgaW4gdGhlIHNhbWUgcm93IG9yIGNvbHVtbiwgYXQgbGVhc3QgdGhhdCBtYW55IGNlbGxzIHdpdGggb3RoZXIgbnVtYmVycyBtdXN0IHNlcGFyYXRlIHRoZW0uPGJyIFwvPlxyXG5cdEZvciBleGFtcGxlLCB0d28gY2VsbHMgYm90aCBjb250YWluaW5nICYjMzk7MSYjMzk7IG1heSBub3QgYmUgb3J0aG9nb25hbGx5IGFkamFjZW50LCBidXQgbXVzdCBoYXZlIGF0IGxlYXN0IG9uZSBjZWxsIGJldHdlZW4gdGhlbSB3aXRoIGEgZGlmZmVyZW50IG51bWJlci48YnIgXC8+XHJcblx0VHdvIGNlbGxzIG1hcmtlZCAmIzM5OzMmIzM5OyBpbiB0aGUgc2FtZSByb3cgb3IgY29sdW1uIG11c3QgaGF2ZSBhdCBsZWFzdCB0aHJlZSBjZWxscyB3aXRoIG90aGVyIG51bWJlcnMgYmV0d2VlbiB0aGVtIGluIHRoYXQgcm93IG9yIGNvbHVtbiwgYW5kIHNvIG9uLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSBwb2x5b21pbm9lcyB3aWxsIGJlIG9mIHNpemUgYXQgbW9zdCA4LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgVCAoVCAmbHQ7PSAxMDApLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIHR3byBpbnRlZ2VycyBvbiBhIGxpbmUsIFIgYW5kIEMgKDQmbHQ7PVIsQyZsdDs9MTUpLjxcL3A+XHJcblxyXG48cD5SIGxpbmVzIGZvbGxvdywgZWFjaCBjb250YWluaW5nIGEgc3RyaW5nIG9mIEMgZGlnaXRzIGRfaSgxJmx0Oz1kX2kmbHQ7PTgpLCB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD5OZXh0IFIgbGluZXMgd2lsbCBjb250YWluIEMgaW50ZWdlcnMgKFJ4QyB0YWJsZSwgd2Ugd2lsbCBjYWxsIGl0ICZxdW90O2Rlc2NyJnF1b3Q7KSwgZWFjaCBkZXNjcmliaW5nIHRoZSBjb3JyZXNwb25kaW5nIGNlbGwgaW4gdGhlIHB1enpsZSAoMCZsdDs9ZGVzY3IocixjKSZsdDs9MTUpLjxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgZGVzY3IocixjKSBpcyBkZXRlcm1pbmVkIGJ5IHRoZSB2YWx1ZXMgb2YgY29ubmVjdGlvbnMgd2l0aCBuZWlnaGJvdXJpbmcgY2VsbHMsIGluIHRoZSBmb2xsb3dpbmcgbWFubmVyOjxcL3A+XHJcblxyXG48cHJlPlxyXG5kZXNjcihyLGMpPTBcclxuaWYoY29ubmVjdGVkKChyLGMpLChyLTEsYykpIGRlc2NyKHIsYykrPTE7IChVUClcclxuaWYoY29ubmVjdGVkKChyLGMpLChyLGMrMSkpIGRlc2NyKHIsYykrPTI7IChSSUdIVClcclxuaWYoY29ubmVjdGVkKChyLGMpLChyKzEsYykpIGRlc2NyKHIsYykrPTQ7IChET1dOKVxyXG5pZihjb25uZWN0ZWQoKHIsYyksKHIsYy0xKSkgZGVzY3IocixjKSs9ODsgKExFRlQpXHJcbjxcL3ByZT5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBhIHBvbHlvbWlubyBvZiBzaXplIDEgKHNpbmdsZSBzcXVhcmUgbm90IGNvbm5lY3RlZCB0byBvdGhlcnMpIHdpbGwgaGF2ZSB0aGUgdmFsdWUgb2YgMCBhbmQgYSBzcXVhcmUgdGhhdCBpcyBjb25uZWN0ZWQgb25seSB0byB0aGUgc3F1YXJlcyBhYm92ZSBhbmQgYmVsb3cgd2lsbCBoYXZlIHRoZSB2YWx1ZSBvZiA1LjxcL3A+XHJcblxyXG48cD5TZWUgc2FtcGxlIGlucHV0IGZvciBjbGFyaWZpY2F0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBlaXRoZXIgJnF1b3Q7dmFsaWQmcXVvdDsgb3IgJnF1b3Q7aW52YWxpZCZxdW90OyBvbiBhIHNpbmdsZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==