You are given a string S that contains n lowercase alphabets. There are Q queries of the form [L,R]. Your task is to determine if every character in the range [L,R] can be arranged in such a manner that a palindromic substring for that range can be formed. If it is possible to create the palindrome substring in the provided interval, then print Possible. Otherwise, print Impossible.
Note: The original string is not changed in the process.
Input format
- First line: Q denotes the number of queries
- Second lines: String S of n lowercase English letters
- Third line: Number of queries of the [L,R] format
Output format
Print Q lines for each query. Print Possible if a palindrome substring is formed in the provided interval. Otherwise, print Impossible.
Constraints
|s|≤105|Q|≤105|s|≤1051≤L≤R≤n
In this case We can't make string palindrome if the interval is between [1, 3], [2, 3]. But we could make palindrome for the individual characters so it's possible for [3, 3].
Also for the case [3, 5] it's possible by shuffling the substring cca as cac so it can be formed as a palindrome.
