Lazy Division

You are given an array $a$ of length $n$. You have to perform the following operation on the array $q$ times:

• Given $l, r, m$, perform integer division on each element of the array within the range $[l, r]$(inclusive) with $m$. i.e., set $a_i =$ $\lfloor$ $\dfrac{a_i}{m}$ $\rfloor$

Print the final array after performing all the $q$ operations.

Input

The input starts with the number of test cases — $T (1\le T \le 10^5)$.

The first line of each test case contains $n (1\le n \le 2\times 10^5)$ and $q (1\le q \le 2\times 10^5)$, indicating the number of elements in the array $a$ and the number of operations to be performed respectively.

The second line of each test case contains $a_1, a_2, …, a_n (0\le a_i \le 10^{18})$ — elements of the array $a$.

Then follows $q$ lines, each containing three values: $l, r, m (1\le l \le r \le n, 1\le m \le 10^{18})$ — indicating an operation to be performed on the range $[l, r]$ using $m$.

It is guaranteed that the summation of $n$ and $q$ does not exceed $4\times 10^5$.

Output

For each test case, print the case number (Case #:) followed by $n$ integers — indicating the array after performing all the operations. See the samples for more details.

Sample

2
5 3
2 3 0 9 4
1 3 2
4 5 1
4 4 3
2 2
10 15
1 2 5
1 1 2

Case 1: 1 1 0 3 4
Case 2: 1 3