Un arreglo de \(n\) enteros está ordenado de menor a mayor. Para cada consulta \(x\), encuentra la primera y la última posición donde aparece \(x\), o informa que no aparece.

Con \(10^5\) consultas, recorrer el arreglo en cada una es demasiado lento: cada consulta debe costar \(O(\log n)\).

Entrada

La primera línea tiene \(n\) y \(q\) \((1 \le n, q \le 10^5)\). La segunda tiene el arreglo ordenado y la tercera las \(q\) consultas. Todos los valores tienen valor absoluto a lo más \(10^9 + 1\).

Salida

Para cada consulta, una línea con las posiciones primera y última (contadas desde \(0\)), o -1 -1 si \(x\) no está.

Ejemplo 1

Entrada

6 3
5 7 7 8 8 10
8 6 5

Salida

3 4
-1 -1
0 0

Ejemplo 2

Entrada

1 2
1
1 0

Salida

0 0
-1 -1