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 C {

	long seed;

	static final int P = 1_000_000_007;

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

	static class Segment implements Comparable<Segment> {
		int l, r;
		long val;

		public Segment(int l, int r, long val) {
			this.l = l;
			this.r = r;
			this.val = val;
		}

		Segment nxt, prv;

		@Override
		public int compareTo(Segment o) {
			return Long.compare(val, o.val);
		}

		int eval(int x, int y) {
			int a = (int) (val % y);
			int ret = 1;
			for (; x > 0; x >>= 1) {
				if ((x & 1) == 1) {
					ret = (int) ((long) ret * a % y);
				}
				a = (int) ((long) a * a % y);
			}
			
			ret = (int)((long)ret * (r - l) % y);
			return ret;
		}
	}

	void split(Segment s, int m) {
		if (m <= s.l || m >= s.r) {
			throw new AssertionError();
		}
		// DOESN'T TOUCH LEFT PART
		Segment nxt = s.nxt;
		Segment add = new Segment(m, s.r, s.val);
		s.r = m;

		s.nxt = add;
		add.prv = s;

		add.nxt = nxt;
		nxt.prv = add;
	}

	void submit() {
		int n = nextInt();
		int m = nextInt();
		seed = nextInt();
		int vmax = nextInt();

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

		Segment head = new Segment(-1, 0, -1);
		Segment tmpTail = head;

		for (int i = 0; i < n; i++) {
			Segment seg = new Segment(i, i + 1, a[i]);
			tmpTail.nxt = seg;
			seg.prv = tmpTail;
			tmpTail = seg;
		}

		Segment tail = new Segment(n, n + 1, -1);
		tail.prv = tmpTail;
		tmpTail.nxt = tail;

		Segment[] arr = new Segment[n];
		int arrSz = 0;
		
//		System.err.println(Arrays.toString(a));

		while (m-- > 0) {
			int op = rnd() % 4;
			int l = rnd() % n;
			int r = rnd() % n;
			if (l > r) {
				int tmp = l;
				l = r;
				r = tmp;
			}

			int x = -1, y = -1;

			if (op == 2) {
				x = rnd() % (r - l + 1);
			} else {
				x = rnd() % vmax + 1;
			}

			if (op == 3) {
				y = rnd() % vmax + 1;
			}
			
//			System.err.println(op + ": " + l + "-" + r + " " + x + " " + y);

			r++;

			Segment bef, aft;

			{
				Segment ptr = head;
				while (ptr.r <= l) {
					ptr = ptr.nxt;
				}

				if (ptr.l != l) {
					split(ptr, l);
					bef = ptr;
					ptr = ptr.nxt;
				} else {
					bef = ptr.prv;
				}

				while (ptr.r < r) {
					ptr = ptr.nxt;
				}

				if (ptr.r != r) {
					split(ptr, r);
					aft = ptr.nxt;
				} else {
					aft = ptr.nxt;
				}
			}

			if (op == 0) {
				for (Segment seg = bef.nxt; seg != aft; seg = seg.nxt) {
					seg.val += x;
				}
				
//				for (int i = l; i < r; i++) {
//					a[i] += x;
//				}
				
				
			} else if (op == 1) {
				Segment blob = new Segment(l, r, x);
				bef.nxt = blob;
				blob.prv = bef;

				blob.nxt = aft;
				aft.prv = blob;
				
//				for (int i = l; i < r; i++) {
//					a[i] = x;
//				}
				
			} else if (op == 2) {
				arrSz = 0;
				for (Segment seg = bef.nxt; seg != aft; seg = seg.nxt) {
					arr[arrSz++] = seg;
				}
				Arrays.sort(arr, 0, arrSz);
				int i = 0;
				
				int realX = x;
				
				while (x >= arr[i].r - arr[i].l) {
					x -= arr[i].r - arr[i].l;
					i++;
				}
				out.println(arr[i].val);
				
				
//				long[] tmp = Arrays.copyOfRange(a, l, r);
//				Arrays.sort(tmp);
//				out.println("vs " + tmp[realX]);
				
			} else if (op == 3) {
				int ans = 0;
				for (Segment seg = bef.nxt; seg != aft; seg = seg.nxt) {
					ans += seg.eval(x, y);
					if (ans >= y) {
						ans -= y;
					}
				}
				out.println(ans);
				
				
				
				
//				int zzz = 0;
//				for (int i = l; i < r; i++) {
//					zzz += pow(a[i], x, y);
//					if (zzz >= y) {
//						zzz -= y;
//					}
//				}
//				out.println("vs " + zzz);
			}
			
//			System.err.println(Arrays.toString(a));
//			
//			for (Segment s = head; s != tail; s = s.nxt) {
//				System.err.println(s.l + " " + s.r + " " + s.val);
//			}
//			System.err.println("--------");
			
		}
	}
	
	int pow(long _a, int b, int m) {
		int a = (int) (_a % m);
		int ret = 1;
		for (; b > 0; b >>= 1) {
			if ((b & 1) == 1) {
				ret = (int)((long)ret * a % m);
			}
			a = (int)((long)a * a % m);
		}
		return ret;
	}

	void preCalc() {

	}

	void stress() {

	}

	void test() {

	}

	C() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		preCalc();
		submit();
		// stress();
		// test();
		out.close();
	}

	static final Random rng = new Random();

	static int rand(int l, int r) {
		return l + rng.nextInt(r - l + 1);
	}

	public static void main(String[] args) throws IOException {
		new C();
	}

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	int nextInt() {
		return Integer.parseInt(nextToken());
	}

	long nextLong() {
		return Long.parseLong(nextToken());
	}

	double nextDouble() {
		return Double.parseDouble(nextToken());
	}
}