翡翠城拥有一个环形铁路系统，该系统有 $N$ 个车站，按顺时针方向标记为 $1, 2, \dots, N$。由于近年来城市的快速发展，一条连接车站 $1$ 和车站 $K$ ($1 < K \le N$) 的额外线路现已投入使用。除了这两个端点站外，该线路上还有 $M$ 个其他车站。这些 $M$ 个车站按从车站 $1$ 到车站 $K$ 的方向标记为 $N + 1, N + 2, \dots, N + M$。示意图见图 14。

图 14：翡翠城铁路系统示意图

连接相邻车站的轨道长度不同，因此沿轨道行驶所需的时间也不同。为简便起见，我们将这些轨道标记如下：

• $c_i$：对于 $1 \le i \le N - 1$，表示车站 $i$ 和车站 $i + 1$ 之间的轨道；
• $c_N$：表示车站 $N$ 和车站 $1$ 之间的轨道；
• $x_0$：表示车站 $1$ 和车站 $N + 1$ 之间的轨道；
• $x_j$：对于 $1 \le j \le M - 1$，表示车站 $N + j$ 和车站 $N + j + 1$ 之间的轨道；
• $x_M$：表示车站 $N + M$ 和车站 $K$ 之间的轨道。

给定每条轨道的行驶时间，我们希望计算使用该铁路系统从某个车站 $u$ 到某个车站 $v$ 的最快路径。然而，由于维护原因，某些轨道有时会变得不可用，导致火车无法通过（初始时，所有轨道均可用）。

输入格式

第一行包含三个整数 $N, K$ 和 $M$（如题目描述中所述），随后是一个整数 $Q$，表示查询或更新操作的总数。第二行包含 $N$ 个非负整数，分别表示轨道 $c_1, c_2, \dots, c_N$ 的行驶时间 $t$。第三行包含 $M + 1$ 个非负整数，分别表示轨道 $x_0, x_1, \dots, x_M$ 的行驶时间 $t$。接下来有 $Q$ 行，每行通过以下格式指定一个操作：

• 如果该行以字母 “q” 开头，后跟两个整数 $u$ 和 $v$ ($1 \le u, v \le N + M$)：请求输出从车站 $u$ 到车站 $v$ 的最快行驶时间（如果存在路径）。否则，输出单词 “impossible”。
• 如果该行以字母 “c” 开头，后跟一个整数 $i$ ($1 \le i \le N$)：表示标记为 $c_i$ 的边的状态被切换。具体来说，如果 $c_i$ 原本可用，则操作后 $c_i$ 变为不可用。反之，如果 $c_i$ 原本不可用，则操作后 $c_i$ 变为可用。
• 如果该行以字母 “x” 开头，后跟一个整数 $j$ ($0 \le j \le M$)：表示标记为 $x_j$ 的边的状态被切换。具体来说，如果 $x_j$ 原本可用，则操作后 $x_j$ 变为不可用。反之，如果 $x_j$ 原本不可用，则操作后 $x_j$ 变为可用。

数据范围

• $1 \le N, K, M, Q \le 10^6$；
• 任何轨道的行驶时间均为不超过 $200$ 的非负整数。

输出格式

对于每个查询，在单独的一行中输出相应的答案。

样例

样例输入 1

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

样例输出 1

6
8
9
impossible
6