Scatter Palindrome

Problem For a given string, determine for each queried prefix/substring whether its characters can be rearranged into a palindrome (a "scatter palindrome").

Input / Output

• Input: string s (and optionally query ranges).
• Output: boolean per prefix/substring (or a count of scatter-palindromic ones).

Constraints

• |s| up to 10^5 with many queries — per-query recounting is too slow; precompute.

Example

• "aab" prefixes: "a" ✓, "aa" ✓, "aab" ✓ (aba). "abc" → "ab", "abc" ✗.