Jade City에는 시계 방향으로 $1,2,\ldots,N$번이 붙은 $N$개의 역으로 이루어진 순환 철도 시스템이 있다. 최근 도시의 빠른 발전으로 $1$번 역과 $K$번 역 ($1<K\le N$)을 연결하는 추가 노선이 운행 중이다. 두 종착역 외에 이 노선에는 다른 역이 $M$개 있다. 이 $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