There are n circles on a infinitely large table.With every two circle, either one contains another or isolates from the other.They are never crossed nor tangent.

Alice and Bob are playing a game concerning these circles.They take turn to play,Alice goes first:

1、Pick out a certain circle A,then delete A and every circle that is inside of A.

2、Failling to find a deletable circle within one round will lost the game.

Now,Alice and Bob are both smart guys,who will win the game,output the winner's name.

 

Input

The first line include a positive integer T<=20,indicating the total group number of the statistic.

As for the following T groups of statistic,the first line of every group must include a positive integer n to define the number of the circles.

And the following lines,each line consists of 3 integers x,y and r,stating the coordinate of the circle center and radius of the circle respectively.

n≤20000，|x|≤20000，|y|≤20000，r≤20000。

 

Output

If Alice won,output “Alice”,else output “Bob”

 

Sample Input

210 0 16-100 0 90-50 0 1-20 0 1100 0 9047 0 123 0 1

Sample Output

AliceBob 　　这道题目可以说是模板题…… 　　就是那个SG函数的求法貌似是结论，我不会证明。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 const int N=20010,M=40010; 9 int cnt,fir[N],to[N],nxt[N];10 void addedge(int a,int b){11 nxt[++cnt]=fir[a];12 to[fir[a]=cnt]=b;13 }14 int sqr(int x){ return x*x;}15 int tmp;16 struct Circle{17 int x,y,r;18 Circle(int _=0,int __=0,int ___=0){x=_;y=__;r=___;}19 }c[N];20 21 struct Point{22 int x,id,tp;23 Point(int _=0,int __=0,int ___=0){x=_;id=__;tp=___;}24 friend bool operator<(Point a,Point b){25 double x=c[a.id].y+a.tp*sqrt(sqr(c[a.id].r)-sqr(tmp-c[a.id].x));26 double y=c[b.id].y+b.tp*sqrt(sqr(c[b.id].r)-sqr(tmp-c[b.id].x));27 if(x!=y)return x
           
            s;set
            
             ::iterator it;33 34 int fa[N],sg[N];35 int DFS(int x){36 sg[x]=0;37 for(int i=fir[x];i;i=nxt[i])38 sg[x]^=DFS(to[i])+1;39 return sg[x];40 }41 42 void Init(){43 memset(fir,0,sizeof(fir));44 cnt=0;45 }46 int T,n;47 int main(){48 scanf("%d",&T);49 while(T--){50 Init();scanf("%d",&n);51 for(int i=1;i<=n;i++){52 scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);53 st[2*i-1]=Point(c[i].x-c[i].r,i,-1);54 st[2*i]=Point(c[i].x+c[i].r,i,1);55 }56 sort(st+1,st+2*n+1,cmp);57 for(int i=1;i<=2*n;i++){58 Point x=st[i];tmp=x.x;59 if(x.tp==-1){60 it=s.upper_bound(Point(0,x.id,1));61 if(it==s.end())addedge(fa[x.id]=0,x.id);62 else{63 Point y=*it;64 if(y.tp==1)65 addedge(fa[x.id]=y.id,x.id);66 else67 addedge(fa[x.id]=fa[y.id],x.id);68 }69 s.insert(Point(0,x.id,1));70 s.insert(Point(0,x.id,-1));71 }72 else{73 s.erase(Point(0,x.id,1));74 s.erase(Point(0,x.id,-1));75 }76 }77 printf(DFS(0)?"Alice\n":"Bob\n"); 78 }79 return 0;80 }