Sequence Range Power Update

Given an integer sequence a of length n initialized with zero, you need to process q operations. In each operation, you are given four integers s, l, w, and k (with 0 ≤ k ≤ m). For every i in [1, l], update the sequence by setting $$a_{s+i-1} \gets a_{s+i-1} + w \times i^{k}.$$

All arithmetic is performed modulo (2^{64}) (i.e. using natural unsigned 64-bit integer overflow).

The input begins with three integers n, m, and q. The following q lines each contain four integers s, l, w, and k describing an operation. After performing all operations sequentially, output the final sequence, where each element is taken modulo \(2^{64}\).

Note: \(\text{pow}(a,b)\) denotes \(a^{b}\) in the above pseudocode.

inputFormat

The first line contains three integers n, m, and q separated by spaces.

Then q lines follow, each containing four integers s, l, w, and k describing an operation. The sequence is 1-indexed.

outputFormat

Output n space-separated integers: the final values of the sequence modulo \(2^{64}\) after all operations.

sample

5 2 3
1 3 1 0
2 2 2 1
3 3 1 2

1 3 6 4 9