Square and Sum

Little H is a diligent high school student whose dream is to study computer science at his dream university. To achieve his goal, he has been learning the basics of informatics competitions since childhood.

Today, Little H learned about the square operation. To test his understanding, he devised the following problem. He has a sequence of length \(N\): \(X_1, X_2, \ldots, X_N\). Occasionally, he picks a continuous subarray \([l, r]\) and updates every number in that interval by replacing it with its square modulo a given number \(P\), i.e. each \(X_i\) for \(l \le i \le r\) becomes \(X_i^2 \bmod P\). Additionally, he sometimes wants to know the sum of a continuous subarray \([l, r]\) of the current sequence. Since he does not have the standard answers, he seeks your help to output the correct sum for each query.

Input and Query Format:

• The first line contains three integers \(N\), \(M\), and \(P\): the length of the sequence, the number of queries, and the modulo value.
• The second line contains \(N\) integers \(X_1, X_2, \ldots, X_N\).
• Each of the following \(M\) lines represents a query and is in one of the following formats:
  0 l r: Update query. For all indices \(i\) with \(l \le i \le r\), update \(X_i = X_i^2 \bmod P\).
  1 l r: Sum query. Output the sum of \(X_l + X_{l+1} + \cdots + X_r\).

Note: The indices are 1-based.

inputFormat

The first line contains three integers N, M, and P. The second line contains N integers representing the sequence X. Then, M lines follow, each representing a query. A query is in one of the following formats:

0 l r

or

1 l r

For an update query (0 l r), update all numbers X[i] for l <= i <= r to (X[i]^2 mod P). For a query of type 1, output the sum of the subarray X[l] to X[r].

outputFormat

For each query of type 1, output the corresponding sum on a separate line.

sample

5 5 100
1 2 3 4 5
1 1 5
0 2 4
1 1 5
0 1 3
1 2 4

15
35
113