Magical Headphones

You are given n headphones arranged in a row and numbered from 1 to n. Each headphone has an initial mystical value, which is an integer between 0 and m - 1. You are also given a series of planned operations. There are two types of operations:

1. Plan an Operation: This operation, represented by four integers L, R, a, b, means that for every headphone with index i such that L ≤ i ≤ R, its mystical value will be updated according to the linear transformation \[ x \to (a \cdot x + b) \bmod m, \] where \(x\) is the current mystical value. Each such planned operation is recorded in a list. The operations are numbered in the order they are planned, starting with 1.
2. Query a Planned Sequence: This query is represented by three integers i, j, k. It asks: if you take the planned operations number i through j (in the same order as they were planned) and apply only those operations (and only when the headphone is affected by the operation) to headphone number k, what will be its final mystical value? Note that if an operation’s range does not cover k, it is skipped.

The initial mystical values of the headphones are provided in the input. You need to process Q queries which can be either planning an operation or a query.

inputFormat

The first line contains three integers n, m, Q (1 ≤ n, Q ≤ 10^5 and 2 ≤ m ≤ 10^9): the number of headphones, the modulus, and the number of queries.

The second line contains n integers: v₁, v₂, ..., v_n, where each v_i is the initial mystical value of the i-th headphone (0 ≤ v_i < m).

Then follow Q lines. Each line represents a query in one of the following two formats:

• Plan an Operation: 1 L R a b (with 1 ≤ L ≤ R ≤ n and 0 ≤ a, b < m); this records a planned operation that will update a headphone's mystical value \(x\) to \((a\cdot x+b) \bmod m\) if the headphone index is in the range \([L, R]\).
• Query a Planned Sequence: 2 i j k (with 1 ≤ i ≤ j ≤ [number of planned operations so far] and 1 ≤ k ≤ n); this asks what will be the final mystical value of headphone k if you apply the planned operations from the i-th to the j-th (inclusive) in order. When processing an operation, if the headphone index k is outside its range \([L, R]\), then it has no effect.

For every query of type 2, output the resulting mystical value on a new line.

outputFormat

For each query of type 2, output a single integer — the final mystical value of the queried headphone after applying the specified planned operations in order.

sample

5 10 6
0 1 2 3 4
1 2 4 2 3
1 1 3 3 1
2 1 2 3
2 2 2 5
1 4 5 1 7
2 1 3 4

2
4
6