Jade City には、時計回りに $1,2,\ldots,N$ と番号が付いた $N$ 駅からなる環状鉄道があります。近年の急速な発展に伴い、駅 $1$ と駅 $K$ ($1<K\le N$) を結ぶ追加路線が運行しています。この路線には二つの終点以外に $M$ 駅があり、駅 $1$ から駅 $K$ へ向かう順に $N+1,N+2,\ldots,N+M$ と番号が付いています。図 $14$ を参照してください。

図14：Jade Cityの鉄道網

隣接する駅を結ぶ線路の長さは異なるので、移動にかかる時間も異なります。簡単のため、線路を次のように名付けます。

• $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$ が与えられます。二行目には、線路 $c_1,c_2,\ldots,c_N$ の移動時間 $t$ をそれぞれ表す $N$ 個の非負整数が含まれます。三行目には、線路 $x_0,x_1,\ldots,x_M$ の移動時間 $t$ をそれぞれ表す $M+1$ 個の非負整数が含まれます。その後の $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$ が使用可能なら操作後に使用不能となり、使用不能なら操作後に使用可能となります。

• 行が文字 x で始まり、整数 $j$ ($0\le j\le M$) が続く場合、辺 $x_j$ の状態を切り替えます。具体的には、$x_j$ が使用可能なら操作後に使用不能となり、使用不能なら操作後に使用可能となります。

制約

• $1\le N,K,M,Q\le10^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