시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 1 1 50.000%

문제

다음과 같은 두 가지 조건을 만족하는 바이너리 문자열 (0과 1로만 이루어짐)을 올바른 바이너리 문자열 이라고 한다.

  1. DC-균형: 0과 1의 개수가 같다
  2. RL-제한: 연속된 0또는 1의 개수가 2개를 넘지 않는다

일부 글자가 지워진 바이너리 문자열이 주어졌을 때, 지워진 글자를 0 또는 1로 바꿔서 올바른 바이너리 문자열로 바꿀 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, '0', '1', '.'으로 이루어진 바이너리 문자열이 주어진다. '.'는 지워진 글자를 의미하고, 길이는 2보다 크거나 같고, 100,000보다 작거나 같은 짝수이다.

출력

각각의 테스트 케이스마다 입력으로 주어진 바이너리 문자열을 올바른 바이너리 문자열로 바꿀 수 있으면 "yes"를 없으면 "no"를 출력한다.

예제 입력 1

6
001100110011
110..0...00...0011
..............
01....100100
010101110100
101011011001

예제 출력 1

yes
yes
yes
no
no
no
W3sicHJvYmxlbV9pZCI6IjUzNzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MmNcdWJjMTRcdWI5NzggXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1YmIzOFx1Yzc5MFx1YzVmNCAoMFx1YWNmYyAxXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzlkMClcdWM3NDQgXHVjNjJjXHViYzE0XHViOTc4IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5EQy1cdWFkZTBcdWQ2MTU6IDBcdWFjZmMgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzE5XHViMmU0PFwvbGk+XHJcblx0PGxpPlJMLVx1YzgxY1x1ZDU1YzogXHVjNWYwXHVjMThkXHViNDFjIDBcdWI2MTBcdWIyOTQgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgMlx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVhZTAwXHVjNzkwXHViOTdjIDAgXHViNjEwXHViMjk0IDFcdWI4NWMgXHViYzE0XHVhZmQ0XHVjMTFjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsICYjMzk7MCYjMzk7LCAmIzM5OzEmIzM5OywgJiMzOTsuJiMzOTtcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmIzM5Oy4mIzM5O1x1YjI5NCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVhZTAwXHVjNzkwXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IDJcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNjJjXHViYzE0XHViOTc4IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgJnF1b3Q7eWVzJnF1b3Q7XHViOTdjIFx1YzVjNlx1YzczY1x1YmE3NCAmcXVvdDtubyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTM3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpZ2l0YWwgVHJhbnNtaXNzaW9uIiwiZGVzY3JpcHRpb24iOiI8cD5BIGxpbmUgY29kZSBpcyBhbiBlbmNvZGluZyBvZiBhIGRpZ2l0YWwgc2lnbmFsIHN1aXRhYmxlIGZvciBzZXJpYWwgdHJhbnNtaXNzaW9uIG92ZXIgYSBwaHlzaWNhbCBtZWRpdW0sIHN1Y2ggYXMgY29wcGVyIHdpcmUgb3Igb3B0aWNhbCBmaWJlci4gU3VjaCBjb2RlcyBhcmUgZGVzaWduZWQgdG8gcHJldmVudCBkaXN0b3J0aW9uIG9mIHRoZSBzaWduYWwgZHVlIHRvIHRoZSBwaHlzaWNhbCBwcm9wZXJ0aWVzIG9mIHRoZSB0cmFuc21pc3Npb24gbWVkaXVtLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtIHdlIGNvbnNpZGVyIGEgbGluZSBjb2RlIHRoYXQgb3V0cHV0cyBhIGJpbmFyeSBzdHJpbmcgKGkuZS4gYSBzZXF1ZW5jZSBvZiB6ZXJvcyBhbmQgb25lcykgd2l0aCB0d28gcmVzdHJpY3Rpb25zLiBUaGUgb3V0cHV0IG11c3QgYmU6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+REMtYmFsYW5jZWQ6IGl0IG11c3QgY29udGFpbiBhbiBlcXVhbCBudW1iZXIgb2YgemVyb3MgYW5kIG9uZXM7PFwvbGk+XHJcblx0PGxpPnJ1bi1sZW5ndGggbGltaXRlZDogaXQgbWF5IG5vdCBjb250YWluIG1vcmUgdGhhbiB0d28gY29uc2VjdXRpdmUgemVyb3Mgb3Igb25lcy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Zb3UgaGF2ZSByZWNlaXZlZCBhIHRyYW5zbWlzc2lvbiBhbmQgeW91IHdvbmRlciBpZiBpdCBjb25mb3JtcyB0byB0aGUgYWJvdmUgc3BlY2lmaWNhdGlvbi4gVGhpcyB3b3VsZCBiZSBlYXN5IHRvIHZlcmlmeSwgZXhjZXB0IHRoYXQgeW91IHdlcmUgbm90IGFibGUgdG8gcmVjZWl2ZSBldmVyeSBzeW1ib2wgcHJvcGVybHksIHJlc3VsdGluZyBpbiBibGFua3MgKGVuY29kZWQgYXMgcGVyaW9kcykgaW4gdGhlIHN0cmluZywgd2hpY2ggY291bGQgaGF2ZSBiZWVuIGVpdGhlciBhIHplcm8gb3IgYSBvbmUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgZm9yIGEgZ2l2ZW4gc3RyaW5nIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gZmlsbCBpbiBlYWNoIGJsYW5rIHdpdGggZWl0aGVyIHplcm8gYW5kIG9uZSBzbyB0aGF0IHRoZSByZXN1bHQgaXMgYSB2YWxpZCBsaW5lIGNvZGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjxwPm9uZSBsaW5lIHdpdGggYSBzdHJpbmcgY29uc2lzdGluZyBvZiAmbHNxdW87MCZyc3F1bzssICZsc3F1bzsxJnJzcXVvOyBhbmQgJmxzcXVvOy4mcnNxdW87OiB0aGUgcmVjZWl2ZWQgdHJhbnNtaXNzaW9uLiBUaGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgaXMgZXZlbiBhbmQgYmV0d2VlbiAyIGFuZCAxMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0aGUgd29yZCAmcmRxdW87eWVzJnJkcXVvOyBvciAmcmRxdW87bm8mcmRxdW87LCBpbmRpY2F0aW5nIHdoZXRoZXIgb3Igbm90IHRoZSBibGFua3MgaW4gdGhlIHN0cmluZyBjYW4gYmUgcmVwbGFjZWQgYnkgemVyb3MgYW5kIG9uZXMgdG8gY3JlYXRlIGEgcHJvcGVybHkgY29kZWQgc3RyaW5nLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d