Dados un texto \(h\) y un patrón \(p\), encuentra la primera posición de \(h\) donde aparece \(p\) como substring.

Comparar el patrón desde cada posición cuesta \(O(|h| \cdot |p|)\), y los casos grandes están hechos para que eso no alcance: usa KMP o la Z-function.

Entrada

Dos líneas: \(h\) y \(p\), de letras minúsculas, con \(1 \le |p|, |h| \le 10^6\).

Salida

La posición (contada desde \(0\)) de la primera aparición, o \(-1\) si \(p\) no aparece.

Ejemplo 1

Entrada

sadbutsad
sad

Salida

0

Ejemplo 2

Entrada

leetcode
leeto

Salida

-1

Ejemplo 3

Entrada

a
a

Salida

0