시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1012 275 139 23.440%

문제

백설 공주와 난쟁이 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

힌트

W3sicHJvYmxlbV9pZCI6IjI5MTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWMxMjRcdWFjZjVcdWM4ZmNcdWM2NDAgXHViMDljXHVjN2MxXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWJjMzFcdWMxMjQgXHVhY2Y1XHVjOGZjXHVjNjQwIFx1YjA5Y1x1YzdjMVx1Yzc3NCBOXHViYTg1XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWMyMzIgXHVjMThkXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVhZDExXHVjMGIwXHVjNWQwIFx1Yzc3Y1x1ZDU1OFx1YjdlY1x1YWMwMFx1YWNlMCwgXHViYzMxXHVjMTI0IFx1YWNmNVx1YzhmY1x1YjI5NCBcdWFkZjhcdWIzZDlcdWM1NDggXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNzQ0IFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHViMDljXHVjN2MxXHVjNzc0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVkNzE4XHVkMzBjXHViNzhjXHVjNzQ0IFx1YmQ4OFx1YmE3NFx1YzExYyBcdWFkMTFcdWMwYjBcdWM3M2NcdWI4NWMgXHVjZDljXHVhZGZjXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHViYzMxXHVjMTI0IFx1YWNmNVx1YzhmY1x1YjI5NCBcdWFkZjggXHVjOGZjXHViY2MwXHVjNzQ0IFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJjOFx1YmE3NFx1YzExYyBcdWIwOWNcdWM3YzFcdWM3NzRcdWI0ZTQgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1Y2MwZFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMDljXHVjN2MxXHVjNzc0XHVhYzAwIFx1YWQxMVx1YzBiMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQsIFx1YmMzMVx1YzEyNCBcdWFjZjVcdWM4ZmNcdWIyOTQgXHViMmU0XHVjMmRjIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWJhNzRcdWMxMWMgXHVjYzBkXHVjNzQwIFx1YzBhY1x1YzljNCBcdWM5MTFcdWM1ZDAgXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNWQwIFx1YzYyY1x1YjliNCBcdWM2MDhcdWMwNWMgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhYzAxIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgXHViYWE4XHVjNzkwXHViOTdjIFx1YzRmMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDAgXHVjZDFkIENcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWM5YzRcdWM1ZDAgXHVjYzBkXHVkNzhjIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YWMwMCBcdWM0ZjBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzEgXHVjOTExIFx1YzgwOFx1YmMxOFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVjMGM5XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWMwYWNcdWM5YzRcdWM1ZDAgXHViMDljXHVjN2MxXHVjNzc0XHVhYzAwIEtcdWJhODUgXHVjYzBkXHVkNjAwXHVjNzg4XHVhY2UwLCBLXC8yXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0MCBcdWIwOWNcdWM3YzFcdWM3NzRcdWM3NTggXHViYWE4XHVjNzkwIFx1YzBjOVx1Yzc3NCBcdWFjMTlcdWIyZTRcdWJhNzQgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYzMxXHVjMTI0XHVhY2Y1XHVjOGZjXHVhYzAwIFx1Y2MwZFx1Yzc0MCBcdWMwYWNcdWM5YzQgTVx1YWMxY1x1YzY0MCBcdWFjMDEgXHVjMGFjXHVjOWM0XHVjNWQwIFx1Y2MwZFx1ZDc4YyBcdWIwOWNcdWM3YzFcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNjA4XHVjMDVjIFx1YzBhY1x1YzljNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWJhYThcdWM3OTAgXHVjMGM5XHVjMGMxXHVjNzU4IFx1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMzAwLDAwMCwgMSAmbGU7IEMgJmxlOyAxMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5Y1x1YzdjMVx1Yzc3NFx1YWMwMCBcdWM0ZjBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVjOTA0XHVjNzQ0IFx1YzExYyBcdWM3ODhcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDEwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IE4pIFx1Yzc3NCBcdWM5MDRcdWM3NDAgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIEFcdWJjODhcdWM5ZjggXHViMDljXHVjN2MxXHVjNzc0XHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHViMDljXHVjN2MxXHVjNzc0XHVhZTRjXHVjOWMwIFx1YzBhY1x1YzljNFx1YzVkMCBcdWNjMGRcdWQ2MTRcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgTSBcdWM5MDRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWM5YzRcdWM3NzQgXHVjNjA4XHVjMDU4XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAmcXVvdDtubyZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YzYwOFx1YzA1OFx1YjJlNFx1YmE3NCAmcXVvdDt5ZXMgWCZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1YzA1YyBcdWMwYWNcdWM5YzRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFhcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNWQwIFx1YzgwOFx1YmMxOFx1Yzc3NCBcdWIxMThcdWIyOTQgXHViYWE4XHVjNzkwXHVjNzU4IFx1YzBjOVx1YzBjMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUEFUVUxKQ0kiLCJkZXNjcmlwdGlvbiI6IjxwPlNub3cgV2hpdGUgYW5kIHRoZSBOIGR3YXJmcyBsaXZlIGluIHRoZSBmb3Jlc3QuIFdoaWxlIHRoZSBkd2FyZnMgbWluZSBhd2F5IFNub3cgV2hpdGUgaGFuZ3MgYXJvdW5kIHNvY2lhbCBuZXR3b3Jrcy48XC9wPlxyXG5cclxuPHA+RWFjaCBtb3JuaW5nIHRoZSBkd2FyZnMgZm9ybSBhIGxvbmcgbGluZSBhbmQgZ28gd2hpc3RsaW5nIGF3YXkgdG8gdGhlIG1pbmUuIFNub3cgV2hpdGUgcnVucyBhcm91bmQgdGhlbSBhbmQgc25hcHMgcGljdHVyZXMgdG8gdXBsb2FkIG9udG8gaGVyIGZhdm9yaXRlIHNvY2lhbCBuZXR3b3JrLjxcL3A+XHJcblxyXG48cD5XaGVuIGR3YXJmcyBlbnRlciB0aGUgbWluZSwgU25vdyBXaGl0ZSBnb2VzIGJhY2sgdG8gdGhlaXIgaG91c2UgYW5kIGdvZXMgdGhyb3VnaCB0aGUgcGljdHVyZXMsIHNlbGVjdGluZyBwcmV0dHkgb25lcy4gRWFjaCBkd2FyZiBoYXMgYSBjb2xvcmVkIGNhcCwgYW5kIHRoZXJlIGFyZSBDIGRpZmZlcmVudCBjb2xvcnMuIEEgcGljdHVyZSBpcyBwcmV0dHkgaWYgbW9yZSB0aGFuIGhhbGYgY2FwcyBvbiBpdCBhcmUgb2YgdGhlIHNhbWUgY29sb3IuIEluIG90aGVyIHdvcmRzLCBpZiB0aGVyZSBhcmUgSyBkd2FyZnMgb24gdGhlIHBpY3R1cmUsIGl0IGlzIHByZXR0eSBpZiBzdHJpY3RseSBtb3JlIHRoYW4gSyBcLyAyIGR3YXJmcyBoYXZlIHNhbWUgY29sb3JlZCBjYXBzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNoZWNrIGZvciBhIHNldCBvZiBNIHBpY3R1cmVzIGlmIHRoZXkgYXJlIHByZXR0eSwgYW5kIHdoYXQgY29sb3IgaXMgZG9taW5hdGluZyBpZiB0aGV5IGFyZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEMgKDMgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEMgJmxlOyAxMCAwMDApIG51bWJlciBvZiBkd2FyZnMgYW5kIG51bWJlciBvZiBjb2xvcnMuPFwvcD5cclxuXHJcbjxwPlNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCBDIChpbmNsdXNpdmUpLCBjb2xvcnMgb2YgZHdhcnZlcyBoYXRzLCBvcmRlcmVkIHRoZSB3YXkgdGhleSBmb3JtZWQgdGhlIGxpbmUgdGhhdCBtb3JuaW5nLjxcL3A+XHJcblxyXG48cD5UaGlyZCBsaW5lIGNvbnRhaW5zIE0gKDEgJmxlOyBNICZsZTsgMTAwMDApLCBudW1iZXIgb2YgcGljdHVyZXMuPFwvcD5cclxuXHJcbjxwPk5leHQgTSBsaW5lcyBjb250YWluIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSAmbGU7IEIgJmxlOyBOKS4gRWFjaCBsaW5lIGRlc2NyaWJlcyBvbmUgcGljdHVyZS4gT24gaXQgdGhlcmUgYXJlIGFsbCBkd2FydmVzIHN0YXJ0aW5nIGZyb20gQS10aCBhbGwgdGhlIHdheSB0byB0aGUgQi10aC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgTSBsaW5lcy4gRm9yIGVhY2ggcGljdHVyZSBvdXRwdXQgJmxkcXVvO25vJnJkcXVvOyBpZiBTbm93IFdoaXRlIGRvZXNuJiMzOTt0IHRoaW5rIHRoZSBwaWN0dXJlIGlzIHByZXR0eSwgYW5kICZsZHF1bzt5ZXMgWCZyZHF1bzssIHdoZXJlIFggaXMgdGhlIGNvbG9yIGRvbWluYXRpbmcgb24gdGhlIHBpY3R1cmUsIGlmIHNoZSBkb2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==