AT_arc209_c [ARC209C] Adjusting a Rectangle

正の整数 $ N, X $ および長さ $ N $ の整数列 $ S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N) $ が与えられます。 ここで、 $ P $ の各要素は $ 1 $ または $ -1 $ です。 クエリが $ Q $ 個与えられます。各クエリでは、 $ 1 \leq l \leq r \leq N $ を満たす整数 $ l, r $ が与えられ、あなたは以下のようなゲームを行います。 - はじめ、あなたのスコアは $ 0 $ であり、整数 $ a, b $ が $ a = 1, b = 1 $ で初期化されている。 - $ i = l, l+1, \dots, r $ の順に、以下の操作を行う。 - $ i $ が偶数のときは $ a $ の値、 $ i $ が奇数のときは $ b $ の値を、 $ 1 $ 以上 $ X $ 以下の好きな整数に置き換える。 - その後、 $ ab \geq S_i $ ならあなたのスコアに $ P_i $ を加算する。そうでないとき、スコアは変動しない。 $ P_i $ は負の値も取り得ることに注意せよ。 各クエリに対して、ゲームが終了した時点でのあなたのスコアとしてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ Q $ $ S_1 $ $ S_2 $ $ \ldots $ $ S_N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ 各クエリは以下の形式で与えられる。 > $ l $ $ r $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリにおいて、ゲームが終了した時点でのあなたのスコアとしてあり得る最大値を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリにおいて、以下の手順によってゲームが終了した時点でのスコアを $ 2 $ にすることができます。 $ i $ 操作 $ a $ $ b $ スコア- $ 1 $ $ 1 $ $ 0 $ $ 5 $ $ b $ の値を $ 4 $ に置き換える。 $ ab < S_5 \, (= 5) $ のためスコアは変動しない。 $ 1 $ $ 4 $ $ 0 $ $ 6 $ $ a $ の値を $ 2 $ に置き換える。 $ ab \geq S_6 \, (= 7) $ のためスコアに $ P_6 \, (= 1) $ を加算する。 $ 2 $ $ 4 $ $ 1 $ $ 7 $ $ b $ の値を $ 3 $ に置き換える。 $ ab \geq S_7 \, (= 3) $ のためスコアに $ P_7 \, (= -1) $ を加算する。 $ 2 $ $ 3 $ $ 0 $ $ 8 $ $ a $ の値を $ 4 $ に置き換える。 $ ab \geq S_8 \, (= 9) $ のためスコアに $ P_8 \, (= 1) $ を加算する。 $ 4 $ $ 3 $ $ 1 $ $ 9 $ $ b $ の値を $ 4 $ に置き換える。 $ ab \geq S_9 \, (= 16) $ のためスコアに $ P_9 \, (= 1) $ を加算する。 $ 4 $ $ 4 $ $ 2 $ ゲームが終了した時点でのスコアを $ 3 $ 以上にすることはできないので、 $ 2 $ を出力します。 ### Constraints - $ 1 \le N, X, Q \le 10^5 $ - $ 1 \le S_i \le 10^5 $ - $ P_i = 1 $ または $ P_i = -1 $ - 各クエリに対して $ 1 \le l \le r \le N $ - 入力される値は全て整数