Graph Operations and Connected Components Product Sum

Given an undirected graph with n vertices (numbered 1 through n) and initially no edges, an integer u, an integer v, and an array a of n integers. You need to process q operations on the graph. The operations can be of four types:

1. 1 x y: Add an edge between vertices x and y. It is guaranteed that such an edge does not exist before this operation.
2. 2 x y: Remove the edge between vertices x and y. It is guaranteed that such an edge exists before this operation.
3. 3 x y: Update the value at vertex x by setting a[x] to y.
4. 4 x: For the given integer x, consider the current graph which may be disconnected and thus decomposes into connected components \(C_1, C_2, \dots, C_k\). For each component \(C_i\), calculate the product \[ \prod_{j \in C_i} (a_j + x) \] and then output the sum over all components modulo \(u^v\), i.e., \[ \sum_{i=1}^{k} \left( \prod_{j \in C_i} (a_j + x) \right) \bmod u^v. \]

Note: The graph is 1-indexed. Operations are applied sequentially.

inputFormat

The first line contains four integers n, q, u, v. The second line contains n integers: a₁, a₂, ..., a_n. Each of the following q lines contains an operation in one of the following formats:

• 1 x y
• 2 x y
• 3 x y
• 4 x

outputFormat

For each operation of type 4, output a single integer on a new line representing the required sum modulo \(u^v\).

sample

3 5 2 3
1 2 3
1 1 2
4 1
3 2 10
4 2
2 1 2
4 1

2
1
1