zzzzzz just use cream

현재 온라인 마켓에는 $N$종류의 크림 상품이 있다. 각 크림 상품을 $1$번부터 $N$번까지 번호 붙였을 때, $i$번 크림의 효과는 $A_i$, 유통기한은 $D_i$, 한 통의 가격은 $P_i$이다.

다다스는 크림을 주문할 때, 현재 온라인 마켓에서 판매 중인 모든 종류의 크림을 정확히 $X$통씩 구매한다. 크림을 구매한 날을 $1$일째라고 하면, 유통기한이 $D$인 크림은 $D$일째까지 사용할 수 있다. 유통기한이 지난 크림은 사용할 수 없다. 다다스는 사용할 수 있는 크림이 남아 있는 동안 매일 정확히 한 통의 크림을 사용하며, 하루에 두 종류 이상의 크림을 사용할 수 없다.

이후 총 $Q$개의 질의가 순서대로 주어진다.

• 1 a d p: 효과가 $a$, 유통기한이 $d$, 한 통의 가격이 $p$인 새로운 크림 상품이 온라인 마켓에 추가된다.
• 2: 다다스가 현재 온라인 마켓에서 판매 중인 모든 종류의 크림을 $X$통씩 구매하고, 이후 사용할 수 있는 크림이 없어질 때까지 각 날짜에 얻는 효과의 총합이 최대가 되도록 사용한다고 하자. 이때 최적 사용 후 버리게 되는 크림들의 가격 합을 출력한다.

각 2번 질의는 현재까지 추가된 상품 목록에 대해 독립적으로 계산한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q\ X$ $A_1\ A_2\ \cdots\ A_N$

각 2번 질의마다, 최적 사용 후 버리게 되는 크림들의 가격 합을 한 줄에 하나씩 출력한다.

• $1 \leq N,Q \leq 200\ 000$.
• $1 \leq X \leq 10^8$.