Thế giới của các Nấm đã bắt đầu chuyển sang một giai đoạn phát triển mới, chúng bắt đầu học cách xây dựng quân đội của đế chế của mình. Người đứng đầu vương quốc nấm, Vua Nấm đã kêu gọi được ~n~ các chiến sĩ Nấm được đánh giá trị từ ~0~ đến ~n - 1~. Vua Nấm suy xét kết hợp họ thành một lực lượng lớn mạnh, mỗi chiến sĩ có một hàm ~f_i(x) = a_ix + b_i~ làm thang đo sức mạnh sau khi huấn luyện khi sức mạnh cơ bản của chiến sĩ ~i~ là ~x~, trong quá trình huấn luyện do có điều chỉnh phương pháp huấn luyện nên các giá trị ~a_i~ và ~b_i~ sẽ được thay đổi. Nếu huấn luyện nhiều chiến sĩ từ ~l~ đến ~r~ thì được một đội quân có sức mạnh ~f_{r-1}(f_{r-2}(...f_l(x)))~. Vua Nấm đặt ra các câu hỏi rằng nếu huấn luyện các chiến sĩ từ ~l~ đến ~r~ thì sức mạnh đội quân là bao nhiêu, Bạn hãy giúp Vua Nấm trả lời các câu hỏi đó nhé.

Cụ thể ~q~ truy vấn có dạng:

• ~0~ ~p~ ~c~ ~d~: thay đổi ~f_p(x) = cx+d~.
• ~1~ ~l~ ~r~ ~x~: in ~f_{r-1}(f_{r-2}(...f_l(x)))~ mod ~998244353~.

Input

Dòng đầy tiên là cặp giá trị ~n~ và ~q~.

~n~ dòng tiếp theo, gồm cặp giá trị ~a_i~ và ~b_i~.

~q~ dòng tiếp theo, là các truy vấn ~0~ ~p~ ~c~ ~d~ và ~1~ ~l~ ~r~ ~x~.

Output

Gồm q dòng, ứng với mỗi câu hỏi của Vua Nấm hãy đưa ra kết quả cần thiết.

Constraints

~1 \le n, q \le 10^5~

~0 \le a_i, b_i, c, d, x \le 998244353~

~0 \le l_i < r_i \le n~

~0 \le p < n~

Input Sample 1

5 5
1 2
3 4
5 6
7 8
9 10
1 0 5 11
1 2 4 12
0 1 13 14
1 0 4 15
1 2 5 16

Output Sample 1

14005
470
8275
5500

Subtask

• SubTask ~1~: ~50~% số test ứng với ~n, q \le 10^3~.
• SubTask ~2~: ~20~% số test ứng với ~b_i = d = 0~.
• Subtask ~3~: ~30~% số test còn lại, không ràng buộc gì thêm.