9999023 - 书架

小 P 有一个神奇的书架，书架上有 n 本书，第 i 本书的颜色一开始为 ci，一 共有 K 种不同的颜色，接下来小 P 会执行以下的 m 个操作，每个操作为以下两 种中的一种：

1. 修改操作：给出 l, r, a, b，对于所有的 i ∈ [l, r]，将所有的 ci 修改为 (a × ci + b) mod K。
2. 询问操作，给出 l, r，询问区间 [l, r] 中一共出现了多少种不同的颜色。

文件 book.in 中读入数据。 第一行三个整数 n, m, k。 第二行共 n 个整数，第 i 个整数为 ci。 接下来一共 m 行，每一行第一个整数为 op。 若 op = 1，那么接下来紧跟四个整数 l, r, a, b，表示这是一次修改操作。 若 op = 2，那么接下来紧跟两个整数 l, r，表示这是一次询问操作。

对于每一次询问操作，输出一行一个整数，表示该次询问操作的答案。