Thời đại công nghệ phát triển, trí tuệ con người đã có những chuyển biến đột phá. Bidibidi, một nhà khoa học mới nổi, các thành phẩm nghiên cứu của ông mang lại nhiều thành tựu to lớn và khai phá nhiều lĩnh vực mà con người bấy lâu nay còn đang dang dở. Mới đây một phát minh gây sốc của ông là tái tạo lại trái đất thời nguyên thủy, ông xây dựng một mô hình nhỏ có đầy đủ hệ sinh thái và tài nguyên tựa như trái đất phiên bản nhỏ, đồng thời ông còn có thể tùy chỉnh được thời không trong mô hình mà mình tạo ra giúp cho thời gian bên trong mô hình nhanh hơn ở ngoài gấp nhiều lần. Trong một lần thí nghiệm, ông vô tình khiến cho thời gian bên trong mô hình hoàn toàn vượt xa thế giới thực, sự sống đã tồn tại trong mô hình ấy. Khác với địa cầu, động vật có trí thông minh trong thế giới của ông lại là loài Nấm chúng vô cùng nhỏ bé nhưng lại rất thông minh. Cụ thể, chúng hình thành một quần thể và bắt đầu mở rộng lãnh thổ của mình sang các vùng lân cận khác. Chúng khoanh vùng ~n~ địa điểm và sắp xếp những nơi cần chiếm đóng thành một hàng ngang và được đánh số từ ~1~ đến ~n~ đồng thời mỗi khu vực được chúng quy ước mức độ phong phú của tài nguyên bằng số ~a_i~. Sau tất cả chúng họp bàn với nhau rằng nơi nào sẽ được chiếm đóng, mọi Nấm đều có suy nghĩ riêng chúng, đã có ~q~ đề xuất sẽ khai thác nơi tài nguyên phong phú nhất từ khu vực thứ ~l_i~ đến ~r_i~. Số lượng các ý kiến quá lớn các Nấm không thể xử lý hết, bạn hãy giúp chúng trả lời kết quả mà chúng mong muốn.

Input

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

Dòng thứ hai, Gồm ~n~ giá trị ~a_i~.

~q~ dòng tiếp theo, gồm các giá trị ~l_i~ và ~r_i~ đại diện đề xuất thứ ~i~.

Output

Gồm ~q~ dòng, Ứng với mỗi đề xuất của các Nấm hãy đưa ra kết quả cần thiết.

Constraints

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

~1 \le a_i \le 10^5~

~1 \le l_i \le r_i \le n~

Input Sample 1

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

Output Sample 1

3
2
5

Subtask

• SubTask ~1~: ~90~% số test ứng với ~q \le 10^3~
• SubTask ~2~: ~10~% số test còn lại, không ràng buộc gì thêm

Sau khi xác định được chính xác các khu vực cần phải khai thác, các Nấm lại đặt ra câu hỏi lớn rằng khu vực tài nguyên phong phú như vậy có lẽ nào sẽ bị nhiều động vật hung dữ để mắt đến hay không. Vì để cẩn trọng chúng bắt đầu hoạch định lại các khu vực cần khai thác, Chính xác là khu vực có giá trị phong phú thứ hai của các đề xuất trước đó. Nhưng trong quá trình lên kế hoạch chúng phát hiện rằng đã có nhưng nơi tính toán sai lệch mức độ phong phú cần được thay đổi lại giá trị. Chúng không tài nào có thể xử lý cả hai cùng một lúc, bạn hãy giúp các Nấm hoạch định lại kế hoạch nhé.

Cụ thể, có ~2~ loại truy vấn:

• ~0~ ~p~ ~x~: Thay đổi mức độ phong phú của khu vực ~p~ thành ~x~.
• ~1~ ~l~ ~r~: Trả lời kết quả của đề xuất khai thác từ khu vực ~l~ đến ~r~, nếu không tồn tại hãy in ra ~-1~.

Input

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

Dòng thứ hai, Gồm ~n~ giá trị ~a_i~.

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

Output

Gồm các dòng của truy vấn loại ~1~, Ứng với mỗi đề xuất của các Nấm hãy đưa ra kết quả cần thiết.

Constraints

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

~1 \le a_i \le 10^5~

~1 \le l_i \le r_i \le n~

~1 \le p, x \le n~

Input Sample 1

5 4
1 3 2 5 4
1 2 3
0 3 3
1 2 3
1 1 5

Output Sample 1

2
-1
4

Subtask

• SubTask ~1~: ~90~% số test ứng với ~q \le 10^3~
• SubTask ~2~: ~10~% số test còn lại, không ràng buộc gì thêm

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.

Các vương quốc của thế giới Bidibidi đã hoàn thành quá trình huấn luyện của họ. Bidibidi nhận ra bản thân đã làm cho thời gian trong mô hình đi quá nhanh không kịp quan sát, ông liền tinh chỉnh lại để thời gian trôi chậm hơn dễ quan sát. Khi mọi thứ bắt đầu sôi động hơn, Bidibidi quyết định nghỉ ngơi một xíu và xem các trận chiến cho zui. Có ~n~ vương quốc với sức mạnh tương ứng ~a_i~. Vương quốc có sức mạnh to lớn luôn muốn phô trương lực lượng của mình, vì thế vương quốc ~j~ sẽ tuyên chiến với vương quốc ~i~ và ~k~ cùng lúc nếu sức mạnh của cả hai vương quốc ấy đều thấp hơn nó (~i < j < k~). Bạn có biết nhà khoa học BIdibidi đã theo dõi tổng cộng bao nhiêu trận chiến không, hãy in ra kết quả nhé.

Input

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

Dòng thứ hai, gồm ~n~ giá trị ~a_i~.

Output

Một dòng duy nhất là số trận chiến mà Bidibidi theo dõi.

Constraints

~1 \le n \le 10^5~

~1 \le a_i \le 10^9~

Input Sample 1

4
1 3 5 2

Output Sample 1

3

Subtask

• SubTask ~1~: ~50~% số test ứng với ~n \le 500~.
• SubTask ~2~: ~40~% số test ứng với ~a_i \le n~.
• Subtask ~3~: ~10~% số test còn lại, không ràng buộc gì thêm.