Description

Snow White and $n$ dwarfs are in the forest. While the $n$ dwarfs are mining, Snow White is playing on the computer.

Every morning, the dwarfs form a long line and go to the mine. Snow White runs around them, takes photos, and uploads them to her favorite app.

After the dwarfs enter the mining area, Snow White returns to her house, looks through the pictures, and selects the nice ones. Each dwarf has a colored hat, and there are $c$ different colors. A photo is nice if more than half of the hats in it are of the same color. In other words, if there are $k$ dwarfs in a picture, then the picture is nice if more than $\dfrac{k}{2}$ dwarfs have hats of the same color.

For the $m$-th picture, determine whether it is nice. If it is nice, output which color is the main color.

Input Format

The first line contains two positive integers $n, c$, representing the number of dwarfs and the number of colors.

The second line contains $n$ integers between $1$ and $c$, representing the hat colors of the dwarfs, in the order of the line in the morning.

The third line contains a positive integer $m$, representing the number of pictures.

Then follow $m$ lines. Each line contains two positive integers $a$ and $b$. Each line describes a picture that contains all dwarfs from position $a$ to position $b$.

Output Format

Output $m$ lines. For each picture, if Snow White thinks the picture is not nice, output no. If she thinks it is nice, output yes and $x$, where $x$ is the main color in the picture.

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

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

Hint

Constraints

• For $30\%$ of the testdata, $1 \le m < 10$, $3 \le n \le 3 \cdot 10^5$, $1 \le c \le 10^4$, $1 \le a \le b \le n$.
• For another $30\%$ of the testdata, $1 \le m \le 10^4$, $3 \le n \le 3 \cdot 10^5$, $1 \le c < 10$, $1 \le a \le b \le n$.
• For $100\%$ of the testdata, $1 \le m \le 10^4$, $3 \le n \le 3 \cdot 10^5$, $1 \le c \le 10^4$, $1 \le a \le b \le n$.

Notes

Translated from COCI 2009-2010 #3 T5 PATULJCI. Full score is 120. Each test point is worth 12 points. There are 10 test points in total.

Translated by ChatGPT 5