EIU Programming Practices and Exams

ABC Company needs to upgrade its current warehouse management software. The new software needs to be able to manage import/export transactions with a rule that first-in, first-out products are given priority. Given a list of transactions to be processed in order (output transactions larger than the inventory count will not be processed), output the products in stock after executing the transactions knowing that Initially there are no products in warehouse.

Input

The first line is the number of transactions (N <= 10⁶).

The ith line in the next N lines begins with a +/- sign corresponding to an import/export transaction, followed by 4 integers Ci, Qi, Pi and Ti, respectively, the item code, quantity, and unit price of the product. per product, time of transaction (Qi, Pi, Ti <= 10⁹, Ci 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, output the product code, quantity, average value of each product based on the input price, and the time of oldest item separated by a space.

Products are printed in ascending order of product code, the average value rounded down to the unit

Example

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

Output:
1 5 20000 1
2 25 24000 2