Problem: — Willem...

— What's the matter?

— It seems that there's something wrong with Seniorious...

— I'll have a look...

<image>

Seniorious is made by linking special talismans in particular order.

After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.

Seniorious has n pieces of talisman. Willem puts them in a line, the i-th of which is an integer ai.

In order to maintain it, Willem needs to perform m operations.

There are four types of operations:

  * 1 l r x: For each i such that l ≤ i ≤ r, assign ai + x to ai.
  * 2 l r x: For each i such that l ≤ i ≤ r, assign x to ai.
  * 3 l r x: Print the x-th smallest number in the index range [l, r], i.e. the element at the x-th position if all the elements ai such that l ≤ i ≤ r are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1 ≤ x ≤ r - l + 1.
  * 4 l r x y: Print the sum of the x-th power of ai such that l ≤ i ≤ r, modulo y, i.e. <image>.

Input

The only line contains four integers n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109).

The initial values and operations are generated using following pseudo code:
    
    
      
    def rnd():  
      
        ret = seed  
        seed = (seed * 7 + 13) mod 1000000007  
        return ret  
      
    for i = 1 to n:  
      
        a[i] = (rnd() mod vmax) + 1  
      
    for i = 1 to m:  
      
        op = (rnd() mod 4) + 1  
        l = (rnd() mod n) + 1  
        r = (rnd() mod n) + 1  
      
        if (l > r):   
             swap(l, r)  
      
        if (op == 3):  
            x = (rnd() mod (r - l + 1)) + 1  
        else:  
            x = (rnd() mod vmax) + 1  
      
        if (op == 4):  
            y = (rnd() mod vmax) + 1  
      
    

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

Output

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

Examples

Input

10 10 7 9


Output

2
1
0
3


Input

10 10 9 9


Output

1
1
3
3

Note

In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.

The operations are:

  * 2 6 7 9
  * 1 3 10 8
  * 4 4 6 2 4
  * 1 4 5 8
  * 2 1 7 1
  * 4 7 9 4 4
  * 1 2 7 9
  * 4 5 8 1 1
  * 2 5 7 5
  * 4 3 10 8 5

Solution (in JAVA):

Solution:
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;

public class Main {
    private static final int mod = 1000000007;
    private static int seed;
    private static int rnd(){
        int ret = seed;
        seed = mul(seed,7,mod);
        seed = add(seed,13,mod);
        return ret;
    }

    private static int mul(int a,int b,int m) {
        long ret = a*(long)b;
        return (int)(ret%m);
    }

    private static int add(int a,int b,int m) {
        a += b;
        if (a >= m) a -= m;
        return a;
    }

    private static int powmod(int x,int p,int m) {
        if (p == 0) return 1;
        int y = 1;
        for (;p > 1;p >>= 1) {
            if (p%2 == 1) y = mul(x,y,m);
            x = mul(x,x,m);
        }
        return mul(x,y,m);
    }

    private static long [] A;
    private static TreeMap<Integer,Integer> L;

    private static void fix_left(int l,int r) {
        Integer R = L.ceilingKey(l);
        if (L.get(R) < l) {
            A[l-1] = A[R];
            L.put(l-1,L.get(R));
            L.put(R,l);
        }
    }

    private static void fix_right(int l,int r) {
        Integer R = L.ceilingKey(r);
        if (R > r) {
            A[r] = A[R];
            L.put(r,L.get(R));
            L.put(R,r+1);
        }
    }

    public static void main(String[] args) throws Exception {
        IO io = new IO(null, null);
        int n = io.getNextInt();
        int m = io.getNextInt();
        seed = io.getNextInt();
        int vmax = io.getNextInt();

        A = new long[n];
        for (int i = 0;i < n;i++)
            A[i] = rnd()%vmax + 1;

        L = new TreeMap<>();
        for (int i = 0;i < n;) {
            int j = i;
            while (j < n && A[i] == A[j])
                j++;
            L.put(j-1,i);
            i = j;
        }

        ArrayList<pair> AS = new ArrayList<pair>();

//        System.err.println(L);

        for (int q = 0;q < m;q++) {
            int op = rnd()%4 + 1;
            int l = rnd()%n ;
            int r = rnd()%n ;
            if (l > r) {
                int t = l;
                l = r;
                r = t;
            }



            int x = rnd();
            if (op == 3) x = x%(r-l+1) + 1;
            else x = x%vmax + 1;


            fix_left(l,r);
            fix_right(l,r);

//            System.err.println(op + ": " + l + " " + r + " " + x);
//            System.err.println(L);
            if (op == 1) {
                int cr = l-1;
                while (cr < r) {
                    cr++;
                    Integer R = L.ceilingKey(cr);
                    A[R] += x;
                    cr = R;
                }

            }
            else if (op == 2) {
                int cr = l-1;
                while (cr < r) {
                    cr++;
                    Integer R = L.ceilingKey(cr);
                    cr = R;
                    L.remove(R);
                }
                A[r] = x;
                L.put(r,l);
            }
            else if (op == 3) {
                AS.clear();
                int cr = l-1;
                while (cr < r) {
                    cr++;
                    Integer R = L.ceilingKey(cr);
                    int cl = L.get(R);
                    AS.add(new pair(A[R],R-cl+1));
                    cr = R;
                }

                Collections.sort(AS);
                long v = 0;
                for (pair p : AS)
                    if (p.siz >= x) {
                        v = p.v;
                        break;
                    }
                    else x -= p.siz;
                io.println(v);
            }
            else {
                int y = rnd()%vmax + 1;
                int ans = 0;
                int cr = l-1;
                while (cr < r) {
                    cr++;
                    Integer R = L.ceilingKey(cr);
                    int cl = L.get(R);
                    int v = (int)(A[R]%y),ctr = R - cl +1;
//                    System.err.println(l + " " + r + " vs " + cl + " " + R) ;
//                    System.err.println("+" + ctr + " * " +  v + "^" + x);
                    ans = add(ans,mul(ctr,powmod(v,x,y),y),y);
                    cr = R;
                }
//                System.err.println("mod " + y);
                io.println(ans);
            }
//            System.err.println("{");
//            for (int R : L.keySet())
//                System.err.println("\t" + L.get(R) + " " + R + " " + A[R]);
//            System.err.println("}");
        }


        io.close();
    }


}

class pair implements Comparable<pair>{
    long v;
    int siz;
    public pair(long x,int y) {
        v = x;
        siz = y;
    }
    @Override
    public int compareTo(pair o) {
        long diff = v - o.v;
        if (diff < 0) return -1;
        if (diff == 0) return 0;
        return 1;
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}