Sophie gives a list of numbers to her five-year-old daughter and explains four types of operations that she can perform on this list. Sophie also gives her a list that shows the sequence in which these operations can be performed. Each operation is performed on the output of the previous operation.

Operation 1: Add a value V to all the numbers in the list from index X to Y.
Operation 2: Subtract the value V from all the numbers in the list from index X to Y.
Operation 3: Initialize all the numbers in the list from index X to Y with the value V.
Operation 4: Find the sum of all the values in the list from index X to Y and add that sum to all the elements in the list.

Write an algorithm to help Sophie’s daughter perform the operations and output the final li st of numbers.

Input
The first line of the input consists of two space-separated integers - N and P representing the size of the list provided by Sophie and the number of operations to be performed on the list, respectively.
The second line consists of N space-separated integers - num1, num2, ..., numN , representing the numbers of the list provided by Sophie.
The next P lines consist of four space-separated integers - op, X, Y and V, representing the type of operation; the start and end index of the range of numbers on which the operations must be performed; and the value that will be used to perform the operation, respectively.

Output
Print N space-separated integers representing the final list after performing all the operations.

Constraints:
1 ≤ N ≤ 105
1 ≤ P ≤ 105
1 ≤ V ≤ 105 , if op != 4
V = 0 , if op = 4
-105 ≤ numi ≤ 105
1 ≤ i ≤ N

Note
As the output of an operation on the number of the list can be very large, modulo it by 1000000007.

Example
Input:
6 5
20 13 4 5 8 10
1 2 3 2
3 1 4 1
2 5 6 5
4 1 6 0
3 2 4 2

Output:
13 2 2 2 15 17

Explanation:
The input list = 20 13 4 5 8 10.
After the first operation, the list is 20 15 6 5 8 10.
After the second operation, the list is 1 1 1 1 8 10.
After the third operation, the list is 1 1 1 1 3 5.
After the fourth operation, the list is 13 13 13 13 15 17.
After the fifth operation, the final list is 13 2 2 2 15 17.