Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input:
sadbutsad
sad
Output: 0

Example 2:

Input:
leetcode
leeto
Output: -1

Constraints:

• 1 ≤ haystack.length, needle.length ≤ 10⁴
• haystack and needle consist of only lowercase English letters

Input format: First line: haystack string. Second line: needle string.

Output format: Index of first occurrence, or -1.