You are not given n non-negative integers X₀, X₁, ..., X_n-1 less than 2²⁰ , but they do exist, and their values never change.

I‘ll gradually provide you some facts about them, and ask you some questions.

There are two kinds of facts, plus one kind of question:

There will be at most 10 test cases. Each case begins with two integers n and Q (1 <= n <= 20,000, 2 <= Q <= 40,000). Each of the following lines contains either a fact or a question, formatted as stated above. The k parameter in the questions will be a positive integer not greater than 15, and the v parameter in the facts will be a non-negative integer less than 2²⁰. The last case is followed by n=Q=0, which should not be processed.

For each test case, print the case number on its own line, then the answers, one on each one. If you can‘t deduce the answer for a particular question, from the facts I provide you before that question, print "I don‘t know.", without quotes. If the i-th fact (don‘t count questions) cannot be consistent with all the facts before that, print "The first i facts are conflicting.", then keep silence for everything after that (including facts and questions). Print a blank line after the output of each test case.

2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
3 3
I 0 1 6
I 0 2 2
Q 2 1 2
2 4
I 0 1 7
Q 2 0 1
I 0 1 8
Q 2 0 1
0 0

Case 1:
I don‘t know.
3
1
2
Case 2:
4
Case 3:
7
The first 2 facts are conflicting.

注意：逻辑运算的优先级比比较运算符的优先级低。

#include<stdio.h>
#include<string.h>

const int N = 20005;

int fath[N],XOR[N],n,vist[N];
int know[N],ans[N];

void init()
{
    for(int i=0;i<=n;i++)
    {
        fath[i]=i; XOR[i]=0;
        know[i]=0; vist[i]=0;
    }
}
int findfath(int x)
{
    if(x!=fath[x])
    {
        int tx=fath[x];
        fath[x]=findfath(fath[x]);
        XOR[x]^=XOR[tx];
    }
    return fath[x];
}
int set1(int x,int v)
{
    if(know[x])
    {
        if(ans[x]!=v)return 0;
        else return 1;
    }

    int tx=findfath(x);
    if(know[tx])
    {
       if(XOR[x]!=(ans[tx]^v))
            return 0;
    }
    else
        know[tx]=1,ans[tx]=XOR[x]^v;
    know[x]=1; ans[x]=v;
    return 1;
}
int set2(int x,int y,int v)
{
    int tx=findfath(x);
    int ty=findfath(y);
    if(tx==ty)
    {
        if((XOR[x]^XOR[y])!=v)return 0;
        else return 1;
    }

    if(know[tx])
    {
        fath[ty]=tx; XOR[ty]=XOR[x]^XOR[y]^v;
    }
    else
    {
        fath[tx]=ty; XOR[tx]=XOR[x]^XOR[y]^v;
    }
    return 1;
}
int a[N],node[N];
int Qoperator(int conflict)
{
    int k,nk=0;
    scanf("%d",&k);
    for(int i=0;i<k;i++)
        scanf("%d",&a[i]);
    if(conflict)
        return -1;
    int flag=0,aa=0;
    for(int i=0;i<k;i++)
    {
        if(know[a[i]])
            aa^=ans[a[i]];
        else
        {
            int x=findfath(a[i]);
            if(know[x])
            {
                ans[a[i]]=XOR[a[i]]^ans[x]; know[a[i]]=1;
                aa^=ans[a[i]];
            }
            else
            {
                node[nk++]=x;
                vist[x]++;
                aa^=XOR[a[i]];
                if(vist[x]%2) flag++;
                else flag--;
            }
        }
    }
    for(int j=0;j<nk;j++)
        vist[node[j]]=0;
    if(flag)
        return -1;
    return aa;
}
int main()
{
    int cas=0,m,a,b,v,conflict,flag;
    char s[50];
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        printf("Case %d:\n",++cas);
        init();
        conflict=0;
        int index=0;
        while(m--)
        {
            scanf("%s",s);
            if(s[0]=='I')
            {
                index++;
                scanf("%d%d",&a,&b);
                if(getchar()=='\n')
                {
                    if(conflict)continue;
                    flag=set1(a,b);
                }
                else
                {
                   scanf("%d",&v);
                    if(conflict)continue;
                    flag=set2(a,b,v);
                }

                if(flag==0)
                {
                    printf("The first %d facts are conflicting.\n",index); conflict=1;
                }
            }
            else
            {
                flag=Qoperator(conflict);
                if(conflict==0)
                {
                    if(flag==-1)
                    printf("I don't know.\n");
                    else
                    printf("%d\n",flag);
                }
            }
        }
        printf("\n");
    }
}