COCI 2009/2010, Contest #3

Task PATULJCI

Snow White and the N dwarfs live in the forest. While the dwarfs mine away, Snow White hangs around social networks.

Each morning, the dwarfs form a long line and go whistling away to the mine. Snow White runs around them and snaps pictures to upload onto her favorite social network.

When the dwarfs enter the mine, Snow White goes back to their house and goes through the pictures, selecting pretty ones. Each dwarf has a colored cap, and there are C different colors. A picture is pretty if more than half the caps on it are of the same color. In other words, if there are K dwarfs on the picture, it is pretty if strictly more than K / 2 dwarfs have same colored caps.

Write a program that will check whether a set of M pictures is pretty, and what color is dominating if they are.

Input

The first line contains two integers N and C (3 ≤ N ≤ 300 000, 1 ≤ C ≤ 10 000), the number of dwarfs and the number of colors.

The second line contains N integers between 1 and C (inclusive), colors of the dwarfs' hats, ordered the way they formed the line that morning.

The third line contains M (1 ≤ M ≤ 10 000), number of pictures.

The next M lines each contain two integers A and B (1 ≤ A ≤ B ≤ N). Each line describes one picture. On it there are all the dwarfs starting from A-th all the way to the B-th.

Output

Output M lines. For each picture output "no" if Snow White doesn't think the picture is pretty, and "yes X", where X is the color dominating on the picture, if she does.

Grading

In test cases worth 30% of the points, M will be smaller than 10.

In test cases worth an additional 30%, C will be smaller than 10.

Sample Input

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

Sample Output

no
yes 1
no
yes 1
no
yes 2
no
yes 3

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Jul 23, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)