Cho một dãy số nguyên ~a_1, a_2, \ldots, a_n~ và số nguyên ~m~. Bạn hãy thực hiện ~q~ truy vấn thuộc một trong hai dạng sau:

• 1 l r x: cộng thêm ~x~ vào các phần tử ~a_l, a_{l+1}, \ldots, a_r~.

• 2 l r: tính ~(a_l^m + a_{l+1}^m + \ldots + a_r^m) \bmod m~.

Dữ liệu

• Dòng đầu tiên gồm ba số nguyên dương ~m, n~ và ~q~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^6)~.

• ~q~ dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng trên ~(1 \le l \le r \le n,\ 1 \le x \le 10^6)~.

Kết quả

• Với mỗi truy vấn loại ~2~, in ra kết quả trên một dòng.

Ràng buộc

• Subtask 1 (30%): ~1 \le n, q \le 1000,\ m = 2~.

• Subtask 2 (30%): ~1 \le n, q \le 10^5,\ m = 5~.

• Subtask 3 (40%): ~1 \le n, q \le 2 \times 10^5,\ m = 10007~.

Ví dụ

Sample Input

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

Sample Output

1
0