cho.sh

買い物 2 (Shopping 2)

시간 제한2초메모리 제한1024 MB

문제

JOI 商店には N 個の商品があり，商品には 1 から N までの番号が付けられている．

それぞれの商品には，定価と種類が定められている．商品 i (1 ≦ i ≦ N) の定価は Pi 円である．商品の種類は 1 以上 M 以下の整数で表され，商品 i (1 ≦ i ≦ N) の種類は Ai である．

JOI 商店は，セールを行うことにした．セールは M 日間続き，j 日目 (1 ≦ j ≦ M) には種類 j の商品をすべて定価の半額で買うことができる．

セールの期間中に，Q 人の客が JOI 商店を訪れた．客には 1 から Q までの番号が付けられている．客 k (1 ≦ k ≦ Q) はセールの Tk 日目に JOI 商店を訪れ，商品 Lk, Lk+1, …, Rk を 1 つずつ買った．

セールの効果を調査するため，それぞれの客が商品を買うのにかかった金額を知りたい．

商品の情報と客の情報が与えられたとき，それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ．

입력

入力は以下の形式で与えられる．

N   M   Q
P1   A1
P2   A2
︙
PN   AN
T1   L1   R1
T2   L2   R2
︙
TQ   LQ   RQ

출력

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

제한

  • 1 ≦ N ≦ 200 000．
  • 1 ≦ M≦ 200 000．
  • 1 ≦ Q ≦ 200 000．
  • 2 ≦ Pi ≦ 109 (1 ≦ i ≦ N)．
  • Pi は偶数である (1 ≦ i ≦ N)．
  • 1 ≦ Ai ≦ M (1 ≦ i ≦ N)．
  • 1 ≦ Tk ≦ M (1 ≦ k ≦ Q)．
  • 1 ≦ Lk ≦ Rk ≦ N (1 ≦ k ≦ Q)．
  • 入力される値はすべて整数である．