Jade City ma kolej obwodową z $N$ stacjami oznaczonymi $1,2,\ldots,N$ zgodnie z ruchem wskazówek zegara. W związku z szybkim rozwojem miasta w ostatnich latach uruchomiono dodatkową linię łączącą stację $1$ ze stacją $K$ ($1<K\le N$). Poza tymi dwiema stacjami końcowymi jest na niej $M$ innych stacji. Oznaczono je $N+1,N+2,\ldots,N+M$ w kierunku od stacji $1$ do stacji $K$. Ilustrację przedstawiono na rysunku $14$.

Rysunek 14: Ilustracja sieci kolejowej Jade City

Odcinki torów łączące sąsiednie stacje mają różne długości, więc przejazd nimi wymaga różnej ilości czasu. Dla uproszczenia oznaczamy je następująco:

• $c_i$: dla $1\le i\le N-1$ tor między stacją $i$ a stacją $i+1$;

• $c_N$: tor między stacją $N$ a stacją $1$;

• $x_0$: tor między stacją $1$ a stacją $N+1$;

• $x_j$: dla $1\le j\le M-1$ tor między stacją $N+j$ a stacją $N+j+1$;

• $x_M$: tor między stacją $N+M$ a stacją $K$.

Mając dane czasy przejazdu każdego z tych odcinków, chcemy obliczyć najszybszy sposób przejazdu ze stacji $u$ do stacji $v$ tą siecią kolejową. Jednak od czasu do czasu niektóre tory mogą stać się niedostępne z powodu konserwacji i pociąg nie może nimi przejechać. Początkowo wszystkie tory są dostępne.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $N,K,M$ opisane w treści zadania, a po nich liczbę całkowitą $Q$ oznaczającą łączną liczbę zapytań lub operacji aktualizacji. Drugi wiersz zawiera $N$ nieujemnych liczb całkowitych, oznaczających kolejno czasy przejazdu $t$ dla torów $c_1,c_2,\ldots,c_N$. Trzeci wiersz zawiera $M+1$ nieujemnych liczb całkowitych, oznaczających kolejno czasy przejazdu $t$ dla torów $x_0,x_1,\ldots,x_M$. Następnie jest $Q$ wierszy, każdy określający operację w następującym formacie:

• Jeśli wiersz zaczyna się od litery q, po której są dwie liczby całkowite $u,v$ ($1\le u,v\le N+M$), należy wypisać najkrótszy czas przejazdu ze stacji $u$ do stacji $v$, jeśli istnieje trasa. W przeciwnym razie wypisz impossible.

• Jeśli wiersz zaczyna się od litery c, po której jest liczba całkowita $i$ ($1\le i\le N$), zmienia się stan krawędzi $c_i$. Dokładniej, jeśli $c_i$ była dostępna, po operacji staje się niedostępna; jeśli była niedostępna, po operacji staje się dostępna.

• Jeśli wiersz zaczyna się od litery x, po której jest liczba całkowita $j$ ($0\le j\le M$), zmienia się stan krawędzi $x_j$. Dokładniej, jeśli $x_j$ była dostępna, po operacji staje się niedostępna; jeśli była niedostępna, po operacji staje się dostępna.

Ograniczenia

• $1\le N,K,M,Q\le10^6$;

• Czas przejazdu dowolnym torem jest nieujemną liczbą całkowitą nieprzekraczającą $200$.

Wyjście

Dla każdego zapytania wypisz odpowiadającą mu odpowiedź w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

6
8
9
impossible
6