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
1
1
1
1
1 1 1 1

1

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

/*
 * author:yanghui
 */
public class C3232 {

	class InputReader {

		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public InputReader() throws FileNotFoundException {
			reader = new BufferedReader(new FileReader("d:/input.txt"));
			tokenizer = null;
		}

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

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

	}

	class TreeNode {
		TreeNode L, R;
		int num;
		int add;
		int size;
		int pri;
		int key;
		int sum = 0;
	}

	TreeNode NULL;

	void init() {
		NULL = new TreeNode();
		NULL.L = NULL.R = NULL;
		NULL.pri = -0x7FFFFFFF;
		NULL.size = 0;
		NULL.key = 0;
		NULL.num = 0;
	}

	class Treap {

		TreeNode root;
		Random rand = new Random();

		public Treap() {
			root = NULL;
		}

		public int size() {
			return root.size;
		}

		public TreeNode build(int left, int right, int key[]) {
			if (left > right)
				return NULL;
			int mid = (left + right) / 2;
			TreeNode root = newNode(key[mid], 1);
			root.L = build(left, mid - 1, key);
			root.R = build(mid + 1, right, key);
			up(root);
			return root;
		}

		TreeNode newNode(int key, int num) {
			TreeNode ret = new TreeNode();
			ret.L = ret.R = NULL;
			ret.key = key;
			ret.pri = rand.nextInt();
			ret.size = num;
			ret.num = num;
			ret.add = 0;
			ret.sum = key;
			return ret;
		}

		TreeNode newNode(TreeNode a) {
			TreeNode ret = new TreeNode();
			ret.L = a.L;
			ret.R = a.R;
			ret.key = a.key;
			ret.pri = a.pri;
			ret.size = a.size;
			ret.num = a.num;
			ret.add = a.add;
			ret.sum = a.sum;
			return ret;
		}

		void up(TreeNode root) {
			if (root == NULL)
				return;
			root.size = root.L.size + root.R.size + root.num;
			root.sum = root.L.sum + root.R.sum + root.key;
		}

		void down(TreeNode root) {
			return;
			/*
			 * if(root == NULL) return; if(root.add != 0){ root.L.add +=
			 * root.add; root.R.add += root.add; root.L.key += root.add;
			 * root.R.key += root.add; root.add = 0; }
			 */
		}

		TreeNode merge(TreeNode small, TreeNode large) {
			if (small == NULL)
				return large;
			if (large == NULL)
				return small;
			if (small.pri < large.pri) {
				TreeNode a = newNode(small);
				down(a);
				a.R = merge(a.R, large);
				up(a);
				return a;
			} else {
				TreeNode b = newNode(large);
				down(b);
				b.L = merge(small, b.L);
				up(b);
				return b;
			}
		}

		TreeNode[] split(TreeNode rt, int rank, int opt) {
			if (rt == NULL)
				return new TreeNode[] { NULL, NULL };
			TreeNode root = newNode(rt);
			down(root);
			if (rank == 0)
				return new TreeNode[] { NULL, root };
			if (rank <= root.L.size) {
				down(root.L);
				TreeNode[] tmp = split(root.L, rank, opt);
				root.L = tmp[1];
				up(root);
				return new TreeNode[] { tmp[0], root };
			} else if (rank == root.L.size + 1) {
				down(root.R);
				TreeNode tmp = root.R;
				root.R = NULL;
				up(root);
				return new TreeNode[] { root, tmp };
			} else {
				down(root.R);
				TreeNode[] tmp = split(root.R, rank - root.L.size - 1, opt);
				root.R = tmp[0];
				up(root);
				return new TreeNode[] { root, tmp[1] };
			}
		}

		void visit(TreeNode root) {
			if (root != NULL) {
				down(root);
				visit(root.L);
				System.out.println(root.key + " " + root.add + " " + root.size);
				visit(root.R);
			}
		}

	}

	Treap tr;
	Treap tree[];

	public void update(int pos, int idx) {
		TreeNode t[] = tr.split(tree[idx].root, pos - 1, 1);
		TreeNode tt[] = tr.split(t[1], 1, 1);
		tt[0].key++;
		tree[idx + 1].root = tr.merge(t[0], tr.merge(tt[0], tt[1]));
	}

	public int query(int left, int len, int idx) {
		TreeNode t[] = tr.split(tree[idx].root, left - 1, 1);
		TreeNode tt[] = tr.split(t[1], len, 1);
		return tt[0].sum;
	}

	public int query(int left, int right, int ll, int len) {
		return query(ll, len, right) - query(ll, len, left - 1);
	}

	public int cal(int a, int x, int n) {
		return (a - 1 + x) % n + 1;
	}
	
    public int max(int x ,int y){
    	return Math.max(x,y);
    }
    
    public int min(int x ,int y){
    	return Math.min(x,y);
    }

	public void run() {
		init();
		InputReader reader = new InputReader(System.in);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		int n = reader.nextInt();
		int re[] = new int[n + 1];
		tr = new Treap();
		tree = new Treap[n + 1];
		for (int i = 0; i <= n; i++) {
			tree[i] = new Treap();
		}
		tree[0].root = tr.build(1, n, re);
		int pos[] = new int[n + 1];
		for (int i = 1; i <= n; i++)
			re[i] = reader.nextInt();
		int tmp = 0;
		for (int i = 1; i <= n; i++) {
			tmp = reader.nextInt();
			pos[tmp] = i;
		}
		for (int i = 1; i <= n; i++) {
			update(pos[re[i]], i - 1);
		}
		int m = reader.nextInt();
		int x = -1;
		int l1, l2, r1, r2;
		for (int i = 1; i <= m; i++) {
			x++;
			int a = reader.nextInt();
			int b = reader.nextInt();
			int c = reader.nextInt();
			int d = reader.nextInt();
			l1 = min(cal(a,x,n),cal(b,x,n));
			r1 = max(cal(a,x,n),cal(b,x,n));
			l2 = min(cal(c,x,n),cal(d,x,n));
			r2 = max(cal(c,x,n),cal(d,x,n));
			out.println(query(l1,r1,l2,r2-l2+1));
		}
		out.flush();
	}

	public static void main(String args[]) {
		new C3232().run();
	}
}
