Problem

Given a sorted list of lowercase strings items and a lowercase query string query, return all items that start with query. The result must preserve the original sorted order. Implement the search efficiently without scanning the entire list unless necessary.

Examples

Example 1:

Input: items = ["apple", "application", "banana", "band", "bandana"], query = "app"
Output: ["apple", "application"]
Explanation: Both returned strings begin with "app".

Example 2:

Input: items = ["car", "card", "care", "dog"], query = "cat"
Output: []
Explanation: No string in the list starts with "cat".

Constraints

• 1 <= len(items) <= 10^5
• 0 <= len(query) <= 100
• 0 <= len(items[i]) <= 100
• items is sorted in non-decreasing lexicographic order
• All strings contain only lowercase English letters