Lazy Division

bi11a1 CUET CSE Fest 2022 - Inte...
Limits 1s, 240 MB

You are given an array aa of length nn. You have to perform the following operation on the array qq times:

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

Print the final array after performing all the qq operations.

Input

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

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

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

Then follows qq lines, each containing three values: l,r,m(1lrn,1m1018)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][l, r] using mm.

It is guaranteed that the summation of nn and qq does not exceed 4×1054\times 10^5.

Output

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

Sample

InputOutput
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

Submit

Login to submit.

Statistics

71% Solution Ratio
KnightshadeEarliest, 1M ago
Farhan20Fastest, 0.1s
Error_CoderLightest, 5.6 MB
NoorSayedShortest, 735B
Toph uses cookies. By continuing you agree to our Cookie Policy.