시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB260836334.426%

문제

보물 사냥꾼인 한신이는 6576번 아즈텍 문명의 유적지에서 가져온 보물지도가 가짜라는 것을 알게되었다. 이것에 화가난 한신이는 자신뿐만 아니라 다른사람에게도 이 거짓 지도를 보내서 장난을 칠 계획을 가지게 된다. 이 지도를 아무나 읽을수 있다면 한신이가 매우 곤란해진다. 이것을 위해 한신이를 도와주자!

지도는 XBM 형식이며 이것을 쿼드 트리 구조로 암호화하여 보낼것이다. 가능하겠는가?

입력

  • 첫 번째 줄에는 "#define quadtree_width n"가 입력이 되는데 여기서 n은 가로 픽셀 크기를 의미한다. (이 사진은 n*n 픽셀이다.)
  • 두 번째 줄에는 "#define quadtree_height n"가 입력이 되는데 여기서 n은 세로 픽셀 크기를 의미한다.
  • 세 번째 줄에는 "static char quadtree_bits[] = {"가 입력된다.
  • 그리고 다음 n줄에는 사진 한줄의 픽셀값이 n/8개의 헥사값로 변환되어 입력된다.

    각 헥사값은 8비트로 8개의 픽셀이 왼쪽에서 오른쪽으로 변환되어 구성된다. (가장 왼쪽 비트 값은 1이고 맨 오른쪽 비트값은 128이다.) 이 헥사값은 0xdd형식으로 입력이 되며 여기서 d는 { 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f }중 하나이다.

    예시 : 8 픽셀의 WBBBBWWB는 0x9e로 쓰인다.
    (2+4+8+16+128 = 158 = 0x9e) 각 헥사값은 콤마(,)로 구분된다.
  • 마지막 줄은 "};"가 입력된다.

출력

처음 정수 n (8 <= n <= 512)을 출력하고, B와 W그리고 Q로 정확하게 쿼드트리 구조로 사진을 암호화하여 출력한다.

예제 입력 1

#define quadtree_width 16
#define quadtree_height 16
static char quadtree_bits[] = {
0xf0,0xf0,
0xf0,0xf0,
0xf0,0xf0,
0xf0,0xf0,
0x0f,0x0f,
0x0f,0x0f,
0x0f,0x0f,
0x0f,0x0f,
0xf0,0xf0,
0xf0,0xf0,
0xf0,0xf0,
0xf0,0xf0,
0x0f,0x0f,
0x0f,0x0f,
0x0f,0x0f,
0x0f,0x0f,
};

예제 출력 1

16
QQWBBWQWBBWQWBBWQWBBW
W3sicHJvYmxlbV9pZCI6IjY1ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmZmNcdWI0ZGMgXHVkMmI4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjZjRcdWJiM2MgXHVjMGFjXHViMGU1XHVhZmJjXHVjNzc4IFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1YjI5NCA8YSBocmVmPVwiXC9wcm9ibGVtXC82NTc2XCIgdGFyZ2V0PVwiX2JsYW5rXCI+NjU3Nlx1YmM4ODxcL2E+IFx1YzU0NFx1Yzk4OFx1ZDE0ZCBcdWJiMzhcdWJhODVcdWM3NTggXHVjNzIwXHVjODAxXHVjOWMwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzgzOFx1YzYyOCBcdWJjZjRcdWJiM2NcdWM5YzBcdWIzYzRcdWFjMDAgXHVhYzAwXHVjOWRjXHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjOGNcdWI0MThcdWM1YzhcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1YzVkMCBcdWQ2NTRcdWFjMDBcdWIwOWMgXHVkNTVjXHVjMmUwXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1YmZkMFx1YjljYyBcdWM1NDRcdWIyYzhcdWI3N2MgXHViMmU0XHViOTc4XHVjMGFjXHViNzhjXHVjNWQwXHVhYzhjXHViM2M0IFx1Yzc3NCBcdWFjNzBcdWM5ZDMgXHVjOWMwXHViM2M0XHViOTdjIFx1YmNmNFx1YjBiNFx1YzExYyBcdWM3YTVcdWIwOWNcdWM3NDQgXHVjZTYwIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzQgXHVjOWMwXHViM2M0XHViOTdjIFx1YzU0NFx1YmIzNFx1YjA5OCBcdWM3N2RcdWM3NDRcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVhY2U0XHViNzgwXHVkNTc0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWFjODNcdWM3NDQgXHVjNzA0XHVkNTc0IFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAhPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YjNjNFx1YjI5NCBYQk0gXHVkNjE1XHVjMmRkXHVjNzc0XHViYTcwIFx1Yzc3NFx1YWM4M1x1Yzc0NCBcdWNmZmNcdWI0ZGMgXHVkMmI4XHViOWFjIFx1YWQ2Y1x1Yzg3MFx1Yjg1YyBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWQ1NThcdWM1ZWMgXHViY2Y0XHViMGJjXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NThcdWFjYTBcdWIyOTRcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICZxdW90OyNkZWZpbmUgcXVhZHRyZWVfd2lkdGggPGVtPm48XC9lbT4mcXVvdDtcdWFjMDAgXHVjNzg1XHViODI1XHVjNzc0IFx1YjQxOFx1YjI5NFx1YjM3MCBcdWM1ZWNcdWFlMzBcdWMxMWMgblx1Yzc0MCBcdWFjMDBcdWI4NWMgXHVkNTNkXHVjMTQwIFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIChcdWM3NzQgXHVjMGFjXHVjOWM0XHVjNzQwIDxlbT5uKm4gPFwvZW0+XHVkNTNkXHVjMTQwXHVjNzc0XHViMmU0Lik8XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJnF1b3Q7I2RlZmluZSBxdWFkdHJlZV9oZWlnaHQgPGVtPm48XC9lbT4mcXVvdDtcdWFjMDAgXHVjNzg1XHViODI1XHVjNzc0IFx1YjQxOFx1YjI5NFx1YjM3MCBcdWM1ZWNcdWFlMzBcdWMxMWMgblx1Yzc0MCBcdWMxMzhcdWI4NWMgXHVkNTNkXHVjMTQwIFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICZxdW90O3N0YXRpYyBjaGFyIHF1YWR0cmVlX2JpdHNbXSA9IHsmcXVvdDtcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHVjNzRjIG5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjOWM0IFx1ZDU1Y1x1YzkwNFx1Yzc1OCBcdWQ1M2RcdWMxNDBcdWFjMTJcdWM3NzQgPGVtPm5cLzg8XC9lbT5cdWFjMWNcdWM3NTggXHVkNWU1XHVjMGFjXHVhYzEyXHViODVjIFx1YmNjMFx1ZDY1OFx1YjQxOFx1YzViNCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPGJyIFwvPlxyXG5cdDxiciBcLz5cclxuXHRcdWFjMDEgXHVkNWU1XHVjMGFjXHVhYzEyXHVjNzQwIDhcdWJlNDRcdWQyYjhcdWI4NWMgOFx1YWMxY1x1Yzc1OCBcdWQ1M2RcdWMxNDBcdWM3NzQgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ2NThcdWI0MThcdWM1YjQgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiAoXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWJlNDRcdWQyYjggXHVhYzEyXHVjNzQwIDFcdWM3NzRcdWFjZTAgXHViOWU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJlNDRcdWQyYjhcdWFjMTJcdWM3NDAgMTI4XHVjNzc0XHViMmU0LikgXHVjNzc0IFx1ZDVlNVx1YzBhY1x1YWMxMlx1Yzc0MCAweDxlbT5kZDxcL2VtPlx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3ODVcdWI4MjVcdWM3NzQgXHViNDE4XHViYTcwIFx1YzVlY1x1YWUzMFx1YzExYyBkXHViMjk0IHsgMCwxLDIsMyw0LDUsNiw3LDgsOSxhLGIsYyxkLGUsZiB9XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48YnIgXC8+XHJcblx0PGJyIFwvPlxyXG5cdFx1YzYwOFx1YzJkYyA6IDggXHVkNTNkXHVjMTQwXHVjNzU4IFdCQkJCV1dCXHViMjk0IDB4OWVcdWI4NWMgXHVjNGYwXHVjNzc4XHViMmU0LjxiciBcLz5cclxuXHQoMis0KzgrMTYrMTI4ID0gMTU4ID0gMHg5ZSkgXHVhYzAxIFx1ZDVlNVx1YzBhY1x1YWMxMlx1Yzc0MCBcdWNmNjRcdWI5YzgoLClcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1Yzc0MCAmcXVvdDt9OyZxdW90O1x1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjOThcdWM3NGMgXHVjODE1XHVjMjE4IDxlbT5uPFwvZW0+ICg4ICZsdDs9IDxlbT5uPFwvZW0+ICZsdDs9IDUxMilcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBCXHVjNjQwIFdcdWFkZjhcdWI5YWNcdWFjZTAgUVx1Yjg1YyBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgXHVjZmZjXHViNGRjXHVkMmI4XHViOWFjIFx1YWQ2Y1x1Yzg3MFx1Yjg1YyBcdWMwYWNcdWM5YzRcdWM3NDQgXHVjNTU0XHVkNjM4XHVkNjU0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2NTgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUXVhZCBUcmVlIiwiZGVzY3JpcHRpb24iOiJcblxuPHA+XG48XC9wPjxwPlxuXG5IYXZpbmcgcmVhbGl6ZWQgdGhhdCB0aGUgcXVhZHRyZWUtZW5jb2RlZCB0cmVhc3VyZSBtYXAgd2FzIGEgZmFrZSxcbkZsb3JpZGEgSm9uZXMgbWFsaWNpb3VzbHkgcGxhbnMgdG8gYWxzbyBwbGF5IGEgcHJhbmsgZm9yIHRoZSBuZXh0IHRyZWFzdXJlXG5odW50ZXIgYWZ0ZXIgaGltLiBCdXQgZm9yIHRoYXQsIGhlIG5lZWRzIHlvdXIgaGVscCBvbmNlIGFnYWluOlxuPFwvcD48cD5cbkNhbiB5b3Ugd3JpdGUgYSBwcm9ncmFtIHRoYXQgdGFrZXMgYSBwaWN0dXJlIGluIHRoZSBYQk0gZm9ybWF0IGFuZFxuPGVtPmVuY29kZXM8XC9lbT4gaXQgd2l0aCB0aGUgcXVhZHRyZWUgc2NoZW1lP1xuXG4gICAgPFwvcD4iLCJpbnB1dCI6IlxuPHVsPlxuPGxpPlxuVGhlIGZpcnN0IGxpbmUgd2lsbCBiZSBcIiNkZWZpbmUgcXVhZHRyZWVfd2lkdGggPGk+bjxcL2k+XCIgd2hlcmUgPGk+bjxcL2k+IGlzXG50aGUgcGljdHVyZSBzaXplIGluIHBpeGVscy4gKFRoZSBwaWN0dXJlIGlzIHF1YWRyYXRpYzogPGk+bipuPFwvaT4gcGl4ZWxzKVxuPFwvbGk+PGxpPlxuVGhlIHNlY29uZCBsaW5lIHdpbGwgYmUgXCIjZGVmaW5lIHF1YWR0cmVlX2hlaWdodCA8aT5uPFwvaT5cIiBhY2NvcmRpbmdseS5cbjxcL2xpPjxsaT5cblRoZSB0aGlyZCBsaW5lIHdpbGwgYmUgXCJzdGF0aWMgY2hhciBxdWFkdHJlZV9iaXRzW10gPSB7XCIuXG48XC9saT48bGk+XG5UaGVuLCA8aT5uPFwvaT4gbGluZXMgd2lsbCBmb2xsb3csIGVhY2ggb25lIGVuY29kaW5nIG9uZSBwaXhlbCByb3cgb2YgdGhlIHBpY3R1cmUuXG5UaGVyZSB3aWxsIGJlIDxpPm5cLzg8XC9pPiBoZXhhZGVjaW1hbCBudW1iZXJzIHBlciBsaW5lLjxcL3A+PHA+XG5FYWNoIGhleGFkZWNpbWFsIG51bWJlciBpcyBjb21wb3NlZCBvZiA4IGJpdHMgdGhhdCBlbmNvZGUgOCBwaXhlbHMgZnJvbSBsZWZ0IHRvIHJpZ2h0XG4od2hlcmUgdGhlIGxlZnRtb3N0IGJpdCBoYXMgdGhlIHZhbHVlIDEgYW5kIHRoZSByaWdodG1vc3QgYml0IGhhcyB0aGUgdmFsdWUgMTI4KS5cblRoZSBoZXhhZGVjaW1hbCBudW1iZXJzIGFyZSBwcmludGVkIGluIHRoZSBmb3JtIDB4PGk+ZGQ8XC9pPiB3aGVyZVxuPGk+ZDxcL2k+IGlzIG9uZSBjaGFyYWN0ZXIgb2YgdGhlIHNldCB7IDAsMSwyLDMsNCw1LDYsNyw4LDksYSxiLGMsZCxlLGYgfS5cbjxcL3A+PHA+XG5FeGFtcGxlOiBUaGUgOCBwaXhlbHMgV0JCQkJXV0IgYXJlIHdyaXR0ZW4gYXMgMHg5ZS4gKDIrNCs4KzE2KzEyOCA9IDE1OCA9IDB4OWUpXG48XC9wPjxwPlxuQWZ0ZXIgZWFjaCBoZXhhZGVjaW1hbCBudW1iZXIsIGEgY29tbWEgZm9sbG93cy5cbjxcL2xpPjxsaT5cblRoZSBsYXN0IGxpbmUgd2lsbCBiZSBcIn07XCIuIFxuPFwvbGk+PFwvdWw+XG4iLCJvdXRwdXQiOiJcbiAgICBcbkZpcnN0LCBwcmludCB0aGUgaW50ZWdlciA8aT5uPFwvaT4gKDggJmx0Oz0gPGk+bjxcL2k+ICZsdDs9IDUxMikgb24gYSBsaW5lIGJ5IGl0c2VsZi5cbjxcL3A+PHA+XG5UaGVuLCBwcmludCBhIHN0cmluZyBjb25zaXN0aW5nIG9mIHRoZSBsZXR0ZXJzIEIsIFcgYW5kIFEgdGhhdCBjb3JyZWN0bHkgZW5jb2RlcyB0aGVcbnBpY3R1cmUgd2l0aCB0aGUgcXVhZHRyZWUgc2NoZW1lLlxuPFwvcD48cD5GaW5hbGx5LCB0ZXJtaW5hdGUgdGhlIHN0cmluZyB3aXRoIGEgbmV3bGluZSBjaGFyYWN0ZXIuXG5cbiAgICAiLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d