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$.
Input
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 $N$ lines, each line contains three integers $L_i,~R_i$ and $Ans_i$, describing the question and BrotherK's answer.
$T$ is about 10
$2~\le~N~\le~1000$
$1~\le~L_i~\lt~R_i~\le~N$
$1~\le~Ans_i~\le~10^9$
Output
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.
