dp[i][j][k]表示匹配a串的第i个字符与b串的第j个字符时，当前的a[i]选/不选时的答案

#include<bits/stdc++.h>
#define int long long
#define maxn 105 
using namespace std;
inline char get(){
    static char buf[30000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++; 
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
string a,b;
int n,m;
int dp[maxn][maxn][2];//a串匹配到i，b串匹配到j时是否可行 
/*
若当前位匹配(if(a[i]==b[j]){
当前的不选=》当前的删除=》删除上一个匹配的位置 
*/
stack<int> p;
int note[maxn]; 
signed main(){
    cin>>a>>b;
    n=a.size(),m=b.size();
    a=" "+a;b=" "+b;
    for(register int i=0;i<n;i++)dp[i][0][0]=dp[i][0][1]=1;
    int ans=0;
    for(register int i=1;i<=n;i++){
        if(a[i]=='(')p.push(i);
        else{
            int cas=p.top();
            p.pop();
            note[i]=cas;
        }
    }
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m && j<=i;j++){
            if(a[i]==b[j]){
                if(a[i]==')')dp[i][j][0]=dp[note[i]][j][0];
                else dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]);
            }
            else{
                if(a[i]==')')dp[i][j][0]=dp[note[i]][j][0];
                else dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                dp[i][j][1]=0;
            }
            if(j==m)ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
        }
    }
    if(ans)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
}