You're working on Atlassian Confluence, where every document edit is encoded as a binary audit log. During synchronization across multiple devices, some audit events become unknown due to network conflicts and are represented as ?.
The platform has a validation rule: highly repetitive symmetric patterns are treated as suspicious because they can trigger expensive merge heuristics. Specifically, any contiguous segment that forms a palindrome of length 5 or more is considered invalid.
Before accepting a synchronized document, you need to determine whether the unknown events can be resolved without violating this rule.
Problem
You are given a string S consisting of the characters '0', '1', and '?'.
'0' and '1' represent known audit events.
'?' represents an unresolved event that can be replaced with either '0' or '1'.
Determine whether it is possible to replace every '?' so that the resulting string contains no palindromic substring of length 5 or greater.
Return:
"POSSIBLE" if at least one valid assignment exists.
"IMPOSSIBLE" otherwise.
Examples
Example 1
Input
S = "011???00"
One valid assignment is:
01101000
The resulting string contains no palindrome of length 5 or more.
Output
POSSIBLE
Example 2
Input
S = "00000"
The entire string is a palindrome of length 5.
Output
IMPOSSIBLE