MOG Round #10Ended |
Fito tiene $N$ mascotas, entre perros, gatos, gallos y patos. Es todo un zoológico lo que tiene en el patio de su casa. Fito se siente muy orgulloso de sus animales y le gusta todos los días tirarles varias fotos a todos los animales para guardarlas. Todos los animales tienen un collar de un solo color, pero Fito solo pudo hacer collares de $K$ colores distintos. A Fito le gusta guardar las fotos solo si las encuentra “pintorescas”, una fotos es “pintoresca” si más de la mitad de los collares son del mismo color. Nuestra tarea es ayudar a Fito a saber dada $P$ fotos si son “pintorescas” y de serlo, saber cuál es el color que predomina.
La primera línea de la entrada contiene dos enteros, $N$ y $K$ separados por un espacio $(3 \leq N \leq 300000, 1 \leq K \leq 10000)$. La segunda línea contiene $N$ enteros entre $1$ y $K$ (incluyéndolo) que representan los colores de los collares de los $N$ animales. La tercera línea contiene el número $P$ $(1 \leq P \leq 10000)$. Las siguientes $P$ líneas contienen dos números $X$ y $Y$ $(1 \leq X \leq Y \leq N)$. Cada línea representa los animales que están presentes en la foto, si $X= 2$ y $Y =5$ quiere decir que en esa foto están los animales del $2$ al $5$.
Se imprimen $P$ líneas, por cada línea se imprime $\texttt{no}$ si la foto no es “pintoresca” y cuando es “pintoresca” se imprime $\texttt{si}$ y $Q$ separados por un espacio, donde $Q$ es el color dominante de la fotografía.