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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Comparator;
import java.util.Collections;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CWillemChthollyAndSeniorious solver = new CWillemChthollyAndSeniorious();
        solver.solve(1, in, out);
        out.close();
    }

    static class CWillemChthollyAndSeniorious {
        int seed;
        int vmax;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.readInt();
            int m = in.readInt();
            seed = in.readInt();
            vmax = in.readInt();
            TreeMap<Integer, Node> map = new TreeMap<>();
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = (rnd() % vmax) + 1;
            }
            Node last;
            map.put(n, last = new Node(null, n, a[n]));
            for (int i = n - 1; i > 0; i--) {
                map.put(i, last = new Node(last, i, a[i]));
            }

            while (m-- > 0) {
                int op = (rnd() % 4) + 1;
                int l = (rnd() % n) + 1;
                int r = (rnd() % n) + 1;

                if (l > r) {
                    int t = l;
                    l = r;
                    r = t;
                }

                int x, y = 0;
                if (op == 3) {
                    x = (rnd() % (r - l + 1)) + 1;
                } else {
                    x = (rnd() % vmax) + 1;
                }

                if (op == 4) {
                    y = (rnd() % vmax) + 1;
                }

                if (!map.containsKey(l)) {
                    Node v = map.lowerEntry(l).getValue();
                    Node mid;
                    map.put(l, mid = new Node(v.next, l, v.v));
                    v.next = mid;
                }

                if (r + 1 <= n && !map.containsKey(r + 1)) {
                    Node v = map.lowerEntry(r + 1).getValue();
                    Node mid;
                    map.put(r + 1, mid = new Node(v.next, r + 1, v.v));
                    v.next = mid;
                }

                if (op == 1) {
                    Node t = map.get(l);
                    while (t != null && t.a <= r) {
                        t.v += x;
                        t = t.next;
                    }
                } else if (op == 2) {
                    Node t = map.get(l).next;
                    while (t != null && t.a <= r) {
                        map.remove(t.a);
                        t = t.next;
                    }
                    t = map.get(l);
                    t.next = map.get(r + 1);
                    t.v = x;
                } else if (op == 3) {
                    Node t = map.get(l);
                    ArrayList<Node> list = new ArrayList<>();
                    while (t != null && t.a <= r) {
                        list.add(t);
                        t = t.next;
                    }
                    Collections.sort(list, Comparator.comparingLong(o -> o.v));
                    int cnt = 0;
                    long prev = -1;
                    for (int i = 0; i < list.size(); i++) {
                        if (cnt >= x) {
                            out.println(prev);
                            break;
                        }
                        if (i == list.size() - 1) {
                            if (list.get(i).v == 513664833) {
                                int ttt = 0;
                            }
                            out.println(list.get(i).v);
                            break;
                        }
                        prev = list.get(i).v;
                        cnt += (list.get(i).next == null ? r + 1 : list.get(i).next.a) - list.get(i).a;
                    }
                } else {
                    Node t = map.get(l);
                    long ans = 0;
                    if (m == 456) {
                        int ttt = 0;
                    }
                    while (t != null && t.a <= r) {
                        ans += (pow(t.v, x, y) * ((t.next == null ? r + 1 : t.next.a) - t.a)) % y;
                        ans %= y;
                        t = t.next;
                    }
                    out.println(ans);
                }
            }
        }

        int rnd() {
            int ret = seed;
            seed = (int) ((seed * 7L + 13) % 1000000007);
            return ret;
        }

        long pow(long a, long b, int mod) {
            long ans = 1;
            a %= mod;
            while (b > 0) {
                if (b % 2 == 1) ans = (ans * a) % mod;
                a = (a * a) % mod;
                b /= 2;
            }
            return ans;
        }

    }

    static class Node {
        Node next;
        int a;
        long v;

        public Node(Node tn, int ta, long tv) {
            next = tn;
            v = tv;
            a = ta;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}