1차원 애니팡

1차원 세계에는 1차원 애니팡이라는 게임이 있다. 1차원 세계에 사는 스피드 게이머 무지는 이 게임을 최대한 빠르게 클리어하고 싶다.

게임은 처음에 첫 번째 라운드의 정수 블록 $N$개를 1차원 배열의 형태로 준다. 이 정수 블록들이 다음 상태이면 해당 라운드가 클리어된다.

어떤 인접한 블록끼리도 부호가 같은 경우가 없다. 양수, 0, 음수는 서로 다른 부호를 갖는다.

즉 $1 \le i < N$인 $i$에 대해 $A_{i} > 0 \;\And\; A_{i+1} > 0$이거나 $A_{i} < 0 \; \And \;A_{i+1} < 0$이거나 $A_{i} = 0 \;\And\; A_{i+1} = 0$인 경우가 없다.

무지가 블록에 할 수 있는 연산은 다음과 같다.

1. $i$번째 블록의 값 $A_{i}$에 $-1$을 곱한다. 이 연산은 $R$초가 걸린다.
2. $i$번째 블록의 값 $A_{i}$를 1만큼 증가시키거나 감소시킨다. 이 연산은 $C$초가 걸린다.

연산은 같은 블록에 여러 번 수행할 수 있다.

$T+1$개의 라운드를 클리어해야 하며, 두 번째 라운드부터는 각 라운드가 시작할 때 이전 라운드의 초기 상태에서 $K$번째 블록의 값이 $V$로 바뀐다. (이전 라운드의 클리어 상태가 아니라 초기 상태이다.)

이때 각 라운드를 클리어하기 위한 최소 시간을 구하자.

입력의 첫 줄에 양의 정수 $N$, $R$, $C$, $T$가 차례대로 주어진다. 각각 블록의 수, 1번 연산의 비용, 2번 연산의 비용, 블록의 값이 바뀌는 횟수를 나타낸다. ($1 \le N, R, C, T \le 100,000$)

두 번째 줄에 첫 번째 라운드의 $N$개 정수 블록을 나타내는 수열 $A_{1}, ..., A_{N}$이 차례대로 주어진다. ($-10,000 \le A_{i} \le 10,000$)

세 번째 줄부터 $T+2$번째 줄까지 이전 라운드의 초기 상태에서 $K$번째 블록의 값을 $V$로 바꾸는 것을 나타내는 정수 $K, V$가 주어진다. ($1 \le K \le N$, $-10,000 \le V \le 10,000$)

첫 번째 라운드부터 $T+1$번째 라운드까지 각 라운드를 클리어하는 최소 시간을 한 줄에 하나씩 차례대로 출력한다.