Cho một mảng gồm \(N\) số nguyên dương \(a_1,a_2,...a_N\) \((1 \le a_i \le 10^9)\) và \(M\) truy vấn trên đó. Mỗi truy vấn thuộc một trong hai loại sau:

• Loại \(1\): Có dạng \(1\) \(L\) \(R\) \(P\) với ý nghĩa là truy vấn loại \(1\), lấy tất cả các số trong đoạn \([L,R]\) mà chia hết cho \(P\) đem chia cho \(P\) với P thuộc (2,3,5)
• Loại 2: Có dạng \(2\) \(L\) \(D\) với ý nghĩa là truy vấn loại \(2\), gán số nguyên dương \(D\) cho phần tử ở vị trí \(L\).

Yêu cầu

• hãy in ra mảng cuối cùng nhận được sau \(M\) truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(N,M (1 \le N,M \le 5 \times 10^4)\)
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, ... a_N\)
• \(M\) dòng tiếp theo là mô tả các truy vấn thuộc loại \(1\) hoặc \(2\) nêu ở trên.

Dữ liệu ra

• Dãy số thu được sau \(M\) truy vấn.

Input 1

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

Output 1

5 1 1