Fibonacci Password Update

You are given a sequence ({a_n}). There will be (m) operations. Each operation is described by five non-negative integers (l, r, k, p, c) and applies to all indices (i) with (l \le i \le r) (1-indexed). For each such index, update (a_i) as follows: [ a_i \gets \bigl( (f_{a_i})^k + c \bigr) \bmod p, ] where (f_n) denotes the Fibonacci sequence defined by [ f_n = \begin{cases} n, & \text{if } n \le 1,\ f_{n-1} + f_{n-2}, & \text{if } n > 1. \end{cases} ] After performing all operations, output the final sequence (the passwords). Note that when (k = 0), define (x^0 = 1) for any (x), including (x = 0).

inputFormat

The first line contains two integers (n) and (m), representing the number of elements in the sequence and the number of operations, respectively. The second line contains (n) non-negative integers (a_1, a_2, \ldots, a_n) separated by spaces. Each of the next (m) lines contains five non-negative integers (l, r, k, p, c) describing an operation. It is guaranteed that (1 \le l \le r \le n).

outputFormat

Output the final sequence of (n) integers after performing all operations, separated by spaces.

sample

5 2
0 1 2 3 4
1 3 2 100 5
2 5 1 50 10

5 18 18 12 13