[USACO] 2-2-4 Party Lamps

/*
ID: 551100k1
LANG: C++
TASK: lamps
*/
#include<stdio.h>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
map<string,map<int,int> > ma;
map<string,int> rr;
int n,c;
vector<int> A,B;
vector<string> arr;
string a;
void dfs(string s,int v){
    int i;
    if(v==c){
        return;
    }
    a=s;
    for(i=0;i<n;i++)
        if(a[i]=='0') a[i]='1';
        else a[i]='0';
    if(ma[a][v]==0){
        if(v%2+c%2==1 && rr[a]==0) arr.push_back(a),rr[a]=1;
        ma[a][v]=1;
        dfs(a,v+1);
    }
    a=s;
    for(i=0;i<n;i+=2)
        if(a[i]=='0') a[i]='1';
        else a[i]='0';
    if(ma[a][v]==0){
        if(v%2+c%2==1 && rr[a]==0) arr.push_back(a),rr[a]=1;
        ma[a][v]=1;
        dfs(a,v+1);
    }
    a=s;
    for(i=1;i<n;i+=2)
        if(a[i]=='0') a[i]='1';
        else a[i]='0';
    if(ma[a][v]==0){
        if(v%2+c%2==1 && rr[a]==0) arr.push_back(a),rr[a]=1;
        ma[a][v]=1;
        dfs(a,v+1);
    }
    a=s;
    for(i=0;i<n;i+=3)
        if(a[i]=='0') a[i]='1';
        else a[i]='0';
    if(ma[a][v]==0){
        if(v%2+c%2==1 && rr[a]==0) arr.push_back(a),rr[a]=1;
        ma[a][v]=1;
        dfs(a,v+1);
    }
}
bool check(string s){
    int i;
    for(i=0;i<A.size();i++)
        if(s[A[i]]=='0')
            return 0;
    for(i=0;i<B.size();i++)
        if(s[B[i]]=='1')
            return 0;
    return 1;
}
int main(){
    freopen("lamps.in","r",stdin);
    freopen("lamps.out","w",stdout);
    int x,i,is=1;
    scanf("%d%d",&n,&c);
    while(scanf("%d",&x) && x!=-1) A.push_back(x-1);
    while(scanf("%d",&x) && x!=-1) B.push_back(x-1);
    string s;
    for(i=0;i<n;i++)
        s+='1';
    if(c%2==0) arr.push_back(s);
    rr[s]=1;
    dfs(s,0);
    sort(arr.begin(),arr.end());
    for(i=0;i<arr.size();i++){
        if(check(arr[i]))
            puts(arr[i].c_str()),is=0;
    }
    if(is) puts("IMPOSSIBLE");
}