시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1870 596 233 27.444%

문제

백설 공주와 난쟁이 N명과 함께 숲 속에 살고 있다. 난쟁이는 매일 광산에 일하러가고, 백설 공주는 그동안 페이스북을 하고 있다.

매일 아침 난쟁이는 한 줄로 휘파람을 불면서 광산으로 출근을 한다. 백설 공주는 그 주변을 돌아다니면서 난쟁이들 사진을 찍는다.

난쟁이가 광산에 들어가면, 백설 공주는 다시 집으로 돌아간다. 집으로 돌아가면서 찍은 사진 중에 페이스북에 올릴 예쁜 사진을 고른다. 각 난쟁이는 모두 모자를 쓰고 있다. 모자의 색상은 총 C가지가 있다. 사진에 찍힌 난쟁이가 쓰고 있는 모자의 색상 중 절반보다 많은 색이 같은 색이라면 예쁜 사진이다. 즉, 사진에 난쟁이가 K명 찍혀있고, K/2보다 많은 난쟁이의 모자 색이 같다면 예쁜 사진이다.

백설공주가 찍은 사진 M개와 각 사진에 찍힌 난쟁이가 주어졌을 때, 예쁜 사진인지 아닌지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000)

둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다.

셋째 줄에는 사진의 수 M이 주어진다. (1 ≤ M ≤ 10,000)

다음 M개 줄에는 두 정수 A와 B가 주어진다. (1 ≤ A ≤ B ≤ N) 이 줄은 사진의 정보를 의미하고, A번째 난쟁이부터 B번째 난쟁이까지 사진에 찍혔다는 뜻이다.

출력

출력은 총 M 줄이다. 각 사진이 예쁘지 않다면 "no"를 출력하고, 예쁘다면 "yes X"를 출력한다. 예쁜 사진인 경우에 X는 사진에 절반이 넘는 모자의 색상이다.

예제 입력 1

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

예제 출력 1

no
yes 1
no
yes 1
no
yes 2
no
yes 3
W3sicHJvYmxlbV9pZCI6IjI5MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWMxMjRcdWFjZjVcdWM4ZmNcdWM2NDAgXHViMDljXHVjN2MxXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzFcdWMxMjQgXHVhY2Y1XHVjOGZjXHVjNjQwIFx1YjA5Y1x1YzdjMVx1Yzc3NCBOXHViYTg1XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWMyMzIgXHVjMThkXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVhZDExXHVjMGIwXHVjNWQwIFx1Yzc3Y1x1ZDU1OFx1YjdlY1x1YWMwMFx1YWNlMCwgXHViYzMxXHVjMTI0IFx1YWNmNVx1YzhmY1x1YjI5NCBcdWFkZjhcdWIzZDlcdWM1NDggXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHViMDljXHVjN2MxXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVkNzE4XHVkMzBjXHViNzhjXHVjNzQ0IFx1YmQ4OFx1YmE3NFx1YzExYyBcdWFkMTFcdWMwYjBcdWM3M2NcdWI4NWMgXHVjZDljXHVhZGZjXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHViYzMxXHVjMTI0IFx1YWNmNVx1YzhmY1x1YjI5NCBcdWFkZjggXHVjOGZjXHViY2MwXHVjNzQ0IFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjOFx1YmE3NFx1YzExYyBcdWIwOWNcdWM3YzFcdWM3NzRcdWI0ZTQgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1Y2MwZFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMDljXHVjN2MxXHVjNzc0XHVhYzAwIFx1YWQxMVx1YzBiMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQsIFx1YmMzMVx1YzEyNCBcdWFjZjVcdWM4ZmNcdWIyOTQgXHViMmU0XHVjMmRjIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVjYzBkXHVjNzQwIFx1YzBhY1x1YzljNCBcdWM5MTFcdWM1ZDAgXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNWQwIFx1YzYyY1x1YjliNCBcdWM2MDhcdWMwNWMgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhYzAxIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgXHViYWE4XHVjNzkwXHViOTdjIFx1YzRmMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjZDFkIENcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWM5YzRcdWM1ZDAgXHVjYzBkXHVkNzhjIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YWMwMCBcdWM0ZjBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzEgXHVjOTExIFx1YzgwOFx1YmMxOFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVjMGM5XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWMwYWNcdWM5YzRcdWM1ZDAgXHViMDljXHVjN2MxXHVjNzc0XHVhYzAwIEtcdWJhODUgXHVjYzBkXHVkNjAwXHVjNzg4XHVhY2UwLCBLXC8yXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0MCBcdWIwOWNcdWM3YzFcdWM3NzRcdWM3NTggXHViYWE4XHVjNzkwIFx1YzBjOVx1Yzc3NCBcdWFjMTlcdWIyZTRcdWJhNzQgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjMTI0XHVhY2Y1XHVjOGZjXHVhYzAwIFx1Y2MwZFx1Yzc0MCBcdWMwYWNcdWM5YzQgTVx1YWMxY1x1YzY0MCBcdWFjMDEgXHVjMGFjXHVjOWM0XHVjNWQwIFx1Y2MwZFx1ZDc4YyBcdWIwOWNcdWM3YzFcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWJhYThcdWM3OTAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMzAwLDAwMCwgMSAmbGU7IEMgJmxlOyAxMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YWMwMCBcdWM0ZjBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM5YzRcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0gJmxlOyAxMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyBOKSBcdWM3NzQgXHVjOTA0XHVjNzQwIFx1YzBhY1x1YzljNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwLCBBXHViYzg4XHVjOWY4IFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YmQ4MFx1ZDEzMCBCXHViYzg4XHVjOWY4IFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YWU0Y1x1YzljMCBcdWMwYWNcdWM5YzRcdWM1ZDAgXHVjYzBkXHVkNjE0XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVjZDFkIE0gXHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMGFjXHVjOWM0XHVjNzc0IFx1YzYwOFx1YzA1OFx1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgJnF1b3Q7bm8mcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM2MDhcdWMwNThcdWIyZTRcdWJhNzQgJnF1b3Q7eWVzIFgmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2MDhcdWMwNWMgXHVjMGFjXHVjOWM0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBYXHViMjk0IFx1YzBhY1x1YzljNFx1YzVkMCBcdWM4MDhcdWJjMThcdWM3NzQgXHViMTE4XHViMjk0IFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBBVFVMSkNJIiwiZGVzY3JpcHRpb24iOiI8cD5Tbm93IFdoaXRlIGFuZCB0aGUgTiBkd2FyZnMgbGl2ZSBpbiB0aGUgZm9yZXN0LiBXaGlsZSB0aGUgZHdhcmZzIG1pbmUgYXdheSBTbm93IFdoaXRlIGhhbmdzIGFyb3VuZCBzb2NpYWwgbmV0d29ya3MuPFwvcD5cclxuXHJcbjxwPkVhY2ggbW9ybmluZyB0aGUgZHdhcmZzIGZvcm0gYSBsb25nIGxpbmUgYW5kIGdvIHdoaXN0bGluZyBhd2F5IHRvIHRoZSBtaW5lLiBTbm93IFdoaXRlIHJ1bnMgYXJvdW5kIHRoZW0gYW5kIHNuYXBzIHBpY3R1cmVzIHRvIHVwbG9hZCBvbnRvIGhlciBmYXZvcml0ZSBzb2NpYWwgbmV0d29yay48XC9wPlxyXG5cclxuPHA+V2hlbiBkd2FyZnMgZW50ZXIgdGhlIG1pbmUsIFNub3cgV2hpdGUgZ29lcyBiYWNrIHRvIHRoZWlyIGhvdXNlIGFuZCBnb2VzIHRocm91Z2ggdGhlIHBpY3R1cmVzLCBzZWxlY3RpbmcgcHJldHR5IG9uZXMuIEVhY2ggZHdhcmYgaGFzIGEgY29sb3JlZCBjYXAsIGFuZCB0aGVyZSBhcmUgQyBkaWZmZXJlbnQgY29sb3JzLiBBIHBpY3R1cmUgaXMgcHJldHR5IGlmIG1vcmUgdGhhbiBoYWxmIGNhcHMgb24gaXQgYXJlIG9mIHRoZSBzYW1lIGNvbG9yLiBJbiBvdGhlciB3b3JkcywgaWYgdGhlcmUgYXJlIEsgZHdhcmZzIG9uIHRoZSBwaWN0dXJlLCBpdCBpcyBwcmV0dHkgaWYgc3RyaWN0bHkgbW9yZSB0aGFuIEsgXC8gMiBkd2FyZnMgaGF2ZSBzYW1lIGNvbG9yZWQgY2Fwcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjaGVjayBmb3IgYSBzZXQgb2YgTSBwaWN0dXJlcyBpZiB0aGV5IGFyZSBwcmV0dHksIGFuZCB3aGF0IGNvbG9yIGlzIGRvbWluYXRpbmcgaWYgdGhleSBhcmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBDICgzICZsZTsgTiAmbGU7IDMwMCAwMDAsIDEgJmxlOyBDICZsZTsgMTAgMDAwKSBudW1iZXIgb2YgZHdhcmZzIGFuZCBudW1iZXIgb2YgY29sb3JzLjxcL3A+XHJcblxyXG48cD5TZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzIGJldHdlZW4gMSBhbmQgQyAoaW5jbHVzaXZlKSwgY29sb3JzIG9mIGR3YXJ2ZXMgaGF0cywgb3JkZXJlZCB0aGUgd2F5IHRoZXkgZm9ybWVkIHRoZSBsaW5lIHRoYXQgbW9ybmluZy48XC9wPlxyXG5cclxuPHA+VGhpcmQgbGluZSBjb250YWlucyBNICgxICZsZTsgTSAmbGU7IDEwMDAwKSwgbnVtYmVyIG9mIHBpY3R1cmVzLjxcL3A+XHJcblxyXG48cD5OZXh0IE0gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgTikuIEVhY2ggbGluZSBkZXNjcmliZXMgb25lIHBpY3R1cmUuIE9uIGl0IHRoZXJlIGFyZSBhbGwgZHdhcnZlcyBzdGFydGluZyBmcm9tIEEtdGggYWxsIHRoZSB3YXkgdG8gdGhlIEItdGguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE0gbGluZXMuIEZvciBlYWNoIHBpY3R1cmUgb3V0cHV0ICZsZHF1bztubyZyZHF1bzsgaWYgU25vdyBXaGl0ZSBkb2VzbiYjMzk7dCB0aGluayB0aGUgcGljdHVyZSBpcyBwcmV0dHksIGFuZCAmbGRxdW87eWVzIFgmcmRxdW87LCB3aGVyZSBYIGlzIHRoZSBjb2xvciBkb21pbmF0aW5nIG9uIHRoZSBwaWN0dXJlLCBpZiBzaGUgZG9lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #3 5번