An đang chơi một trò chơi giải mật mã cùng Bình. Ban đầu, An có dãy số nguyên ~A~ gồm ~N~ phần tử được đánh số thứ tự từ ~1~ đến ~N~ và một số nguyên dương ~P~. Bình gọi cho An ~Q~ truy vấn. Mỗi truy vấn sẽ gồm bộ 3 số nguyên ~L, R, K~, trong đó từ ~L~ đến ~R~ là chỉ số bắt đầu và kết thúc của một đoạn trong dãy ~A~. Truy vấn được coi là hợp lệ nếu tồn tại một tập con không rỗng của các phần tử ~A_L, ..., A_R~, sao cho tích của các phần tử trong tập con đó chia cho ~P~ dư ~K~.

Số lượng truy vấn hợp lệ chính là mật mã cần tìm. Em hãy giúp An tìm ra mật mã của trò chơi.

Dữ liệu vào

• Dòng đầu tiên chứa 3 số nguyên dương ~N, Q, P~ (~1 \le N, P \le 5000~, ~1 \le Q \le 2 \cdot 10^5~), là số lượng phần tử của mảng, số lượng truy vấn và số ~P~.
• Dòng thứ 2 chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~0 \le A_i \le P~ với ~1 \le i \le N~), là các phần tử của mảng ~A~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~L_i, R_i, K_i~ (~1 \le L_i \le R_i \le N~, ~0 \le K_i \le P~), là bộ ba số ~L, R, K~ của mỗi truy vấn.

Dữ liệu ra

Ghi ra số nguyên duy nhất là số lượng truy vấn hợp lệ.

Ví dụ

Đầu vào

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

Đầu ra

2

Giải thích

• Truy vấn ~1~: Chọn tập con ~\{3, 4\}~ có tích ~3*4=12~ chia ~7~ dư ~5~, hợp lệ.
• Truy vấn ~2~: Không có tập con nào chia ~7~ dư ~3~, không hợp lệ.
• Truy vấn ~3~: Chọn tập con ~\{1, 4\}~ có tích ~1*4=4~ chia ~7~ dư ~4~, hợp lệ.
• Số lượng truy vấn hợp lệ: ~2~

Tính điểm

• Subtask 1 ~(50\%)~: ~1 \leq N \leq 10, 1 \leq Q \leq 100~.
• Subtask 2 ~(30\%)~: ~1 \leq N, P, Q \leq 100~.
• Subtask 3 ~(20\%)~: Không có ràng buộc gì thêm.