## Problem

### Description

— Willem…
— What’s the matter?
— It seems that there’s something wrong with Seniorious…
— I’ll have a look…

After over years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
has pieces of talisman. Willem puts them in a line, the of which is an integer .
In order to maintain it, Willem needs to perform operations.
There are four types of operations:

1. : For each such that , assign to .
2. : For each such that , assign to .
3. : Print the smallest number in the index range , i.e. the element at the position if all the elements such that are taken and sorted into an array of non-decreasing integers. It’s guaranteed that .
4. : Print the sum of the power of such that , modulo , i.e. .

### Input

The only line contains four integers (,,.
The initial values and operations are generated using following pseudo code:

Here is the type of the operation mentioned in the legend.

### Output

For each operation of types or , output a line containing the answer.

Input 1

Output 1

Input 2

Output 2

### Note

In the first example, the initial array is .
The operations are:

1. 中的每个数
2. 中的每个数赋为
3. 询问区间中的第小值
4. 询问