The current warehouse management software of ABC Company requires an upgrade, and the new software should be able to manage import/export transactions based on the first-in, first-out rule. The priority should be given to the products that arrived first. If the output transaction exceeds the inventory count, it will not be processed. Given a list of transactions that need to be processed in order, the output should show the products in stock after executing the transactions. It should be noted that there are no products in the warehouse initially.

Input

• The first line is the number of transactions ~(N \leq 10^6)~.
• The ~i-~th line in the next ~N~ lines begins with a +/- sign corresponding to an import/export transaction, followed by ~4~ integers ~C_i, Q_i, P_i~ and ~T_i,~ respectively, the item code, quantity, and unit price of the product. per product, time of transaction ~(Q_i, P_i, T_i \leq 10^9, C_i~ with no more than ~9~ digits). The time of the following transaction is always greater than or equal to the previous transaction.

Output

• For each product in stock, with every import transaction that the product has not been totally exported, output the product code, value of the remaining products based on the input price, and the time the product was imported.

• Products are printed in ascending order of product code and imported time.

Sample Input

6
+ 1 25 20000 1
- 1 20 30000 2
+ 2 15 30000 2
- 2 25 25000 4
- 2 5 20000 5
+ 2 15 20000 5

Sample Output

1 100000 1
2 300000 2
2 300000 5 

Explanation:

• Product ~1~:

  • Import ~25~ products, export ~20~ then there are ~5~ products left of the first import. Therefore, value of the remaining products should be ~5 * 20000 = 100000~

• Product ~2~:

  • Import ~15~, cannot export ~25~, but export ~5~. There are ~10~ products left in stock of the first import, then value ~= 10 * 30000 = 300000~
  • Import ~15~, no export, value ~= 15 * 20000 = 300000~