匈牙利国家舞团正在排练一套新的编舞。舞团中共有 $N$ 名舞者，编号为 $0$ 至 $N - 1$，其中 $N$ 是一个偶数。

在排练时，编舞家首先让舞者们排成一队。队伍中的位置从 $0$ 到 $N - 1$ 进行编号，开始时位置 $i$ 被舞者 $P[i]$ 占据。

舞者们排好队后，编舞家会要求他们执行一系列动作。每个动作必须在开始执行下一个动作之前完成。舞者们正在练习以下 $4$ 种类型的动作：

1. 每个舞者循环向右移动 $K$ 个位置，其中 $0 \le K < N$。也就是说：

   • 对于每个从 $0$ 到 $N - K - 1$（包含）的 $i$，当前站在位置 $i$ 的舞者移动到位置 $i + K$；并且
   • 对于每个从 $N - K$ 到 $N - 1$（包含）的 $i$，当前站在位置 $i$ 的舞者移动到位置 $i + K - N$。

2. 每个舞者循环向左移动 $K$ 个位置，其中 $0 \le K < N$。也就是说：

   • 对于每个从 $K$ 到 $N - 1$（包含）的 $i$，当前站在位置 $i$ 的舞者移动到位置 $i - K$；并且
   • 对于每个从 $0$ 到 $K - 1$（包含）的 $i$，当前站在位置 $i$ 的舞者移动到位置 $i - K + N$。

3. 对于每个从 $0$ 到 $\frac{N}{2} - 1$（包含）的 $i$，位置 $2i$ 和 $2i + 1$ 的舞者交换位置。

4. 假设在执行此动作之前，位置 $i$（$0 \le i < N$）被舞者 $r_i$ 占据。对于每个从 $0$ 到 $N - 1$（包含）的 $j$，舞者 $j$ 移动到位置 $r_j$。

注意，在每个动作结束时，舞者们所处的位置都是互不相同的。

在下一次排练之前，编舞家计划了由 $M$ 个动作组成的序列供舞团练习。他将动作一个接一个地添加到序列中。有时，在添加下一个动作之前，他想知道在执行完当前已添加到序列中的所有动作后，某些舞者将立即占据什么位置。

你的任务是模拟编舞家计划的舞蹈动作，并回答他关于舞者位置的提问。

实现细节

你需要实现以下函数：

void init(int N, int[] P)

• N：舞者的数量。
• P：长度为 $N$ 的数组，描述舞者的初始顺序。
• 该函数恰好被调用一次，且在任何其他函数调用之前。

void move_right(int K)

• K：每个舞者向右移动的位置数。
• 该函数向动作序列中添加一个第 1 类型的动作。

void move_left(int K)

• K：每个舞者向左移动的位置数。
• 该函数向动作序列中添加一个第 2 类型的动作。

void swap_places()

• 该函数向动作序列中添加一个第 3 类型的动作。

void move_around()

• 该函数向动作序列中添加一个第 4 类型的动作。

上述函数 move_right、move_left、swap_places 和 move_around 总共会被调用 $M$ 次。

int get_position(int D)

• D：代表一名舞者的整数。
• 该函数应返回在执行完此调用之前已添加到动作序列中的所有动作后，舞者 D 的位置。
• 该函数会被调用 $Q$ 次。

样例

考虑以下调用序列：

init(6, [5, 1, 4, 2, 0, 3])

共有 $6$ 名舞者，舞者的初始顺序由数组 [5, 1, 4, 2, 0, 3] 给出，即位置 $0$ 被舞者 $5$ 占据，位置 $1$ 被舞者 $1$ 占据，位置 $2$ 被舞者 $4$ 占据，依此类推。

move_left(2)

每个舞者循环向左移动两个位置。移动后，舞者的顺序变为 [4, 2, 0, 3, 5, 1]。

get_position(0)

此调用询问在执行第一个动作后舞者 $0$ 的位置。舞者 $0$ 站在位置 $2$。因此，该函数应返回 $2$。

swap_places()

在此动作之后，舞者的顺序变为 [2, 4, 3, 0, 1, 5]。

move_around()

每个舞者的新位置确定如下：

• 舞者 0：位置 0 被舞者 2 占据，因此舞者 0 移动到位置 2。
• 舞者 1：位置 1 被舞者 4 占据，因此舞者 1 保持在位置 4。
• 舞者 2：位置 2 被舞者 3 占据，因此舞者 2 移动到位置 3。
• 舞者 3：位置 3 被舞者 0 占据，因此舞者 3 移动到位置 0。
• 舞者 4：位置 4 被舞者 1 占据，因此舞者 4 保持在位置 1。
• 舞者 5：位置 5 被舞者 5 占据，因此舞者 5 保持在位置 5。

在此动作之后，舞者的顺序变为 [3, 4, 0, 2, 1, 5]。

get_position(3)

在执行完目前为止的所有动作后，舞者 $3$ 处于位置 $0$。该函数应返回 $0$。

数据范围

• $1 \le N \le 100\,000$
• 对于满足 $0 \le i < N$ 的每个 $i$，有 $0 \le P[i] < N$
• 对于满足 $0 \le i < j < N$ 的每个 $i$ 和 $j$，有 $P[i] \ne P[j]$
• $0 \le M \le 100\,000$
• $1 \le Q \le 200\,000$
• $0 \le K < N$
• $0 \le D < N$

子任务

1. （7 分）仅执行第 1 类型和第 2 类型的动作。
2. （12 分）$N \cdot (Q + M) \le 1\,000\,000$
3. （10 分）仅执行第 4 类型的动作。
4. （14 分）仅执行第 3 类型和第 4 类型的动作。
5. （28 分）仅执行第 1 类型、第 2 类型和第 4 类型的动作。
6. （29 分）无附加限制。

评测程序示例

样例评测程序按以下格式读取输入：

• 第 1 行：$N\ M\ Q$
• 第 2 行：$P[0]\ P[1]\ \dots\ P[N - 1]$

• 第 $3 + l$ 行（$0 \le l < M + Q$）：

  • 执行第 1 类型的动作：1 K
  • 执行第 2 类型的动作：2 K
  • 执行第 3 类型的动作：3
  • 执行第 4 类型的动作：4
  • 询问舞者的位置：5 D

样例评测程序按以下格式打印你的答案：

• 第 $1 + q$ 行（$0 \le q < Q$）：get_position 返回的值