상점에는 N 개의 상품이 있으며 상품에는 1 에서 N 까지의 번호가 매겨져 있다.

각 상품에는 정가와 종류가 정해져 있다.

상품 i\ ( 1≤i≤N )의 정가는 P_i 원 이다.

상품의 종류는 1 이상 M 이하의 정수로 나타내고, 상품 i\ ( 1≤i≤N )의 종류는 A_i 이다.

상점은 세일을 하기로 했다. 세일은 M 일간 계속되고, j 일째( 1≤j≤M )에는 종류 j 의 상품을 모두 정가의 반값으로 살 수 있다.

판매 기간 동안 Q 명의 고객이 상점을 방문했다. 고객은 1 에서 Q 까지 번호가 매겨져 있다.

손님 k\ ( 1 ≤ k ≤ Q )는 판매의 T_k 일째에 상점을 방문하여 상품 L_k , L_k+ 1 ,\ ...,\ R_k 를 하나씩 샀다.

판매의 효과를 조사하기 위해 각 고객이 상품을 사는 데 사용한 금액을 알고 싶다.

상품 정보와 고객 정보가 주어지면 각 고객이 상품을 구입하는 데 사용한 금액을 구하는 프로그램을 작성하시오.

쇼핑 2 timer 2초 memory 1024MB

쇼핑 2 2초 1024MB