Caçando Águas Vivas

Bob Esponja Calça Quadrada está mais uma vez nos famosos Campos de Água Viva, sua atividade favorita! O campo é extenso e pode ser modelado como uma linha de $N$ posições, da posição 1 até a posição $N$.

Cada água viva $i$ possui um Nível de Força ($x_i$), que mede a dificuldade (e a raridade) de sua captura. Bob Esponja só aceita iniciar uma expedição de caça se tiver certeza de que a água viva menos poderosa na área definida ainda assim será digna de seu esforço.

Antes de cada expedição, ele estabelece um Nível Mínimo de Raridade ($T$). Para que a expedição seja considerada um sucesso, é necessário que o Nível de Força mais baixo encontrado no segmento de caça definido $[L, R]$ seja maior ou igual ao seu Nível Mínimo de Raridade ($T$).

Se o Nível de Raridade mínimo nesse segmento for menor que $T$, significa que há uma água viva muito fraca, e a expedição não vale o risco de decepção. Nesse caso, ele se lamenta: “Ah, mexilhoes!”. Você deve ajudar Bob Esponja a processar $Q$ consultas de expedição.

Tarefa

Dado o arranjo inicial dos $N$ Níveis de Força das águas vivas e um Nível Mínimo de Raridade $T$ fixo para o dia, responda a $Q$ consultas. Para cada consulta, dada uma faixa de índices $[L, R]$, encontre o Nível de Força mínimo da faixa e verifique se ele satisfaz a condição $\ge T$.

Entrada

A entrada é dada no seguinte formato:

$$\begin{aligned} N\ Q\ T \\ x_1\ x_2\ \dots\ x_N \\ L_1\ R_1 \\ L_2\ R_2 \\ \vdots \\ L_Q\ R_Q \end{aligned}$$

1. A primeira linha contém três inteiros: $N$ (o número de águas vivas), $Q$ (o número de consultas), e $T$ (o Nível Mínimo de Raridade).

2. A segunda linha contém $N$ inteiros $x_i$, representando o Nível de Força da água viva na posição $i$.

3. As próximas $Q$ linhas contêm dois inteiros cada, $L$ e $R$, definindo a faixa de caça.

Restrições

• $1 \le N, Q \le 200,000$

• $-10^9\le x_i \le 10^9$

• $min(x_i) \le T \le max(x_i)$

• $1 \le L \le R \le N$

Saída

Para cada uma das $Q$ consultas:

• Se o Nível de Força MÍNIMO no segmento $[L, R]$ for $\ge T$, imprima:

Estou pronto, estou pronto, estou pronto!

• Caso contrário, imprima:

Ah, mexilhoes!

Exemplo 1

Entrada

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

Saída

Ah, mexilhoes!
Ah, mexilhoes!
Ah, mexilhoes!
Ah, mexilhoes!
Estou pronto, estou pronto, estou pronto!

Exemplo 2

Entrada

5 1 3
3 4 5 6 7
1 5

Saída

Estou pronto, estou pronto, estou pronto!