Bài tập

Vào dịp lễ Giáng sinh, siêu thị Winmart tổ chức chương trình khuyến mãi vô cùng hấp dẫn dành cho \(n\) mặt hàng hot nhất mùa. Các mặt hàng này được xếp từ trái sang phải theo thứ tự với mức giá đặc biệt ưu đãi là \(p_i\) cho mỗi sản phẩm. Số lượng mỗi mặt hàng là không giới hạn, sẵn sàng đáp ứng mọi nhu cầu của các khách hàng thân thiết.

Chương trình khuyến mãi đã thu hút rất nhiều sự chú ý, đặc biệt là từ \(m\) khách hàng VIP --- những người không chỉ yêu thích mua sắm mà còn có niềm đam mê săn khuyến mãi. Mỗi khách hàng \(i\) đã chuẩn bị cho mình một số tiền là \(t_i\) và sẽ bắt đầu hành trình mua sắm của mình từ vị trí \(l_i\) đến \(r_i\) trên kệ hàng.

Trong hành trình này, mỗi khách hàng sẽ "săn" nhiều nhất có thể các món hàng trong phạm vi đã định cho đến khi số tiền không đủ để mua thêm. Họ không ngại chi tiêu, nhưng cũng muốn tiết kiệm một khoản để tiếp tục hành trình mua sắm các sản phẩm khác trong tương lai. Tại mỗi vị trí lần lượt từ \(l\) đến \(r\), họ sẽ cố gắng mua hết tất cả các sản phẩm có thể sau đó mới chuyển đến kệ hàng tiếp theo.

Yêu cầu: Hãy giúp siêu thị Winmart tính toán số tiền còn lại của từng khách hàng VIP sau khi họ đã thoả mãn sở thích mua sắm của mình.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) \((n, m \leq 2 \times 10^5)\) --- số lượng mặt hàng và số lượng khách hàng VIP.
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\) \((1 \leq p_i \leq 10^9)\) --- giá tiền của từng mặt hàng theo thứ tự từ trái sang phải. Các sản phẩm này được chọn lọc kỹ lưỡng, đa dạng từ đồ gia dụng, thời trang, đến các thiết bị công nghệ cao cấp.
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(t_i, l_i, r_i\) \((1 \leq l_i \leq r_i \leq n, 1 \leq t_i \leq 10^{18})\) --- số tiền ban đầu của khách hàng \(i\) và phạm vi kệ hàng mà họ sẽ khám phá.

Output

Ghi ra file \(m\) số nguyên, mỗi số thể hiện số tiền còn lại của khách hàng tương ứng sau khi đã hoàn thành hành trình mua sắm của mình.

Example

5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

2
0
1

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n, m \leq 5000\).
• Có \(15\%\) số test tương ứng với \(15\%\) số điểm có \(p_{i} \leq p_{i + 1}\) với \(i = 1..n - 1\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(p_{i} \geq p_{i + 1}\) với \(i = 1..n - 1\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho một lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) tới \(r\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) tới \(c\) theo thứ tự từ trái qua phải. Trên bảng có một số ô cấm.

Bạn cần đi từ góc trái trên \(–\) ô \((1, 1)\) tới góc phải dưới \(–\) ô \((r, c)\). Tại mỗi bước, bạn được đi theo một trong năm hướng như hình vẽ dưới đây:

\begincenter

\endcenter

Một đường đi được gọi là đường đi đẹp khi và chỉ khi đường đi có những tính chất sau:

• Mọi bước đi đều đi theo một trong năm hướng nêu trên.
• Hai bước đi liên tiếp nhau phải đi theo hai hướng khác nhau.
• Đường đi không đi qua ô cấm nào.

Ví dụ, đường đi dưới đây là một đường đi đẹp:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có một bước đi không theo cả năm hướng trên:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có hai bước đi liên tiếp theo cùng một hướng:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có đi qua ô cấm:

\begincenter

\endcenter

Hãy đếm số đường đi đẹp từ ô \((1, 1)\) tới ô \((r, c)\).

Input

Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2207)\) \(–\) số hàng và số cột của bảng.

\(r\) dòng tiếp theo, mỗi dòng chứa \(c\) kí tự mô tả bảng. Ký tự . thể hiện ô không cấm và ký tự # thể hiện ô cấm.

Dữ liệu vào đảm bảo hai ô \((1, 1)\) và \((r, c)\) đều không phải ô cấm.

Output

In ra một số nguyên duy nhất là số đường đi đẹp modulo \(998244353\).

Example

3 3
...
.#.
...

6

4 4
....
.##.
.#..
....

6

7 21
.....................
.####...#...#..#...#.
.#...#..#...#..#...#.
.####....#.#...#####.
.#.......#.#...#...#.
.#........#....#...#.
.....................

0

Scoring

• Subtask \(1\) (\(50\) điểm): \(r, c \leq 7\)

• Subtask \(2\) (\(50\) điểm): \(r, c \leq 2207\)

Vào năm 2112, thế giới đã tiến tới một kỷ nguyên hoàng kim. Nhờ sự bùng nổ của công nghệ và trí tuệ nhân tạo, năng suất lao động đạt đến mức cực thịnh, của cải dư thừa đủ để cung cấp cho gấp đôi dân số toàn cầu. Xã hội vận hành theo lý tưởng: mọi người làm việc theo năng lực và hưởng thụ theo nhu cầu. Tuy nhiên, bản năng trao đổi và thú vui mua sắm của con người vẫn không hề mất đi.

Tại "Đại lộ Bình Minh", có \(n\) cửa hàng xếp kề nhau thành một đường thẳng, đánh số từ \(1\) tới \(n\). Mỗi cửa hàng ở đây vô cùng chuyên môn hóa: cửa hàng \(i\) chỉ bán duy nhất một loại mặt hàng đặc trưng với giá niêm yết là \(a_i\). Để đảm bảo trật tự kinh doanh và giúp khách hàng dễ dàng hoạch định chi tiêu, các chủ tiệm đã ký kết một hiệp ước: các mặt hàng được sắp xếp sao cho giá của chúng không tăng khi đi từ đầu phố đến cuối phố, tức là \(a_i \ge a_{i+1}\) với mọi \(1 \le i < n\).

Mặc dù vậy, sự biến động của chuỗi cung ứng vẫn khiến giá cả hàng hóa thay đổi. Sở Giao dịch Hàng hóa (MXV) sẽ cập nhật mức giá sàn mới theo từng giai đoạn. Khi có một thông báo điều chỉnh giá, thông tin sẽ được truyền từ đầu phố (cửa hàng \(1\)) lan dần xuống cuối phố. Tuy nhiên, do mạng lưới truyền dẫn đôi khi bị nhiễu, thông tin chỉ lan đến cửa hàng thứ \(x\) rồi dừng lại. Khi đó, tại mỗi cửa hàng \(i\) (\(1 \le i \le x\)), giá sẽ được cập nhật lại thành:

Lưu ý rằng sau mỗi lần điều chỉnh, tính chất không tăng của dãy giá vẫn luôn được bảo toàn.

Cư dân năm 2112 cũng có thói quen mua sắm rất đặc biệt. Một người mua hàng khi ghé thăm đại lộ sẽ mang theo một số tiền \(c\) và bắt đầu hành trình từ một cửa hàng \(u\) bất kỳ, sau đó đi bộ dọc theo chiều tăng của số thứ tự cho đến cuối phố. Tại mỗi cửa hàng \(i\) đi ngang qua, nếu số tiền còn lại đủ để mua mặt hàng \(a_i\), họ sẽ lập tức mua nó và cập nhật số tiền còn lại:

Nếu không đủ tiền, họ lẳng lặng bỏ qua và đi tiếp sang cửa hàng tiếp theo với hy vọng tìm được món hàng rẻ hơn ở phía cuối phố. Nhiệm vụ của bạn là ghi lại kết quả của \(q\) hoạt động diễn ra trên đại lộ.

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 3 \cdot 10^5\)) --- số lượng cửa hàng.

Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 2 \cdot 10^{13}\)) --- giá ban đầu của các mặt hàng (\(a_i \ge a_{i+1}\)).

Dòng tiếp theo chứa số nguyên \(q\) (\(1 \le q \le 3 \cdot 10^5\)) --- số lượng hoạt động.

\(q\) dòng tiếp theo, mỗi dòng mô tả một hoạt động thuộc một trong hai loại:

• 1 x y: Thông tin giá sàn \(y\) lan đến cửa hàng \(x\). Cập nhật giá các cửa hàng từ \(1\) đến \(x\). (\(1 \le x \le n, 1 \le y \le 2 \cdot 10^{13}\)).
• 2 u c: Khách hàng xuất phát từ cửa hàng \(u\) với số tiền \(c\) (\(1 \le u \le n, 1 \le c \le 2 \cdot 10^{13}\)).

Output

Với mỗi hoạt động loại 2, in ra một số nguyên duy nhất trên một dòng là số lượng món hàng khách hàng mua được.

Example

8
1919 1650 1496 849 674 565 98 20
9
2 6 2356
1 1 236
1 7 1122
2 7 4086
2 5 6863
1 8 1532
1 8 825
1 2 1890
2 1 10000

3
2
4
6

Scoring

• Subtask 1 (20% số điểm): \(n, q \le 5000\).
• Subtask 2 (20% số điểm): \(a_i\) và \(y\) luôn có dạng \(2^k\) với \(k\) là một số nguyên không âm.
• Subtask 3 (15% số điểm): Không có hoạt động loại 1.
• Subtask 4 (15% số điểm): Tất cả hoạt động loại 1 xảy ra trước các hoạt động loại 2.
• Subtask 5 (30% số điểm): Không có ràng buộc gì thêm.

Cho một dãy số nguyên không âm \(a_1,a_2,\ldots,a_n\) và một số nguyên \(\delta\).

• Đếm số dãy con liên tiếp, khác rỗng mà với mọi hai phần tử bất kỳ trong dãy con đó, chênh lệch không vượt quá \(\delta\) (tức \(\max-\min \le \delta\)).
• Đếm số dãy con, khác rỗng mà với mọi hai phần tử bất kỳ trong dãy con đó, chênh lệch không vượt quá \(\delta\).

Kết quả có thể rất lớn, hãy in ra hai đáp án theo modulo \(998244353\).

\InputFile

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(\delta\) (\(1 \le n \le 5\cdot 10^5\), \(0 \le \delta \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,\ldots,a_n\) (\(0 \le a_i \le 10^9\)).

\OutputFile

In ra hai số nguyên không âm trên một dòng, lần lượt là đáp án của (1) và (2), đều modulo \(998244353\).

\Scoring
\begin itemize

• Có \(35\%\) số điểm ứng với \(n \le 20\).
• Có \(25\%\) số điểm ứng với \(a_1 \le a_2 \le \cdots \le a_n\).
• \(40\%\) số điểm không có ràng buộc gì thêm.
  \end itemize

Example

3 1
1 3 2

4 5

5 4
1 2 3 4 5

15 31

6 0
0 0 1 1 1 0

10 14