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| \le 10^5\\ |Q| \le 10^5\\ |s| \le 10^5\\ 1 \le L \le R \le n\\\)