document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define ALL(X) (X).begin(), (X).end()
  4. #define REP(I, N) for (int I = 0; I < (N); ++I)
  5. #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
  6. #define RI(X) scanf("%d", &(X))
  7. #define RII(X, Y) scanf("%d%d", &(X), &(Y))
  8. #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
  9. #define DRI(X) int (X); scanf("%d", &X)
  10. #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
  11. #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
  12. #define RS(X) scanf("%s", (X))
  13. #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
  14. #define MP make_pair
  15. #define PB push_back
  16. #define MS0(X) memset((X), 0, sizeof((X)))
  17. #define MS1(X) memset((X), -1, sizeof((X)))
  18. #define LEN(X) strD(X)
  19. #define PII pair<int,int>
  20. #define VI vector<int>
  21. #define VPII vector<pair<int,int> >
  22. #define PLL pair<long long,long long>
  23. #define VPLL vector<pair<long long,long long> >
  24. #define F first
  25. #define S second
  26. typedef long long LL;
  27. using namespace std;
  28. const LL INF = 2e18;
  29. const int SIZE = 1e7+10;
  30. int N,M;
  31. LL E,x[100010];
  32. int d[40],ban[SIZE],D,tt;
  33. struct Union_Find{
  34.     int d[200],num[200];
  35.     void init(int n){
  36.         REP(i,n)d[i]=i,num[i]=1;
  37.     }
  38.     int find(int x){
  39.         return (x!=d[x])?(d[x]=find(d[x])):x;
  40.     }
  41.     bool uu(int x,int y){
  42.         x=find(x);
  43.         y=find(y);
  44.         if(x==y)return 0;
  45.         if(num[x]>num[y])swap(x,y);
  46.         num[y]+=num[x];
  47.         d[x]=y;
  48.         return 1;
  49.     }
  50. }U;
  51. int bfs[SIZE];
  52. bool valid(int ed){
  53.     int rr=0;
  54.     REP(i,D){
  55.         bfs[rr++]=i;
  56.         ban[i]=tt;
  57.     }
  58.     REP(i,rr){
  59.         int x=bfs[i];
  60.         REP(j,N){
  61.             if(x+d[j]>ed)return 1;
  62.             if(ban[x+d[j]]!=tt){
  63.                 ban[x+d[j]]=tt;
  64.                 bfs[rr++]=x+d[j];
  65.             }
  66.             if(x>=d[j]&&ban[x-d[j]]!=tt){
  67.                 ban[x-d[j]]=tt;
  68.                 bfs[rr++]=x-d[j];
  69.             }
  70.         }
  71.     }
  72.     return 0;
  73. }
  74. int main(){
  75.     CASET{
  76.         RII(N,M);
  77.         scanf("%I64d",&E);
  78.         REP(i,N)RI(d[i]);
  79.         sort(d,d+N);
  80.         int gg=d[0];
  81.         REPP(i,1,N)gg=__gcd(gg,d[i]);
  82.         REP(i,N)d[i]/=gg;
  83.         REP(i,M){
  84.             scanf("%I64d",&x[i]);
  85.             if(x[i]%gg){
  86.                 i--;M--;
  87.             }
  88.             else x[i]/=gg;
  89.         }
  90.         if(E%gg){
  91.             puts("evading is impossible");
  92.             continue;
  93.         }
  94.         E/=gg;
  95.         if(!M){
  96.             puts("evadable");
  97.             continue;
  98.         }
  99.         U.init(100);
  100.         REPP(i,d[0],100){
  101.             REP(j,N){
  102.                 if(i>=d[j])U.uu(i,i-d[j]);
  103.             }
  104.             if(U.num[U.find(i)]==i+1){
  105.                 D=i+1;
  106.                 break;
  107.             }
  108.         }
  109.         D=max(D,d[N-1]+1);
  110.         sort(x,x+M);
  111.         bool fail=0;
  112.         for(int i=0,j;i<M;){
  113.             LL low=x[i]-D;
  114.             tt++;
  115.             for(j=i;j+1<M&&x[j]+D>=x[j+1];j++);
  116.             for(;i<=j;i++)ban[x[i]-low]=tt;
  117.             if(!valid(x[j]-low)){
  118.                 fail=1;
  119.                 break;
  120.             }
  121.         }
  122.         puts(fail?"evading is impossible":"evadable");
  123.     }
  124.     return 0;
  125. }
');