Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)


In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.---Wikipedia

BrotherK and Ery like playing mathematic games. Today, they are playing a game with GCD.

BrotherK has an array $A$ with $N$ elements: $A_1$ ~ $A_N$, each element is a integer in [1, 10^9]. Ery has $Q$ questions, the i-th question is to calculate
GCD($A_{L_i},~A_{L_i + 1},~A_{L_i + 2},~...,~A_{R_i}$), and BrotherK will tell her the answer.

BrotherK feels tired after he has answered $Q$ questions, so Ery can only play with herself, but she don't know any elements in array $A$. Fortunately, Ery remembered all her questions and BrotherK's answer, now she wants to recovery the array $A$.


The first line contains a single integer $T$, indicating the number of test cases.

Each test case begins with two integers $N,~Q$, indicating the number of array $A$, and the number of Ery's questions. Following $Q$ lines, each line contains three integers $L_i,~R_i$ and $Ans_i$, describing the question and BrotherK's answer.

$T$ is about 10





For each test, print one line.

If Ery can't find any array satisfy all her question and BrotherK's answer, print "Stupid BrotherK!" (without quotation marks). Otherwise, print $N$ integer, i-th integer is $A_i$.

If there are many solutions, you should print the one with minimal sum of elements. If there are still many solutions, print any of them.

Sample Input

2 2 2 1 2 1 1 2 2 2 1 1 2 2

Sample Output

Stupid BrotherK! 2 2