给您两个排列 p 和 q,由 n 个元素和 m 个以下形式的查询组成:l1, r1, l2, r2 (l1 ≤ r1; l2 ≤ r2)。查询的响应是从 1 到 n 的整数的数量,它们在第一个排列中的位置在段 [l1, r1] 中(包括边界),在第二个排列中的位置在段 [l2, r2] 中(也包括边界)。
n 个元素的排列是 n 个不同整数的序列,每个整数不小于 1 且不大于 n。
排列 g1, g2, ..., gn 中数字 v (1 ≤ v ≤ n) 的位置是这样的数字 i,即 gi = v。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106),即两种排列中的元素数量。下面一行包含 n 个整数,用空格分隔:p1, p2, ..., pn (1 ≤ pi ≤ n)。这些是第一个排列的元素。下一行包含相同格式的第二个排列 q1, q2, ..., qn。
下面一行包含一个整数m (1 ≤ m ≤ 2·105),即查询次数。
接下来的 m 行包含一行查询的描述。第 i 个查询的描述由四个整数组成:a、b、c、d(1 ≤ a、b、c、d ≤ n)。查询参数l1、r1、l2、r2是使用以下算法从数字a、b、c、d获得的:
1.引入变量x。如果是第一个查询,则该变量等于 0,否则等于前一个查询的响应加一。
2. 引入函数 f(z) = ((z - 1 + x) mod n) + 1。
3.假设l1 = min(f(a), f(b)), r1 = max(f(a), f(b)), l2 = min(f(c), f(d)), r2 = max(f(c), f(d))。
输出
在单独的行中打印每个查询的响应。
示例
输入 #1
3 3 1 2 3 2 1 1 1 2 3 3
输出 #1
1
输入 #2
4 4 3 2 1 2 3 4 1 3 1 2 3 4 1 3 2 1 1 4 2 3
输出 #2
1 1 2