AT_abc427_g [ABC427G] Takahashi's Expectation 2

高橋くんは、これからいくつかのプレゼントをもらいます。 高橋くんにはテンションという整数のパラメータがあり、テンションはプレゼントをもらうごとに変動します。 それぞれのプレゼントは価値 $ P $ という整数のパラメータをもち、このパラメータによって高橋くんのテンションは次のように変動します。 - もらったプレゼントの価値 $ P $ がテンションの値以上であるとき、高橋くんはプレゼントに喜び、テンションが $ A $ だけ増加する。 - もらったプレゼントの価値 $ P $ がテンションの値より小さいとき、高橋くんはプレゼントにがっかりし、テンションが $ B $ だけ減少する。 はじめ、高橋くんが受け取る予定のプレゼントは $ N $ 個あり、 $ i $ 番目 $ (1\le i\le N) $ に受け取るプレゼントの価値は $ P _ i $ です。 追加クエリ、質問クエリの $ 2 $ 種類からなる $ Q $ 個のクエリが与えられるので、その全てを順に処理し、すべての質問クエリに答えてください。 $ i $ 番目のクエリは $ 2 $ つの整数 $ T _ i,X _ i $ によって表され、 $ T _ i=1 $ のとき追加クエリ、 $ T _ i=2 $ のとき質問クエリです。 追加クエリでは、受け取る予定のプレゼントの末尾に、価値が $ X _ i $ であるプレゼントを新たに追加します。 質問クエリでは、次の質問に答えてください。 > 高橋くんのテンションがはじめ $ X _ i $ だったときの、受け取る予定のプレゼントをすべて受け取ったあとの高橋くんのテンションを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A $ $ B $ $ P _ 1 $ $ P _ 2 $ $ \ldots $ $ P _ N $ $ Q $ $ T _ 1 $ $ X _ 1 $ $ T _ 2 $ $ X _ 2 $ $ \vdots $ $ T _ Q $ $ X _ Q $

質問クエリの個数を $ q $ 個として、 $ q $ 行にわたって出力せよ。 $ i $ 行目 $ (1\le i\le q) $ には、 $ i $ 個めの質問クエリに対する答えを出力せよ。

### Sample Explanation 1 はじめ、高橋くんが受け取る予定のプレゼントの価値は、受け取る順にそれぞれ $ 59,-26,53,58 $ です。 $ 5 $ 回のクエリは、それぞれ次のようになっています。 - 高橋くんのテンションがはじめ $ 9 $ であったとき、プレゼントを受け取るたびに高橋くんのテンションは $ 9\rightarrow40\rightarrow-1\rightarrow30\rightarrow61 $ と変動するため、最終的なテンションである $ 61 $ を出力します。 - 高橋くんが受け取る予定のプレゼントに価値が $ 79 $ のプレゼントが追加され、高橋くんが受け取る予定のプレゼントの価値が $ 59,-26,53,58,79 $ となります。 - 高橋くんのテンションがはじめ $ 32 $ であったとき、プレゼントを受け取るたびに高橋くんのテンションは $ 32\rightarrow63\rightarrow22\rightarrow53\rightarrow84\rightarrow43 $ と変動するため、最終的なテンションである $ 43 $ を出力します。 - 高橋くんが受け取る予定のプレゼントに価値が $ 38 $ のプレゼントが追加され、高橋くんが受け取る予定のプレゼントの価値が $ 59,-26,53,58,79,38 $ となります。 - 高橋くんのテンションがはじめ $ 462 $ であったとき、プレゼントを受け取るたびに高橋くんのテンションは $ 462\rightarrow421\rightarrow380\rightarrow339\rightarrow298\rightarrow257\rightarrow216 $ と変動するため、最終的なテンションである $ 216 $ を出力します。 ### Sample Explanation 2 入力や出力すべき値の絶対値が $ 2 ^ {32} $ 以上になる場合があることに注意してください。 ### Constraints - $ 1\le N\le2\times10 ^ 5 $ - $ 1\le A\le10 ^ 9 $ - $ 1\le B\le10 ^ 9 $ - $ -10 ^ 9\le P _ i\le10 ^ 9\ (1\le i\le N) $ - $ 1\le Q\le2\times10 ^ 5 $ - $ T _ i=1 $ もしくは $ T _ i=2\ (1\le i\le Q) $ - $ T _ i=2 $ となるような整数 $ i\ (1\le i\le Q) $ が存在する - $ T _ i=1 $ ならば $ -10 ^ 9\le X _ i\le10 ^ 9\ (1\le i\le Q) $ - $ T _ i=2 $ ならば $ -10 ^ {12}\le X _ i\le10 ^ {12}\ (1\le i\le Q) $ - 入力はすべて整数