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$ $D_1\ D_2\ \cdots\ D_N$ $P_1\ P_2\ \cdots\ P_N$ $query_1$ $query_2$ $\vdots$ $query_Q$

각 $query_j$ ($1 \leq j \leq Q$)는 다음 두 형식 중 하나이다.

$1\ a\ d\ p$ $2$

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

• $1 \leq N,Q \leq 200\ 000$.
• $1 \leq X \leq 10^8$.
• $1 \leq A_i \leq 10^9$ ($1 \leq i \leq N$).
• $1 \leq D_i \leq X$ ($1 \leq i \leq N$).
• $1 \leq P_i \leq 10^4$ ($1 \leq i \leq N$).
• 1 a d p 형식의 질의에서 $1 \leq a \leq 10^9$, $1 \leq d \leq X$, $1 \leq p \leq 10^4$이다.
• 처음 주어지는 모든 $A_i$와 1번 질의로 추가되는 모든 $a$는 서로 다르다.
• 입력으로 주어지는 모든 수는 정수이다.