Goods Market

A market called Goods Market has just opened. It starts with $N$ shops, and new shops keep moving in. The market is large enough to hold any number of shops.

The owner can raise the rent. One raise adds $K$ baht to the rent of every shop that is in the market at that moment. A shop that goes through two raises pays $2K$ baht more than its starting rent. A shop that moves in after the first raise and goes through only the second one pays $K$ baht more. A shop is affected only by the raises that happen after it moves in.

When there are too many tenants, the owner evicts one shop with the cheapest rent. If several shops share the cheapest rent, the owner evicts one of them, and the sum of the remaining rents is the same either way. The owner decides when to evict.

The market goes through $M$ operations of three types.

1. A new shop moves in at a rent of $P$ baht.
2. The rent of every shop in the market goes up by $K$ baht.
3. The owner evicts one shop with the cheapest rent. If the market has no shop, nothing happens.

Find the number of shops left after all operations and the sum of their rents.

The first line has the number of questions $T$. ($1 \le T \le 20$)

The first line of each question has three integers $N$, $M$, $K$. ($1 \le N, M \le 100{,}000$, $1 \le K \le 100$)

The next line has $N$ integers $X_i$, the starting rent of shop $i$. ($1 \le X_i \le 10{,}000{,}000$)

Each of the following $M$ lines has the operation type $A$. When $A$ is 1, the same line also has an integer $P$. ($1 \le P \le 10{,}000{,}000$) When $A$ is 2 or 3, the line has that one integer only.

For each question, print the number of shops left after all operations and the sum of their rents on one line, separated by a space.