AT_arc209_c [ARC209C] Adjusting a Rectangle

You are given positive integers $ N, X $ and integer sequences of length $ N $ : $ S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N) $ . Here, each element of $ P $ is $ 1 $ or $ -1 $ . You are given $ Q $ queries. In each query, you are given integers $ l, r $ satisfying $ 1 \leq l \leq r \leq N $ , and you play the following game: - Initially, your score is $ 0 $ , and integers $ a, b $ are initialized as $ a = 1, b = 1 $ . - For $ i = l, l+1, \dots, r $ in this order, perform the following operation: - If $ i $ is even, replace the value of $ a $ with any integer between $ 1 $ and $ X $ (inclusive); if $ i $ is odd, replace the value of $ b $ with any integer between $ 1 $ and $ X $ (inclusive). - After that, if $ ab \geq S_i $ , add $ P_i $ to your score. Otherwise, the score does not change. Note that $ P_i $ can be negative. For each query, find the maximum possible value of your score when the game ends.

The input is given from Standard Input in the following format: > $ 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 $ Each query is given in the following format: > $ l $ $ r $

Output $ Q $ lines. The $ i $ -th line should contain the maximum possible value of your score when the game ends in the $ i $ -th query.

### Sample Explanation 1 In the first query, you can make the score $ 2 $ when the game ends by the following procedure: $ i $ Operation $ a $ $ b $ Score- $ 1 $ $ 1 $ $ 0 $ $ 5 $ Replace the value of $ b $ with $ 4 $ . Since $ ab < S_5 \, (= 5) $ , the score does not change. $ 1 $ $ 4 $ $ 0 $ $ 6 $ Replace the value of $ a $ with $ 2 $ . Since $ ab \geq S_6 \, (= 7) $ , add $ P_6 \, (= 1) $ to the score. $ 2 $ $ 4 $ $ 1 $ $ 7 $ Replace the value of $ b $ with $ 3 $ . Since $ ab \geq S_7 \, (= 3) $ , add $ P_7 \, (= -1) $ to the score. $ 2 $ $ 3 $ $ 0 $ $ 8 $ Replace the value of $ a $ with $ 4 $ . Since $ ab \geq S_8 \, (= 9) $ , add $ P_8 \, (= 1) $ to the score. $ 4 $ $ 3 $ $ 1 $ $ 9 $ Replace the value of $ b $ with $ 4 $ . Since $ ab \geq S_9 \, (= 16) $ , add $ P_9 \, (= 1) $ to the score. $ 4 $ $ 4 $ $ 2 $ It is impossible to make the score $ 3 $ or more when the game ends, so output $ 2 $ . ### Constraints - $ 1 \le N, X, Q \le 10^5 $ - $ 1 \le S_i \le 10^5 $ - $ P_i = 1 $ or $ P_i = -1 $ . - For each query, $ 1 \le l \le r \le N $ . - All input values are integers.