int mex(set<int>mset)
{
    int m=0;
    while(mset.find(m)!=mset.end())
    m++;
    return m;
}


int grundy(string &s,int ci)
{
    //cout<<s<<endl;
    if(dp.find(s)!=dp.end())
    {
        return dp[s];
    }
    if (ci==0) {
        dp[s] = 0;
        string t = s;
        //cout<<s<<endl;
        //reverse(s.begin(), s.end());
        //dp[t] = 0;
        return 0;
        }
    if (ci == 1) {
      dp[s] = 1;
      string t = s;
      //cout<<s<<endl;
      //reverse(s.begin(), s.end());
      //dp[t] = 1;
      return 1;
    }
    int n=s.length();
    set<int>mset;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='X')
            continue;
        if (s[i] == 'I') {
          s[i] = 'X';
          int ans = grundy(s,ci-1);
          mset.insert(ans);
          s[i] = 'I';
          //cout<<"BACK TO "<<s<<endl;
        }

        if((i+1)<n && s[i]=='I' && s[i+1]=='I')
        {
            s[i]='X';
            s[i+1]='X';
            int ans=grundy(s,ci-2);
            mset.insert(ans);
            s[i]='I';
            s[i+1]='I';
        }
        
    }
    dp[s]=mex(mset);
    return dp[s];
}



string isWinning(int n, string config) {
    /*
     * Return WIN or LOSE depending on whether you will win
     */
    int c=count(config.begin(),config.end(),'I');
    bool ans=(bool)grundy(config,c);
    vector<string>arr(2);
    arr[0]="LOSE";
    arr[1]="WIN";
    return arr[ans];
}