Problem: You are given two permutations p and q, consisting of n elements, and m queries of the form: l1, r1, l2, r2 (l1 ≤ r1; l2 ≤ r2). The response for the query is the number of such integers from 1 to n, that their position in the first permutation is in segment [l1, r1] (borders included), and position in the second permutation is in segment [l2, r2] (borders included too).

A permutation of n elements is the sequence of n distinct integers, each not less than 1 and not greater than n.

Position of number v (1 ≤ v ≤ n) in permutation g1, g2, ..., gn is such number i, that gi = v.

Input

The first line contains one integer n (1 ≤ n ≤ 106), the number of elements in both permutations. The following line contains n integers, separated with spaces: p1, p2, ..., pn (1 ≤ pi ≤ n). These are elements of the first permutation. The next line contains the second permutation q1, q2, ..., qn in same format.

The following line contains an integer m (1 ≤ m ≤ 2·105), that is the number of queries.

The following m lines contain descriptions of queries one in a line. The description of the i-th query consists of four integers: a, b, c, d (1 ≤ a, b, c, d ≤ n). Query parameters l1, r1, l2, r2 are obtained from the numbers a, b, c, d using the following algorithm: 

  1. Introduce variable x. If it is the first query, then the variable equals 0, else it equals the response for the previous query plus one. 
  2. Introduce function f(z) = ((z - 1 + x) mod n) + 1. 
  3. Suppose l1 = min(f(a), f(b)), r1 = max(f(a), f(b)), l2 = min(f(c), f(d)), r2 = max(f(c), f(d)). 

Output

Print a response for each query in a separate line.

Examples

Input

3
3 1 2
3 2 1
1
1 2 3 3


Output

1


Input

4
4 3 2 1
2 3 4 1
3
1 2 3 4
1 3 2 1
1 4 2 3


Output

1
1
2

Solution (in JAVA):

Solution:
import static java.util.Arrays.fill;

import java.io.*;
import java.util.*;

public class C {

	static void solve() throws IOException {
		int n = nextInt();
		int[] p = new int[n];
		int[] inQ = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = nextInt() - 1;
		}
		for (int i = 0; i < n; i++) {
			inQ[nextInt() - 1] = i;
		}
		int x = 0;
		int queries = nextInt();
		Tree tree = new Tree(p, inQ);
		while (queries-- > 0) {
			int a = nextInt(), b = nextInt(), c = nextInt(), d = nextInt();
			int fa  = (a - 1 + x)%n+1; 
			int fb  = (b - 1 + x)%n+1; 
			int fc  = (c - 1 + x)%n+1; 
			int fd  = (d - 1 + x)%n+1; 
			if (fa > fb) {
				int t = fa;
				fa = fb;
				fb = t;
			}
			if (fc > fd) {
				int t = fc;
				fc = fd;
				fd = t;
			}
//			System.err.println(fa+" "+fb+", "+fc+" "+fd);
			x = tree.query(fa, fb, fc, fd);
			out.println(x);
			++x;
		}
	}

	static class Tree {
		int[][] list;

		Tree(int[] p, int[] inQ) {
			int n = p.length;
			int size = Integer.highestOneBit(2 * n - 1);
			list = new int[2 * size][];
			fill(list, new int[0]);
			for (int i = size; i < size + n; i++) {
				list[i] = new int[] { inQ[p[i - size]] };
			}
			for (int i = size - 1; i > 0; --i) {
				int[] l1 = list[2 * i];
				int[] l2 = list[2 * i + 1];
				int[] l = Arrays.copyOf(l1, l1.length + l2.length);
				System.arraycopy(l2, 0, l, l1.length, l2.length);
				Arrays.sort(l);
				list[i] = l;
			}
//			for (int i = 1; i < list.length; i++) {
//				System.err.println(Arrays.toString(list[i]));
//			}
		}

		int left1, right1;
		int left2, right2;

		int queryAnswer;

		int query(int l1, int r1, int l2, int r2) {
			left1 = l1 - 1;
			left2 = l2 - 1;
			right1 = r1;
			right2 = r2;
			queryAnswer = 0;
			go(1, 0, list.length / 2);
			return queryAnswer;
		}

		private void go(int i, int from, int to) {
			if (to <= left1 || from >= right1) {
				return;
			}
			if (from >= left1 && to <= right1) {
				queryAnswer += count(list[i], left2, right2);
				return;
			}
			int mid = from + to >> 1;
			go(2 * i, from, mid);
			go(2 * i + 1, mid, to);
		}

		private static int count(int[] array, int from, int to) {
			return binarySearch(array, to) - binarySearch(array, from);
		}

		private static int binarySearch(int[] array, int value) {
			int left = -1, right = array.length;
			while (right - left > 1) {
				int mid = left + right >>> 1;
				if (array[mid] < value) {
					left = mid;
				} else {
					right = mid;
				}
			}
			return right;
		}
	}

	static BufferedReader br;
	static PrintWriter out;

	public static void main(String[] args) throws IOException {
		InputStream input = System.in;
		PrintStream output = System.out;
		File file = new File("c.in");
		if (file.exists() && file.canRead()) {
			input = new FileInputStream(file);
		}
		br = new BufferedReader(new InputStreamReader(input));
		out = new PrintWriter(output);
		solve();
		out.close();
	}

	public static int nextInt() throws IOException {
		int c = br.read();
		while ((c < '0' || c > '9') && c != '-')
			c = br.read();
		boolean negative = false;
		if (c == '-') {
			negative = true;
			c = br.read();
		}
		int m = 0;
		while (c >= '0' && c <= '9') {
			m = m * 10 + c - '0';
			c = br.read();
		}
		return negative ? -m : m;
	}
}