Incredible commandos

Time Limit: 1 Second    Memory Limit: 65536 KB

This problem is about AUT Commandos Mission (ACM). AUT Commandos group has C commandos. After some  successful  intelligence  operations,  the  group  discovered  that  R  convicts  have  plans  to  rob  some banks of AUT City. AUT Commandos want to devise a plan to catch each one of the robbers exactly at the time when he starts the attack and right at the crime scene. 

There are N banks in AUT and M bidirectional streets that each one connects two different banks. There is at most one street between two banks and each street has a certain length. AUT commandos know the  map  of  AUT  City.  Also  they  know  that  i‐th  robber  has  planned  to  rob  bank  bi  at  time  ti.  If  a commando wants to catch i‐th robber he should be in bank b_i  at time t_i. Catching a robber completely takes  K  unit  of  time.  Don’t  forget  AUT  Commandos  are  skillful  and  professional,  so  they  can  catch  a robber alone and as soon as they have caught one, they can go for another.  

At time zero, i‐th commando is in bank si. Commandos move at most one meter per unit of time (or they can stay still for some time). Now incredible AUT Commandos want to know if there is any way to catch all the robbers. 

 

Input

The  first  line  begins  with  an  integer  T  (T  ≤  100),  the  number  of  tests.  The  first  line  of  each  test  case contains  integers  N,  M,  K  (1  ≤  N  ≤  100,  1  ≤  M  ≤  N  (N‐1)/2,  0  ≤  K  ≤  10⁶)—the  number  of  banks,  the number  of  streets  and  the  time  needed  to  catch  a  robber,  respectively.  Then  M  lines  follow,  i‐th  of which  contains  three  integers  ui,  v_i,  l_i  (1  ≤  u_i,  v_i  ≤  N,  u  ≠  v,  1  ≤  l_i ≤  106),  meaning  that  there  is  a  street between bank u_I and bank v_i with length of l_i meters. 

In the following line there is an integer C (1 ≤ C ≤ 100), the number of commandos. Next line contains C integers s_I (1 ≤ s_i ≤ N), which specify the starting banks of commandos. Next line contains an integer R (1 ≤ R ≤ 100), the number of robbers. The following R lines each contain two integers bi, t_i (1 ≤ b_i ≤ N, 1 ≤ t_i ≤ 10⁶), meaning that i‐th robber wants to rob bank b_i at time t_i. It is guaranteed that for each i ≠ j, either b_i ≠ b_j or t_I ≠ t_j. 

 

Output

If AUT commandos can catch all of the robbers print “They are incredible!” Otherwise print “Bad luck!” (Quotes for clarity). 

 

Sample Input

2
4 3 0
1 3 10
2 3 2
3 4 3
2
1 2
2
3 8
4 5
3 2 1
1 2 3
2 3 3
1
1
2
2 3
3 6

Sample Output

They are incredible!
Bad luck!

Submit

Source: AUT 2012