← 返回题目列表

Codeforces · 323/C

C. 两种排列

中文机器翻译题面 查看原题

给您两个排列 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