Một dãy ~f~ có độ dài vô hạn được định nghĩa như sau:

• ~f_0 = 0~.
• ~f_1 = 1~.
• ~f_i = (f_{i - 1} + 2 \times f_{i - 2})~ mod ~1058375681~ ~\forall~ ~i > 1~ (~a~ mod ~b~ là phần dư khi lấy ~a~ chia ~b~).

Cho một dãy ~a~ có độ dài ~n~ ~(a_1, a_2, ... , a_n)~, ban đầu tất cả phần tử của dãy đều bằng ~0~, hãy thực hiện các truy vấn thuộc một trong hai loại sau:

• Sao chép một đoạn dãy ~f~ và dán vào dãy ~a~: cho ba số ~l~, ~r~ và ~k~, gán ~a_i = f_{i + k - 1}~ ~\forall~ ~l \leq i \leq r~.
• Tính tổng một đoạn dãy ~a~: cho hai số ~l, r~, tính ~(a_l + a_{l + 1} + ... + a_r)~ mod ~1058375681~.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, q~ tương ứng là độ dài dãy ~a~ và số truy vấn cần xử lý ~(1 \leq n, q \leq 10^5)~.

~q~ dòng tiếp theo, mỗi dòng thể hiện một trong hai loại truy vấn sau:

• ~1~ ~l~ ~r~ ~k~: gán ~a_i = f_{i + k - 1}~ ~\forall~ ~l \leq i \leq r~.

• ~2~ ~l~ ~r~: tính ~(a_l + a_{l + 1} + ... + a_r)~ mod ~1058375681~.

Trong mọi truy vấn ~1 \leq l \leq r \leq n~, ~1 \leq k \leq 10^9~.

Output

Với mỗi truy vấn loại ~2~, in ra trên một dòng giá trị cần tìm.

Subtask

• ~15\%~ số test có ~n, q \leq 1000, k \leq 10^5~.
• ~25\%~ số test khác có ~n, q, k \leq 10^5~.
• Các test còn lại không có ràng buộc gì thêm.

Sample Input

5 6
1 1 3 1
2 1 5
1 3 5 6
2 1 5
2 1 4
2 3 3

Sample Output

5
599
258
85