## Problem

### Description

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

is made by linking special talismans in particular order.
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. 询问

## Code

------------- Thanks For Reading -------------
0%