Cho mảng ~A~ gồm ~n~ phần tử. Có ~q~ thao tác, mỗi thao tác thuộc 2 loại:

• ~1 \ l \ r \ x~: Tăng giá trị các phần tử ~A_l, A_{l+1}, \dots, A_r~ lên ~x~.
• ~2 \ l \ r~: Tính và in ra tổng các tích ~A_i \times A_j~ thỏa mãn ~l \le i \le j \le r~ và ~j - i \ge k~. Nói cách khác, tính: ~\sum_{i=l}^{r} \sum_{j=i+k}^{r} A_i \times A_j~.

Do đáp án của truy vấn loại 2 có thể lớn, hãy in ra đáp án sau khi chia lấy dư cho ~998244353~.

Yêu cầu: Thực hiện các thao tác và in ra kết quả cho các truy vấn loại 2.

Input

• Dòng đầu tiên ghi 3 số ~n, q, k~ (~1 \le n, q \le 10^5, 1 \le k \le 5~).
• Dòng tiếp theo ghi ~n~ số lần lượt là giá trị của ~A_1, A_2, \dots, A_n~ (~0 \le A_i < 998244353~).
• ~q~ dòng tiếp theo, mỗi dòng ghi một truy vấn có cấu trúc như trên.
• Dữ liệu đảm bảo ~1 \le l \le r \le n~ và ~0 < x < 998244353~.

Output

• Với mỗi truy vấn loại 2, in ra trên một dòng đáp án của truy vấn.