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.*;
import java.util.*;

public class MainC {
	static StdIn in = new StdIn();
	static PrintWriter out = new PrintWriter(System.out);
	static long seed;
	
	public static void main(String[] args) {
		int n=in.nextInt(), m=in.nextInt();
		seed=in.nextLong();
		int vmax=in.nextInt();
		TreeMap<Integer, Long> intervals = new TreeMap<Integer, Long>();
		for(int i=0; i<n; ++i)
			intervals.put(i, rnd()%vmax+1L);
		intervals.put(n, 0L);
		while(m-->0) {
			int op=rnd()%4, l=rnd()%n, r=rnd()%n, x, y, i;
			if(l>r) {
				l^=r;
				r^=l;
				l^=r;
			}
			if(op==2)
				x=rnd()%(r-l+1);
			else
				x=rnd()%vmax+1;
			Map.Entry<Integer, Long> l2=intervals.floorEntry(l);
			if(l2.getKey()<l)
				intervals.put(l, l2.getValue());
			if(intervals.higherKey(r)>r+1)
				intervals.put(r+1, intervals.floorEntry(r).getValue());
			List<Map.Entry<Integer, Long>> entries = new ArrayList<Map.Entry<Integer, Long>>();  
			Map.Entry<Integer, Long> entry=intervals.floorEntry(l);
			while(entry!=null&&entry.getKey()<=r+1) {
				entries.add(entry);
				entry=intervals.higherEntry(entry.getKey());
			}
			List<Pair> valCnts = new ArrayList<Pair>();
			switch(op) {
			case 0:
				for(i=0; i<entries.size()-1; ++i)
					intervals.put(entries.get(i).getKey(), entries.get(i).getValue()+x);
				break;
			case 1:
				for(i=1; i<entries.size()-1; ++i)
					intervals.remove(entries.get(i).getKey());
				intervals.put(entries.get(0).getKey(), (long)x);
				break;
			case 2:
				for(i=0; i<entries.size()-1; ++i)
					valCnts.add(new Pair(entries.get(i).getValue(), entries.get(i+1).getKey()-entries.get(i).getKey()));
				Collections.sort(valCnts);
				i=0;
				while(x-valCnts.get(i).b>=0) {
					x-=valCnts.get(i).b;
					++i;
				}
				out.println(valCnts.get(i).a);
				break;
			case 3:
				y=(rnd()%vmax)+1;
				for(i=0; i<entries.size()-1; ++i)
					valCnts.add(new Pair(entries.get(i).getValue(), entries.get(i+1).getKey()-entries.get(i).getKey()));
				long t=0;
				for(Pair p : valCnts)
					t=(t+expM(p.a%y, x, y)*p.b)%y;
				out.println(t);
				break;
			}
		}
		out.close();
	}
	
	static int rnd() {
		int ret=(int)seed;
		seed=(seed*7+13)%1000000007;
		return ret;
	}
	
	static long expM(long b, int p, long m) {
		if(p==0)
			return 1;
		if(p%2==1)
			return b*expM(b*b%m, p/2, m)%m;
		return expM(b*b%m, p/2, m);
	}
	
	static class Pair implements Comparable<Pair> {
		long a;
		int b;
		Pair(long a, int b) {
			this.a=a;
			this.b=b;
		}
		public int compareTo(Pair o) {
			return Long.compare(a, o.a);
		}
	}
	
	interface Input {
		public String next();
		public String nextLine();
		public int nextInt();
		public long nextLong();
		public double nextDouble();
	}
	static class StdIn implements Input {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;
		public StdIn() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		public StdIn(InputStream in) {
			try{
				din = new DataInputStream(in);
			} catch(Exception e) {
				throw new RuntimeException();
			}
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		public String next() {
			int c;
			while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
			StringBuilder s = new StringBuilder();
			while (c != -1)
			{
				if (c == ' ' || c == '\n'||c=='\r')
					break;
				s.append((char)c);
				c=read();
			}
			return s.toString();
		}
		public String nextLine() {
			int c;
			while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
			StringBuilder s = new StringBuilder();
			while (c != -1)
			{
				if (c == '\n'||c=='\r')
					break;
				s.append((char)c);
				c = read();
			}
			return s.toString();
		}
		public int nextInt() {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}
		public int[] readIntArray(int n) {
			int[] ar = new int[n];
			for(int i=0; i<n; ++i)
				ar[i]=nextInt();
			return ar;
		}
		public long nextLong() {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		public long[] readLongArray(int n) {
			long[] ar = new long[n];
			for(int i=0; i<n; ++i)
				ar[i]=nextLong();
			return ar;
		}
		public double nextDouble() {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				ret = ret * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (c == '.')
				while ((c = read()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);
			if (neg)
				return -ret;
			return ret;
		}
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
		private byte read() {
			try{
				if (bufferPointer == bytesRead)
					fillBuffer();
				return buffer[bufferPointer++];
			} catch(IOException e) {
				throw new RuntimeException();
			}
		}
		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
}