Cho mảng gồm ~n~ số nguyên dương ban đầu đều là ~1~, ví trị trong mảng được đánh số từ ~0~ đến ~n - 1~.

Có số nguyên ~q~ là số lượng truy vấn, mỗi truy vấn có định dạng sau:

• 1 l r x, Tăng giá trị của các phần tử từ ~l~ đến ~r~ lên ~x~ đơn vị.

• 2 l r x, Giảm giá trị của các phần tử từ ~l~ đến ~r~ xuống ~x~ đơn vị, nếu âm sẽ gán lại về ~0~.

• 3 l r, các phần tử có giá trị chẵn từ ~l~ đến ~r~ giảm một nửa.

• 4 l r, Các phần tử có giá trị lẻ từ ~l~ đến ~r~ tăng gấp đôi.

• 5 l3 r3 l4 r4, Thực hiện cùng lúc truy vấn loại 3 với l3 r3 và 4 với l4 r4.

• 6 l1 r1 x1 l2 r2 x2, Thực hiện cùng lúc truy vấn loại 1 với l1 r1 x1 và 2 với l2 r2 x2.

• 7, in ra các giá trị của mảng thời điểm hiện tại.

Đảm bảo kết quả của bài toán vẫn sẽ tính được trong kiểu int64

Input

• Dòng đầu tiên là ~n~ và ~q~ lần lượt là số lượng phần tử trong mảng và số lượng truy vấn.
• ~q~ dòng tiếp theo mỗi dòng là truy vấn theo định dạng đã đề cập ở trên.

Output

• In ra q dòng là kết quả của các truy vấn loại 7.

Constraints

• ~1 \le n, q \leq 10^3~
• ~0 \le x~

Input Sample 1

7 12
1 4 5 7
7
2 3 3 45
7
3 4 6
7
4 0 6
7
5 2 5 5 5
7
6 1 3 43 3 5 21
7

Output Sample 1

1 1 1 1 8 8 1 
1 1 1 0 8 8 1 
1 1 1 0 4 4 1 
2 2 2 0 4 4 2 
2 2 1 0 2 2 2 
2 45 44 22 0 0 2