Golden Steiner Tree (Hard)

この問題は、yukicoder No.3608 - Golden Steiner Tree の制約を一部強化した問題である。

問題文

$\varphi = \dfrac{1+\sqrt{5}}{2}$ とする。

正整数 $N, R, B$ が与えられる。

頂点 $1, 2, \dots, N$ からなる無向グラフに以下の条件で辺を張る。

• $1$ 以上 $N$ 以下のすべての整数 $i$ について以下の操作を行う。
  • $1 \le \left\lfloor i \varphi \right\rfloor \le N$ ならば、頂点 $i$ と頂点 $\left\lfloor i \varphi \right\rfloor$ の間に重み $R$ の赤色の辺を張る。
  • $1 \le \left\lfloor i \varphi^2 \right\rfloor \le N$ ならば、頂点 $i$ と頂点 $\left\lfloor i \varphi^2 \right\rfloor$ の間に重み $B$ の青色の辺を張る。

はじめ、グラフの頂点はすべて黒色に塗られている。

正整数 $Q$ と $Q$ 個のクエリが与えられる。 $q$ 番目のクエリは整数の組 $(t_q, x_q)$ として与えられ、その内容は以下の通りである。

• $t_q = 1$ のとき、頂点 $x_q$ が白色に塗られているなら黒色に、黒色に塗られているなら白色に塗る。
• $t_q = 2$ のとき、赤色の辺の重みを $x_q$ にする。
• $t_q = 3$ のとき、青色の辺の重みを $x_q$ にする。

クエリを処理するたびに、以下の問題の答えを求めよ。

辺を $0$ 個以上削除してすべての白色の頂点が連結にできるか判定し、できるならば残っている辺の重みの総和としてありうる最小値を求めよ。
連結にすることができないならば -1 を出力せよ。白色の頂点が $0$ 個の場合、答えは 0 になる。

制約

• 入力はすべて整数である。
• $1 \le N \le 10^9$
• $1 \le 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\})$

入力

入力は以下の形式で標準入力から与えられる。

出力

$Q$ 行出力せよ。 $q$ 行目には $q$ 個目のクエリを処理した直後における問題の答えを出力せよ。

サンプル

サンプル 1

入力

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

$\left\lfloor 4 \varphi \right\rfloor = 6$ であるため、$2$ 個目のクエリを処理した直後の問題の答えは $3$ になる。