AT_joi2024_yo2_b 買い物 2 (Shopping 2)

JOI 商店には $ N $ 個の商品があり，商品には $ 1 $ から $ N $ までの番号が付けられている． それぞれの商品には，**定価**と**種類**が定められている．商品 $ i $ ( $ 1 \leqq i \leqq N $ ) の定価は $ P_i $ 円である．商品の種類は $ 1 $ 以上 $ M $ 以下の整数で表され，商品 $ i $ ( $ 1 \leqq i \leqq N $ ) の種類は $ A_i $ である． JOI 商店は，セールを行うことにした．セールは $ M $ 日間続き， $ j $ 日目 ( $ 1 \leqq j \leqq M $ ) には種類 $ j $ の商品をすべて定価の半額で買うことができる． セールの期間中に， $ Q $ 人の客が JOI 商店を訪れた．客には $ 1 $ から $ Q $ までの番号が付けられている．客 $ k $ ( $ 1 \leqq k \leqq Q $ ) はセールの $ T_k $ 日目に JOI 商店を訪れ，商品 $ L_k, L_k+1, \dots, R_k $ を $ 1 $ つずつ買った． セールの効果を調査するため，それぞれの客が商品を買うのにかかった金額を知りたい． 商品の情報と客の情報が与えられたとき，それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ M $ $ Q $ $ P_1 $ $ A_1 $ $ P_2 $ $ A_2 $ $ \vdots $ $ P_N $ $ A_N $ $ T_1 $ $ L_1 $ $ R_1 $ $ T_2 $ $ L_2 $ $ R_2 $ $ \vdots $ $ T_Q $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ． $ k $ 行目 ( $ 1 \leqq k \leqq Q $ ) には，客 $ k $ が商品を買うのにかかった金額を，単位 (円) を省いて出力せよ．

### 小課題 1. ( $ 15 $ 点) $ N \leqq 2\,000 $ ， $ M \leqq 2\,000 $ ， $ Q \leqq 2\,000 $ ． 2. ( $ 20 $ 点) $ M = 1 $ ． 3. ( $ 12 $ 点) $ M \leqq 10 $ ． 4. ( $ 14 $ 点) $ A_i \neq A_j $ ( $ 1 \leqq i < j \leqq N $ )． 5. ( $ 22 $ 点) $ P_i = 2 $ ( $ 1 \leqq i \leqq N $ )． 6. ( $ 17 $ 点) 追加の制約はない． ### Sample Explanation 1 客 $ 1 $ が商品を買うのにかかった金額は $ 40 \div 2 + 30 \div 2 + 20 \div 2 = 45 $ 円であるため， $ 1 $ 行目には $ 45 $ を出力する． 客 $ 2 $ が商品を買うのにかかった金額は $ 30 \div 2 + 20 \div 2 + 50 \div 2 = 50 $ 円であるため， $ 2 $ 行目には $ 50 $ を出力する． 客 $ 3 $ が商品を買うのにかかった金額は $ 10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75 $ 円であるため， $ 3 $ 行目には $ 75 $ を出力する． この入力例は小課題 $ 1,2,3,6 $ の制約を満たす． ### Sample Explanation 2 客 $ 1 $ が商品を買うのにかかった金額は $ 40 + 30 + 20 \div 2 = 80 $ 円であるため， $ 1 $ 行目には $ 80 $ を出力する． 客 $ 2 $ が商品を買うのにかかった金額は $ 30 + 20 + 50 \div 2 = 75 $ 円であるため， $ 2 $ 行目には $ 75 $ を出力する． 客 $ 3 $ が商品を買うのにかかった金額は $ 10 + 40 + 30 \div 2 + 20 + 50 = 135 $ 円であるため， $ 3 $ 行目には $ 135 $ を出力する． この入力例は小課題 $ 1,3,6 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 1,3,4,6 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 1,3,5,6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 1,3,6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 200\,000 $ ． - $ 1 \leqq M\leqq 200\,000 $ ． - $ 1 \leqq Q \leqq 200\,000 $ ． - $ 2 \leqq P_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ P_i $ は偶数である ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq A_i \leqq M $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq T_k \leqq M $ ( $ 1 \leqq k \leqq Q $ )． - $ 1 \leqq L_k \leqq R_k \leqq N $ ( $ 1 \leqq k \leqq Q $ )． - 入力される値はすべて整数である．