Problem Statement

Let $\varphi = \dfrac{1+\sqrt{5}}{2}$.

You are given positive integers $N, R, B$.

Add edges to an undirected graph with vertices $1, 2, \dots, N$ according to the following conditions.

• For every integer $i$ between $1$ and $N$, inclusive, perform the following operations.
  • If $1 \le \left\lfloor i \varphi \right\rfloor \le N$, add a red edge of weight $R$ between vertex $i$ and vertex $\left\lfloor i \varphi \right\rfloor$.
  • If $1 \le \left\lfloor i \varphi^2 \right\rfloor \le N$, add a blue edge of weight $B$ between vertex $i$ and vertex $\left\lfloor i \varphi^2 \right\rfloor$.

Initially, all vertices of the graph are painted black.

You are given a positive integer $Q$ and $Q$ queries. The $q$-th query is given as a pair of integers $(t_q, x_q)$, and its meaning is as follows.

• If $t_q = 1$: if vertex $x_q$ is painted white, paint it black; if it is painted black, paint it white.
• If $t_q = 2$: set the weight of the red edges to $x_q$.
• If $t_q = 3$: set the weight of the blue edges to $x_q$.

After processing each query, find the answer to the following problem.

Determine whether all white vertices can be made connected by deleting $0$ or more edges, and if so, find the minimum possible total weight of the remaining edges.
If they cannot be made connected, print -1. If there are $0$ white vertices, the answer is 0.

Constraints

• All input values are integers.
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le R, B \le 10^9$
• $1 \le t_q \le 3 ~ (1 \le q \le Q)$
• $1 \le x_q \le N ~ (1 \le q \le Q, t_q = 1)$
• $1 \le x_q \le 10^9 ~ (1 \le q \le Q, t_q \in \{2, 3\})$

Input

The input is given from standard input in the following format.

$N$ $R$ $B$
$Q$
$t_1$ $x_1$
$t_2$ $x_2$
$\vdots$
$t_Q$ $x_Q$

Output

Print $Q$ lines. On the $q$-th line, print the answer to the problem immediately after processing the $q$-th query.

Sample

8 3 5
8
1 4
1 6
1 7
2 10
3 1
1 4
1 6
1 7

0
3
11
25
21
21
0
0